On unreliability upper
bound of non-branching programs at the onetype constant faults at the outputs
of computational operators
Grabovskaya S. M., Kurysheva V. V.
Penza State University
The realization
of Boolean functions by non-branching programs with a conditional stop-operator
is considered in an arbitrary complete finite basis B.
A program with a
conditional stop-operator [1] is characterized by the presence of the control
command – the conditional stop command, giving the possibility of early
stoppage of the work under certain conditions (namely, on admission unit at the
stop-operator input). 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 only type 0 or only type 1 at the outputs. We will call the
constant fault of type 0 at the output, if it is that, the computational
operator realizes the function φ,
ascribed to him, in good condition and the function 0 in failure. The fault of
type 1 is determined similarly.
Furthermore, we assume that all computational operators are prone
the constant faults of type 0 at the outputs.
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 fault at the
output of the program Pr for all
possible input vectors.
Theorem 1. [2]
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.
[3] 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 Rf with
unreliability Nε(Rf)≤N. Let
g(x1, x2, x3) is the function
of the form 
, and Prg is the program, realized the function g(x1, x2, x3),
and Nε(Prg) is unreliability
of the program Prg. Then in this basis any Boolean function f
can be realized by the program Prf, that the inequality is
Nε(Prf )≤ Nε(Prg)+3N2.
Boolean functions
of the form x1x2
x2x3
x1x3
c1x1
c2x2
c3x3
c0
(ci ϵ {0, 1}, i ϵ {0, 1, 2, 3})
are called special functions.
Lemma 1. [4] The variables identification in any
non-linear and non-special function of three or more variables can result in
either a non-linear function of two variables or a special function.
In other words,
it’s possible to obtain either some non-linear function of two variables ψ(x1,x2)=x1x2
c1x1
c2x2
c0
or some special function
φ(x1, x2, x3)=x1x2
x2x3
x1x3
c1x1
c2x2
c3x3
c0,
where c0, c1, c2, c3
ϵ {0, 1}
by means of substitution (identification and/or renaming of variables).
There is Lemma 2
and Theorem 3 [6] for case of non-linear function of two variables.
Lemma 2. [6] In
the complete finite basis, containing a non-linear function of two variables, the
function g(x1, x2, x3) can be realized by the non-branching program with a conditional
stop-operator, for which unreliability is not more than ε.
Theorem 3. [6] In
the complete finite basis, containing a non-linear function of two variables,
any Boolean function f can be realized by the non-branching program with
absolutely reliable conditional stop-operators, whose unreliability Nε(Prf)≤ε+30ε2 for all ε
ϵ (0,
1/960].
Therefore,
we consider only complete finite bases, in which the variable substitution in a non-linear function results in a special function.
There is Lemma 3.
Lemma 3. In the complete finite basis, containing some special
function, the function g(x1, x2, x3) can be realized by the non-branching program with a conditional
stop-operator, for which unreliability is not more than ε.
Theorems 1, 2 and
Lemma 3 imply Theorem 4.
Theorem 4. In the complete finite basis, containing a special
function, any Boolean function f can be realized by the non-branching program
with a conditional stop-operator, whose unreliability Nε(Prf)≤ε+30ε2 for all ε
ϵ (0,
1/960].
Theorems 3 and 4
imply Theorem 5.
Theorem 5. In an arbitrary complete
finite basis any Boolean function f can be realized by the non-branching
program with absolutely reliable conditional stop-operators, whose
unreliability Nε(Prf)≤ε+30ε2 for all ε
ϵ (0,
1/960].
Theorems 2, 5 and
Lemmas 2, 3 imply Theorem 6 (the second iteration step).
Theorem 6. In an arbitrary complete
finite basis any Boolean function f can be realized by the non-branching
program with unreliability Nε(Prf)≤ε+4ε2 for all
ε ϵ (0,
1/960].
Note. It is easy to
verify that Theorem 6 is true in case of the constant fault of type 1 at the
computational operators’ outputs.
Thus, in an
arbitrary finite basis B any Boolean
function f can be realized by the non-branching program with absolutely
reliable conditional stop-operators at the onetype constant faults at the
computational operators’ outputs with unreliability no more than ε+4ε2 for all ε
ϵ (0,
1/960].
For circuits
of FE it is known [2] that in the basis
B any Boolean function f can be realized by the circuit of FE
at the onetype constant faults with unreliability no more than 3ε+100ε2 for all ε
ϵ (0,
1/960]. However, this upper bound can be improved in some bases. For example,
in the basis {x1˅x2, 
1} it is 2ε+42ε2
for all
ε ϵ (0, 1/140]; in the basis {x1→x2, x1
x2}
it is ε+45ε2 for all ε ϵ (0, 1/320].
Whereas for non-branching programs unreliability upper bound is ε+4ε2 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-00212 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] N. P. Redkin: Complete checking tests, Mathematical Problems of
Cybernetics.1989. N 2. P. 198–222
[5] S. V.
Jablonski: Introduction to Discrete Mathematics, A textbook for higher education, ed. V. A. Sadovnichii, Moscow (in Russia), 2001.
[6] S. M. Grabovskaya, Y. D. Ilyina: On reliability of non-branching
programs at the onetype constant faults at the outputs of computational
operators// Proceedings of the VIII International Scientific Conference
“Education and science of the XXI century” (Sofia, Bulgaria, 17–25 October 2012). V. 43. Mathematics. Physics,
Sofia, 2012. P. 46–48.
[7] M. A.
Alekhina: Synthesis asymptotically
optimal reliable circuits (Monograph), Penza, 2006.