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

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.