Complexity of self-correcting circuits for some sequence of Boolean functions

V. M. Krasnov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2009), pp. 55-57

Résumé

$k$-Self-correcting schemes of functional elements in the basis $\{x_1\ x_2,\bar x\}$ 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 $\delta$ ($\delta\in\{0,1\}$) otherwise. Each unreliable conjunctor has the weight 1. It is stated that the complexity of realization of monotone threshold symmetric functions $f_2^n(x_1,\dots,x_n)=\bigvee\limits_{\scriptscriptstyle 1\leq i j \leq n}x_ix_j$, $n=3,4,\ldots$ by such schemes asymptotically equals $(k+3)n$.