Fault Diagnosis and Fault Tolerance: A Systematic Approach to Special Topics

ISBN-13: 9783540549628 / Angielski / Miękka / 1992 / 197 str.

Tinghuai Chen; Ting-Huai Chen

Opis

With the rapid growth of integration scale of VLSI chips and the present need for reliable computers in space exploration, fault diagnosis and fault toleran ce have become more important than before, and hence reveal a lot of interest ing topics which attract many researchers to make a great number of contribu tions to this field. In recent years, many new and significant results have been achieved. A quick scan over the proceedings of the conferences on fault tolerant computing and design automation as well as on testing will convince the reader of that. But unfortunately these achievements have not been entire ly reflected in the textbooks, so that there seems to be a gap for the new researcher who already has the basic knowledge and wants to begin research in this area. As a remedy for this deficiency, this book is intended for begin ners, especially graduate students, as a textbook which will lead them to the frontier of some branches of the fault-tolerant computing field. The first chapter introduces the four-valued logic B4 and its applica tions. In 1966 Roth first proposed this four-valued logic as a technique to generate tests for logical circuits, but this work did not concern the mathe matical basis of B4 itself."

Spis treści

1 Four-Valued Logic and Its Applications.- 1.1 Introduction.- 1.2 Mathematical Basis.- 1.2.1 Four-Valued Boolean Algebra B4.- 1.2.2 Boolean Expression.- 1.2.3 Mapping B4n?B4 and Boolean Functions.- 1.2.4 Vector Forms.- 1.2.5 Canonical Forms.- 1.2.6 Expressions for Boolean Functions.- 1.3 STAR Expansions, Boolean Difference and Boolean Differential.- 1.3.1 Expansion Formulae.- 1.3.2 Boolean Difference.- 1.3.3 Boolean Differential.- 1.3.4 Geometrical Interpretation.- 1.4 Combined Components.- 1.4.1 Front and Rear Values.- 1.4.2 Binary Coding.- 1.4.3 Interpretation for Testing.- 1.5 Boolean Equations.- 1.5.1 Basic Concepts.- 1.5.2 A1·A2···An·j=0 with j=1,D,$$\overline D$$; and A1=x1 or $${{\overline x }_}$$.- 1.5.3 Deriving Star Expansion Via Solving Equation.- 1.6 Test Generation for Combinational Circuits.- 1.6.1 Fault and (Static) Test.- 1.6.2 The Test for Single Fault.- 1.7 Statical Test Generation for Sequential Circuits.- 1.7.1 Example to Derive Tests.- 1.7.2 Comparison with Other Method.- 1.8 Identification of Hazards and Dynamic Testing.- 1.8.1 The Dynamic Behavior and Dynamic Tests of Combinational Circuit.- 1.8.2 Identification of Hazards.- 1.8.3 Dynamic Tests and Hazardous Tests.- 1.9 Transition Logic.- 1.9.1 Proposition Calculus and Predicate Calculus.- 1.9.2 Logical Inferences.- 1.9.3 Other Logic.- 1.10 Comparison with Other Logics.- 1.10.1 Addition of States.- 1.10.2 Extension to Power Set.- 1.10.3 Merging of States.- 1.10.4 Extension by Direct Product.- References.- 2 Computer System Diagnosis and Society Diagnosis.- 2.1 Introduction (PMC Model).- 2.1.1 Self-Diagnosis of System.- 2.1.2 Basic Definitions.- 2.2 One Step System Diagnosis for PMC Model.- 2.2.1 The Characterization Problem.- 2.2.2 Diagnosing Algorithm.- 2.2.3 Optimal Design.- 2.3 The Extension of System Diagnosis.- 2.3.1 Extension along Diagnostic Goals.- 2.3.2 Extension along Models.- 2.3.3 Extension along the State Values.- 2.3.4 Extension along Diagnosing Method.- 2.3.5 The Combination of Different Extensions.- 2.4 The Application of System Diagnosis.- 2.4.1 The Diagnosis for Analog Circuits.- 2.4.2 Fault-Tolerant Computing.- 2.4.3 Society Diagnosis.- References.- 3 Testability Design via Testability Measures.- 3.1 Introduction.- 3.1.1 The Problem of Testability and Its Measure.- 3.1.2 Definition of Testability and Measures.- 3.1.3 Testability in Term of Controllability and Observability.- 3.1.4 Testability Measure and Algorithm.- 3.1.5 J. Hayes’ Suggestion.- 3.1.6 Problems Studied in this Chapter.- 3.2 Testability Design.- 3.2.1 Testability Measure.- 3.2.2 Means to Improve Testability.- 3.2.3 Constraints A,B,C,D,E and Objective Function F.- 3.2.4 ILP Problem for Testability.- 3.2.5 Asynchronous Sequential Circuits.- 3.2.6 Experimental Results.- 3.3 Design for Testability at Module Level.- 3.3.1 Definition of Testability.- 3.3.2 Probability Function Ill.- 3.3.3 Controllability Spectrum.- 3.3.4 Observability Spectrum.- 3.3.5 Modifications and Other Problems.- 3.4 Applications.- References.- 4 NMRC: A Technique for Redundancy.- 4.1 Introduction.- 4.2 NMRC System Model.- 4.2.1 System Description.- 4.2.2 Fault Pattern.- 4.2.3 Maximum Likelihood Selection.- 4.3 Analysis of Fault Tolerance Capability.- 4.3.1 Definitions.- 4.3.2 Module-FT Degree.- 4.3.3 Module-Comparator FT Degree.- 4.4 Optimal NMRC System Design.- 4.5 An Example for Comparison Analysis.- 4.5.1 Performance Comparison.- 4.5.2 Cost Comparison.- 4.5.3 Reliability Comparison.- 4.5.4 Diagnosability Comparison.- 4.6 Conclusion.- References.- 4.A.1 The Proof of Theorem 4.4.- 4.A.2 The Proof of Lemma 2.- 5 Fault Tolerance of Switching Interconnection ß-Networks.- 5.1 Introduction.- 5.1.1 Multicomputer Systems.- 5.1.2 Connecting Capability and Structure of ICN.- 5.1.3 ß-elements and ß-network.- 5.1.4 Communication Delay.- 5.1.5 Fault Model for a ß-element.- 5.2 General Inequalities.- 5.2.1 Proof of [log2n]+l ? d ? n.- 5.2.2 Proof of K ? d -1.- 5.3 ISE-MISE-RMISE.- 5.3.1 ISE.- 5.3.2 MISE.- 5.3.3 RMISE.- 5.4 C 1n,t ß-networks.- 5.4.1 Definition of C 1n,t Networks.- 5.4.2 Expressions for K and d.- 5.4.3 Relative Optimization.- 5.4.4 Maximize d.- 5.4.5 Maximize K.- 5.5 RFT Network.- 5.5.1 Swi tching Elements.- 5.5.2 RFT Networks.- 5.5.3 Routing Algorithm and Fault-Tolerance.- 5.6 Conclusion.- References.- 6 The Connectivity of Hypergraph and the Design of Fault Tolerant Multibus Systems.- 6.1 Introduction.- 6.2 Connectivity of Hypergraph.- 6.2.1 Definitions.- 6.2.2 Basic Theorems.- 6.2 3 Properties of Hypergraph with the Best Connectivity.- 6.3 BIB Design and the Optimized Multibus System.- 6.3.1 BIB Design.- 6.3.2 Theorems.- 6.3.3 Optimized Design.- 6.4 WBIB and the Optimized Multibus System.- 6.4.1 Examples of WBIB.- 6.4.2 Definitions of WBIB Design.- 6.4.3 WBIB Design for ?=2.- 6.4.4 WBIB Design for ?=3.- 6.4.5 WBIB Design for ? and the Fault Tolerance Degree.- 7.5 Optimal Design.- 7.5.1 Cost Optimal.- 7.5.2 Tx (G) Optimal.- 7.6 Conclusion.- References.

O autorze

The diagnosis of faults in VLSI chips and the design of chips to be fault-tolerant form the subject of this book. Seven topics are treated at a level appropriate for researchers beginning work in the field. The treatment is formal enough to be widely applicable.