Test generation and embedding for built-in self-test

Built-in self-test (BIST) is a design methodology in which parts of a circuit are dedicated or modified to enable the circuit to test itself. One major challenge for BIST is the design of efficient test pattern generators (TPGs), which generate test sequences that achieve high fault coverage in practical test time, with minimal hardware overhead and performance degradation. In this dissertation, an integrated framework, that employs a new design technique called input reduction, to design efficient BIST TPGs for stuck-at faults, transition delay faults, and path delay faults is developed. The proposed technique analyzes the circuit function and identifies inputs that can be combined into test signals in the test mode without sacrificing fault coverage. Test signals derived are used to obtain BIST TPG designs, which guarantee the detection of all detectable faults in practical test length, and to derive compact test sets, which require much less disk space and test application time in external testing using automatic test equipment. A simple relaxed version of the proposed technique can be used to order the scan chains, so that for each transition/path delay fault at least one two-pattern test can be applied.;For two-pattern testing, the TPG stages connected to the circuit inputs (called the taps) must be carefully selected to ensure that maximal transition coverage can be achieved. Necessary and sufficient conditions and a TPG design procedure based on these conditions for commonly used TPGs to ensure complete/maximal transition coverage have been derived. New concepts pertaining to two-pattern pseudo-exhaustive testing have also been identified and exploited to develop a new TPG design procedure based on interleaved cyclic codes. A new notion of test cones is presented to further reduce the TPG size.;The proposed design framework includes a new ATPG formulation for path delay faults based on Boolean satisfiability. Conditions to detect a target path delay fault are represented by a Boolean formula. Compared to existing techniques, the proposed technique shows tremendous time saving on formula extraction, which also leads to low test generation time.