Lower bounds for unreliability of circuits in the rosser - tourkett basis

We consider the implementation of four-valued logic functions by circuits consisting of unreliable functional gates in the Rosser - Tourkett basis. It is assumed that all elements of the circuit independently with probability p are subject to inverse failures on the outputs, i. e. each basic element can give each of incorrect values with the probability p and correct value with the probability 1 - 3p. In this paper, a class K of four-valued functions is introduced in such a way that almost all four-valued functions are contained in K and any circuit realizing a function from K operates with an unreliability that is asymptotically (for small p) not less than 9p.

Keywords

Authors

References