內(nèi)容講稿測(cè)試課1

1、Extra TopicRedundancy Removal Using ATPGRedundancy identificationRedundancy removalIrredundant Hardware and Test PatternsCombinational ATPG can find redundant (unnecessary) hardwareFault Test a sa1, b sa0 A = 1 a sa0, b sa1 A = 0Therefore, these faults are not redundantRedundant Hardware and Simplif

2、icationRedundant Fault q sa1Multiple Fault Maskingf sa0 tested when fault q sa1 not thereMultiple Fault Maskingf sa0 masked when fault q sa1 also presentIntentional Redundant ImplicantionEliminates hazards in circuit outputLecture 4Major Combinational Automatic Test-Pattern Generation AlgorithmsDefi

3、nitionsD-Algorithm (Roth) - 1966PODEM (Goel) - 1981X-Path-CheckBacktracingSummaryD Notation5-value D notation 0 0 in both good & faulty circuit 1 1 in both good & faulty circuit X dont care or not yet specified D 1 in good circuit, 0 in bad circuit D 0 in good circuit, 1 in bad circuitD mean

4、s DiscrepancyWhy? Instead of using two circuits (fault-free & faulty), we want to solve the ATPG problem on one circuit To do so, every signal value must be able to describe fault-free and faulty values simultaneously Hence we introduce D and D185 Valued D AlgebraRed shaded area represents 2 val

5、ue boolean operationsSimilar operations exist for NAND, NOR, etc19（1）D-CubeCube another name of vectorCollapsed truth table entry to characterize logicUse Roths 5-valued algebraCan change all Ds to Ds and Ds to Ds (do both)AND gate:Rows 1 & 3Reverse inputsAnd two cubesInterchange D and DAD1DD1DB

6、1DDDD1dDDDDDDD Intersection () Operations empty D-intersection: 0 0 = 0 X = X 0 = 0 1 1 = 1 X = X 1 = 1 X X = X20（2）Primitive D-Cubes of a Fault (PDF)Specify the minimum input conditions which must be applied to a logic element to produce an error signal at its outputUsed when fault activationExampl

7、e: AND gate output stuck-at faultsS-a-0 fault: 11DS-a-1 fault: 0XD or X0Dsa0sa122Bridging Fault CircuitBridging Fault D-Cubes of FailureCube-setG0G1F0F1a0X1X0X1bX0X101Xa*0X1X011b*X0X1011Cube-setPDFs forBridging faultb01a*1Db*D1a10（3）Singular Cover (SC)Also known as primitive cube (PC)The minimum inp

8、ut assignments for the output of a gate to be 0 or 1Essentially the collapsed truth tableUsed in line justification and implication23Example24（4）Propagation D-Cube (PDC)The minimum input assignments required to propagate a D or D from the gate input(s) to the gate outputUsed in D-Drive25（5）Test Cube

9、 (TC)Fully or partially specified Boolean values for testing a faultIn D algorithm, a test cube containsNot only primary inputs, but also internal nodesNotationTC(n) = test cube at ATPG step n26D-frontierA set of gates whose output value is currently X, but have one or more fault signals (D or D) at

10、 their inputsInitially the D-frontier consists of only one gate (output of the fault site)ExampleBlue gates are D-frontiersWhite gates are NOT28D-DriveThe D-Drive selects an elements in the D-frontier and attempts to propagate the D and/or D from its input(s) to its output (using propagation D-cube)

11、29ImplicationForward implicationPartially specified input values uniquely determines the output valuesBackward implicationKnowing the output values (and some input values) can uniquely determine the un-specified input valuesImplication means NO choiceExamples30Forward ImplicationBackward Implication

12、Unique determination of all gate inputs when the gate output and some of the inputs are givenBacktrackWhen a conflict occurs, backtrack to the last decision point and take another choiceChoice can be: PDF, PDC, SC, D-Drive gate33Implication Stack after Backtrack01000001111EFBBFF1UnexploredPresent As

13、signmentSearched and InfeasibleObjectives and Backtracing of ATPG AlgorithmObjective desired signal value goal for ATPGGuides it away from infeasible/hard solutionsBacktrace Determines which primary input and value to set to achieve objectiveUse testability measuresImplication Procedure1.Model fault

14、 with appropriate primitive D-cube of failure (PDF)2.Select propagation D-cubes to propagate fault effect to a circuit output (D-drive procedure)3.Select singular cover cubes to justify internal circuit signals (Consistency procedure)Put signal assignments in test cubeRegrettably, cubes are selected

