CPE/EE 428, CPE 528 Testing Combinational Logic (4)DefinitionsMore DefinitionsJustify AlgorithmAn example of justificationTest Generation: Propagate AlgorithmTesting Digital CircuitsDetectionFault DominanceEquivalence and Dominance SummaryAside: Fault LocationOverall processTest GenerationPrimary inputs and outputsPropagate, JustifyImply all you can…Look behind yourself too…Slide 18Slide 19Slide 20Will this always work?Test Generation: Basic AlgorithmAutomatic Test-Pattern Generation (ATPG)Reconvergent FanoutTest Generation — exampleTest generation — example, cont’dBacktrackingMaintaining the decision treeObservations on approachMore terminologyD-FrontierJ-FrontierSlide 33Implication RevisitedBackward ImplicationForward ImplicationWhere are we now?Implication Process RevisitedAll Pieces in PlaceD-AlgorithmTest Generation: The D AlgorithmA circuit and fault to testTracing through an exampleSlide 44Slide 45Slide 46Slide 47Slide 48What about the J-frontier?Slide 50Slide 51Another exampleSlide 53Summary: D algorithmSlide 55Summary: D AlgorithmCPE/EE 428, CPE 528 Testing Combinational Logic (4)Department of Electrical and Computer Engineering University of Alabama in Huntsville01/14/19 VLSI Design II: VHDL 2Definitions•Test generation algorithms work in terms of:–Primary inputs — (PI) a controllable input to a circuit. E.g., a pin on an IC, or an output of an FF in a scan system–Primary outputs — (PO) an observable output of the circuit. E.g., a pin on an IC, or a D input to an FF in a scan system•Justify, justification — the process of selecting PIs to force a certain line to have a specific value•Propagate, propagation — the process of selecting appropriate PIs that allow a discrepancy “D” to be pushed to a PO•Test generation algorithms are all about–finding the appropriate PIs to control to activate a fault –finding the appropriate PIs to control to propagate the fault to one of the POs.01/14/19 VLSI Design II: VHDL 3More Definitions•Forward implication–Def: Knowing one or more gate inputs, imply the output value.–Assume all gate inputs are the same value — either all c or all c’–Then the output is output = value  i•We can refine this if we know the controlling value•i.e. only one of the inputs needs to have c to know output•Backward implication–Def: Knowing the output and possibly some inputs, imply one or more of the inputs–Assume all gate inputs are the same — either all c or c’–Then the inputs are: inputs = output  i•We can refine this if we know the controlling value•If the input needed to produce the output is c, then only one input needs to have it.01/14/19 VLSI Design II: VHDL 4Justify Algorithm•Justify (l , v) — Recursive algorithm to justify line l to value vl = vif l is a primary input return — you’re done on this pathset c and i to controlling/inversion values of gate driving l inval = v  iif (inval == c) select one input j of gate l Justify (j, inval)else for every input j of gate l Justify (j, inval)l 1x0011l01/14/19 VLSI Design II: VHDL 5An example of justificationl = vif l is a primary input return — you’re done on this pathset c and i to controlling/inversion values of gate driving l inval = v  iif (inval == c) select one input j of gate l Justify (j, inval)else for every input j of gate l Justify (j, inval)justify a to 1aPOB01/14/19 VLSI Design II: VHDL 6Test Generation: Propagate Algorithm•Prop (l , err) — Propagate value err from line l l = errif line l is a primary output return — you’re homek = fanout gate of line l c,i = controlling/inversion value of gate kfor every input j of k other than l Justify (j, c’)Propagate (k, err  i)l kJustify enabling values onto other inputsPropagatefurther01/14/19 VLSI Design II: VHDL 7Testing Digital Circuits•What you know–Fault models — what can go wrong and how we model it•physical and logical–Basic idea of detection — activate fault and propagate to output•What you don’t know–how to figure out, systematically, whether the whole thing works–how to reduce the number of faults to consider when generating tests•Today–Review equivalence and fault collapsing–Begin test generation algorithms01/14/19 VLSI Design II: VHDL 8•Basic approach seen so far–Select a line and a fault — line l s-a-v–Activate the fault•Drive line l to v’ — selecting the inputs needed to set an internal line to a known value is known as line justification•Activation creates a discrepancy “D”–Propagate the fault•Propagate the discrepancy D along a sensitized path to any primary output1/0Detections-a-00/10x1Notation: good value/bad valuediscrepancy01/14/19 VLSI Design II: VHDL 9Fault Dominance•Equivalence vs. Dominance–Dominance is a special case of fault equivalence–Fault equivalence, ifZ f (x) = Z g (x) for all xthen the faults are functionally equivalent.–If this is true for a subset of x, then there is a dominance relation•Dominance–Let Tg be the set of all tests that detect a fault g. –A fault f dominates the fault g iff f and g are functionally equivalent under Tg. Z f (t) = Z g (t) for all t in Tg–Tg is a subset of Tf01/14/19 VLSI Design II: VHDL 10Equivalence and Dominance Summary•What are the equivalence classes?s-a-0s-a-1s-a-0s-a-1s-a-0s-a-1EquivalenceA0, B0, Z1 DominanceZ0 dominates A1, B111, 01, 1001/14/19 VLSI Design II: VHDL 11Aside: Fault Location•Detection got us down to three tests–We’re left with three tests for this gate if we’re interested in fault detection.–If we’re interested in fault location, we need more•To isolate y s-a-1–Need to apply both 10 and 01–10, alone, detects the equivalent faults y s-a-1 and z s-a-0–01, alone, detects the equivalent faults x s-a-1 and z s-a-0–Together, they can isolate the three faults (assuming only one fault active).TgTf100100xyzsa1sa1sa001/14/19 VLSI Design II: VHDL 12Overall processdefine fault modelselect target faultgenerate test for targetfault simulatediscard detected faultsno more faults: doneset of faults for circuit01/14/19 VLSI Design II: VHDL 13Test Generation•Toward an algorithmic means to generate test vectors•What do we want in a test vector?–fault activation and propagation–if the discrepancy D wiggles (i.e. from good to bad), then so does the output–how do we determine if a function changes with respect to a variable •Use Automatic Test Generation