The Reliability of Circuits in the Basis Anticonjunction with Constant Faults of Gates

摘要

We consider the realization of Boolean functions by asymptotically optimal reliable circuits with constant faults at the outputs of the gates in the basis {x|y} (where x|y п??- anticonjunction i.п??. ). It is proved that almost all Boolean functions can be realized by asymptotically optimal reliable circuits that operate with unreliability asymptotically equal to 2ε_(0) +ε_(1) at ε_(0), ε_(1) → 0, where ε_(0) – probability of faults of type 0 at the output of basis gate, ε_(1) – probability of faults of type 1 at the output of basis gate.