Boolean techniques in testing of digital circuits [Elektronische Ressource] / von Junhao Shi

Haake-Vm

Informations

• Publié par: universitat_bremen
• Publié le: 01 janvier 2006
• Nombre de lectures: 9
• Langue: English

Extrait

BOOLEAN TECHNIQUES IN
TESTING OF DIGITAL CIRCUITS
von
Junhao Shi
Dissertation
zur Erlangung des akademischen Grades eines
Doktors der Ingenieurwissenschaften
- Dr.Ing. -
Vorgelegt im Fachbereich 3 (Mathematik & Informatik)
der Universit¨ at Bremen
im November 2006Datum des Promotionskolloqiums: Feb.15, 2007
Gutachter : Prof.Dr. Rolf Drechsler
Prof.Dr. Jan Peleska
iiTo my wife
iiTable of Contents
Table of Contents iii
List of Tables vi
List of Figures ix
Abstract xi
Acknowledgements xiii
1 Introduction 1
1.1 Problem Description . . ......................... 1
1.1.1 ATPG ............................... 2
1.1.2 Synthesis for Testability ..................... 5
1.2 Contributions of this Thesis ....................... 6
2 Preliminaries 11
2.1 Boolean Techniques............................ 11
2.1.1 Boolean Functions ........................ 1
2.1.2 Binary Decision Diagrams .................... 13
2.1.3 SAT Problem ........................... 16
2.2 Digital Circuits .............................. 20
2.2.1 Combinational Logic Circuits .................. 20
2.2.2 BDD Circuits 2
2.2.3 Circuits with Tri-state Elements................. 23
2.3 Fault Models ............................... 26
2.3.1 Stuck At Fault Model ...................... 27
2.3.2 Path Delay Fault Model ..................... 28
2.3.3 Bridging Fault Model....................... 29
iii2.4 ATPG................................... 31
2.4.1 Deterministic Test Generation .................. 32
2.4.2 Fault Simulation ......................... 34
2.4.3 ATPG Systems .......................... 35
3 Testing of BDD Circuits 39
3.1 Introduction ................................ 39
3.2 ATPG in Polynomial Time ....................... 41
3.2.1 BDD Circuits of General Boolean Functions .......... 41
3.2.2 BDD of Symmetric Function .............. 53
3.3 Testability of BDD Circuits 54
3.3.1 BDD Transformation 54
3.3.2 Testability Under the Stuck At Fault Model .......... 57
3.3.3 Ty the Path Delay Fault Model ......... 57
3.3.4 Testability under the Bridging Fault Model........... 60
3.3.5 Partial Simplification ....................... 62
3.3.6 Experimental Results 64
3.4 Optimization of BDD Circuits ...................... 71
3.4.1 Sifting with Different Objective Functions ........... 71
3.4.2 Experimental Results 73
4 SAT based ATPG for Industrial Circuits 79
4.1 Introduction ................................ 80
4.2 Encoding for Tri-state Circuits 81
4.2.1 Four-Valued Logic ........................ 81
4.2.2 Boolean Encoding......................... 82
4.2.3 Transformation to SAT Instance................. 83
4.2.4 Experimental Results for ATPG 86
4.3 SAT-based ATPG . . . .......................... 89
4.3.1 D-Algorithm............................ 89
4.3.2 Encoding ............................. 93
4.3.3 Variable Selection......................... 94
4.3.4 Experimental Results....................... 97
4.4 Combination with Classical TPG .................... 105
4.4.1 Classical Test Generation 106
4.4.2 Combination ........................... 108
4.4.3 Experimental Results 10
5 Conclusion 117
ivBibliography 120
Index 130
vviList of Tables
2.1 4-valued AND gate ............................ 25
2.2 Truth table of 3-state BUS ........................ 26
2.3 Truth table of 3-state BUS0 ....................... 26
2.4 Truth table of 3-state BUS1 27
3.1 Detect function for SAF . 42
3.2 Classical approaches ........................... 6
3.3 Path delay fault coverage of BDD circuits ............... 6
3.4 Path delay fault coverage of the BDD circuit for symmetric function . 67
3.5 Comparison with earlier works...................... 68
3.6 Test pattern generation for benchmark circuits............. 70
3.7 BDD statistics............................... 74
3.8 Results for the circuits .......................... 74
3.9 Path delay fault coverage of optimized BDD circuits.......... 76
3.10 Circuits optimized by sifting for RPT .................. 7
4.1 Boolean encodings ............................ 82
4.2 AND gate over{0, 1,Z,U} ........................ 84
4.3 Number of clauses for each encoding 85
4.4 Number of gates for each type ...................... 86
4.5 Memory and run time for different encodings.............. 87
4.6 Representation of a gate in CNF..................... 91
4.7 Encoding of the 4-valued domain .................... 92
vii4.8 Clauses for the 4-valued AND gate ................... 92
4.9 Clauses for the 4-valued DRIV...................... 93
4.10 CNF size for a 2-input AND gate .................... 93
4.11 Results for the Boolean circuit model .................. 100
4.12 Results for the 4-valued circuit model 101
4.13 PASSAT with different variable selection strategies .......... 102
4.14 PASSAT for industrial benchmarks ................... 103
4.15 Run-Time of different SAT solvers.................... 104
4.16 Time to classify faults .......................... 104
4.17 Runtime of FAN and SAT ........................ 12
4.18 Pre-identification results(1) ....................... 13
4.19 results(2) 114
4.20 the number of test patterns of FAN and SAT.............. 15
viiiList of Figures
1.1 Design Flow ................................ 2
2.1 BDD for the function f = x · x + x .................. 141 2 3
2.2 Type 1 reduction rule .......................... 16
2.3 Type 2 rule 16
2.4 Multiplexer cell MUX of AND, OR, and INVERTER ......... 21
2.5 PTL multiplexer as wired OR of two NMOS transistors ........ 21
2.6 Mapping a BDD to a circuit ....................... 2
2.7 BDD circuit over MUXLIB........................ 23
2.8 BDD circuit over STD .......................... 24
2.9 Element and truth table of DRIV bus-driver .............. 25
2.10 Element and truth table of NDRIV bus-driver ............. 25
2.11 Stuck at fault ............................... 28
2.12 Bridging fault 30
2.13 Main inputs and outputs of the ATPG process ............. 31
2.14 Example circuit with a SA1 fault and a test for it ........... 3
2.15 General structure of the state-of-the-art of ATPG systems ...... 35
3.1 Calculation of paths ........................... 47
3.2 Example for the calculations of paths .................. 47
3.3 Test pattern generation for BF...................... 49
3.4 Propagation, if level(g) > level(h).................... 51
3.5 Feedback loop ............................... 51
ix