Comparison of LFSR and CA for BISTIntroductionBuilt-In Self TestLinear Feedback Shift Register (LFSR)Cellular Automata (CA)ComparisonSummary and ConclusionReferences4/26/05 Dhingra: ELEC7250 1Comparison of LFSR and CA for BISTSachin DhingraELEC 7250: VLSI TestingDhingra: ELEC7250 24/26/05Introduction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 (CA)A collection of nodes logically related to their neighbors using XOR gatesDhingra: ELEC7250 34/26/05Built-In Self Test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) Test Pattern Generator Circuit Under TestTest Controller Output Response AnalyzerInput IsolationCircuitrySystem InputsSystem OutputsNormal OperationTest ModeDhingra: ELEC7250 44/26/05Linear Feedback Shift Register (LFSR)Two TypesExternal FeedbackInternal FeedbackCharacteristic PolynomialAll zero state is invalidMax. Sequence Length = 2n – 1Primitive and Non-primitiveReciprocal of primitive polynomial is also primitiveP*(x) = xnP(1/x)Compact DesignLess than one gate per nodeParallel Pattern generationSignature AnalysisSignature Analysis Register (SAR)Multiple Input Signature Register (MISR)P (x) = x0 + x1 + x3 + x4Dhingra: ELEC7250 54/26/05Cellular Automata (CA)One-Dimensional Linear CALinear Hybrid Cellular Automata (LHCA) Linear Cellular Automata Register (LCAR)“Rules” define the logical relationship of a node with its neighbors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Null Boundary Condition – No Feedback Faster ⇒Cyclic Boundary Condition – Feedback Slower⇒Highly Random VectorsRule 150 Rule 90Null boundary conditionRule 90Rule 90Dhingra: ELEC7250 64/26/05ComparisonCharacteristic LFSR CA Area OverheadLeastLess than one Gate/nodeHigher than LFSROne Gate/nodeMax. Length SequenceEasy to implementWell defined P(x)Harder to implementCombination of rules not well definedPerformanceLower – External FeedbackXOR gates in FeedbackHigher – Internal Feedback Max. one gate/pathHighNo gates in feedbackParallel Pattern RandomnessLowShifting of DataHighLogical relation with neighborsStuck-at-fault detectionHigh HighStuck-open and Delay fault Detection LowLess number of transitionsHighHigher number of transitions due to higher randomnessCAD friendlinessNoNodes cannot be cascadedYesNodes can be easily cascadedSignature AliasingHigher ProbabilityShifting of DataLower ProbabilityDhingra: ELEC7250 74/26/05Summary 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 stuck-open 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 neededDhingra: ELEC7250 84/26/05References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 Designer’s 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 self-test,” 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,