Volume 26, No 1, 2019, P. 89-113

UDC 519.718.7
K. A. Popkov
Short complete fault detection tests for logic networks with fan-in two

Abstract:
It is established that we can implement almost every Boolean function on $n$ variables by a logic network in the basis {$x \And y, x \lor y, 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 {$x \And y, x \lor y, x \oplus y, 1$} (in the basis {$x \And y, x \lor y, x \lor \bar{y}, x \oplus y$}) 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.

Keywords: logic network, arbitrary stuck-at fault, complete fault detection test.

DOI: 10.33048/daio.2019.26.623

Kirill A. Popkov ¹
1. Keldysh Institute of Applied Mathematics,
4 Miusskaya Square, 125047 Moscow, Russia
e-mail: kirill-formulist@mail.ru

Received July 16, 2018
Revised August 2, 2018
Accepted November 28, 2018

References

[1] Yu. V. Borodina, Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs, Vestn. Mosk. Univ., Ser. 15, No. 1, 40–44, 2008 [Russian]. Translated in Mosc. Univ. Comput. Math. Cybern., 32, No. 1, 42–46, 2008.

[2] Yu. V. Borodina, Lower estimate of the length of the complete test in the basis {x | y}, Vestn. Mosk. Univ., Ser. 1, No. 4, 49–51, 2015 [Russian]. Translated in Mosc. Univ. Math. Bull., 70, No. 4, 185–186, 2015.

[3] Yu. V. Borodina and 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, Diskretn. Mat., 22, No. 3, 127–133, 2010 [Russian]. Translated in Discrete Math. Appl., 20, No. 4, 441–449, 2010.

[4] K. A. Popkov, Tests of contact closure for contact circuits, Diskretn. Mat., 28, No. 1, 87–100, 2016 [Russian]. Translated in Discrete Math. Appl., 26, No. 5, 299–308, 2016.

[5] K. A. Popkov, Complete fault detection tests of length 2 for logic networks under stuck-at faults of gates, Diskretn. Anal. Issled. Oper., 25, No. 2, 62–81, 2018 [Russian]. Translated in J. Appl. Ind. Math., 12, No. 2, 302–312, 2018.

[6] N. P. Red’kin, On complete checking tests for circuits of functional elements, Vestn. Mosk. Univ., Ser. 1, No. 1, 72–74, 1986 [Russian].

[7] N. P. Red’kin, On circuits admitting short tests, Vestn. Mosk. Univ., Ser. 1, No. 2, 17–21, 1988 [Russian].

[8] N. P. Red’kin, On complete fault detection tests for logic circuits, in Mathematical Problems of Cybernetics, Vol. 2, pp. 198–222, Nauka, Moscow, 1989 [Russian].

[9] N. P. Red’kin, Reliability and Diagnosis of Circuits, Izd. MGU, Moscow, 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, Diskretn. Mat., 25, No. 2, 104–120, 2013 [Russian]. Translated in Discrete Math. Appl., 23, No. 3–4, 343–362, 2013.

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

[12] S. V. Yablonskii, Certain questions of reliability and monitoring of control systems, in Mathematical Problems of Cybernetics, Vol. 1, pp. 5–25, Nauka, Moscow, 1988 [Russian].

[13] S. DasGupta, C. R. P. Hartmann, and L. D. Rudolph, Dual-mode logic for function-independent fault testing, IEEE Trans. Comput., 29, No. 11, 1025–1029, 1980.

[14] V. Geetha, N. Devarajan, and P. N. Neelakantan, Network structure for testability improvement in exclusive-OR sum of products Reed–Muller canonical circuits, Int. J. Eng. Res. Gen. Sci., 3, No. 3, 368–378, 2015.

[15] J. P. Hayes, On modifying logic networks to improve their diagnosability, IEEE Trans. Comput., 23, No. 1, 56–62, 1974.

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

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

[18] P. N. Neelakantan and A. Ebenezer Jeyakumar, Single stuck-at fault diagnosing circuit of Reed–Muller canonical exclusive-or sum of product Boolean expressions, J. Comput. Sci., 2, No. 7, 595–599, 2006.

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

[20] H. Rahaman, D. K. Das, and B. B. Bhattacharya, Testable design of AND-EXOR logic networks with universal test sets, Comput. Electr. Eng., 35, No. 5, 644–658, 2009.

[21] S. M. Reddy, Easily testable realization for logic functions, IEEE Trans. Comput., 21, No. 1, 124–141, 1972.

[22] K. K. Saluja and S. M. Reddy, On minimally testable logic networks, IEEE Trans. Comput., 23, No. 5, 552–554, 1974.

[23] K. K. Saluja and S. M. Reddy, Fault detecting test sets for Reed–Muller canonic networks, IEEE Trans. Comput., 24, No. 10, 995–998, 1975.

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