This article is cited in
1 paper
Mathematical Backgrounds of Computer and Control System Reliability
On the arbitrarily reliable implementation of Boolean functions by non-branching programs with a conditional stop operator in bases with generalized conjunction
S. M. Grabovskayaa,
M. A. Alekhinab a Penza State University, Penza, Russia
b Penza State Technological University, Penza, Russia
Abstract:
The implementation of Boolean functions by non-branching programs with a conditional stop operator is considered in a complete finite basis containing a generalized conjunction, i.e. a function of the form
$x_1^{\alpha_1}\& x_2^{\alpha_2}$ $(\alpha_1, \alpha_2 \in \{0, 1\})$. The computational operators are assumed to go into faulty states of an arbitrary type independently of each other with a probability not exceeding the value
$N(B)$, i.e. unreliability of the most unreliable (“bad”) of the basic elements. In addition, conditional stop operators are also unreliable and independently of each other are prone to two types of faults: the first and second kind. The fault of the first kind is characterized by the fact that on admission to the stop-operator input unit this operator does not work with a probability
$\delta \in (0, 1/2)$ and, therefore, the program work continues. The fault of the second kind is that on admission to the stop-operator input zero this operator works with probability
$\eta \in (0, 1/2)$, and, hence, the program work stops. Denote
$\mu=\max\{\delta, \eta\}$. To increase the reliability of source programs, we use the function
$g(x_1, x_2, x_3, x_4)$ of the form $(x_1^{\sigma_1}x_2^{\sigma_2}\vee x_3^{\sigma_3}x_4^{\sigma_4})^{\sigma_5}$ $(\sigma_i \in \{0, 1\}, i \in \{1, 2, 3, 4, 5\})$ and the method of multiple duplication of circuits and programs. We prove that if the complete finite basis
$B$ contains a function of the form
$x_1^{\alpha_1}\& x_2^{\alpha_2}$ $(\alpha_1, \alpha_2 \in \{0, 1\})$, then any Boolean function
$f$ can be implemented by a non-branching program with unreliability no more than
$[0{,}84]^t\cdot 5{,}17\cdot N(B)$ for any natural
$t$ with
$N(B)\in (0, 1/960]$ and
$\mu \in (0, 1/10]$. So, it is proved that an arbitrary Boolean function can be implemented with an arbitrarily reliable non-branching program.
Keywords:
Boolean function, non-branching program, conditional stop operator, synthesis, reliability.
UDC:
519.718
DOI:
10.17223/20710410/43/5