Hierarchical testing using precomputed tests for modules.

Abstract

This thesis presents a new theory and method for generating tests for digital integrated circuits (ICs). Unlike most previous test generation techniques, which use logic-gate models of ICs, our method uses hierarchical models containing large primitive modules such as ALUs and multipliers connected by multi-bit buses. Many modern ICs are composed of complex, previously designed modules that can only be tested by reusing tests that were computed when the modules were designed. Our method propagates stimulus signals to the inputs of each module, and propagates module responses to the IC's primary outputs. We describe and evaluate a program we designed named PathPlan, one of the first test generators to use circuit and signal hierarchy and precomputed tests. PathPlan propagates symbolic references to precomputed tests along circuit paths. It is much faster than conventional test generators, and some of its features have already been applied commercially. However PathPlan and other hierarchical test generators described in the literature cannot generate tests for ICs whose bus structure is irregular, that is, when some buses are truncated. We present a general theory of signal propagation that enables the development of hierarchical test generation programs for complex circuits with truncated buses. A special representation of a module's input-output behavior called a propagation function is defined to quantify the module's signal transmission properties. A propagation algebra is developed and used to combine propagation functions for modules into propagation functions for multi-module circuits. Several theorems governing the transparency of signal transmission in circuits are proved using this algebra. The algebra also forms the basis for an efficient, hierarchical error propagation method for test generation, and a novel design-for-testability strategy. Finally, we describe a successor program to PathPlan called PathPlan2. This new test generator propagates module test stimulus signals as symbolic expressions, and implements the hierarchical error signal propagation method based on our theory to transmit module responses. It handles circuits with irregular bus structures and is more powerful and general than PathPlan, nevertheless, its performance is at least as good.