Mathematics /4. Applied mathematics

Doctor of science, professor Alekhina M.A., student  Ilyina J.D.  

Penza State University, Russia

About complexity of asymptotically optimal on reliability

circuits with inverse faults on the outputs of the elements

We consider the realization of Boolean functions by combinatorial circuits with unreliable gates, realizing functions from an arbitrary complete finite basis B={e1,...,em}. A positive number v(Ei) (call it the weight of the element) is assigned to each element of the basis Ei (i = 1, ..., m) with the function ei.

The circuit S complexity is defined as the sum of the weights of all its elements, and it’s denoted L(S). Let  where the minimum is taken for all basis elements Ei such that n(Ei)> 1 and n(Ei) is the number of essential variables of the function ei, realized  by the element  Ei .

It is supposed that all circuit elements are unreliable and independently of each other are prone output inverse faults with probability ε (εÎ(0,1/2)). The inverse fault at the output is characterized by that the functional element realizes the function e, ascribed to him, in good condition and the function  in failure. The circuit of unreliable elements is assumed to realize the function , when entering of the set =(a1,a2,…,an) at the circuit inputs implies supplying for a set of circuit inputs =(a1,a2,…,an)  with no faults at the output value appears  .

Let  be an arbitrary Boolean function and S be any circuit, realizing the function . Denote  the probability of the value  at the output of the circuit S, realizing the Boolean function  for the input set . Unreliability P(S) of the circuit S is defined as the maximum of numbers  for all possible input sets . Reliability of the circuit S is equal 1−P(S).

It’s introduced Shannon function , characterized complexity of circuits, realizing the functions of n variables in the basis B, where the minimum is taken for all circuits S of unreliable elements, that realize the function  with unreliability  , and the maximum is taken for all Boolean functions f of n variables.

Denote  the minimum number of reliable elements required to realize the function g by a circuit in the basis B. D. Uhlig [1] proved Theorem 1 for output inverse faults with a fault probability e.

Theorem 1 [1]. For any arbitrary small numbers b and h (b, h> 0) there exists  the number e¢ (e¢ Î(0, 1/2)) such that for any eÎ(0, e¢), and anyone p, satisfied the inequality , there is the relation d, where  is the minimum number of reliable elements required to realize the function of voting  in this basis B.

Circuits, satisfied conditions of Theorem 1, are asymptotically optimal on complexity and work with some level of reliability 1–p.

Boolean function of the form  (, ) is called a generalized function of voting.

Let G be a set of Boolean functions of variables  (n ≥ 3), such that each of them is congruent to some generalized function of voting. Obviously  that ÎG.

REMARK 1. Theorem 1 is true, if  instead of the voting function we take any function from the set G.    Therefore (for a given basis), instead of   it is advisable to take a number .

Lemma 1 [2]. In the basis B there is the inequality .

Lemma 2 [3]. Let f  be an arbitrary Boolean function and S1 be a circuit, realizing the function f. Let  g Î G  and A be any circuit, realizing the function g. Then the function f can be realized by  such circuit S2, that P(S2) ≤ P(A)+3P2(S1), where  P(S1) and P(A)  are unreliabilities of circuits S1 and A respectively.

Let , where S is the circuit of unreliable elements, realizing the Boolean function f.

The circuit A of unreliable elements,  realizing the Boolean function f, is called asymptotically optimal on reliability, if  for .

We prove the main result of this article.

Theorem 2. Let B be an arbitrary complete finite basis and Sg be an asymptotically optimal on reliability circuit, realizing the function of voting. For any h> 0 there is the constant ε0 Î (0,1/2) such that any Boolean function  can be realized by the asymptotically optimal on reliability circuit S, for which there are relations P(S) ≤ P(Sg)+196ε2  for any ε Î (0,ε0] and L(S) d 3(1+h)ρ×2n/n  for .

Proof. Let the conditions of the theorem are satisfied and  be any Boolean function. We take an arbitrary number h> 0 and use Theorem 1, considering b = 0,01. Then there is a constant  ε0 Î (0,1/2) , that for any  ε Î (0, ε0]  and p=1,01ε  NG the function f can be realized by the circuit S1, for which P(S1) ≤1,01εNG  and L(S1) d (1+c)ρ 2n/n. According to Lemma 1 we have. Therefore, P(S1) ≤ 8,08ε. Take three copies of circuit S1 and connect their outputs with the inputs of the circuit Sg. Denote S2 this circuit. According to Lemma 2, for ε Î (0, ε0] we obtain P(S2) ≤ P(Sg)+3P2(S1) ≤ P(Sg)+3(8,08ε)2 ≤ P(Sg)+196ε2.

Obviously, L(S2)=3L(S1)+L(Sg) d 3L(S1) d 3(1+h)ρ 2n/n. ƒ

Using Theorem 2, we can improve constant d in the previous result of A.V. Vasin [4]: let the complete basis is B Í B3, then for any h>0 there exist constants cÎ{1,2,3,4,5}, ε0 Î (0, 1/2), d > 0  and the class of functions K, depending only on the basis, that for all n ≥ 3, any Boolean function ÎK can be realized by the asymptotically optimal on reliability circuit S, for which P(S) ≤ cε+dε2    for all ε Î (0,ε0], d≤ 2252 and L(S) d 3(1+h)ρ 2n/n for .

Corollary 1. Let the complete basis  B Í B3.  For any h>0, there exist constants c Î{1,2,3,4,5}, ε0 Î (0, 1/2)  and the class of functions K, depending only on the basis, that for all n ≥ 3 any Boolean function ÎK can be realized by the  asymptotically optimal on reliability circuit S, for which P(S) ≤ cε+360ε2   for all 
ε Î (0,ε0] and   L(S) d 3(1+h)ρ 2n/n  for .

Theorem proof follows from the fact, that [4] in the complete basis B Í B3 the voting function can be realized by the asymptotically optimal on reliability circuit Sg, for which P(Sg) ≤ cε+161ε2  for all  εÎ (0,1/960].

Circuits, satisfied the conditions of Corollary 1, are asymptotically optimal on reliability for functions from class K, and their complexity differs from complexity of minimal circuits of absolutely reliable elements in 3(1+h) times, where h is an arbitrary small positive number. Note that the class K contains almost all Boolean functions.

References

1. Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory. Intern. ๑onf. FCT'87 (Kazan,  June 1987). – Proc. Berlin: Springer-Verl., 1987. – P. 462 – 469. (Lecture Notes in Comput. Sci.; V. 278).

2. M.A. Alekhina:  About number of  gates of circuits, realized generic function of voting // News of higher education institute. Volga region. Physic-mathematical sciences. – Penza (in Penza), 2013, in press.

3. M.A. Alekhina: Synthesis of the asymptotically optimal on the reliability combinatorial circuits (Monograph), Penza (in Penza), 2006. – 156 p.

4. Vasin ภ.ย. Asymptotically optimal circuits on  reliability in complete final basis of  three-input gates. – Thesis … candidate of  physic-mathematical sciences, Penza, 2010. – 100 p.