Geodesic
Estimations on lengths of tests of functional elements under a~large number of permissible faults
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 52-70.

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

The problems of check of operability and state diagnosis of $N$ logic gates which realize a given Boolean function $f(x_1,\dots,x_n)$ in their perfect states are studied by means of composition of one-output logic circuits of them and observation of values produced by these circuits on any value sets of input variables. Random constant faults on outputs of gates are permitted; at the same time, it is assumed that not more than $k$ gates are faulted, where $k$ is a given natural number that does not rank over $N$. It is needed to minimize a number of circuits required for check of operability and determination of states of all gates. A lower bound on a number of these circuits is obtained when $k$ is close to $N$. As a corollary from this bound it is derived that, under some condition for $N$ and belonging of $k$ to some segment, the number of circuits mentioned cannot be less than $ck$, where $c>1$ is a constant which does not depend on choice of $k$ from this segment. Bibliogr. 15.
Keywords: logic gate, fault, logic circuit, check test
Mots-clés : diagnostic test. 
@article{DA_2015_22_5_a2,
     author = {K. A. Popkov},
     title = {Estimations on lengths of tests of functional elements under a~large number of permissible faults},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {52--70},
     publisher = {mathdoc},
     volume = {22},
     number = {5},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_5_a2/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - Estimations on lengths of tests of functional elements under a~large number of permissible faults
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 52
EP  - 70
VL  - 22
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_5_a2/
LA  - ru
ID  - DA_2015_22_5_a2
ER  - 
%0 Journal Article
%A K. A. Popkov
%T Estimations on lengths of tests of functional elements under a~large number of permissible faults
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 52-70
%V 22
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_5_a2/
%G ru
%F DA_2015_22_5_a2
K. A. Popkov. Estimations on lengths of tests of functional elements under a~large number of permissible faults. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 52-70. http://geodesic.mathdoc.fr/item/DA_2015_22_5_a2/

[1] E. F. Beckenbach, R. Bellman, An Introduction to Inequalities, Random House, New York, 1961 | MR | MR | Zbl

[2] O. B. Lupanov, Asymptotic Bounds on Complexity of Control Systems, Izd. MGU, Moscow, 1984

[3] K. A. Popkov, “Bounds on lengths of check and diagnostic tests for logic gates”, Diskretn. Anal. Issled. Oper., 21, no. 6, 73–89 | Zbl

[4] K. A. Popkov, “Fault detection and diagnostic tests for AND, OR, and NOT gates”, Mosc. Univ. Math. Bull., 69:6 (2014), 267–271 | DOI | MR | Zbl

[5] K. A. Popkov, “Fault detection and diagnostic tests for logic gates”, Discrete Math. Appl., 24:4 (2014), 213–225 | DOI | DOI | MR

[6] K. A. Popkov, “On single tests for logic gates”, Diskretn. Mat., 27:2 (2015), 73–93 | DOI

[7] N. P. Red'kin, “On complete checking tests for circuits of functional elements”, Vestn. Mosk. Univ. Ser. 1, 1986, no. 1, 72–74 | MR | Zbl

[8] N. P. Red'kin, “On complete checking tests for circuits of functional elements”, Mathematical Problems of Cybernetics, 2, ed. S. V. Yablonskii, Nauka, Moscow, 1989, 198–222 | MR | Zbl

[9] N. P. Red'kin, Reliability and Diagnosis of Circuits, Izd. MGU, Moscow, 1992

[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

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

[13] S. V. Yablonskii, “Reliability and monitoring of control systems”, Proc. All-Union Seminar on Discrete Mathematics and Its Applications, Izd. MGU, Moscow, 1986, 7–12 | MR

[14] S. V. Yablonskii, “Certain questions of reliability and monitoring of control systems”, Mathematical Problems of Cybernetics, 1, ed. S. V. Yablonskii, Nauka, Moscow, 1988, 5–25 | MR

[15] Reddy S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., 21:1 (1972), 124–141 | MR