Diskretnyi Analiz i Issledovanie Operatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2015, Volume 22, Issue 5, Pages 52–70 (Mi da828)

Estimations on lengths of tests of functional elements under a large number of permissible faults

K. A. Popkov

Lomonosov Moscow State University, 1 Leninskie Gory, 119991 Moscow, Russia

Abstract: The problems of check of operability and state diagnosis of $N$ logic gates which realize a given Boolean function $f(x_1,…,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, diagnostic test.

DOI: https://doi.org/10.17377/daio.2015.22.476

Full text: PDF file (294 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2015, 9:4, 559–569

Bibliographic databases:

UDC: 519.718.7
Revised: 22.07.2015

Citation: K. A. Popkov, “Estimations on lengths of tests of functional elements under a large number of permissible faults”, Diskretn. Anal. Issled. Oper., 22:5 (2015), 52–70; J. Appl. Industr. Math., 9:4 (2015), 559–569

Citation in format AMSBIB
\Bibitem{Pop15} \by K.~A.~Popkov \paper Estimations on lengths of tests of functional elements under a~large number of permissible faults \jour Diskretn. Anal. Issled. Oper. \yr 2015 \vol 22 \issue 5 \pages 52--70 \mathnet{http://mi.mathnet.ru/da828} \crossref{https://doi.org/10.17377/daio.2015.22.476} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3467239} \elib{https://elibrary.ru/item.asp?id=24323029} \transl \jour J. Appl. Industr. Math. \yr 2015 \vol 9 \issue 4 \pages 559--569 \crossref{https://doi.org/10.1134/S1990478915040122}