Efficient circuit specific pseudoexhaustive testing with cellular automata

Pseudoexhaustive testing of a combinational circuit involves applying all possible input patterns to all its individual output cones. Since it does not assume any fault model, the testing ensures detection of all static detectable faults in the circuit that do not require two-pattern tests. Earlier works on pseudoexhaustive testing usually generate test sets that are several orders of magnitude larger than the minimum size test set required for a specific circuit, and are mostly based on LFSRs. This paper presents a novel strategy for constructing circuit-specific pseudoexhaustive test pattern generators, based on cellular automata, that result in generating minimal pseudoexhaustive test sets for combinational circuits. Experimentation with ISCAS85 benchmarks show that as compared to the LFSRs, the cellular automata based approach often results in simpler circuitry with lesser number of shift stages and reduced test length. Moreover, the analytical technique developed here is generic in nature and thus can also be applied for constructing LFSR based pseudoexhaustive test pattern generators.