Geodesic
On the exact value of the length of the minimal single diagnostic test for a particular class of circuits
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 80-103.

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

Under consideration is the problem of synthesis of irredundant logic circuits in the basis $\{\mathbin{\},\vee,\neg\}$ 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. 
@article{DA_2017_24_3_a4,
     author = {K. A. Popkov},
     title = {On the exact value of the length of the minimal single diagnostic test for a particular class of circuits},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {80--103},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_3_a4/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - On the exact value of the length of the minimal single diagnostic test for a particular class of circuits
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 80
EP  - 103
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_3_a4/
LA  - ru
ID  - DA_2017_24_3_a4
ER  - 
%0 Journal Article
%A K. A. Popkov
%T On the exact value of the length of the minimal single diagnostic test for a particular class of circuits
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 80-103
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_3_a4/
%G ru
%F DA_2017_24_3_a4
K. A. Popkov. On the exact value of the length of the minimal single diagnostic test for a particular class of circuits. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 80-103. http://geodesic.mathdoc.fr/item/DA_2017_24_3_a4/

[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, 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] S. S. Kolyada, Upper bounds on the length of fault detection tests for logic circuits, Cand. Sci. Dissertation, Mosk. Gos. Univ., M., 2013 (Russian)

[5] N. P. Red'kin, “On complete fault detection tests for logic circuits”, Vestn. Mosk. Univ., Ser. 1, 1986, no. 1, 72–74 (Russian)

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

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

[8] N. P. Red'kin, Reliability and Diagnosis of Circuits, Izd. MGU, M., 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, 1992, no. 5, 43–46 (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] 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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