Volume 25, No 2, 2018, P. 62-81

UDC 519.718.7
K. A. Popkov
Complete fault detection tests of length 2 for logic networks under stuck-at faults of gates

Abstract:
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.

DOI: 10.17377/daio.2018.25.592

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

Received 6 October 2017

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, Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements, Vestn. Mosk. Univ., Ser. 1, No. 5, 49–52, 2008 [Russian]. Translated in Mosc. Univ. Math. Bull., 63, No. 5, 202–204, 2008.

[3] 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]. Trans?lated in Mosc. Univ. Math. Bull., 70, No. 4, 185–186, 2015.

[4] 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.

[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., No. 4, 65–73, 2016 [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, No. 3, 3–18, 2016 [Russian].

[8] K. A. Popkov, Single fault detection tests for logic networks in the basis “conjunction-negation”, Prepr. Inst. Prikl. Mat. Keldysh., 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, Diskretn. Anal. Issled. Oper., 24, No. 3, 80–103, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 3, 431–443, 2017.

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

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

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

[13] N. P. Red’kin, Nadezhnost’ i diagnostika skhem (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, No. 5, 43–46, 1992 [Russian].

[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, Diskretn. Mat., 25, No. 2, 104–120, 2013 [Russian]. Translated in Discrete Math. Appl., 23, No. 3–4, 343–362, 2013.

[16] D. S. Romanov, Method of synthesis of easily testable circuits admitting single fault detection tests of constant length, Diskretn. Mat., 26, No. 2, 100–130, 2014 [Russian]. Translated in Discrete Math. Appl., 24, No. 4, 227–251, 2014.

[17] D. S. Romanov and 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, No. 2, 87–102, 2016 [Russian].

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

[19] I. A. Chegis and S. V. Yablonskii, Logical methods for control of electric circuits, Tr. MIAN SSSR, 51, 270–360, 1958 [Russian].

[20] S. V. Yablonskii, Reliability and monitoring of control systems, in Materialy Vsesoyuznogo seminara po diskretnoi matematike i eyo prilozheniyam (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].

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

[22] 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.

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

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

[25] 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.

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

[27] 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.

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

[29] 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.

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

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

[32] 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.

[33] 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.