11Testing in EnhancedFault ModelsSrinivas DevadasMITKurt KeutzerUC Berkeley2Grades for Midterm• 135 – 147 A+• 95 – 134 A• 90 – 95 A-• 80 – 89 B• 70 – 79 C• 60 – 69 D• <59 F23Manufacture Verification (Test)RTLSynthesisHDLnetlistlogicoptimizationnetlistLibrary/modulegeneratorsphysicaldesignlayoutmanualdesignIs the manufacturedcircuitconsistentwith the implemented design?Did theybuildwhat Iwanted?absq01dclkabsq01dclk4Defect-related Yield Lossfatal defect types (two types of short circuits, one type of open)35Reduce to combinational problemFlip-flopsCombinationalLogicinputsoutputsmake flip-flops observibleusing scan-design6Common fault Models-a-1abcSingle stuck-at faultx47Defect-related Yield Lossfatal defect types (two types of short circuits, one type of open)How is this likely to affect circuit?8Fault Models - 2Path delay fault0acbGate delay faultabc10Multiple stuck-at faultss-a-0s-a-1acbxx59Redundancy and TestabilityIf a fault in a circuit is redundant, i.e., there is no test for itReplace line on which fault resides with a constant 1 (SA1) or 0 (SA0).cabs-a-0fa b c f1 1 - 11 - 1 1- 1 0 1 a b c f1 - 1 1- 1 0 1facbx10Prime + Irredundant = TestableA prime and irredundant cover for a single-output function represents a two-level circuit that is fully testable for all single stuck-at faults.fcabs-a-1cab0 11 11 - 1 1non-primeirredundantcover-11 11 - 1 1 prime &irredundantcoverxf611CorrespondencePrimality ⇔ s-a-1 faults on AND gate inputsIrredundancy ⇔ s-a-0 faults on OR gate inputsffs-a-0caabbcacbcprime butredundantcoverprime &irredundantcoverx12Multiple-Output FunctionsGiven the two-output function below000 01010 01100 01101 01110 11111 11They form a cover1 1 - 1 11 - - 0 1- - 0 0 11 1 0 1 11 - - 0 1- - 0 0 1Prime and irredundant coverIs it fully testable for single stuck-at faults?713Multiple-Output Functions - 2Don’t really want just a prime covera b c f g1 1 - 1 11 - - 0 1-- 0 0 11 1 - 1 01 - 1 0 1- - 0 0 1baacfgs-a-0redundantconnectionfgbaacx14Testable Multiple-Output Covers– Modify Quine-McCluskey method– Generate primes as usual– During branch & bound covering checkselected prime for unnecessary 1’s inoutput part (I.e. check for unnecessary cubes in outputs)⇒ If there are unnecessary 1’s, replace primein current solution with maximally (output)reduced cube.– Any solution will be fully stuck-at-fault testable8153KMultifaultsTheorem: The set of tests detecting all single faults in a prime and irredundant single-output two-level circuit detect all multifaults.Multiple Stuck-At Faultsf = ab + bc + acs-a-1 on a in abf *= b + bc + acAdditional s-a-0 on bc givesf *= b + acfcabbac16The Boolean n-Cube, Bn917The Boolean n-Cube and a Coverabcac’ + bc’18Primality Test, Redundancy TestabcF= ac’ + bc’abcPrimality Test(Prime literal?)a, b, prime should yieldF(0,0,0) = 0Redundancy Test(Redundant Cube?) Cube irredundantshould yieldF(1,0,0) = 11019Multiple Stuck-At Faults - 1Three cases based on the effect of the multifault:1. Cubes uniformly removed from f: xxfcabbacs-a-0 test for any removed cube will detect multifault20Multiple Stuck-At Faults - 2Three cases based on the effect of the multifault:2.Cubes uniformly raised/expanded in f:xxxfcabbacs-a-1 test for some removed literal in cube (primality test) will detect multifault1121Multiple Stuck-At Faults - 3Three cases based on the effect of the multifault:3. Some cubes removed, some raised: xxxfcabbac• s-a-1 test for some removed literal inunremoved cube will detect multifault.• Why must there be at least one such literal in one such cube?22Theorem does not generalize to multi-outputsNeed to implement each single-output “cone” as prime and irredundant circuit for full multifaulttestabilityMultiple-Output Circuitsbaf4f1f2f3s-a-1’ss-a-0’sfullysingle-faulttestable8-fault isredundantxxxxxxxx1223Defect-related Yield Lossfatal defect types (two types of short circuits, one type of open)How is this likely to affect circuit?24Enhanced Model: Path Delay FaultsNeed to propagate transition down the path that is to be testedf10path from b to fis testedabcpaths from a, bto f are testedf0abc1325Robust/Hazard Free TestingHave to avoid races and hazards ⇒ robust testingpaths from a, brace to set fto 0output glitchesbefore transitionfrom c propagateto fSample?f0abcfabc26Path Delay Fault TestabilityNot all paths in a prime and irredundant two-level circuit are robustly testable010glitchacb1427DefinitionsA path Π in circuit C is associated with a literal l in cube qA relatively essential vertex of a cube q is a minterm that is not in any other cube of C but is in ql m!ab is a relatively essential vertex of q aboveCmabqdl28Testability ConditionsTheorem: (Devadas & Keutzer) Let C be a single-output circuit. Let Π be a path in C that starts with l in cube q.There exists a hazard-free robust delay fault test for Π if and only if:1) There exists a vertex V2that is a relativelyessential vertex of q and2) Vertex V1distance-1 from V2in l is in the OFF-set of C.0<V1, V2>Sufficiency is trivialCmabql101529Suppose <W1, V2> is a delay-fault test for Π.Suppose V2is not a relatively essential vertex of q.So V2has to be a relatively essential vertex of q.Clearly W1has to be in the OFF-set of C.But do W1and V2have to differ only in l ?Necessityraced(V2) = 1Cmabqdl30Necessity - 2If W1and V2are not distance-1 in l we can construct a V1and V2distance-1 in l that are a delay fault test for Π.Need some literal mi∈ disuch that mi= 0 for bothW1and V2. Else glitch would invalidate test.Just arbitrarily set remaining literals in W1other than l to values in V2.qd1d2m1m2lnot allowed1631Example - IRelatively essential vertex of cube a!b 10- is 100But 110 (distance-1 from 100 in b) is in the ON-setTherefore, there is no robust path delay fault test for this pathacba b c 1 0 --0 1-1 032Example - II<111, 010> is a robust path delay fault testCan construct distance-1 test by settingliterals in V1other than c to values in V2Obtain <011, 010>, which is also a robust testacba b c 1 0 --0 1-1 00101733Testability of Multilevel CircuitsWere able to obtain necessary and sufficient conditions for robust path-delay-fault and multi-fault testability based on primality and irredundancy for two-level circuitsWhat about multilevel circuits?111abdc0034ENF is a two-level representation of a multilevel circuitEquivalent Normal FormEM =