Diagnostic Modeling of Digital Systems with Multi-Level Decision Diagrams

Diagnostic Modeling of Digital Systems with Multi-Level Decision Diagrams

Raimund Ubar (Tallinn University of Technology, Estonia), Jaan Raik (Tallinn University of Technology, Estonia), Artur Jutman (Tallinn University of Technology, Estonia) and Maksim Jenihhin (Tallinn University of Technology, Estonia)
DOI: 10.4018/978-1-4666-2038-4.ch025
OnDemand PDF Download:


In order to cope with the complexity of today’s digital systems in diagnostic modeling, hierarchical multi-level approaches should be used. In this chapter, the possibilities of using Decision Diagrams (DD) for uniform diagnostic modeling of digital systems at different levels of abstraction are discussed. DDs can be used for modeling the functions and faults of systems at logic, register transfer and behavior like instruction set architecture levels. The authors differentiate two general types of DDs – logic level binary DDs (BDD) and high level DDs (HLDD). Special classes of BDDs are described: structurally synthesized BDDs (SSBDD) and structurally synthesized BDDs with multiple inputs (SSMIBDD). A method of iterative synthesis of SSBDDs and SSMIBDDs is discussed. Three methods for synthesis of HLDDs for representing digital systems at higher levels are described: iterative superposition of HLDDs for high-level structural representations of systems, symbolic execution of procedural descriptions for functional representations of systems, and creation of vector HLDDs (VHLDD) on the basis of using shared HLDDs for compact representing of a given set of high level functions. The nodes in DDs can be modeled as generic locations of faults. For more precise general specification of faults different logic constraints are used. A functional fault model to map the low level faults to higher levels, particularly, to map physical defects from transistor level to logic level is discussed.
Chapter Preview


The difficulties in developing of analytical multi-level and hierarchical approaches to digital test generation and fault simulation lay in using different languages and models for different levels of abstractions. Most frequent examples are logic expressions for combinational circuits, state transition diagrams for finite state machines (FSM), abstract execution graphs, system graphs, instruction set architecture (ISA) descriptions, flow-charts, hardware description languages (HDL, VHDL, Verilog, System C etc.), Petri nets for system level description etc. All these models need dedicated for the given language manipulation algorithms and fault models which are difficult to merge into hierarchical test methods. HDL based modeling methods which are efficient for fault simulation lack the capability of analytical reasoning and analysis that is needed in test generation and fault diagnosis.

Excellent opportunities for multi-level and hierarchical diagnostic modeling of digital systems provide decision diagrams (DD) because of their uniform cover of different levels of abstraction, and because of their capability for uniform graph-based fault analysis and diagnostic reasoning (Lee, 1959; Ubar, 1976; Akers, 1978; Plakk & Ubar, 1980; Bryant, 1986; Minato, 1996; Sasao, & Fujita, 1996; Ubar, 1996; Drechsler & Becker, 1998).

Complete Chapter List

Search this Book: