| This dissertation proposes a new methodology for exhaustive self-testing of VLSI circuits. The proposed approach, based on partitioning a large VLSI circuit into smaller, exhaustively testable subcircuits, aims to achieve very high fault coverage, while maintaining a tolerable hardware overhead and testing time. There are four major contributions in this work: (1) Circuit partitioning. A graph theoretic model of VLSI circuits is proposed. Based on this model, a circuit partitioning algorithm is devised, to partition the circuit into a set of (pseudo) exhaustively testable subcircuits with restricted hardware overhead. (2) Efficient pseudo-exhaustive test pattern generation. A new algorithm, based on the subcircuit modification technique is proposed, with the objective of generating pseudo-exhaustive test patterns of limited length (2{dollar}sp{lcub}20{rcub}{dollar}) using linear feedback shift registers (LFSRs), for each of the subcircuits. This task is embedded in the circuit partitioning process itself, leading to an efficient and well-coordinated solution. (3) Digital signature reliability enhancement and test architecture design. Digital signature generators to evaluate the test results are designed for each subcircuit leading to (a) enhanced reliability of the signature, which results in a high fault coverage, and (b) reduced hardware overhead. In addition, a novel test architecture, incorporating both the test pattern generators and digital signature generators, which allows concurrent self-testing of as many subcircuits as possible, while keeping the hardware overhead tolerable, is proposed. (4) Parallel test scheduling. Finally, we propose a test scheduling algorithm based on a resource-conflict analysis of the subcircuits and an overlapping test scheduling scheme. While exploiting the full potential of the physical test architecture proposed, this algorithm reduces the overall self-testing time by scheduling as many subcircuits as possible to test themselves concurrently. The well orchestrated design of the test architecture and the test scheduling algorithm, lead to a considerable reduction of testing times for exhaustive testing of large VLSI circuits, as demonstrated by the simulation experiments conducted. |
