×

Complete fault detection tests of length 2 for logic networks under stuck-at faults of gates. (Russian, English) Zbl 1424.94101

Diskretn. Anal. Issled. Oper. 25, No. 2, 62-81 (2018); translation in J. Appl. Ind. Math. 12, No. 2, 302-312 (2018).
Summary: 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.

MSC:

94C12 Fault detection; testing in circuits and networks
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yu. V. Borodina, “Synthesis of Easily-Tested Circuits in the Case of Single-Type Constant Malfunctions at the Element Outputs,” VestnikMoskov.Univ. Ser. 15, No. 1, 40-44 (2008) [Moscow Univ. Comput. Math. Cybernet. 32 (1), 42-46 (2008)]. · Zbl 1146.93327
[2] Yu. V. Borodina, “Circuits Admitting Single-Fault Tests of Length 1 under Constant Faults at Outputs of Elements,” VestnikMoskov. Univ. Ser. 1, No. 5, 49-52 (2008) [Moscow Univ. Math. Bull. 63 (5), 202-204 (2008)]. · Zbl 1304.94140
[3] Yu. V. Borodina, “Lower Estimate of the Length of the Complete Test in the Basis {<Emphasis Type=”Italic“>x | <Emphasis Type=”Italic“>y},” Vestnik Moskov. Univ. Ser. 1, No. 4, 49-51 (2015) [Moscow Univ.Math. Bull. 70 (4), 185-186 (2015)]. · Zbl 1357.94109
[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 (3), 127-133 (2010) [Discrete Math. Appl. 20 (4), 441-449 (2010)]. · Zbl 1201.94149 · doi:10.4213/dm1112
[5] S. S. Kolyada, Upper Bounds on the Length of Fault Detection Tests for Logic Networks, Candidate’s Dissertation in Mathematics and Physics (MGU, Moscow, 2013).
[6] K. A. Popkov, “Lower Bounds for Lengths of Complete Diagnostic Tests for Networks and Inputs of Networks,” Prikl. Diskretn.Mat. No. 4, 65-73 (2016). · Zbl 1492.94229
[7] K. A. Popkov, “On Single Diagnostic Tests for Logic Networks in the Zhegalkin Basis,” Izv. Vyssh. Uchebn. Zaved. Povolzh. Reg. Fiz.-Mat. Nauki, No. 3, 3-18 (2016).
[8] K. A. Popkov, “Single Fault Detection Tests for Logic Networks in the Basis ‘Conjunction-Negation’,” Preprint No. 30 (Inst. Prikl. Mat. Keldysh., Moscow, 2017).
[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 (3), 80-103 (2017) [J. Appl. Indust. Math. 11 (3), 431-443 (2017)]. · Zbl 1399.93061
[10] N. P. Red’kin, “On Complete Checking Tests for Networks of Logic Gates,” Vestnik Moskov. Univ. Ser. 1, No. 1, 72-74 (1986). · Zbl 0597.94024
[11] N. P. Red’kin, “On Networks Admitting Short Tests,” VestnikMoskov. Univ. Ser. 1, No. 2, 17-21 (1988).
[12] Red’kin, N. P., On Complete Fault Detection Tests for Logic Networks, 198-222 (1989), Moscow · Zbl 0712.94027
[13] N. P. Red’kin, Reliability and Diagnosis of Networks (Izd. Moskov. Gos. Univ., Moscow, 1992) [in Russian]. · Zbl 1358.94118
[14] N. P. Red’kin, “On Single-Fault Diagnostic Tests for One-Type Constant Faults at Outputs of Gates,” VestnikMoskov.Univ. Ser. 1, No. 5, 43-46 (1992). · Zbl 0768.94025
[15] D. S. Romanov, “On the Synthesis of Circuits Admitting Complete Fault Detection Test Sets of Constant Length under Arbitrary Constant Faults at theOutputs of the Gates,” Diskretn.Mat. 25 (2), 104-120 (2013) [DiscreteMath. Appl. 23 (3-4), 343-362 (2013)]. · Zbl 1329.94108 · doi:10.4213/dm1239
[16] D. S. Romanov, “Method of Synthesis of Easily Testable Circuits Admitting Single Fault Detection Tests of Constant Length,” Diskretn.Mat. 26 (2), 100-130 (2014) [DiscreteMath. Appl. 24 (4), 227-251 (2014)]. · Zbl 1339.94106 · doi:10.4213/dm1283
[17] D. S. Romanov and E. Yu. Romanova, “A Method of Synthesizing Irredundant Networks 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).
[18] A. B. Ugol’nikov, The Post Classes (Izd. TsPI Mekh.-Mat. Fak. Moskov. Gos. Univ., Moscow, 2008) [in Russian].
[19] I. A. Chegis and S. V. Yablonskii, “LogicalMethods for Control of Electric Circuits,” Trudy MIAN SSSR 51, 270-360 (1958). · Zbl 0092.25306
[20] Yablonskii, S. V., Reliability andMonitoring of Control Systems, 7-12 (1986), Moscow
[21] Yablonskii, S. V., Certain Questions of Reliability and Monitoring of Control Systems, 5-25 (1988), Moscow · Zbl 0695.90049
[22] S. DasGupta, C. R. P. Hartmann, and L. D. Rudolph, “Dual-Mode Logic for Function-Independent Fault Testing,” IEEE Trans. Comput. 29 (11), 1025-1029 (1980). · Zbl 0447.94048 · doi:10.1109/TC.1980.1675500
[23] V. Geetha, N. Devarajan, and P. N. Neelakantan, “Network Structure for Testability Improvement in Exclusive-OR Sum of Products Reed-Muller Canonical Circuits,” Intern. J. Eng. Res. Gen. Sci. 3 (3), 368-378 (2015).
[24] J. P. Hayes, “On Modifying Logic Networks to Improve Their Diagnosability,” IEEE Trans. Comput. 23 (1), 56-62 (1974). · doi:10.1109/T-C.1974.223777
[25] T. Hirayama, G. Koda, Y. Nishitani, and K. Shimizu, “Easily TestableRealization Based on OR-AND-EXOR Expansion with Single-Rail Inputs,” IEICE Trans. Inf. Syst. E-82D (9), 1278-1286 (1999).
[26] A. K. Jameil, “A New Single Stuck Fault Detection Algorithm for Digital Circiuts,” Intern. J. Eng. Res. Gen. Sci. 3 (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 (7), 595-599 (2006). · doi:10.3844/jcssp.2006.595.599
[28] N. P. Rahagude, Integrated Enhancement of Testability and Diagnosability for Digital 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. <Emphasis Type=”Bold”>35 (5), 644-658 (2009). · Zbl 1187.68048 · doi:10.1016/j.compeleceng.2009.01.006
[30] S. M. Reddy, “Easily Testable Realization for Logic Functions,” IEEE Trans. Comput. 21 (1), 124-141 (1972).
[31] K. K. Saluja and S. M. Reddy, “On Minimally Testable Logic Networks,” IEEE Trans. Comput. 23 (5), 552-554 (1974). · Zbl 0279.94032 · doi:10.1109/T-C.1974.223981
[32] K. K. Saluja and S. M. Reddy, “Fault Detecting Test Sets for Reed-MullerCanonic Networks,” IEEE Trans. Comput. 24 (10), 995-998 (1975). · doi:10.1109/T-C.1975.224108
[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),” Intern. J. Emerg. Trends Electr. Electron. 1 (3), 93-96 (2013).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.