Geodesic
Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits
Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 65-73 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $D^P_1(n)$ ($D^P_0(n)$, $D^P_{0,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, $D^O_{B;\,1}(n)$ ($D^O_{B;\,0}(n)$, $D^O_{B;\,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 $B_2=\{x|y\}$, $B^*_2=\{x\uparrow y\}$, $B_3=\{x\&y,\overline x\}$, $B^*_3=\{x\vee y,\overline x\}$. It is shown that the functions $D^P_1(n)$, $D^P_0(n)$, $D^O_{B_2;\,1}(n)$, $D^O_{B^*_2;\,0}(n)$, $D^O_{B_3;\,0,1}(n)$, $D^O_{B^*_3;\,0,1}(n)$ are not less than $\dfrac{2^{{n}/2}\cdot\sqrt[4]n}{2\sqrt{n+(\log_2 n)/2+2}}$ and $ D^P_{0,1}(n)$ is not less than $2^{{n}/2}$ if $n$ is even, and is not less than $\left\lfloor\dfrac{2\sqrt 2}3\cdot 2^{{n}/2}\right\rfloor$ if $n$ is odd.
Keywords: logic circuit, fault, complete diagnostic test, test for inputs of circuits. 
@article{PDM_2016_4_a4,
     author = {K. A. Popkov},
     title = {Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {65--73},
     year = {2016},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_4_a4/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 65
EP  - 73
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_4_a4/
LA  - ru
ID  - PDM_2016_4_a4
ER  - 
%0 Journal Article
%A K. A. Popkov
%T Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 65-73
%N 4
%U http://geodesic.mathdoc.fr/item/PDM_2016_4_a4/
%G ru
%F PDM_2016_4_a4
K. A. Popkov. Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits. Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 65-73. http://geodesic.mathdoc.fr/item/PDM_2016_4_a4/

[1] Chegis I. A., Yablonskii S. V., “Logical methods of control of work of electric schemes”, Trudy Mat. Inst. Steklov, 51, 1958, 270–360 (in Russian) | Zbl

[2] Yablonskii S. V., “Reliability and verification of control systems”, Materialy Vsesoyuznogo seminara po diskretnoy matematike i ee prilozheniyam, MSU Publ., M., 1986, 7–12 (in Russian) | MR

[3] Yablonskiy S. V., “Some questions of reliability and verification of control systems”, Matematicheskie Voprosy Kibernetiki, 1, Nauka Publ., M., 1988, 5–25 (in Russian) | MR

[4] Red'kin N. P., Schemes Reliability and Diagnostics, MSU Publ., M., 1992 (in Russian)

[5] Noskov V. N., “Diagnostic tests for logical device inputs”, Diskretnyy Analiz, 26, IM Publ., Novosibirsk, 1974, 72–83 (in Russian) | MR

[6] Madatyan Kh. A., “Full test for repetition-free contact schemes”, Problemy Kibernetiki, 23, Nauka Publ., M., 1970, 103–118 (in Russian)

[7] Kovatsenko S. V., “Synthesis of easily testable circuits in the Zhegalkin basis for inverse faults”, Vestnik MSU, ser. 15, 2000, no. 2, 45–47 (in Russian) | Zbl

[8] Peterson W. W., Weldon E. J., Error-Correcting Codes, MIT Publ., 1972 | MR | MR

[9] Borodina Yu. V., “The lower bound for the full test length in the basis $\{x|y\}$”, Vestnik MSU, ser. 1, 2015, no. 4, 49–51 (in Russian) | MR | Zbl

[10] Ugol'nikov A. B., Post Classes, Tutorial, MSU, TsPI Publ., M., 2008 (in Russian)