On the arbitrarily reliable implementation of~Boolean~functions by non-branching programs with~a conditional stop operator in~bases~with~generalized conjunction

S. M. Grabovskaya ; M. A. Alekhina

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 70-77.

Résumé

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.

Détail

Keywords: Boolean function, non-branching program, conditional stop operator, synthesis, reliability.

Bibliographie

[1] Chashkin A. V., “On the average time for the computation of the values of Boolean functions”, Diskretn. Anal. Issled. Oper., Ser. 1, 4:1 (1997), 60–78 (in Russian) | MR | Zbl

[2] Alekhina M. A., “Synthesis and complexity of asymptotically optimal circuits with unreliable gates”, Fundamenta Informaticae, 104:3 (2010), 219–225 | MR | Zbl

[3] Alekhina M. A., Vasin A. V., “On bases with unreliability coefficient 2”, Math. Notes, 95:1–2 (2014), 147–173 | DOI | DOI | MR | Zbl

[4] Alekhina M. A., Gusynina Yu. S., Shornikova T. A., “Upper estimate of unreliability of schemes in full finite basis (in $P_2$) for arbitrary faults of gates”, Russian Mathematics, 61:12 (2017), 70–72 | DOI | Zbl

[5] Alekhina M. A., “On the synthesis of reliable circuits of $x/y$ functional elements at the same type constant faults at the element outputs”, Vest. MSU. Matem. Mekhan., 1991, no. 5, 80–83 (in Russian)

[6] Alekhina M. A., “On reliability of circuits over an arbitrary complete finite basis under single-type constant faults at outputs of elements”, Discrete Math. Appl., 22:4 (2012), 383–391 | DOI | DOI | MR | Zbl

[7] Alekhina M. A., Kurysheva V. V., “On the circuits reliability in anticonjunction basis with constant faults at gate inputs”, Russian Mathematics, 60:7 (2016), 1–6 | DOI | MR | Zbl

[8] Yablonskiy S. V., Selected works, eds. V. B. Alekseev, V. I. Dmitriev, MAKS Press Publ., M., 2004, 584 pp. (in Russian)

[9] Alekhina M. A., Grabovskaya S. M., “Reliability of nonbranching programs in an arbitrary complete finite basis”, Russian Mathematics, 56:2 (2012), 10–18 | DOI | MR | Zbl

[10] Grabovskaya S. M., “On methods of raise the reliability of non-branching programs with a conditional stop operator”, Problems of Automation and Control in Technical Systems, Proc. Int. Conf., dedicated to the 70th anniversary of the Victory in the Great Patriotic War (Penza, Russia, May 19–21, 2015), Penz. State Univ., Penza, 2015, 339–342 (in Russian)