Test Pattern Generation using Boolean Proof Engines (eBook)

Preface 5
Acknowledgments 5
Introduction 12
Preliminaries 20
Circuits 20
Fault Models 21
Stuck-at Faults 21
Delay Faults 24
Simple ATPG Framework 27
Classical ATPG Algorithms 31
Stuck-at Faults 31
Delay Faults 34
Benchmarking 37
Boolean Satisfiability 40
SAT Solver 40
Advances in SAT 41
Boolean Constraint Propagation 42
Conflict Analysis 43
Variable Selection Strategies 46
Correctness and Unsatisfiable Cores 46
Optimization Techniques 47
Circuit-to-CNF Conversion 49
Circuit-Oriented SAT 52
SAT-Based ATPG 54
Basic Problem Transformation 55
Structural Information 57
Experimental Results 60
Summary 62
Learning Techniques 64
Introductory Example 65
Concepts for Reusing Learned Information 66
Basic Idea 66
Tracking Conflict Clauses 68
Heuristics for ATPG 70
Notation 70
Incremental SAT-Based ATPG 71
Enhanced Circuit-Based Learning 74
Experimental Results 77
Summary 80
Multiple-Valued Logic 82
Four-Valued Logic 82
Industrial Circuits 83
Boolean Encoding 84
Encoding Efficiency 86
Concrete Encoding 88
Multi-input Gates 90
Modeling of Multi-input Gates 90
Bounded Multi-input Gates 93
Clause Generation 94
Experimental Results 95
Four-Valued Logic 95
Multi-input Gates 96
Summary 97
Improved Circuit-to-CNF Conversion 99
Hybrid Logic 100
Incremental Instance Generation 104
Run Time Analysis 104
Incremental Approach 109
Experimental Results 114
Hybrid Logic 115
Incremental Instance Generation 117
Summary 120
Branching Strategies 122
Standard Heuristics of SAT Solvers 122
Decision Strategies 123
Experimental Results 124
Summary 126
Integration into Industrial Flow 127
Industrial Environment 128
Integration of SAT-Based ATPG 131
Test Pattern Compactness 133
Observability at Outputs 133
Applying Local Don't Cares 135
Experimental Results 137
Integration 137
Test Pattern Compactness 140
Summary 143
Delay Faults 144
Transition Delay 145
Path Delay 148
Non-robust Tests 148
Robust Test Generation 150
Industrial Application 152
Structural Classification 156
Encoding Efficiency for Path Delay Faults 158
Compactness of Boolean Representation 160
Efficiency of Compact Encodings 162
Encoding Selection 164
Incremental Approach 165
Experimental Results 168
Transition Delay Faults 168
Encoding Efficiency for Path Delay Faults 170
Robust and Non-robust Tests 173
Incremental Approach 175
Summary 177
Summary and Outlook 179
Bibliography 179
Index 182