Geodesic
Estimations of unreliability of circuits in Rosser--Turkett~basis (in $P_3$) with faults of type~$0$ at the outputs of gates
Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 62-75.

Voir la notice de l'article provenant de la source Math-Net.Ru

This work belongs to one of the most important branches of mathematical cybernetics such as the theory of the reliability of control systems. The synthesis problem for reliable control systems is one of the main problems in discrete mathematics and mathematical cybernetics. The topicality of the research in this field is due to the importance of numerous applications arising in various sections of science and technology. We consider the realization of ternary logic functions by circuits consisting of unreliable functional elements in Rosser–Turkett basis. We assume that all the circuit elements are exposed to faults of type 0 at their outputs and pass to fault states independently with the probability $\varepsilon$ ($\varepsilon1/2$). We have obtained the following results: 1) any function of ternary logic can be realized by a circuit with unreliability that is asymptotically not more than $\varepsilon$ for small $\varepsilon$; 2) for any function except the constant $0$ and the variable $x_i$ ($i\in\mathbb N$), such a circuit has the asymptotically optimal reliability and operates with the unreliability asymptotically equal to $\varepsilon$ for small $\varepsilon$; 3) the functions $0$ and $x_i $ can be realized absolutely reliably.
Keywords: ternary logic functions, circuit from functional gates, unreliability of a circuit, reliability of a circuit, faults of type $0$. 
@article{PDM_2017_3_a4,
     author = {M. A. Alekhina and O. Yu. Barsukova},
     title = {Estimations of unreliability of circuits in {Rosser--Turkett~basis}  (in $P_3$) with faults of type~$0$ at the outputs of gates},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {62--75},
     publisher = {mathdoc},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_3_a4/}
}
TY  - JOUR
AU  - M. A. Alekhina
AU  - O. Yu. Barsukova
TI  - Estimations of unreliability of circuits in Rosser--Turkett~basis  (in $P_3$) with faults of type~$0$ at the outputs of gates
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 62
EP  - 75
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_3_a4/
LA  - ru
ID  - PDM_2017_3_a4
ER  - 
%0 Journal Article
%A M. A. Alekhina
%A O. Yu. Barsukova
%T Estimations of unreliability of circuits in Rosser--Turkett~basis  (in $P_3$) with faults of type~$0$ at the outputs of gates
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 62-75
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_3_a4/
%G ru
%F PDM_2017_3_a4
M. A. Alekhina; O. Yu. Barsukova. Estimations of unreliability of circuits in Rosser--Turkett~basis  (in $P_3$) with faults of type~$0$ at the outputs of gates. Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 62-75. http://geodesic.mathdoc.fr/item/PDM_2017_3_a4/

[1] Von Neuman J., “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata Studies, eds. C. Shannon, J. McCarthy, Princeton University Press, 1956, 43–98 ; Avtomaty, IL, M., 68–139 | MR

[2] Dobrushin R. L. and Ortyukov S. I., “Upper bound on the redundancy of self-correcting arrangements of unreliable functional elements”, Problems Inform. Transmission, 13:3 (1977), 203–218 | MR | MR | Zbl

[3] Ortyukov S. I., “On the redundancy of the Boolean functions implementation by circuits from unreliable elements”, Proc. Seminar on Discr. Math. and its Appl. (Moscow, 27–29 Jan. 1987), MSU Publ., Moscow, 1989, 166–168 (in Russian)

[4] Uhlig D., “Reliable networks from unreliable gates with almost minimal complexity”, LNCS, 278, 1987, 462–469

[5] Pippenger N., “On networks of noisy gates”, 26th Ann. Symp. Foundations of Computer Science (Portland, 21–23 Oct. 1985), 30–38

[6] Yablonskiy C. V., “Asymptotically best method for synthesizing reliable circuits from unreliable elements”, Banach Center Publ., 7:1 (1982), 11–19 (in Russian) | DOI

[7] Tarasov V. V., “The synthesis of reliable circuits from unreliable elements”, Math. Notes, 20:3 (1976), 775–780 | DOI | MR | Zbl

[8] Vinogradov Yu.|A., “On the synthesis of three-valued MDS-circuits”, Matematicheskie Voprosy Kibernetiki, 3, 1991, 187–198 (in Russian) | Zbl

[9] Vinogradov Yu. A., “On the synthesis of four-valued quasicomplementary MOSFETs”, Matematicheskie Voprosy Kibernetiki, 8, 1999, 298–300 (in Russian) | Zbl

[10] Barsukova O. Yu., Synthesis of reliable schemes realizing the functions of two-valued and three-valued logics, PhD Thesis, Penza, 2014, 87 pp. (in Russian)

[11] Alekhina M. A., Kargin S. P., “On synthesis of unreliable element circuits in $P_4$”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2014, no. 4(32), 47–56 (in Russian)

[12] Alekhina M. A., “Synthesis of circuits containing unreliable gates in $P_k$”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2015, no. 3, 8–10 (in Russian)

[13] Alekhina M. A., Barsukova O. Yu., “On the reliability of circuits realizing functions from $P_3$”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2012, no. 1(21), 57–65 (in Russian)

[14] Alekhina M. A., Barsukova O. Yu., “Circuit failure estimate in the Rosser–Turkett basis”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2014, no. 1(29), 5–19 (in Russian)

[15] Alekhina M. A., Barsukova O. Yu., “Unreliability of circuits in the basis by Rosser–Turkett”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2014, no. 7, 109–110 (in Russian)

[16] Alekhina M. A., Barsukova O. Yu., “On reliability of circuits realizing ternary logic functions”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 12–24 (in Russian) | MR | Zbl

[17] Alekhina M. A., Kargin S. P., “Asymptotic reliability-optimal circuits in the Rosser–Turkett basis in $P_4$”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2015, no. 1, 37–53 (in Russian)

[18] Alekhina M. A., Barsukova O. Yu., “A lower bound for unreliability of circuits in the Webb basis”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2015, no. 8, 102–103 (in Russian)

[19] Yablonskiy S. V., Introduction to Discrete Mathematics, Vyssh. Shk., Moscow, 2001, 384 pp. (in Russian) | MR