Test-driven transformations in logic design.

Abstract

Computer-aided design tools, which aim at a satisfactory tradeoff of conflicting design objectives, expedite several aspects of modern integrated circuit design. As circuit complexity increases, the process of testing a circuit, which is critical to its correct and continued operation, becomes increasingly difficult. As a circuit is transformed iteratively during design to improve area or delay, its test sets and testability are changed, often in unpredictable ways. Hence, determining sets of input test patterns and the faults that they detect as one circuit is transformed into another is extremely complex, and is normally a separate process from design. Yet, there exist empirical results demonstrating a close relationship among the test sets for different implementations of the same function. Our goal is to develop methods to predict and control changes to test sets and to add a test dimension to the design optimization process that complements methods concerned with area and delay. We propose the concept of test-set preserving (TSP) transformations, which preserve the complete test sets for the initial circuit. Thus any complete test set for the initial circuit completely tests all transformed circuits, and each transformed design is guaranteed to be testable with respect to the faults of interest. We also introduce the concept of test-set altering (TSA) transformations, which add a minimum number of tests to maintain complete test sets for transformed circuits. This enables test-set computation to take place in parallel with circuit transformation and puts testing on an equal footing with area and delay in making complex VLSI design tradeoffs. We also introduce other forms of test-set preservation and alteration that are applicable to initial test sets that are incomplete. In this case, TSP and TSA transformations monotonically reduce the number of undetected faults in transformed designs thereby improving their incomplete test sets incrementally. Finally, we consider fundamental properties of transformation sets, such as completeness and nonredundancy. We develop complete nonredundant sets of transformations for some special circuit classes and derive necessary and sufficient conditions for complete sets of transformations for single- and multiple-output circuit classes.