Cellular automata as a built in self test structure

ABSTRACT

This paper presents an efficient BIST solution for VLSI circuit testing based on GF(2p) CA (Cellular automata on an extended Galois Field). The novel architecture of GF(2p)) CA permits the BIST structure to be highly customized to the circuit under test (CUT). A methodology has been proposed to optimize the design of GF(2p) CA structure to maximize the fault coverage in a given CUT. In addition, an innovative scheme based on logic folding is presented to reduce the BIST overhead and make it more effective for large circuits.

REFERENCES

• 1: Paul H. Bardell , William H. McAnney , Jacob Savir, Built-in test for VLSI: pseudorandom techniques, Wiley-Interscience, New York, NY, 1987
• 2: P. D. Hortensius et al., "Cellular automata based pseudorandom number generators for built in self test," IEEE Trans. on CAD, vol. 8, pp. 842-859, August 1989.
• 3: M. G. Karpovsky and V. K. Yarmolik, "Transparent memory bist," in Proc. of the Memory Design and Test, pp. 106- 111, 1994.
• 4: D. K. Pradhan and M. Chatterjee, "GLFSR-A New Test Pattern Generator for Built-in-Self-Test," IEEE Trans. on CAD, vol. 18, no. 2, pp. 319-328, 1999.
• 5: Janusz Rajski , Nagesh Tamarapalli , Jerzy Tyszer, Automated synthesis of large phase shifters for built-in self-test, Proceedings of the 1998 IEEE International Test Conference, p.1047-1056, October 18-22, 1998
• 6: Biplab K. Sikdar , Kolin Paul , Gosta Pada Biswas , P. Pal Chaudhuri , Vamsi Boppana , Cliff Yang , Sobhan Mukherjee, Theory and Application of GF(2p) Cellular Automata as On-chip Test Pattern Generator, Proceedings of the 13th International Conference on VLSI Design, p.556, January 04-07, 2000
• 7: Kolin Paul , Dipanwita Roy Chowdhury, Application of GF(2p) CA in Burst Error Correcting Codes, Proceedings of the 13th International Conference on VLSI Design, p.562, January 04-07, 2000
• 8: Kolin Paul , Ranadeep Ghosal , Biplab Sikdar , Santashil Pal Chaudhuri , D. Roy Choudhury, GF(2p) CA Based Vector Quantization for Fast Encoding of Still Images, Proceedings of the 13th International Conference on VLSI Design, p.140, January 04-07, 2000
• 9: P. P. Chaudhuri, D. R. Chowdhury, S. Nandi, and S. Chatterjee, Additive Cellular Automata - Theory and Applications, vol. 1. IEEE Computer Society Press, California, USA, ISBN 0-8186-7717-1, 1997.
• 10: H. K. Lee , D. S. Ha, HOPE: an efficient parallel fault simulator for synchronous sequential circuits, Proceedings of the 29th ACM/IEEE conference on Design automation, p.336-340, June 08-12, 1992, Anaheim, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  C. Computer Systems Organization

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Performance, Theory