Short complete fault detection tests for~logic~networks with fan-in two

K. A. Popkov

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 89-113.

Résumé

It is established that we can implement almost every Boolean function on $n$ variables by a logic network in the basis $$\begin{gathered} \{x \\ ,y,x\vee y, \end{gathered}$$ $x\oplus y,1\}$, allowing a complete fault detection test with length at most $4$ under arbitrary stuck-at faults at outputs of gates. The following assertions are also proved: We can implement each Boolean function on $n$ variables by a logic network in the basis $$\begin{gathered} \{x \\ ,y,x\vee y,x\oplus y,1\} \end{gathered}$$ (in the basis $$\begin{gathered} \{x \\ ,y,x\vee y,x\vee \bar{y},x\oplus y\} \end{gathered}$$) containing at most one dummy variable and allowing a complete fault detection test of length at most $5$ (at most $4$, respectively) under faults of the same type. Illustr. 2, bibliogr. 24.

Détail

Mots-clés : logic network, arbitrary stuck-at fault, complete fault detection test.

Bibliographie

[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, “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

[3] 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

[4] K. A. Popkov, “Tests of contact closure for contact circuits”, Discrete Math. Appl., 26:5 (2016), 299–308 | DOI | DOI | MR | Zbl

[5] K. A. Popkov, “Complete fault detection tests of length $2$ for logic networks under stuck-at faults of gates”, J. Appl. Ind. Math., 12:2 (2018), 302–312 | DOI | MR | Zbl

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

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

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

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

[10] 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

[11] 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, M., 1986, 7–12 (Russian)

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

[13] 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

[14] 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

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

[16] 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

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

[18] 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

[19] Rahagude N. P., Integrated enhancement of testability and diagnosability for digital circuits, Diss. ...Mast. Sci., Blacksburg, Virginia, 2010, 75 pp.

[20] 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

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

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

[23] 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

[24] 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. (IJETEE), 1:3 (2013), 93–96