Test pattern generation using Boolean proof engines

After producing a chip, the functional correctness of the integrated circuit has to be checked. Otherwise products with malfunctions would be delivered to customers, which is not acceptable for any company. Many algorithms for "Automatic Test Pattern Generation" (ATPG) have been proposed in the last 30 years. But due to the ever increasing design complexity, new techniques have to be developed that can cope with today’s circuits. While classical approaches are based on backtracking on the circuit structure, several approaches based on "Boolean Satisfiability" (SAT) have been proposed since the early 80s. In __Test Pattern Generation using Boolean Proof Engines__, we give an introduction to ATPG. The basic concept and classical ATPG algorithms are reviewed. Then, the formulation as a SAT problem is considered. As the underlying engine, modern SAT solvers and their use on circuit related problems are comprehensively discussed. Advanced techniques for SAT-based ATPG are introduced and evaluated in the context of an industrial environment. The chapters of the book cover efficient instance generation, encoding of multiple-valued logic, usage of various fault models, and detailed experiments on multi-million gate designs. The book describes the state of the art in the field, highlights research aspects, and shows directions for future work. Preface -1 Acknowledgments -1 Introduction -1 Preliminaries -1 Circuits -1 Fault Models -1 Stuck-at Faults -1 Delay Faults -1 Simple ATPG Framework -1 Classical ATPG Algorithms -1 Stuck-at Faults -1 Delay Faults -1 Benchmarking -1 Boolean Satisfiability -1 SAT Solver -1 Advances in SAT -1 Boolean Constraint Propagation -1 Conflict Analysis -1 Variable Selection Strategies -1 Correctness and Unsatisfiable Cores -1 Optimization Techniques -1 Circuit-to-CNF Conversion -1 Circuit-Oriented SAT -1 SAT-Based ATPG -1 Basic Problem Transformation -1 Structural Information -1 Experimental Results -1 Summary -1 Learning Techniques -1 Introductory Example -1 Concepts for Reusing Learned Information -1 Basic Idea -1 Tracking Conflict Clauses -1 Heuristics for ATPG -1 Notation -1 Incremental SAT-Based ATPG -1 Enhanced Circuit-Based Learning -1 Experimental Results -1 Summary -1 Multiple-Valued Logic -1 Four-Valued Logic -1 Industrial Circuits -1 Boolean Encoding -1 Encoding Efficiency -1 Concrete Encoding -1 Multi-input Gates -1 Modeling of Multi-input Gates -1 Bounded Multi-input Gates -1 Clause Generation -1 Experimental Results -1 Four-Valued Logic -1 Multi-input Gates -1 Summary -1 Improved Circuit-to-CNF Conversion -1 Hybrid Logic -1 Incremental Instance Generation -1 Run Time Analysis -1 Incremental Approach -1 Experimental Results -1 Hybrid Logic -1 Incremental Instance Generation -1 Summary -1 Branching Strategies -1 Standard Heuristics of SAT Solvers -1 Decision Strategies -1 Experimental Results -1 Summary -1 Integration into Industrial Flow -1 Industrial Environment -1 Integration of SAT-Based ATPG -1 Test Pattern Compactness -1 Observability at Outputs -1 Applying Local Don't Cares -1 Experimental Results -1 Integration -1 Test Pattern Compactness -1 Summary -1 Delay Faults -1 Transition Delay -1 Path Delay -1 Non-robust Tests -1 Robust Test Generation -1 Industrial Application -1 Structural Classification -1 Encoding Efficiency for Path Delay Faults -1 Compactness of Boolean Representation -1 Efficiency of Compact Encodings -1 Encoding Selection -1 Incremental Approach -1 Experimental Results -1 Transition Delay Faults -1 Encoding Efficiency for Path Delay Faults -1 Robust and Non-robust Tests -1 Incremental Approach -1 Summary -1 Summary and Outlook -1 Bibliography -1 Index 181 Front Matter....Pages i-xii Introduction....Pages 1-8 Preliminaries....Pages 9-28 Boolean Satisfiability....Pages 29-42 SAT-Based ATPG....Pages 43-52 Learning Techniques....Pages 53-70 Multiple-Valued Logic....Pages 71-87 Improved Circuit-to-CNF Conversion....Pages 89-111 Branching Strategies....Pages 113-117 Integration into Industrial Flow....Pages 119-135 Delay Faults....Pages 137-171 Summary and Outlook....Pages 173-175 Back Matter....Pages 177-192 Gives an introduction to ATPG. This work reviews the basic concept and classical ATPG algorithms. It also considers the formulation as a SAT problem. It covers efficient instance generation, encoding of multiple-valued logic, usage of various fault models, and detailed experiments on multi-million gate designs