MuTaTe: an efficient design for testability technique for multiplexor based circuits

ABSTRACT

We present a technique to derive fully testable circuits under the Stuck-At Fault Model (SAFM) and the Path-Delay Fault Model (PDFM). Starting from a function description as a Binary Decision Diagram (BDD) the netlist is generated by a linear time mapping algorithm. Only one additional input and one inverter are needed to achieve 100% testable circuits under SAFM and PDFM. Experiments are given to show the advantages of the the technique in comparison to previously presented methods.

REFERENCES

• 1: S. B. Akers. Binary decision diagrams. IEEE Trans. on Comp. 27:509--516, 1978.
• 2: Pranav Ashar , Srinivas Devadas , Kurt Keutzer, Gate-Delay-Fault Testability Properties of Multiplexor-Based Networks, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.887-896, October 26-30, 1991
• 3: Pranav Ashar , Srinivas Devadas , Kurt Keutzer, Testability properties of multilevel logic networks derived from binary decision diagrams, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.35-54, April 1991
• 4: Pranav Ashar , Srinivas Devadas , Kurt Keutzer, Path-delay-fault testability properties of multiplexor-based networks, Integration, the VLSI Journal, v.15 n.1, p.1-23, July 1993 [doi>10.1016/0167-9260(93)90002-T]
• 5: Bernd Becker, Synthesis for Testability: Binary Decision Diagrams, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.501-512, February 13-15, 1992
• 6: Bernd Becker, Testing with decision diagrams, Integration, the VLSI Journal, v.26 n.1-2, p.5-20, Dec. 1998 [doi>10.1016/S0167-9260(98)00018-2]
• 7: M. A. Breuer and A. D. Friedman. Diagnosis & reliable design of digital systems Computer Science Press, 1976.
• 8: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 9: Randal E. Bryant, Binary decision diagrams and beyond: enabling technologies for formal verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.236-243, November 05-09, 1995, San Jose, California, United States
• 10: R. Drechsler. MuTaTe: An efficient design for testability technique for multiplexor based circuits. In GI/ITG/GMM-Workshop "Testmethods and Reliability of Circuits and Systems", 2003.
• 11: Wolfgang Günther , Rolf Drechsler, ACTion: combining logic synthesis and technology mapping for MUX-based FPGAs, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.14, p.1321-1334, Dec. 2000 [doi>10.1016/S1383-7621(00)00027-8]
• 12: C. Y. Lee. Representation of switching circuits by binary decision diagrams. Bell System Technical Jour. 38:985--999, 1959.
• 13: L. Macchiarulo , L. Benini , E. Macii, On-the-fly layout generation for PTL macrocells, Proceedings of the conference on Design, automation and test in Europe, p.546-551, March 2001, Munich, Germany
• 14: Arindam Mukherjee , Ranganathan Sudhakar , Malgorzata Marek-Sadowska , Stephen I. Long, Wave steering in YADDs: a novel non-iterative synthesis and layout technique, Proceedings of the 36th ACM/IEEE conference on Design automation, p.466-471, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309981]
• 15: A. K. Pramanick and S. M. Reddy. On the design of path delay fault testable combinational circuits. In Int'l Symp. on Fault-Tolerant Comp. pages 374--381, 1990.
• 16: E. Sentovich, K. Singh, L. Lavagno, Ch. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuit synthesis. Technical report, University of Berkeley, 1992.
• 17: G. L. Smith. Model for delay faults based upon paths. In Int'l Test Conf. pages 342--349, 1985.
• 18: F. Somenzi. CUDD: CU Decision Diagram Package Release 2.3.0 University of Colorado at Boulder, 1998.
• 19: S. Yang. Logic synthesis and optimization benchmarks user guide. Technical Report 1/95, Microelectronic Center of North Carolina, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.0 General

General Terms:
Algorithms, Design

Keywords:
BDDs, decision diagrams, design for testability, logic synthesis, multiplexor based circuits