Geodesic
A method of synthesis of irredundant circuits admitting single fault detection tests of constant length
Diskretnaya Matematika, Tome 29 (2017) no. 4, pp. 87-105.

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

A constructive proof is given that in each of the bases $B'=\{ x\mathbin{\} y, x\oplus y, x\sim y\}$, $B_1=\{ x\mathbin{\} y, x\oplus y, 1\}$ any $n$-place Boolean function may be implemented: a) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates) a single fault detection test of length at most 16, b) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most $2n-2\log_2 n+O(1)$; besides, there exists an $n$-place function that cannot be implemented by an irredundant circuit admitting a detecting test whose length is smaller than $2n-2\log_2 n-\Omega(1)$, c) by an irredundant combinational circuit with $n$ inputs and three outputs admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most 17.
Keywords: circuit of gates, fault detection test, stuck-at fault, Shannon function, easily testable circuit. 
@article{DM_2017_29_4_a5,
     author = {D. S. Romanov and E. Yu. Romanova},
     title = {A method of synthesis of irredundant circuits admitting single fault detection tests of constant length},
     journal = {Diskretnaya Matematika},
     pages = {87--105},
     publisher = {mathdoc},
     volume = {29},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_4_a5/}
}
TY  - JOUR
AU  - D. S. Romanov
AU  - E. Yu. Romanova
TI  - A method of synthesis of irredundant circuits admitting single fault detection tests of constant length
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 87
EP  - 105
VL  - 29
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_4_a5/
LA  - ru
ID  - DM_2017_29_4_a5
ER  - 
%0 Journal Article
%A D. S. Romanov
%A E. Yu. Romanova
%T A method of synthesis of irredundant circuits admitting single fault detection tests of constant length
%J Diskretnaya Matematika
%D 2017
%P 87-105
%V 29
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_4_a5/
%G ru
%F DM_2017_29_4_a5
D. S. Romanov; E. Yu. Romanova. A method of synthesis of irredundant circuits admitting single fault detection tests of constant length. Diskretnaya Matematika, Tome 29 (2017) no. 4, pp. 87-105. http://geodesic.mathdoc.fr/item/DM_2017_29_4_a5/

[1] Redkin N. P., Nadezhnost i diagnostika skhem, Izdatelstvo MGU, Moskva, 1992, 192 pp.

[2] Reddy S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., 21:1 (1972), 124–141 | MR

[3] Hayes J. P., “On modifying logic networks to improve their diagnosability”, IEEE Trans. Comput., C-23:1 (1974), 56–62 | DOI | MR

[4] Saluja K. K., Reddy S. M., “On minimally testable logic networks”, IEEE Trans. Comput., C-23:1 (1974), 552–554 | DOI | MR

[5] Noskov V. N., “Metod sinteza udobnykh dlya kontrolya kombinatsionnykh skhem”, Diskret. matem., 5:4 (1993), 3–23 | MR | Zbl

[6] Hirayama T., Koda G., Nishitani Y., Shimizu K., “Easily testable realization based on OR-AND-EXOR expansion with single-rail inputs”, IEICE Trans. Inf. and Syst., E-82D:9 (1999), 1278–1286

[7] Kalay U., Hall D. V., Perkowski M. A., “A minimal universal test set for self-test of EXOR-Sum-of-Products circuits”, IEEE Trans. Comput., 49:3 (2000), 267–276 | DOI

[8] Inose H., Sakauchi M., “Synthesis of automatic fault diagnosable logical circuits by function conversion method”, First USA-Japan Computer Conf. Proc., 1972, 426–430

[9] DasGupta S., Hartmann C. R. P., Rudolph L. D., “Dual-mode logic for function-independent fault testing”, IEEE Trans. Comput., C-29:11 (1980), 1025–1029 | DOI | MR

[10] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 1986, no. 1, 72–74

[11] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matem. voprosy kibernetiki, v. 2, Nauka, Moskva, 1989, 198–222 | MR

[12] Romanov D. S., “Metod sinteza legkotestiruemykh skhem, dopuskayuschikh edinichnye proveryayuschie testy konstantnoi dliny”, Diskretnaya matematika, 26:2 (2014), 100–130 | DOI | Zbl

[13] Redkin N. P., “O proveryayuschikh testakh dlya skhem pri odnotipnykh konstantnykh neispravnostyakh na vkhodakh elementov”, Izv. vuzov. Matematika, 1988, no. 7, 57–64 | MR

[14] Borodina Yu. V., “O sinteze legkotestiruemykh skhem v sluchae odnotipnykh konstantnykh neispravnostei na vykhodakh elementov”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. kibern., 2008, no. 1, 40–44 | MR | Zbl

[15] Borodina Yu. V., “O skhemakh, dopuskayuschikh edinichnye testy dliny 1 pri konstantnykh neispravnostyakh na vykhodakh elementov”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 2008, no. 5, 49–52 | MR | Zbl

