Geodesic
Complete fault detection tests of length~2 for logic networks under stuck-at faults of gates
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 62-81.

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

We consider the problem of the synthesis of the logic networks implementing Boolean functions of n variables and allowing short complete fault detection tests regarding arbitrary stuck-at faults at the outputs of gates. We prove that there exists a basis consisting of two Boolean functions of at most four variables in which we can implement each Boolean function by a network allowing such a test with length at most 2. Illustr. 1, bibliogr. 33.
Keywords: logic network, stuck-at fault, complete fault detection test. 
@article{DA_2018_25_2_a3,
     author = {K. A. Popkov},
     title = {Complete fault detection tests of length~2 for logic networks under stuck-at faults of gates},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {62--81},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_2_a3/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - Complete fault detection tests of length~2 for logic networks under stuck-at faults of gates
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 62
EP  - 81
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_2_a3/
LA  - ru
ID  - DA_2018_25_2_a3
ER  - 
%0 Journal Article
%A K. A. Popkov
%T Complete fault detection tests of length~2 for logic networks under stuck-at faults of gates
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 62-81
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_2_a3/
%G ru
%F DA_2018_25_2_a3
K. A. Popkov. Complete fault detection tests of length~2 for logic networks under stuck-at faults of gates. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 62-81. http://geodesic.mathdoc.fr/item/DA_2018_25_2_a3/

[1] Yu. V. Borodina, “Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs”, Mosc. Univ. Comput. Math. Cybern., 32:1 (2008), 42–46 | DOI | MR | Zbl

[2] Yu. V. Borodina, “Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements”, Mosc. Univ. Math. Bull., 63:5 (2008), 202–204 | DOI | MR | Zbl

[3] Yu. V. Borodina, “Lower estimate of the length of the complete test in the basis $\{x\mid y\}$”, Mosc. Univ. Math. Bull., 70:4 (2015), 185–186 | DOI | MR | Zbl

[4] Yu. V. Borodina, P. A. Borodin, “Synthesis of easily testable circuits over the Zhegalkin basis in the case of constant faults of type 0 at outputs of elements”, Discrete Math. Appl., 20:4 (2010), 441–449 | DOI | DOI | MR | Zbl

[5] S. S. Kolyada, Upper bounds on the length of fault detection tests for logic circuits, Cand. Sci. Dissertation, Mosk. Gos. Univ., Moscow, 2013 (Russian)

[6] K. A. Popkov, “Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits”, Prikl. Diskretn. Mat., 2016, no. 4, 65–73 (Russian)

[7] K. A. Popkov, “On single diagnostic tests for logic circuits in the Zhegalkin basis”, Izv. Vyssh. Uchebn. Zaved. Povolzh. Reg. Fiz.-Mat. Nauki, 2016, no. 3, 3–18 (Russian)

[8] K. A. Popkov, Single fault detection tests for logic networks in the basis “conjunction-negation”, Prepr. No. 30, Inst. Prikl. Mat. Keldysh, Moscow, 2017 (Russian)

[9] K. A. Popkov, “On the exact value of the length of the minimal single diagnostic test for a particular class of circuits”, J. Appl. Ind. Math., 11:3 (2017), 431–443 | DOI | MR | Zbl

[10] N. P. Red'kin, “On complete checking tests for circuits of functional elements”, Vestn. Mosk. Univ. Ser. 1, 1986, no. 1, 72–74 (Russian) | Zbl

[11] N. P. Red'kin, “On circuits admitting short tests,”, Vestn. Mosk. Univ. Ser. 1, 1988, no. 2, 17–21 (Russian) | Zbl

[12] N. P. Red'kin, “On complete fault detection tests for logic circuits”, Mathematical Problems of Cybernetics, 2, Nauka, Moscow, 1989, 198–222 (Russian) | MR

[13] N. P. Red'kin, Reliability and Diagnosis of Circuits, Izd. MGU, Moscow, 1992 (Russian)

[14] N. P. Red'kin, “On single-fault diagnostic tests for one-type constant faults at outputs of gates”, Vestn. Mosk. Univ. Ser. 1, 1992, no. 5, 43–46 (Russian) | Zbl

[15] D. S. Romanov, “On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates”, Discrete Math. Appl., 23:3–4 (2013), 343–362 | DOI | MR | Zbl

[16] D. S. Romanov, “Method of synthesis of easily testable circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 24:4 (2014), 227–251 | DOI | DOI | MR | Zbl

[17] D. S. Romanov, E. Yu. Romanova, “A method of synthesizing irredundant circuits admitting small single fault diagnostic test sets at stuck-at faults at outputs of gates”, Izv. Vyssh. Uchebn. Zaved. Povolzh. Reg. Fiz.-Mat. Nauki, 2016, no. 2, 87–102 (Russian)

[18] A. B. Ugol'nikov, The Post Classes, Izd. TsPI Mekh.-Mat. Fak. MGU, Moscow, 2008 (Russian)

[19] I. A. Chegis, S. V. Yablonskii, “Logical methods for control of electric circuits”, Tr. MIAN SSSR, 51, 1958, 270–360 (Russian) | MR | Zbl

[20] S. V. Yablonskii, “Reliability and monitoring of control systems”, Proc. All-Union Seminar on Discrete Math. and Its Applications (Moscow, Russia, Jan. 31 – Feb. 2, 1984), Izd. MGU, Moscow, 1986, 7–12 (Russian)

[21] S. V. Yablonskii, “Certain questions of reliability and monitoring of control systems”, Mathematical Problems of Cybernetics, 1, Nauka, Moscow, 1988, 5–25 (Russian)

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

[23] Geetha V., Devarajan N., Neelakantan P. N., “Network structure for testability improvement in exclusive-OR sum of products Reed–Muller canonical circuits”, Int. J. Eng. Res. Gen. Sci., 3:3 (2015), 368–378 | MR

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

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

[26] Jameil A. K., “A new single stuck fault detection algorithm for digital circiuts”, Int. J. Eng. Res. Gen. Sci., 3:1 (2015), 1050–1056

[27] Neelakantan P. N., Ebenezer Jeyakumar A., “Single stuck-at fault diagnosing circuit of Reed–Muller canonical exclusive-or sum of product Boolean expressions”, J. Comput. Sci., 2:7 (2006), 595–599 | DOI

[28] Rahagude N. P., Integrated enhancement of testability and diagnosability for digitac circuits, Mast. Sci. Dissertation., Virginia Polytech. Inst. State Univ., Blacksburg, VA, 2010, 75 pp.

[29] Rahaman H., Das D. K., Bhattacharya B. B., “Testable design of AND-EXOR logic networks with universal test sets”, Comput. Electr. Eng., 35:5 (2009), 644–658 | DOI | Zbl

[30] Reddy S. M., “Easily testable realizations for logic functions”, IEEE Trans. Comput., 21:11 (1972), 1183–1188 | DOI | MR | Zbl

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

[32] Saluja K. K., Reddy S. M., “Fault detecting test sets for Reed–Muller canonic networks”, IEEE Trans. Comput., 24:10 (1975), 995–998 | DOI | MR

[33] Singh S. P., Sagar B. B., “Stuck-at fault detection in combinational network coefficients of the RMC with fixed polarity (Reed–Muller coefficients)”, Int. J. Emerg. Trends Electr. Electron., 1:3 (2013), 93–96