Geodesic
Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits
Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 65-73

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

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. 
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/
@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

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