References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9 QUADRATIC 0-1 PROGRAMMING 8S 9. 1 Energy Minimization 86 9. 2 Notation and Tenninology . . . . . . . . . . . . . . . . . 87 9. 3 Minimization Technique . . . . . . . . . . . . . . . . . . 88 9. 4 An Example . . . . . . . . . . . . . . . . . . . . . . . . 92 9. 5 Accelerated Energy Minimization. . . . . . . . . . . . . 94 9. 5. 1 Transitive Oosure . . . . . . . . . . . . . . . . . 94 9. 5. 2 Additional Pairwise Relationships 96 9. 5. 3 Path Sensitization . . . . . . . . . . . . . . . . . 97 9. 6 Experimental Results 98 9. 7 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . 100 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 10 TRANSITIVE CLOSURE AND TESTING 103 10. 1 Background . . . . . . . . . . . . . . . . . . . . . . . . 104 10. 2 Transitive Oosure Definition 105 10. 3 Implication Graphs 106 10. 4 A Test Generation Algorithm 107 10. 5 Identifying Necessary Assignments 112 10. 5. 1 Implicit Implication and Justification 113 10. 5. 2 Transitive Oosure Does More Than Implication and Justification 115 10. 5. 3 Implicit Sensitization of Dominators 116 10. 5. 4 Redundancy Identification 117 10. 6 Summary 119 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 11 POLYNOMIAL-TIME TESTABILITY 123 11. 1 Background 124 11. 1. 1 Fujiwara's Result 125 11. 1. 2 Contribution of the Present Work . . . . . . . . . 126 11. 2 Notation and Tenninology 127 11. 3 A Polynomial TlDle Algorithm 128 11. 3. 1 Primary Output Fault 129 11. 3. 2 Arbitrary Single Fault 135 11. 3. 3 Multiple Faults. . . . . . . . . . . . . . . . . . . 137 11. 4 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . 139 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 ix 12 SPECIAL CASES OF HARD PROBLEMS 141 12. 1 Problem Statement 142 12. 2 Logic Simulation 143 12. 3 Logic Circuit Modeling . 146 12. 3. 1 Modelfor a Boolean Gate . . . . . . . . . . . . . 147 12. 3. 2 Circuit Modeling 148 12.
Inhaltsverzeichnis
1 Introduction. - 1. 1 What is Test Generation? . - 1. 2 Why Worry About Test Generation? . - 1. 3 How About Parallel Processing? . - 1. 4 Neural Computing. - 1. 5 A Novel Solution. - 1. 6 Polynomial Time Test Problems. - 1. 7 Application to Other NP-complete Problems. - 1. 8 Organization of the Book. - References. - 2 Logic Circuits and Testing. - 2. 1 Logic Circuit Preliminaries. - 2. 2 Test Generation Problem. - 2. 3 Test Generation Techniques. - 2. 4 Parallelization. - References. - 3 Parallel Processing Preliminaries. - 3. 1 Synchronous Parallel Computing. - 3. 2 Parallel Test Generation. - References. - 4 Introduction to Neural Networks. - 4. 1 Discrete Model of Neuron. - 4. 2 Electrical Neural Networks. - References. - 5 Neural Modeling for Digital Circuits. - 5. 1 Logic Circuit Model. - 5. 2 Existence of Neural Models. - 5. 3 Properties of Neural Models. - 5. 4 Three-Valued Model. - 5. 5 Summary. - References. - 6 Test Generation Reformulated. - 6. 1 ATG Constraint Network. - 6. 2 Fault Injection. - 6. 3 Test Generation. - 6. 4 Summary. - References. - 7 Simulated Neural Networks. - 7. 1 Iterative Relaxation. - 7. 2 Implementation and Results. - 7. 3 Parallel Simulation. - 7. 4 Summary. - References. - 8 Neural Computers. - 8. 1 Feasibility and Performance. - 8. 2 ANZA Neurocomputer. - 8. 3 Energy Minimization. - 8. 4 Enhanced Formulation. - 8. 5 ANZA Neurocomputer Results. - 8. 6 Summary. - References. - 9 Quadratic 0-1 Programming. - 9. 1 Energy Minimization. - 9. 2 Notation and Terminology. - 9. 3 Minimization Technique. - 9. 4 AnExample. - 9. 5 Accelerated Eneigy Minimization. - 9. 6 Experimental Results. - 9. 7 Summary. - References. - 10 Transitive Closure and Testing. - 10. 1 Background. - 10. 2 Transitive Closure Definition. - 10. 3 Implication Graphs. - 10. 4 A Test Generation Algorithm. - 10. 5 Identifying Necessary Assignments. - 10. 6 Summary. - References. - 11 Polynomial-time Testability. - 11. 1 Background. - 11. 2 Notation and Terminology. - 11. 3 A Polynomial Time Algorithm. - 11. 4 Summary. - References. - 12 Special Cases of Hard Problems. - 12. 1 Problem Statement. - 12. 2 Logic Simulation. - 12. 3 Logic Circuit Modeling. - 12. 4 Simulation as a Quadratic 0-1 Program. - 12. 5 Quadratic 0-1 Program as Simulation. - 12. 6 Minimizing Special Cases. - 12. 7 Summary. - References. - 13 Solving Graph Problems. - 13. 1 Background. - 13. 2 Notation and Terminology. - 13. 3 Maximum Weighted Independent Sets. - 13. 4 Conflict Graphs of Boolean Gates. - 13. 5 AnExample. - 13. 6 Summary. - References. - 14 Open Problems. - References. - 15 Conclusion.