Redundancy removal and test generation for circuits with non-Boolean primitives

Production VLSI circuits typically consist of primitives like tri-state buffers, bidirectional buffers and bus configurations that assume non-Boolean values like the high-impedance state. The present work describes a systematic methodology for extending test generation algorithms to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure, (2) function of non-Boolean primitives is separated into Boolean and non-Boolean components, and energy functions are derived only for the Boolean component, and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. Further, in this paper, we report the first known method of identifying and removing redundancies in production circuits using formulations based on energy minimization, satisfiability or BDD-based methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. Redundancy removal results on several production VLSI circuits, ISCAS 85 and full-scan versions of the ISCAS 89 benchmark circuits are reported