[16] Borodina Yu. V., Borodin P. A., “Sintez legkotestiruemykh skhem v bazise Zhegalkina pri konstantnykh neispravnostyakh tipa “0” na vykhodakh elementov”, Diskretnaya matematika, 22:3 (2010), 127–133 | DOI | MR | Zbl

[17] Borodina Yu. V., “Nizhnyaya otsenka dliny polnogo testa v bazise $\{x|y\}$”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 2015, no. 4, 49–51 | MR | Zbl

[18] Romanov D. S., “O sinteze skhem, dopuskayuschikh polnye proveryayuschie testy konstantnoi dliny otnositelno proizvolnykh konstantnykh neispravnostei na vykhodakh elementov”, Diskretnaya matematika, 25:2 (2013), 104–120 | DOI | Zbl

[19] Popkov K. A., “O tochnom znachenii dliny minimalnogo edinichnogo diagnosticheskogo testa dlya odnogo klassa skhem”, Preprinty IPM im. M. V. Keldysha RAN, 2015, 074, 20 pp.

[20] Romanov D. S., Romanova E. Yu., “Metod sinteza neizbytochnykh skhem, dopuskayuschikh korotkie edinichnye diagnosticheskie testy pri konstantnykh neispravnostyakh na vykhodakh elementov”, Izv. vuzov. Povolzhsk. reg. Fiz-matem. nauki, 2016, no. 2, 87–102

[21] Popkov K. A., “O edinichnykh diagnosticheskikh testakh dlya skhem iz funktsionalnykh elementov v bazise Zhegalkina”, Preprinty IPM im. M. V. Keldysha RAN, 2016, 050, 16 pp.

[22] Popkov K. A., “Edinichnye proveryayuschie testy dlya skhem iz funktsionalnykh elementov v bazise «kon'yunktsiya-otritsanie»”, Preprinty IPM im. M. V. Keldysha RAN, 2017, 030, 31 pp.

[23] Popkov K. A., “Nizhnie otsenki dlin polnykh diagnosticheskikh testov dlya skhem i vkhodov skhem”, Prikladnaya diskretnaya matematika, 2016, no. 4(34), 65–73

[24] Popkov K. A., “Nizhnie otsenki dlin edinichnykh testov dlya skhem iz funktsionalnykh elementov”, Diskretnaya matematika, 29:2 (2017), 53–69 | DOI

[25] Alekhina M. A., “O nadezhnosti skhem iz nenadezhnykh funktsionalnykh elementov pri odnotipnykh konstantnykh neispravnostyakh na vykhodakh elementov”, Diskretnaya matematika, 5:2 (1993), 59–74 | MR | Zbl

[26] Alekhina M. A., Sintez asimptoticheski optimalnykh po nadezhnosti skhem iz nenadezhnykh elementov, IITs PGU, Penza, 2006, 156 pp.

[27] Alekhina M. A., Klyanchina D. M., “Ob asimptoticheski optimalnykh po nadezhnosti skhemakh v nekotorykh spetsialnykh bazisakh”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, 2010, no. 4(16), 3–13 | MR

[28] Alekhina M. A., “O nadezhnosti skhem v proizvolnom polnom konechnom bazise pri odnotipnykh konstantnykh neispravnostyakh na vykhodakh elementov”, Diskretnaya matematika, 24:3 (2012), 17–24 | DOI | Zbl

[29] Alekhina M. A., Barsukova O. Yu., “The reliability of circuits in the basis anticonjuction with constant faults of gates”, Comput. Sci. Inf. Technol., 2(1) (2014), 51–54

[30] Alekhina M. A., “Sintez nadezhnykh skhem pri konstantnykh neispravnostyakh na vkhodakh i vykhodakh elementov”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, 2015, no. 2, 3–15 | MR | Zbl

[31] Alekhina M. A., Kurysheva V. V., “O nadezhnosti skhem v bazise “antikon'yunktsiya” pri konstantnykh neispravnostyakh na vkhodakh elementov”, Izv. vuzov. Matematika, 2016, no. 7, 3–9 | Zbl

[32] Romanov D. S., Romanova E. Yu., “Korotkie testy dlya skhem v bazise Zhegalkina”, Intellektualnye sistemy. Teoriya i prilozheniya, 20:3 (2016), 73–78 | MR

[33] Noskov V. N., “O slozhnosti testov, kontroliruyuschikh rabotu vkhodov logicheskikh skhem”, Diskretnyi analiz, v. 27, IM SO AN SSSR, Novosibirsk, 1975, 23–51

[34] Pogosyan G. R., O proveryayuschikh testakh dlya logicheskikh skhem, VTs AN SSSR, Moskva, 1982, 57 pp.