Hierarchical modeling and test generation for digital circuits.

This dissertation investigates a hierarchical approach to test generation for digital circuits, based on new high-level circuit and bus fault models which substantially generalize the classical gate-level circuit model and the single stuck-line (SSL) fault model. The high-level circuits consist of register-level components linked by n-bit buses. Signals on buses are represented by vectors, allowing many faults to be tested in parallel. A new high-level test generation algorithm called VPODEM has been designed and implemented, which can generate tests for large circuits more rapidly than conventional algorithms. For certain types of circuits, tests generated using VPODEM for bus faults in a high-level model detect all SSL faults on corresponding lines in the gate-level model. Moreover, VPODEM reduces to st and ard PODEM if gate-level circuit and fault models are used. Thus, our approach allows test generation for general circuits in a truly hierarchical fashion, with both high- and low-level fault types, yielding 100 percent SSL fault coverage with fewer test patterns and less test generation effort than conventional one-level approaches. Experimental results presented for representative circuits show a 50 percent reduction in the test set size using our approach, compared to generating tests using PODEM alone. Design for testability is then addressed with a view to making useful circuits containing some irregularities more amenable to test generation using our hierarchical approach. First, ad hoc design modifications that greatly enhance testability, are considered for array-like and tree-like circuits, which include such useful circuits as carry-lookahead generators, counters, and decoders. In decoder trees, such modifications reduce the complexity of test generation from $O(2\\sp{n})$ to $O(n)$. A systematic design modification technique is then developed for a class of circuits called "generalized" tree circuits, which provide fast implementations of common arithmetic functions. It is shown that the test set size for generalized trees can be reduced from $O(n)$ to O(log$\\sb2 n$). The proposed technique is applied to a 16-bit ALU design, resulting in a speedup of approximately 10 in the test generation process, with less than 20 percent area overhead and almost no performance degradation.PhDComputer scienceElectrical engineeringUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/161901/1/8821548.pd