Structural Decision Diagrams in Digital Test: Theory and Applications

Preface
	The Idea
Acknowledgements
Contents
1 Introduction
2 Overview of Structural Decision Diagrams
	2.1 A Short History of Structural Decision Diagrams
		2.1.1 Binary Decision Diagrams
		2.1.2 Logic-Level Structural Decision Diagrams
		2.1.3 High-Level Decision Diagrams
	2.2 Binary Decision Diagrams
	2.3 Structurally Synthesized Binary Decision Diagrams
	2.4 Shared Structurally Synthesized BDDs
	2.5 High-Level Decision Diagrams
		2.5.1 About the Similarity of Low- and High-Level Structural DDs
		2.5.2 RTL Modeling of Digital Modules with HLDDs
		2.5.3 RTL Modeling of Control Circuits with HLDDs
		2.5.4 Instruction-Level Modeling of Microprocessors
	2.6 Structural DDs as a Universal Tool for Digital Test
3 Structurally Synthesized BDDs
	3.1 Synthesis of SSBDDs
		3.1.1 Definition of SSBDD
		3.1.2 Synthesis of the SSBDD Model for a Digital Circuit
		3.1.3 Verification of the Correctness of SSBDDs
	3.2 Properties and Specific Features of SSBDDs
		3.2.1 Basic Operations on SSBDDs
		3.2.2 Basic Properties of SSBDD
		3.2.3 SSBDDs and Boolean Algebra
		3.2.4 SSBDDs and Functional BDDs
	3.3 Equivalent Transformations of SSBDDs
		3.3.1 Mapping Between SSBDDs and FFRs of Digital Circuits
		3.3.2 Restructuring of SSBDDs to Speed-Up Simulation
		3.3.3 Optimization of SSBDDs by Reconfiguring the Structure
		3.3.4 Restructuring of SSBDDs for Sharing the Sub-graphs
	3.4 Shared Structurally Synthesized BDD
		3.4.1 Definitions and the Structure of S3BDDs
		3.4.2 Synthesis of S3BDDs
		3.4.3 The Size of the S3BDD Model
4 Fault Modelling with Structural BDDs
	4.1 Fault Modeling with Structural BDDs
		4.1.1 Modeling Faults with SSBDDs
		4.1.2 Measuring Fault Coverage Using SSBDDs
		4.1.3 Modeling Faults with S3BDDs
		4.1.4 Mapping of S3BDD Nodes to Signal Paths in Circuits
		4.1.5 Making Faults Observable in S3BDDs
		4.1.6 Modeling Path and Path Segment Delay Faults in S3BDDs
	4.2 Extending the Class of Faults
		4.2.1 Generalization of the SAF Model
		4.2.2 Modeling Physical Defects by Boolean Differential Equations
		4.2.3 Hierarchical Fault Modeling Using Conditional SAF
	4.3 Fault Collapsing
		4.3.1 Related Work and Definitions
		4.3.2 Fault Equivalence and Fault Dominance in the SSBDD Model
		4.3.3 Fault Collapsing in SSBDDs
5 Logic-Level Fault Simulation
	5.1 Fault-Free Logic Simulation
		5.1.1 Fault-Free Simulation with Structural BDDs
		5.1.2 Multi-valued Logic Simulation with SSBDDs
	5.2 Fault Simulation in Combinational Circuits
		5.2.1 Related Work and Overview
		5.2.2 Parallel Fault Simulation with SSBDDs
		5.2.3 Critical Path Parallel Pattern Fault Backtracing
		5.2.4 Fault Simulation for the Extended Class of Faults
		5.2.5 Fault Simulation in Multiple Core Environments
	5.3 Fault Simulation in Sequential Circuits
		5.3.1 Combining Combinational and Sequential Simulation
		5.3.2 Design for Testability for Fault Simulation in Sequential Circuits
	5.4 Identification of Critical Paths with Logic Simulation
		5.4.1 The Concept of True Critical Path Identification
		5.4.2 Calculation of the Lengths of Sensitized Paths in Sequential Circuits with SSBDDs
		5.4.3 Search for the Longest Critical Paths in Sequential Circuits
