On universal diagnostic tests for a class of faults of combinational schemes. (Russian) Zbl 0555.94019

Switching memoryless circuits (combinational schemes) are considered. Let us denote the set of all n-dimensional binary vectors by \(E_ n\) and let k be a natural number. Definition 1. The transformation \(h: E_ n\to E_ n\) is called k-operator, if a) k numbers \(i_ 1,i_ 2,...,i_ k\) from the set \(\{\) 1,2,...,n\(\}\) and b) k Boolean functions of n variables \(g_ 1,g_ 2,...,g_ k\) may be found such that for any \(a=(a_ 1,a_ 2,...,a_ k)\) and \(b=(b_ 1,b_ 2,...,b_ n)\) it follows from the equality \(h(a_ 1,...,a_ n)=(b_ 1,b_ 2,...,b_ n)\) that \(b_ j=g_ j(a_{i_ 1},...,a_{i_ k})\) if \(j\in (i_ 1,...,i_ k)\) and \(b_ j=a_ j\) for \(j\in \{1,...,n\}\setminus \{i_ 1,...,i_ k\}\). - Let \(F^ k\) be the set of all k-operators and \(f=f(x_ 1,...,x_ n)\) some Boolean function. Definition 2. The set \(T\subset E_ n\) is called diagnostic test for f with respect to \(F^ k\) if for any \(h_ i\in F^ k\) and \(h_ j\in F^ k\) from the validity of the inequality \(f(h_ i(\tilde x))\not\equiv f(h_ j(\tilde x))\) on \(E_ n\) it follows that \(f(h_ j(\tilde x))\not\equiv f(h_ i(\tilde x))\) on T (the symbol \(\not\equiv\) means, that the functions linked by it are not equal on the given set).
The following theorem is proved: Let f be a Boolean function of n variables, and \(T\subset E\) be a set of power \(C(k)]\log_ 2n[\), C(k) being a constant which depends only on k. Then ”almost all” pairs \(<f,T>\) possess the following property: T is a diagnostic test for f with respect to \(F^ k\). ”Almost all” should be understood as follows: the ratio of those \(<f,T>\), which do not possess the above property, tends to zero with increasing n.
Reviewer: V.Ostianu


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: EuDML