Structural Decision Diagrams in Digital Test: Theory and Applications

✍ Scribed by Raimund Ubar, Jaan Raik, Maksim Jenihhin, Artur Jutman

• Publisher: Birkhäuser
• Year: 2024
• Tongue: English
• Leaves: 608
• Series: Computer Science Foundations and Applied Logic
• Category: Library

✦ Synopsis

This is the first book that sums up test-related modeling of digital circuits and systems by a new structural-decision-diagrams model. The model represents structural and functional information jointly and opens a new area of research.

The book introduces and discusses applications of two types of structural decision diagrams (DDs): low-level, structurally synthesized binary DDs (SSBDDs) and high-level DDs (HLDDs) that enable diagnostic modeling of complex digital circuits and systems.

Topics and features:

• Provides the definition, properties and techniques for synthesis, compression and optimization of SSBDDs and HLDDs
• Provides numerous working examples that illustrate the key points of the text
• Describes applications of SSBDDs and HLDDs for various electronic design automation (EDA) tasks, such as logic-level fault modeling and simulation, multi-valued simulation, timing-critical path identification, and test generation
• Discusses the advantages of the proposed model to traditional binary decision diagrams and other traditional design representations
• Combines SSBDDs with HLDDs for multi-level representation of digital systems for enabling hierarchical and cross-level solving of complex test-related tasks

This unique book is aimed at researchers working in the fields of computer science and computer engineering, focusing on test, diagnosis and dependability of digital systems. It can also serve as a reference for graduate- and advanced undergraduate-level computer engineering and electronics courses.

Three authors are affiliated with the Dept. of Computer Systems at the Tallinn University of Technology, Estonia: Raimund Ubar is a retired Professor, Jaan Raik and Maksim Jenihhin are tenured Professors. Artur Jutman, PhD, is a researcher at the same university and the CEO of Testonica Lab Ltd., Estonia.

✦ Table of Contents

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