On single detecting test sets for circuits of switching type

Background. Testing of discrete models of switching-type circuits is an important theoretical problem with applications to testing and verification of VLSI. The article considers a class of so-called generalized iterative switching circuits (GISC). This class consists of classical switching circuits (SC), however, it allows the usage of superpositions. The aim of this work is to demonstrate that for an arbitrary nonconstant Boolean function it is possible to construct a circuit realizing or modeling this function (in the latter case the circuit realizes a function after substitution constants instead of some input variables), and allowing a small single detecting test set. Materials and methods. The authors used circuit design methods based on the Zhegalkin polinomials. Results. It has been established that for an arbitrary nonconstant Boolean function $f$ depending on $n$ variables there exist testable GISCs realizing $f$ and admitting a) the single fault detecting test set (under homogeneous faults - closures or breakings) of power $O(1)$, b) the single fault detecting test set of power $O(n)$. Moreover, it has proved that for an arbitrary nonconstant Boolean function f depending on n variables there exist testable GISCs and SCs modeling f and admitting the single fault detecting test set of power $O(1)$.