|
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,\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, diagnostic test.
Received: 13.02.2015 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
Linking options:
https://www.mathnet.ru/eng/da828 https://www.mathnet.ru/eng/da/v22/i5/p52
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 54 | References: | 48 | First page: | 12 |
|