Testability and test plan generation in hierarchical macro testing

The IC production process contains uncertainties by nature. Therefore, every IC should undergo a structural test before being shipped to customers. The main problem of structural testing of digital VLSI circuits is the conflict between on one hand the enormous amount of transistors (typically in the order of 10^6), and therefore the enormous amount of possible fault causes, on a device and on the other hand the limited accessibility of these transistors via IC pins (typically less than 10^2). Macro test is a successful strategy to overcome the latent intractability of structural testing. The circuit is partitioned into modules, called macros. These modules should be testable, i.e., should have a set of test patterns and a test access protocol (the test plan). Test plan generation is the process of
expanding the test plans described at the terminals of a macro to a test plan described at the chip pinning. Test plan generation can only succeed if the terminals of the macro under consideration are controllable and observable. To avoid complexity problems, we use abstractions of the functionality of other macros to access the macro under consideration. In this document the notions described above are elaborated formally. Algorithms to compute controllability and observability of all terminals in the circuit are given, as well as an algorithm for hierarchy expansion and a backtracking algorithm that performs test plan generation.