The reliability of non-branching programs at the onetype constant

faults at the outputs of computational operators

Grabovskaya S. M., Ilyina Y. D.

Penza State University

We consider the realization of Boolean functions by non-branching programs with a conditional stop-operator in a complete finite basis B, containing a function of the form (x₁^a&x₂^b)^c, where a, b, c ϵ {0, 1} (a non-linear function of two elements).

A program with a conditional stop-operator [1] characterized by the control command – the conditional stop command, giving the possibility of early stoppage of the work under certain conditions. It is assumed that conditional stop-operators are absolutely reliable, and all computational operators independently of each other with probability ε ϵ (0, 1/2) are prone the onetype constant faults at the outputs. As the conditional stop-operator is reliable, it works when it is input unit. We will call the constant fault of type 0 (type 1) at the output, if it is that, the computational operator realizes the function φ, ascribed to him, in good condition and the function 0 (function 1) in failure.

Note that a circuit of functional elements (FE) can be considered a special case of non-branching programs, namely, a non-branching program without stop-operators.

Unreliability N_ε(Pr) of the program Pr is called the maximum faults at the output of the program Pr for all possible input vectors.

Furthermore, we assume that all computational operators are prone the constant faults of type 0 at the outputs.

Theorem 1. [1] In an arbitrary complete finite basis any Boolean function f can be realized by the circuit S, whose unreliability N_ε(S)≤3,11ε for all ε ϵ (0, 1/960].

Theorem 2. [2] Let B is the complete finite basis, and let there exists N, such that any Boolean function f can be realized by the non-branching program R_f with unreliability N_ε(R_f)≤N. Let g(x₁, x₂, x₃) is the function of the form , and Pr_g is the program, realized the function g(x₁, x₂, x₃), and N_ε(Pr_g) is unreliability of the program Pr_g. Then any Boolean function f in this basis can be realized by the program Pr_f, that the inequality is N_ε(Pr_f )≤ N_ε(Pr_g)+3N².

We have Lemma 1.

Lemma 1. In the basis B the function g(x₁, x₂, x₃) can be realized by the non-branching program with a conditional stop-operator, for which unreliability is not more than ε.

Theorems 1 and 2 and Lemma 1 implies Theorem 3.

Theorem 3. In the complete finite basis, containing a non-linear function of two elements, any Boolean function f can be realized by the non-branching program with an absolutely reliable conditional stop-operator with unreliability N_ε(Pr_f)≤ε+30ε² for all ε ϵ (0, 1/960].

Note. It is easy to verify that Theorem 3 is true in the case of the constant faults of type 1 at the computational operators outputs.

Thus, in the finite basis B, containing a non-linear function of two elements, an arbitrary Boolean function f can be realized by a non-branching program with an absolutely reliable conditional stop-operator at the onetype constant faults at the computational operators outputs with unreliability no more than ε+30ε² for all
ε ϵ (0, 1/960].

For circuits of FE it is known [5] that in the basis B an arbitrary Boolean function f can be realized by the circuit of FE at the onetype constant faults with unreliability no more than 3ε+100ε² for all ε ϵ (0, 1/960]. However, this upper bound can be improved in some bases. For example, in the basis {x₁˅x₂, ₁} it is 2ε+42ε² for all ε ϵ (0, 1/140]; in the basis {x₁˅x₂, x₁~x₂} it is ε+6ε² for all ε ϵ (0, 1/320]. Whereas for non-branching programs unreliability upper bound is ε+30ε² for all
ε ϵ (0, 1/960], which is generally better than for circuits of FE.

This work was supported by the Russian Foundation for Basic Research (project number 11-01-00212a and 12-01-31340).

References

[1] A. V. Chashkin: On average computation time of Boolean functions, Discrete analysis and research of operations, January–March, 1997. V. 4. N 1. P. 60–78.

[2] M. A. Alekhina: The reliability of circuits at the onetype constant faults at the outputs of elements, Proceedings of the X International Seminar “Discrete mathematics and its applications” (Moscow, 1–6 February 2010), ed. O. M. Kasim-Zade. Moscow (in Russia), 2010. P. 83–85.

[3] S. M. Grabovskaya: Asymptotically optimal reliable non-branching programs with a conditional stop-operator (Dissertation for the degree of candidate of physical and mathematical sciences), Penza, 2012.

[4] S. V. Jablonski: Introduction to Discrete Mathematics, A textbook for higher education, ed. V. A. Sadovnichii, Moscow (in Russia), 2001.

[5] M. A. Alekhina: Synthesis asymptotically optimal reliable circuits (Monograph), Penza, 2006.