Volume 21, No 1, 2014, P. 30–43

UDC 519.718
S. M. Grabovskaya
On upper bound of non-branching programs unreliability at one-type constant faults on the computational operators outputs

The realization of Boolean functions by non-branching programs with a conditional stop is considered in an arbitrary complete finite basis. It is supposed that conditional stop-operators are absolutely reliable and all computational operators are prone to one type constant faults at the outputs independently of each other with probability$\varepsilon\in(0,1/2)$. For the basis, the upper bound $\varepsilon+4\varepsilon^2$ is obtained for unreliability of non-branching programs realizing any Boolean function for all $\varepsilon\in(0,1/960]$.
Ill. 4, bibliogr. 6.

Keywords: Boolean function, non-branching program, conditional stop-operator, synthesis, reliability, one-type constant faults.

Grabovskaya Svetlana Mikhailovna 1,2
1. The Penza State University,
40 Krasnaya St., 440026 Penza, Russia
e-mail: swetazin@mail.ru

 © Sobolev Institute of Mathematics, 2015