Complexity of Self-Correcting Circuits for Some Sequence of Boolean Functions / V.M. Krasnov // Vestn. Mosk. Univ., Matem. Mekhan. 2009. № 5. P. 55-57 [Moscow Univ. Math. Bulletin. Vol. 64, No 5, 2009. P. 216-218]
k-Self-correcting schemes of functional elements in the basis {&, -} are considered. It is assumed that constant faults on outputs of functional elements are of the same type. Inverter are supposed to be reliable in service. The weight of each inverter is equal to 1. Conjunctors can be reliable in service, or not reliable. Each reliable conjunctor implements a conjunction of two variables and has a weight p > k+2. Each unreliable conjunctor implements a conjunction in its correct state and implements a boolean constant δ (δ∈{0,1}) otherwise. Each unreliable conjunctor has the weight 1. It is stated that the complexity of realization of monotone threshold symmetric functions f2n(x1,...,xn) = V1≤i<j≤nxixj, n= 3,4,..., by such schemes asymptotically equals (k+3)·n.
Key words: schemes of the functional elements, complexity of implementation, Boolean functions.