Volume 24, No 3, 2017, P. 80-103

UDC 519.718.7
K. A. Popkov
On the exact value of the length of the minimal single diagnostic test for a particular class of circuits

Abstract:
Under consideration is the problem of synthesis of irredundant logic circuits in the basis {&, ∨, ¬} which implement Boolean functions of $n$ variables and allow some short single diagnostic tests regarding uniform constant faults at outputs of gates. For each Boolean function permitting implementation by an irredundant circuit, the minimal possible length value of such a test is found. In particular, we prove that this value is at most 2.
Illustr. 3, bibliogr. 27.

Keywords: logic circuit, fault, single diagnostic test.

DOI: 10.17377/daio.2017.24.546

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

Received 8 June 2016
Revised 27 February 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 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] S. S. Kolyada, Upper bounds on the length of fault detection tests for logic circuits, Cand. Sci. Dissertation, Mosk. Gos. Univ., Moscow, 2013 [Russian].

[5] N. P. Red’kin, On complete fault detection tests for logic circuits, Vestn. Mosk. Univ., Ser. 1, No. 1, 72–74, 1986 [Russian].

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

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

[8] N. P. Red’kin, Nadezhnost’ i diagnostika skhem (Reliability and Diagnosis of Circuits), Izd. MGU, Moscow, 1992 [Russian].

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

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

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

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

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

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

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

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

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

[19] T. Hirayama, G. Koda, Y. Nishitani, and K. Shimizu, Easily testable realization based on single-rail-input OR-AND-EXOR expressions, IEICE Trans. Inf. Syst., E82-D, No. 9, 1278–1286, 1999.

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

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

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

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

[24] S. M. Reddy, Easily testable realizations for logic functions, IEEE Trans. Comput., 21, No. 11, 1183–1188, 1972.

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

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

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