Test pattern generation and test application time reduction algorithms for VLSI circuits

As the complexity of VLSI circuits is increasing at the rate predicted by Moore's law and the switching frequencies are approaching a gigahertz, testing cost is becoming an important factor in the overall IC manufacturing cost. Testing cost is incurred by test pattern generation and test application processes. In this dissertation, we address both of these factors contributing to the testing cost. We propose new test pattern generation and test application time reduction algorithms for reducing the IC testing cost.; We propose new efficient and robust structure-based techniques for speeding up the deterministic test pattern generation for combinational circuits. These techniques improve the average-case performance of the PODEM algorithm by reducing number of backtracks with a low computational cost. We then extend these techniques to sequential circuits and propose new structure-based techniques for speeding up the deterministic test pattern generation for sequential circuits. These techniques improve the average-case performance of the iterative logic array based deterministic sequential circuit test generation algorithms.; We propose two new algorithms for generating compact test sets for combinational circuits under the single stuck-at fault model and a new heuristic for estimating the minimum single stuck-at fault test set size. We then extend these algorithms to generate compact test sets for pure combinational and full scan circuits under fault models that require two-pattern test sets, in particular for transition and CMOS stuck-open fault models.; We propose a new design-for-testability technique for reducing the test application time of full scan embedded cores without using any additional test access pins other than the ones used for the full scan technique. We also propose a heuristic technique for computing an optimal scan chain configuration for these cores to obtain a minimal test application time.; Finally, we propose a new synthesis technique for reducing the test application time of counter-based exhaustive built-in-self-test test pattern generators. This technique reduces the test application time by reducing the size of the binary counter used in the counter-based test pattern generators.