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.
TopIntroduction
The most important question in testing today’s digital systems is: how to improve the test generation and fault simulation efficiency and quality at continuously increasing complexities of systems? Two main trends can be observed: defect-orientation and high-level modeling. To follow the both trends simultaneously, a hierarchical approach seems to be the only possibility. One of the attractive ways to manage hierarchy in diagnostic modeling (test generation, fault simulation, fault location) in a uniform way on different levels of abstraction is to use decision diagrams (DD).
Traditional flat low-level test methods and tools for complex digital systems have lost their importance, other approaches based mainly on higher level functional and behavioral methods are gaining more popularity (
Lee, Patel, 1997
;
Makris, Collins, Orailoglu & Vishakantaiah, 2000
;
Fummi, & Sciuto, 2000
;
Vedula & Abraham, 2002
;
Mirkhani, Lavasani & Navabi, 2002
;
Al-Yamani, & McCluskey, 2004
;
Kundu, 2004
; Yi, & Hayes, 2006; Misera, Vierhaus, Breitenfeld & Sieber, 2006;Alizadeh, & Fujita, 2010;Misera & Urban, 2010). Hierarchical mixed- or multi-level approaches have also been used both, for test generation (Lee, Patel, 1997;Makris, Collins, Orailoglu & Vishakantaiah, 2000;Vedula & Abraham, 2002;Ravi, Jha, 2001;Ichihara, Okamoto, Inoue, Hosokawa & Fujiwara, 2005), and fault simulation (Mirkhani, Lavasani & Navabi, 2002;Kundu, 2004;Misera, Vierhaus, Breitenfeld & Sieber, 2006;Misera & Urban, 2010). A general idea in these methodologies is detailed low-level fault simulation in one module of a system, while propagating the effects through other modules modeled at a higher level abstraction.
The trend towards higher level modeling moves us away from the real life of defects and, hence, from accuracy of testing. To handle adequately defects in deep-submicron technologies, new fault models and defect-oriented test methods have been introduced for test generation (
Blanton & Hayes, 2003
) and fault diagnosis (
Mahlstedt, Alt & Hollenbeck, 1995
;
Holst & Wunderlich, 2008
). On the other hand, the defect-orientation is increasing the complexity of the diagnostic modeling task even more. To get out from the deadlock, these two opposite trends – high-level modeling and defect-orientation – should be combined into a hierarchical approach. The advantage of hierarchical diagnostic modeling compared to the high-level functional modeling lies in the possibility of constructing and analyzing test plans on higher levels, and modeling faults on more detailed lower levels.
TopBackground
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.