Comparison of LFSR and CA for BIST Sachin Dhingra ELEC 7250: VLSI Testing 4/26/05 Dhingra: ELEC7250 1 Introduction Built-In Self Test Circuit capable of testing itself Two major components Test Pattern Generator Output Response Analyzer Implementation of BIST Linear Feedback Shift Register (LFSR) Shift Register with feedback path linearly related to the nodes using XOR gates Cellular Automata 4/26/05 (CA) A collection of nodes logically related to their neighbors using XOR gates Dhingra: ELEC7250 2 Built-In Self Test System Inputs Input Isolation Circuitry Circuit

Under Test Test Pattern Generator Test Normal Mode Operation System Outputs Output Response Analyzer Test Controller TPG generates pseudo random test vectors Input Isolation Circuitry isolates the normal system inputs from the CUT Output Response Analyzer performs polynomial division for test data compaction (signature analysis) 4/26/05 Dhingra: ELEC7250 3 Linear Feedback Shift Register (LFSR) XOR x 0 FF x 1 External Feedback Internal Feedback XOR x

FF 2 FF x 3 Two Types FF x 4 Internal Feedback/Type I LFSR Characteristic Polynomial All zero state is invalid XOR x0 FF x1 Primitive and Non-primitive Reciprocal of primitive polynomial is also primitive XOR x2 FF FF x3 FF P (x) = x + x + x + x 1

3 x4 External Feedback/Type II LFSR 0 4 Output Response from CUT Less than one gate per node Parallel Pattern generation Signature Analysis Signature Analysis Register (SAR) Multiple Input Signature Register (MISR) XOR FF P*(x) = xnP(1/x) Compact Design XOR Max. Sequence Length = 2n 1 FF FF FF Signature Analysis Register 4/26/05 Dhingra: ELEC7250 4 Cellular Automata (CA)

Rule 150 0 Null boundary condition XOR x FF 2 XOR x FF x3 FF x4 Linear Hybrid Cellular Automata (LHCA) Linear Cellular Automata Register (LCAR) Rule 90 xi(t+1) = xi-1(t) xi+1(t) Rule 150 xi(t+1) = xi-1(t) xi(t) xi+1(t) Combination of Rules Characteristic Polynomial of LFSRs Boundary Condition FF 1 Rules define the logical relationship of a node with its neighbors XOR

Rule 90 Rule 90 One-Dimensional Linear CA Rule 90 Null Boundary Condition No Feedback Faster Faster Cyclic Boundary Condition Feedback Faster Slower Highly Random Vectors 4/26/05 Dhingra: ELEC7250 5 Comparison Characteristic LFSR CA Area Overhead Least Less than one Gate/node Higher than LFSR One Gate/node Max. Length Sequence Easy to implement Well defined P(x) Harder to implement Combination of rules not well defined Performance Lower External Feedback XOR gates in Feedback Higher Internal Feedback Max. one gate/path High No gates in feedback Parallel Pattern Randomness

Low Shifting of Data High Logical relation with neighbors Stuck-at-fault detection High High Stuck-open and Delay fault Detection Low Less number of transitions High Higher number of transitions due to higher randomness CAD friendliness No Nodes cannot be cascaded Yes Nodes can be easily cascaded Signature Aliasing Higher Probability Shifting of Data Lower Probability 4/26/05 Dhingra: ELEC7250 6 Summary and Conclusion LFSRs are more popular because of their compact and simple design CAs are more complex to design but provide patterns with higher randomness CAs perform better in detection of faults such as stuckopen or delay faults, which need two-pattern testing In applications where area overhead is a big concern, LFSRs prove to be a better choice

CAs provide a good alternative for LFSRs when high fault coverage is needed 4/26/05 Dhingra: ELEC7250 7 References M.L. Bushnell, V.D. Agrawal, Essentials of Electronics Testing for Digital, Memory & Mixed Signal VLSI Circuits, Kluwer Academic Publishers, Boston MA, 2000 C. Stroud, A Designers Guide to Built-In Self-Test, Kluwer Academic Publishers, Boston MA, 2002 S. Zhang et. al, Why cellular automata are better than LFSRs as built-in self-test generators for sequential-type faults, IEEE International Symposium on Circuits and Systems, Vol. 1, pp 69-72, 1994 P.D. Hortensius et. al, Cellular automata-based pseudorandom number generators for built-in self-test, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 8, pp 842 - 859, 1989 K. Furuya, E.J. McCluskey, Two-Pattern test capabilities of autonomous TPG circuits, Proc. of International Test Conference, pp 704 711, 1991. L.T. Wang, E.J. McCluskey, Circuits for Pseudoexhaustive Test Pattern Generation, Proc. IEEE International Conference on Computer-Aided Design of Integrated Circuits and Systems, Vol. 7, pp. 1068 1080, 1988 P.D. Hortensius et. al, Cellular automata-based signature analysis for built-in selftest, IEEE Transactions on Computers, Vol. 39, pp. 1273 1283, 1990 K. Furuya et. al, Evaluations of various TPG circuits for use in two-pattern testing, Proceedings of the Third Asian Test Symposium, pp. 242 247, 1994 M. Serra, et. al, The Analysis of One Dimensional Linear Cellular Automata and Their Aliasing Properties, IEEE Trans. on CAD, pp. 767-778, 1990 4/26/05 Dhingra: ELEC7250 8