Uploaded byUsha Mehta
Deterministic Test Pattern Generation ( D-Algorithm of ATPG) (Testing of VLSI Design)
The document discusses deterministic test pattern generation (ATPG) for combinational circuits. It provides an overview of ATPG algorithms and concepts like fault excitation, propagation, and justification. Hard and easy faults are defined based on the difficulty of controlling inputs and observing outputs. Testability measures like controllability and observability are introduced to analyze fault difficulty. Developing one's own ATPG tool is discussed, along with ideas for future extensions.
Deterministic Test Pattern Generation ( D-Algorithm of ATPG) (Testing of VLSI Design)
- 1. Deterministic Test Pattern Generation DrUsha Mehta usha.mehta@ieee.org usha.mehta@nirmauni.ac.in
- 2. Acknowledge • This presentationhas been summarized from various books, papers, websites and presentations on VLSI Design and its various topics all over the world. I couldn’t itemwise mention from where these large pull of hints and work come. However, I’d like to thank all professors and scientists who created such a good work on this emerging field. Without those efforts in this very emerging technology, these notes and slides can’t be finished. 2 DrUshaMehta05-10-2019
- 3. Simple Illustration of ATPG •Consider the fault d/1 in the defective circuit • Need to distinguish the output of the defective circuit from the defect-free circuit • Need: set d=0 in the defect-free circuit • Need: propagate effect of fault to output • Vector: abc=001 (output = 0/1) 3 DrUshaMehta05-10-2019
- 4.
- 5. • Instead ofusing two circuits (fault-free and the faulty) • We will solve the ATPG problem on one single circuit • To do so, every signal value must be able to capture fault-free and faulty values simultaneously • 5-Value Algebra: 0, 1, X, D, D-bar • D: 1/0 fault free/faulty • D-bar: 0/1 5 DrUshaMehta05-10-2019
- 6. Notations…. • For faultto be detected, the corresponding output of the circuit should be different in case of circuit is faulty and faultfree. 6 DrUshaMehta05-10-2019
- 7. Boolean Algebra on5- Valued Logic 7 DrUshaMehta05-10-2019
- 8. Basic ATPG Algorithm PathSensitization Method • Initialize all inputs with X • Activate the fault s-a-v by justifying the line to value v’ • Propagate the fault effect to PO 8 DrUshaMehta05-10-2019
- 9. Fault Excitation • Faultexcitation – the signal value at the fault site must be different from the value of the stuck-at fault (thus fault site must contain a D or a D’) • Propagation: The fault effect must be propagated to a primary output (a D or a D’ must appear at the output) • Some simple observations • There must be at least a D or a D’ on some circuit nets • Ds must form a chain to some output 9 DrUshaMehta05-10-2019
- 10.
- 11.
- 12. Controlling and Inversion Value •Controlling value for AND and NAND is 0 while for OR and NOR, it is 1 • Inversion value for NOT, NOR and NAND is 1 while for ND and OR, it is 0 12 DrUshaMehta05-10-2019
- 13.
- 14.
- 15.
- 16.
- 17.
- 18. Algorithm for CombinationalATPG contd. 18 DrUshaMehta05-10-2019
- 19. Algorithm for CombinationalATPG contd. 19 DrUshaMehta05-10-2019
- 20. Algorithm for CombinationalATPG contd. 20 DrUshaMehta05-10-2019
- 21. While applying deterministictest pattern generation….. • To start the procedure, We need to select one fault from the list • Which fault to consider first • Once we have selected a fault, we need to select the paths • Which path for fault propagation…. • Which path for fault justification… 21 DrUshaMehta05-10-2019
- 22. •Which to choosefirst? •Easy or hard???? •What is your answer? Why? 22 DrUshaMehta05-10-2019
- 23.
- 24. Paradox of Choice… •Many of the times, you need to exercise one or few options from given list and if you succeed with them, you are done. • e.g. Question paper stating: Attempt any five questions. • “Which question to attempt first” • Hard or easy? • EASY • Some times, you need to select all the options and ned to succeed in all. • e.g. The six courses of Sem. II • “Which course to prepare first” • Hard or easy? • HARD 24 DrUshaMehta05-10-2019
- 25. Different Heuristics • Targetto generate tests for easy faults first • More No. of faults will be covered in less time. Hard faults may be neglected at the end…. • Target to generate tests for hard faults first • Any time, a hard fault is detected by a test vector, there is a chance that the same test vector detects lot more faults. 25 DrUshaMehta05-10-2019
- 26. How to judgethe fault? • The fault can be tested easily or with hardship, depends on • The efforts required to set that net with a specific value • The efforts required to set that net with a specific value • i.e. if you want to test s-a-1 on net n, you would try to set n to value ‘0’ 26 DrUshaMehta05-10-2019
- 27. Which fault iseasy/hard? • The fault is easy or hard based on • difficulty involved in setting the corresponding • inputs to specific values (controlling the inputs) • Checking the outputs for correctness (observing the output) 27 DrUshaMehta05-10-2019
- 28. Testability Measures • Analysisof difficulty of testing internal circuit parts –redesign or add special test hardware • Guidance for algorithms computing test patterns – avoid using hard-to-control lines • Estimation of fault coverage • Estimation of test vector length 28 DrUshaMehta05-10-2019
- 29. Which fault iseasy/hard? • The fault is easy or hard based on • difficulty involved in setting the corresponding • inputs to specific values (controlling the inputs) • Checking the outputs for correctness (observing the output) Easy/hard can be determined • Distance from PIs and POs • Testability measures • Probabilities !!!! 29 DrUshaMehta05-10-2019
- 30. Testability Measures • Analysisof difficulty of testing internal circuit parts –redesign or add special test hardware • Guidance for algorithms computing test patterns – avoid using hard-to-control lines • Estimation of fault coverage • Estimation of test vector length 30 DrUshaMehta05-10-2019
- 31. Sandia Controllability andObservability Analysis Program (SCOAP) • Involves Circuit Topological analysis, but no test vectors and no search algorithm • Static analysis • Linear computational complexity • Otherwise, is pointless – might as well use automatic test-pattern generation and calculate: Exact fault coverage and Exact test vectors 31 DrUshaMehta05-10-2019
- 32. • Combinational measures: •CC0 – Difficulty of setting circuit line to logic 0 • CC1 – Difficulty of setting circuit line to logic 1 • CO – Difficulty of observing a circuit line • Sequential measures – analogous: • SC0 • SC1 • SO 32 DrUshaMehta05-10-2019
- 33. • Controllabilities –1 (easiest) to infinity (hardest) • Observabilities – 0 (easiest) to infinity (hardest) • Combinational measures: • Roughly proportional to # circuit lines that must be set to control or observe given line • Sequential measures: • Roughly proportional to # times a flip-flop must be clocked to control or observe given line 33 DrUshaMehta05-10-2019
- 34.
- 35.
- 36. Develop your ownATPG • Algorithms ….. • Run by computing machines…. • What can be inputs to algorithm?…… • And outputs……. • Netlist • Fault list • Test set 36 DrUshaMehta05-10-2019
- 37. Future Scope • Thistool can be further developed with higher fanout branches and fan in for gates capabilities. • It can further accommodate the XOR, XNOR types of gates also. • When there is a contradiction for reconvergent fan out, it chooses the second option based on nearby controllability value. With this if still the problem is not solved, such faults can be referred to advanced ATPGs. • For that link to those tools can be applied. Or fault coverage loss because of such case can be calculated. Based on list of test vectors generated, test compaction can be applied. 37 DrUshaMehta05-10-2019
- 38.