Asymptotically Optimally Reliable Circuits in the Basis {x_1 & x_2 & x_3, x_1 ∨ x_2 ∨ x_3, (x)_1} for Inverse Faults at the Inputs of Elements

摘要

We prove that, in the basis {x_1 & x_2 & x_3,x_1 ∨ X_2 ∨ x_3(x)_1}, for inverse faults at the inputs of functional elements, all Boolean functions f(x_1,X_2,... ,x_n) can be realized by asymptotically optimally reliable circuits operating with unreliability asymptotically (as ε →0) equal to: ε~3 for the constants 0 and 1, ε for the functions (x)_i, and 3ε for f(x_1,X_2,...,x_n)≠0,1,(x)i,x_i, where ε is the error probability at each input of the functional element and i = l,...,n. The functions x_i = 1,..., n, can be realized absolutely reliably. The complexity of asymptotically optimally reliable circuits is equal in order to the complexity of minimal circuits constructed only from reliable elements.