Testability of convergent tree circuits

The testing properties of a class of regular circuits called convergent trees are investigated. Convergent trees include such practical circuits as comparators, multiplexers, and carry-lookahead adders. The conditions for the testability of these tree circuits are derived for a functional fault model. The notion of L-testability is introduced, where the number of tests for a p-level tree is directly proportional to p, rather than exponential in p. Convergent trees that are C-testable (testable with a fixed number of tests, regardless of the tree's size) are also characterized. Two design techniques are also introduced that modify arbitrary tree modules in order to achieve L- and C-testability. Finally, we apply these techniques to the design of a large carry-lookahead adder.