Parity bit calculation and test signal compaction for BIST applications

Parity bit checking and pseudo-exhaustive testing are two design techniques which have been widely discussed in the BIST literature but have seldom been employed in practice because of the exponential nature of the processes involved. In this paper we describe several procedures designed to avoid these exponential explosions. Specifically we show how the parity of a large combinational function can (often) be quickly calculated. This is accomplished by an examination of the circuit realization itself particularly with regard to the connectivity between the various inputs and outputs. We then show how this same approach can be used to partition circuits so that they can be tested efficiently with a relatively small number of test patterns. Using these methods we were able to calculate the parity bits for more than 80% of ISCAS benchmark circuits' outputs. Interestingly enough, only 15% of these outputs were found to be parity-odd, but for these cases high fault coverage was invariably found to result. Several examples are included.This work was partially supported by the National Science Foundation under grant MIP-8902014.