Neural Models and Algorithms for Digital Testing

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.2.1 FaultModeling.- 2.2.2 Problem Definition.- 2.2.3 Complexity of Test Generation.- 2.3 Test Generation Techniques.- 2.4 Parallelization.- References.- 3 Parallel Processing Preliminaries.- 3.1 Synchronous Parallel Computing.- 3.1.1 Program Representation.- 3.1.2 Identification of Program Parallelism.- 3.1.3 Partitioning and Scheduling.- 3.1.4 Performance Measures.- 3.1.5 Solving Problems Using Multiprocessors.- 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.2.1 Neural Networks in Basis Set are Optimal.- 5.2.2 Parameters of Energy Function.- 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.2.1 Test Generation System.- 7.2.2 Experimental Results.- 7.3 Parallel Simulation.- 7.3.1 Synchronous Parallelism..- 7.3.2 Asynchronous Parallelism.- 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.4.1 Transitive Closure.- 8.4.2 Path Sensitization.- 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.5.1 Transitive Closure.- 9.5.2 Additional Pairwise Relationships.- 9.5.3 Path Sensitization.- 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.5.1 Implicit Implication and Justification.- 10.5.2 Transitive Closure Does More Than Implication and Justification.- 10.5.3 Implicit Sensitization of Dominators.- 10.5.4 Redundancy Identification.- 10.6 Summary.- References.- 11 Polynomial-time Testability.- 11.1 Background.- 11.1.1 Fujiwara's Result.- 11.1.2 Contribution of the Present Work.- 11.2 Notation and Terminology.- 11.3 A Polynomial Time Algorithm.- 11.3.1 Primary Output Fault.- 11.3.2 Arbitrary Single Fault.- 11.3.3 Multiple Faults.- 11.4 Summary.- References.- 12 Special Cases of Hard Problems.- 12.1 Problem Statement.- 12.2 Logic Simulation.- 12.3 Logic Circuit Modeling.- 12.3.1 Model for a Boolean Gate.- 12.3.2 Circuit Modeling.- 12.4 Simulation as a Quadratic 0-1 Program.- 12.5 Quadratic 0-1 Program as Simulation.- 12.5.1 A Linear Time Algorithm.- 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.