12.1.1CS150 Newton/PisterOutlinem Last time:Ô Deriving the State Diagram & Datapath (Cont.)Ô Mapping the Datapath onto Controlm This lecture:Ô Combinational Testability and Test-patternGenerationÔ Faults in digital circuitsÔ What is a test? : Controllability & ObservabilityÔ Redundancy & testabilityÔ Test coverage & simple PODEM ATPGÔ Sequential Test: What are sequential faults?Ô SCAN Design12.1.2CS150 Newton/PisterOutlinem Background:Ô Role of Don't-Cares in Logic SynthesisÔ Controllability & ObservabilityÔ Optimality, Redundancy & Testabilitym The Sequential Test Problemm Synthesis-Directed Sequential TestÔ Two Approaches to Full TestabilityÔ Effectiveness and Limitations so far12.1.3CS150 Newton/PisterRole of Don't-Cares in Logic SynthesisCombinationalLogicxbfabm f = xb cannot bereduced further inisolation 00 01 11 1001abx 1112.1.4CS150 Newton/PisterRole of Don't-Cares in Logic SynthesisCombinationalLogicabfxbm x ≠ a + b can never happenm Don't-Care Set: D = x' (a + b) + x a' b'm Minimize f with respect to D.00 01 11 1001abxg g gg12.1.5CS150 Newton/PisterRole of Don't-Cares in Logic Synthesisabxbf = b 00 01 11 1001abx g g gg1 112.1.6CS150 Newton/PisterFault Excitation δ stuck-at-01111gggg12.1.7CS150 Newton/PisterFault Models• Input or output pin (not entire net!)stuck at logic 0 or stuck at logic 1.• Open circuit– Can make a combinational circuit sequential!• Short circuit12.1.8CS150 Newton/PisterFault Propagation δ stuck-at-011110gggm The test is a cube, not a minterm.12.1.9CS150 Newton/PisterOptimality & Redundancy inCombinational LogicabδdcfabdcfCircuit with redundant fault: δ stuck-at-0Circuit with δ = 0f = (a.b).(c+d).c' = (a.b.c + a.b.d).c' = a.b.c.c' + a.b.d.c' = a.b.d.c'f = (a.b).c'.d12.1.10CS150 Newton/PisterPath-Oriented DEcision Making[Goel, 1981](1) Assign all Primary Inputs (PI) to the value "don't care" (]).(2) Given an output signal and a desired value for the output,trace a path to the PIs to obtain a PI assignment.(3) Simulate the PI vector to see if it sets up the desired value onthe output. If so, terminate.(4) If the opposite value is set, assign an opposite value to the PIand re-simulate. If desired value is set, terminate.(5) If the output remains unspecified, repeat the path tracing toset another PI, as necessary.m Procedure continues until either:Ô A successful PI assignment has been found (circuits notequivalent).Ô All possible PI assignments have been exhausted.12.1.11CS150 Newton/PisterCover Extractionm Covers can be generated with as many"don't cares" in the present state part aspossible.abwxcd]d=1d=0c=1c=0a=0a=1a=0 a=1 ONabcd] ] 110] 010] ] 0 OFFabcd1] 011] ] 012.1.12CS150 Newton/PisterTestability and Logic Synthesism Important Issue:Generating tests for circuits with redundanciesis very difficult.Ô Must use algorithms which decrease thenumber of redundancies or eliminate themcompletely during synthesis.12.1.13CS150 Newton/PisterTest Generation for Finite-State Machinesm Irredundant combinational logic does not imply100% sequential testabilitym Sequential Faults: Faults may not be excited("controlled") by primary inputs; faults may notbe propagated to primary outputs ("observed").12.1.14CS150 Newton/PisterFinite-State MachinesCombinationalNext-State LogicLatchesCombinationalOutput LogicPrimary Inputs (PIs)Primary Outputs (POs)Moore Machine12.1.15CS150 Newton/PisterFinite-State MachinesCombinationalNext-State LogicLatchesPrimary Inputs (PIs)Primary Outputs (POs)Mealy Machine12.1.16CS150 Newton/PisterExample Finite-State Machine:State Transition DiagramABDCE1/00/10/11/10/00/01/00/11/11/012.1.17CS150 Newton/PisterExample Finite-State Machine:Encoded States1000100000011101/00/10/11/10/00/01/00/11/11/001110111112.1.18CS150 Newton/PisterState AssignmentFSM ENCODE OPTIMIZEm Find a binary encoding of states which minimizesthe eventual area (or delay) of the FSM aftercombinational logic optimization of NSL and OL.m Need to predict and model the optimizationm State assignment has major effect on testability.12.1.19CS150 Newton/PisterExample Finite-State Machine:Next-State Logicinps(3)'ps(1)'ps(2)ps(2)'in'ps(1)ns(1)ns(2)ns(3)out12.1.20CS150 Newton/PisterMealy Machine at Time tn PInNSLL(Sn )PO nm Sn is state of latches at time tn12.1.21CS150 Newton/PisterFinite-State Machine as Iterated Array PI1NSLL(S 1)PO 1L(S 0) PI2NSLL(S2 )PO 2 PInNSLL(S n )PO n• • •δm Fault is present in all copies of NSLm Fault may mask excitation or propagationm More likely, fault may cause next-state N tobe invalid state Nf.12.1.22CS150 Newton/PisterIdeal Iterated ArrayNSL1NSL2NSL n PI1L(S 1)PO 1L(S 0) PI2L(S2 )PO 2 PInL(S n )PO n• • •δm In an ideal situation, the NSL would beoptimized separately for each possible statetransition!m Each NSL block would be made prime andirredundant separately.12.1.23CS150 Newton/PisterSequential Circuits:Controllability & ObservabilityCombinationalNext-State LogicLatchesPIsPOs001 1:1010 1:1010 0:0111 1:1110 0:1A test:12.1.24CS150 Newton/PisterScan Designm Make all flip-flops scan (i.e. direct read and writeaccess)Ô All inputs to the combinational logic can be setand all outputs can be read.Ô The sequential testing problem becomes acombinational testing problem.m "Overkill" in virtually all cases.m Area and time penalty; often a longer testing time.m But scan can be inserted automatically.12.1.25CS150 Newton/PisterSynthesis Procedure for Fully-TestableNon-Scan Finite-State Machine (Devadas, et.al. 1988)LatchesOutput LogicPrimary Inputs (PIs)Primary Outputs (POs)12NNSLm Partition NSL into single-conecircuitsm Single stuck-fault ⇒ correct &incorrect next-state differ byexactly one bit.m Perform state assignment suchthat all states differing in onebit assert different outputs⇒ one-step propagation12.1.26CS150 Newton/PisterSynthesis Procedure for Fully-TestableNon-Scan Finite-State MachinesGiven a state-transition graph (STG) of a FSM, a100%-testable logic-level implementation of themachine is producedm No scannable latches requiredm Uses partitioned logic approach and constrainedstate assignmentm Small penalty12.1.27CS150 Newton/PisterCascaded Finite-State MachinesδPIsPOsm Is it possible to synthesize a cascade of FSM'ssuch that all embedded faults are detectablenon-scan from the external inputs only?m What is the penalty in real cases?12.1.28CS150 Newton/PisterCoupled Finite-State Machinesδe.g. controllere.g. data pathPIs POs12.1.29CS150 Newton/PisterExample
View Full Document
Unlocking...