Fast seed computation for reseeding shift register in test pattern compression

ABSTRACT

Solving a system of linear equations has been widely used to compute seeds for LFSR reseeding to compress test patterns. However, as chip size is growing, solving linear equations requires a large number of computations that is proportional to n³. This paper proposes a new scan chain architecture and algorithm so that the order of computation is proportional to the number of scan cells in a chip. The new architecture is a methodology change that does not require complex Design-For-Testability (DFT) as proposed in the previous techniques. Instead of solving linear equations, the proposed new seed computation algorithm topologically determines seeds for test vectors. The compression ratio might be slightly lower than the other approaches, but the proposed approach can handle larger designs in a reasonable amount of time. Computation analysis shows that, for 1 million scan cell design, if we assume it takes 1 msec for the proposed technique to compute seeds, it would take more than 14 minutes for other techniques that solve linear equations.

REFERENCES

• 1: Khoche, A., and J. Rivoir, "I/O Bandwidth Bottleneck for Test: Is it Real?," Proc. of International Workshop on Test Resource Partitioning, 2000.
• 2: Konemann, B., "LFSR-Coded Test Patterns for Scan Designs," Proc. of European Test Conference, pp. 237--242, 1991.
• 3: C. C. Krishna , Abhijit Jas , Nur A. Touba, Test vector encoding using partial LFSR reseeding, Proceedings of the IEEE International Test Conference 2001, p.885-893, October 30-November 01, 2001
• 4: Sybille Hellebrand , Janusz Rajski , Steffen Tarnick , Srikanth Venkataraman , Bernard Courtois, Built-In Test for Circuits with Scan Based on Reseeding of Multiple-Polynomial Linear Feedback Shift Registers, IEEE Transactions on Computers, v.44 n.2, p.223-233, February 1995 [doi>10.1109/12.364534]
• 5: Nadime Zacharia , Janusz Rajski , Jerzy Tyszer , John A. Waicukauski, Two-Dimensional Test Data Decompressor for Multiple Scan Designs, Proceedings of the IEEE International Test Conference on Test and Design Validity, p.186-194, October 20-25, 1996
• 6: Janusz Rajski , Jerzy Tyszer , Nadime Zacharia, Test Data Decompression for Multiple Scan Designs with Boundary Scan, IEEE Transactions on Computers, v.47 n.11, p.1188-1200, November 1998 [doi>10.1109/12.736428]
• 7: Gilbert Strang, Linear Algebra And Its Applications, Academic Press, Inc., 1980.
• 8: Bardell, P.H., and W.H. McAnney, "Self-Testing of Multichip Logic Modules," Proc. of International Test Conference, pp. 200--204, 1982.
• 9: M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, San Diego, CA, 1980.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.0 General
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Input/output circuits

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Measurement, Theory