6 Test Generation, Testability and Fault Diagnosis
	6.1 Test Generation Using Structural BDDs
		6.1.1 Path Activation in SSBDDs
		6.1.2 Test Pattern Generation with SSBDDs
		6.1.3 Test Pattern Generation with S3BDDs
		6.1.4 The Problem of Fault Masking
	6.2 Test Pattern Generation for Multiple Faults with SSBDDs
		6.2.1 Related Work
		6.2.2 Contributions of the Method of Test Groups
		6.2.3 The Problem of Fault Masking Revisited
		6.2.4 SSBDDs and the Topological View on the Fault Masking
		6.2.5 The Concept of Test Groups
	6.3 Testability Analysis of Digital Circuits with SSBDDs
		6.3.1 Related Work and Overview
		6.3.2 Calculation of Signal Probabilities in the Logic Circuits
		6.3.3 Calculating the Probabilistic Controllability with SSBDDs
		6.3.4 Controllability of Signals at Internal Nodes of FFRs
		6.3.5 Discussion on Different Methods of Controllability Calculation
		6.3.6 Experimental Research Results on Calculating Signal Probabilities
		6.3.7 Concluding Remarks
	6.4 Fault Diagnosis in the General Case of Multiple Faults
		6.4.1 Angel’s Advocate Approach to Fault Diagnosis
		6.4.2 Boolean Differential Equations and Fault Diagnosis
		6.4.3 A General Equation for Modeling Diagnostic Processes
		6.4.4 Solving Boolean Differential Equations with SSBDDs
		6.4.5 Test Groups and Hierarchical Fault Diagnosis
7 High-Level Decision Diagrams
	7.1 Theoretical Basics of HLDDs
		7.1.1 HLDDs as a Diagnostic Model for Digital Systems
		7.1.2 Behavioral Level Synthesis of HLDDs
		7.1.3 Structural Synthesis of HLDDs
		7.1.4 Timed Superposition of DDs
	7.2 High-Level DDs and Design Simulation
		7.2.1 Simulation of Digital Systems with HLDDs
		7.2.2 Vector High-Level Decision Diagrams
		7.2.3 Code Coverage Measurement with HLDDs
		7.2.4 Hierarchical Fault Simulation Combining SSBDDs and HLDDs
	7.3 Hierarchical Multi-level Test Generation in Sequential Circuits with DDs
		7.3.1 Related Work in Sequential Circuit Test Generation
		7.3.2 Hierarchical Test Generation for Sequential Circuits
		7.3.3 DECIDER
		7.3.4 Untestability Identification in Sequential Circuits with HLDDs
8 HLDD-Based Test Generation for RISC Processors
	8.1 Overview of High-Level Test Generation Concepts for Processors
		8.1.1 Fault Modeling of Digital Systems at Different Levels
		8.1.2 Related Work on the Microprocessor Test
		8.1.3 Research on Software-Based Self-test of Microprocessors
		8.1.4 Contributions Beyond the State of the Art
	8.2 High-Level Fault Modeling of Microprocessors with HLDDs
		8.2.1 Fault Modeling as a Trade-off of Complexity Versus Accuracy
		8.2.2 Traditional High-Level Fault Models for Digital Systems
		8.2.3 HLDD-Based Functional Fault Model for RISC Processors
	8.3 Implementation-Independent Control Fault Model for Processors
		8.3.1 Partitioning of a RISC Processor into Modules
		8.3.2 Theoretical Foundations of the Implementation-Independent Test
		8.3.3 High-Level Control Fault Model of MUTs on HLDDs
		8.3.4 Mixed-Level Identification of Fault Redundancy
		8.3.5 Optimization of HLDDs and High-Level Fault Modeling Trade-offs
	8.4 Extension of Fault Classes for Implementation-Independent Testing
		8.4.1 Mapping of Low-Level Structural Faults to the High-Level Constraints-Based Fault Model
		8.4.2 Extension of the Fault Classes with Implementation-Independent Testing
	8.5 Test Data Generation for the Modules of RISC Processors
		8.5.1 Test Data for Testing the Control Part of a MUT
		8.5.2 Pseudo-exhaustive Test Generation for the Data Part
	8.6 Software-Based Self-Test Synthesis
		8.6.1 Organization of Test Programs and the Concept of Test Templates
		8.6.2 Conformity and Scanning Tests for a MUT
		8.6.3 Test Generation for Delay Faults
	8.7 Multiple Fault Testing in Microprocessors Using HLDDs
		8.7.1 Topological View on Decision Diagrams for Multiple Fault Reasoning
		8.7.2 Merged Cycle-Based HLDD Model for Digital Systems
		8.7.3 Test Generation for Microprocessors Avoiding Fault Masking
References