Minimally Testable Reed-Muller Canonical Forms

Arbitrary switching function realizations based upon Reed- Muller canonical (RMC) expansions have been shown to possess many of the desirable properties of easily testable networks. While realizations based upon each of the 2n possible RMC expansions of a given switching function can be tested for permanent stuck-at-0 and stuck-at-1 faults with a small set of input vectors, certain expansions lead to an even smaller test set because of the resulting network topology. In particular, the selection of an RMC expansion that has a minimal number of literals appearing in an even number of product terms will give rise to switching function realizations requiring still fewer tests. This correspondence presents a solution to the problem of selecting the RMC expansion of a given switching function possessing the smallest test set.