15、 very arbitrarily by D-ALGCircuit and Truth Table Inputsa00001111b00110011c01010101OutputF00010000Singular Cover & D-CubesSingular cover Used for justifying linesPropagation D-cubes Conditions under which difference between good/failing machines propagatesA10D1DB10101DDD1DC101DDd10010DDDD0De0111

16、0DDD0DDF001DDDSteps for Fault d sa0Step123A1B11C1dDDe00FDCube typePDF of AND gateProp. D-cube for NORSing. Cover of NANDD-ALG Example #235D-ALG Example #2 (Cont.)36Flowchart of D-ALGBacktrack last decision: PDCF, PDC, D-frontier choiceChoose a PDCF PDCF = TC(0)PDCTC(i) = TC(i+1)Perform inplicationIs

17、 there a D or D at PO?Choose a gate fromD-frontierChoose a PDCLine justificationTest generated!Backtrack*Backtrack*Given a faultconsistentinconsistentnoyessucceedfail38D-Algorithm Top Level1. Number all circuit lines in increasing level order from PIs to POs;2. Select a primitive D-cube of the fault

18、 to be the test cube;Put logic outputs with inputs labeled as D (D) onto the D-frontier;3. D-drive ();4. Consistency ();5. return ();D-Algorithm D-drivewhile (untried fault effects on D-frontier)select next untried D-frontier gate for propagation;while (untried fault effect fanouts exist)select next

19、 untried fault effect fanout;generate next untried propagation D-cube;D-intersect selected cube with test cube;if (intersection fails or is undefined) continue;if (all propagation D-cubes tried & failed) break;if (intersection succeeded)add propagation D-cube to test cube - recreate D-frontier;F

20、ind all forward & backward implications of assignment;save D-frontier, algorithm state, test cube, fanouts, fault;break;else if (intersection fails & D and D in test cube) Backtrack ();else if (intersection fails) break;if (all fault effects unpropagatable) Backtrack ();D-Algorithm - Consist

21、encyg = coordinates of test cube with 1s & 0s;if (g is only PIs) fault testable & stop;for (each unjustified signal in g)Select highest # unjustified signal z in g, not a PI;if (inputs to gate z are both D and D) break;while (untried singular covers of gate z)select next untried singular cov

22、er;if (no more singular covers)If (no more stack choices) fault untestable & stop;else if (untried alternatives in Consistency)pop implication stack - try alternate assignment;elseBacktrack ();D-drive ();If (singular cover D-intersects with z) delete z from g, add inputs to singular cover to g,

23、find all forward and backward implications of new assignment, and break;If (intersection fails) mark singular cover as failed;Backtrackif (PO exists with fault effect) Consistency ();else pop prior implication stack setting to try alternate assignment;if (no untried choices in implication stack)faul

24、t untestable & stop;else return;Example 7.3 Fault s sa1Primitive D-cube of Failure1 1D Dsa1Example 7.3 Step 2 s sa1Propagation D-cube for v1 1D D0 0sa1D D1 1D DExample 7.3 Step 2 s sa1Forward & Backward Implications1 1D Dsa10 0D DD D1 11 10 01 11 1Example 7.3 Step 3 s sa1Propagation D-cube f

25、or Z test found!1 1D Dsa10 0D DD D1 11 10 01 11 11 1D DExample 7.3 Fault u sa1Primitive D-cube of Failure1 1D D0 0sa1Example 7.3 Step 2 u sa1Propagation D-cube for v1 1D D0 0sa1D D0 0Example 7.3 Step 2 u sa1Forward and backward implications1 1D D0 0sa1D D0 00 01 10 01 10 0Inconsistentd = 0 and m = 1

26、 cannot justify r = 1 (equivalence)BacktrackRemove B = 0 assignmentExample 7.3 BacktrackNeed alternate propagation D-cube for v1 1sa1D D0 0Example 7.3 Step 3 u sa1Propagation D-cube for v1 1sa1D D0 01 1D DExample 7.3 Step 4 u sa1Propagation D-cube for ZD D1 1sa1D D0 01 1D D1 11 1Example 7.3 Step 4 u

27、 sa1Propagation D-cube for Z and implicationsD D1 1sa1D D0 01 1D D1 11 10 00 00 01 11 1Summary of D-ALGD-ALG is completeGuarantee to generate a pattern for a testable faultLarge search space is the problemAssignment of values is allowed for internal linesBacktracking could occur at each gateInefficient for large circuitsD-ALG is blind to global circuit detailsLack of the ability to identi