Abstract:
Let DP1(n) (DP0(n), DP0,1(n)) be the least length of a complete diagnostic test for the primary inputs of logical circuits implementing Boolean functions in n variables and having constant faults of type 1 (respectively 0, both 0 and 1) on these inputs, DOB;1(n) (DOB;0(n), DOB;0,1(n)) be the least length of a complete diagnostic test for logical circuits consisting of logical gates in a basis B, implementing Boolean functions in n variables, and having constant faults of type 1 (respectively 0, both 0 and 1) on outputs of the logical gates, and B2={x|y}, B∗2={x↑y}, B3={x&y,¯¯¯x}, B∗3={x∨y,¯¯¯x}.
It is shown that the functions DP1(n), DP0(n), DOB2;1(n), DOB∗2;0(n), DOB3;0,1(n), DOB∗3;0,1(n) are not less than 2n/2⋅4√n2√n+(log2n)/2+2 and
DP0,1(n) is not less than 2n/2 if n is even, and is not less than
⌊2√23⋅2n/2⌋ if n is odd.
Keywords:
logic circuit, fault, complete diagnostic test, test for inputs of circuits.
Citation:
K. A. Popkov, “Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits”, Prikl. Diskr. Mat., 2016, no. 4(34), 65–73
\Bibitem{Pop16}
\by K.~A.~Popkov
\paper Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits
\jour Prikl. Diskr. Mat.
\yr 2016
\issue 4(34)
\pages 65--73
\mathnet{http://mi.mathnet.ru/pdm564}
\crossref{https://doi.org/10.17223/20710410/34/5}
Linking options:
https://www.mathnet.ru/eng/pdm564
https://www.mathnet.ru/eng/pdm/y2016/i4/p65
This publication is cited in the following 10 articles:
K. A. Popkov, “Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions”, Math. Notes, 113:1 (2023), 80–92
G. Antyufeev, D. S. Romanov, “On Test Sets Concerning Local Stuck-at Faults of Fixed Multiplicity at the Inputs of Circuits”, Math. Notes, 114:3 (2023), 397–402
K. A. Popkov, “Short complete diagnostic tests for circuits with two additional inputs in some basis”, Discrete Math. Appl., 33:4 (2023), 219–230
K. A. Popkov, “Korotkie polnye diagnosticheskie testy dlya skhem s odnim dopolnitelnym vkhodom v standartnom bazise”, PDM, 2022, no. 56, 104–112
K. A. Popkov, “Short conditional complete diagnostic tests for circuits under one-type constant faults of gates”, Discrete Math. Appl., 33:6 (2023), 381–386
K. A. Popkov, “Short complete diagnostic tests for logic circuits in one infinite basis”, Moscow University Mathematics Bulletin, 77:5 (2022), 250–253
G. V. Antyufeev, D. S. Romanov, “Tests with Stuck-At and Shift Faults on Circuit Inputs”, Comput Math Model, 31:4 (2020), 494
K. A. Popkov, “Complete fault detection tests of length 2 for logic networks under stuck-at faults of gates”, J. Appl. Industr. Math., 12:2 (2018), 302–312
K. A. Popkov, “Short single tests for circuits with arbitrary stuck-at faults at outputs of gates”, Discrete Math. Appl., 29:5 (2019), 321–333
D. S. Romanov, E. Yu. Romanova, “A method of synthesis of irredundant circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 29:1 (2019), 35–48