On Realizations of Boolean Functions Requiring a Minimal or Near-Minimal Number of Tests

This paper considers the design of combinational logic circuits which require a minimal or near-minimal number of tests. Bounds on the number of tests required by various network structures are considered. It is shown that for an n-input fanout-free network, the number of single and multiple fault detection test lies between 2 √n and n + 1, while the number of fault locations tests lies between 2 √n and 2n.