Design and testing of regular circuits.

Many integrated circuits (ICs) are regular in that they contain multiple copies of the same subcircuit or module which are interconnected in a uniform manner. Regular circuits are widely used in ICs because they are easy to design and manufacture. They are also easy to test because they need relatively few test patterns to detect faults. This thesis investigates the testing properties of regular circuits. A major goal is to obtain better ways to test ICs by exploiting their existing regularity, or by making them more regular. The structure of regular circuits typically takes the form of one- and two-dimensional arrays, convergent and divergent trees, as well as compositions of these structures. Of these, a tree tends to be the most common underlying structure, being found in such practical circuits as decoders, comparators, adders, register files, and ALUs. Hence, the testability of trees, which include one-dimensional arrays as a special case, is the focus of this work. Formally, a circuit is called a tree if there is at most one path from each primary input to each primary output. The modules of a tree form natural groups called levels, depending on their distance from the primary outputs. The definition of a tree is extended here to include control lines that are shared by all modules in the same level; hence, trees can also be controlled or uncontrolled. The testability of trees is analyzed under a functional fault model that allows the function of any module to change to any other function. Necessary and sufficient conditions are derived for an uncontrolled tree to be completely testable. Sufficient conditions are obtained for the more difficult case of controlled trees. The extent to which common tree circuits, such as multiplexers, decoders, and parity trees, satisfy these testability conditions is also investigated. Necessary and sufficient conditions are derived that allow trees to be tested with very few test patterns. The notion of L-testability is introduced and characterized; a tree is L-testable if all modules in the same level can be simultaneously tested. An L-testable tree has a test set whose size is proportional to its number of levels. Trees can be viewed as a set of overlapping one-dimensional arrays of various lengths and types; this allows the known testing properties of arrays to be extended to trees. A tree is C-testable if it can be tested with a constant number of tests independent of the tree's size. Necessary and sufficient conditions are derived for a tree to be C-testable, as well as, conditions for C-testability using the minimum number of tests. In practice, tree circuits often fail to satisfy all the conditions for L- or C-testability. For such cases, we present low-cost design-for-testability (DFT) methods to make a tree either L- or C-testable by adding extra inputs to its modules. These methods are applied to simple tree circuits such as multiplexers and decoders. We also use them to make large tree-like circuits, including a carry-lookahead adder and an arithmetic-logic unit, easily testable. Finally, we describe the complete design of a small microprocessor that exploits regularity and the proposed DFT methods to achieve a very high degree of self-testing.PhDComputer Science and EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104432/1/9527586.pdfDescription of 9527586.pdf : Restricted to UM users only