A method for pseudo-exhaustive test pattern generation

In order for pseudo-exhaustive test pattern generation to be practical (time requirement less than 2^ω, ω⩽20), two conditions must be satisfied: 1). The function of every element in the circuit must be controllable from no more than ω inputs, and 2). The overall time to exercise all elements in the circuit must not exceed 2^ω. We address both these requirements by inserting a small number of bypass storage cells in the circuit under test and constructing appropriate Linear Feedback Shift Registers (LFSRs) to serve as built-in test pattern generators. Our method is applicable to both the gate-level and the module-level and achieves low hardware overhead by using a new graph model for the representation of the circuit and a metric quantity that couples requirements 1 and 2 above