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

MSC:

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