There Exist Reliable Circuits, Optimal with Respect to Order of Number of Elements, of Unreliable Functional Elements

Assume that $\varphi_{\delta}^s(x_1,\dots,x_k)$ is a Boolean function whose value is 0 on binary combinations with weight $0,1,\dots,]s-\delta k[$ and 1 on binary combinations with weight $]s+\delta k[,\dots,k-1,k$. On the remaining combinations the function $\varphi_{\delta}^s(x_1,\dots,x_k)$ is not defined. It is shown that there exists a synthesis method that makes it possible to reliably implement, in a circuit of unreliable elements (with error probability $\varepsilon$ for each element $\leq\varepsilon(\delta))$, any function $\varphi_{\delta}^s(x_1,\dots,x_k)$ such that the number of elements of the resultant circuit does not exceed $c(\delta)k$, where $c(\delta)$ is independent of $k$.