ABSTRACT FAULT ANALYSIS OF COMBINATIONAL LOGIC NETWORKS BY Lung-Hsiung Chang The algebraic model called the Complete Gate Equivalent Model (CGEM) which describes completely and precisely the physical and logical structures of a multiple output network is proposed for the study of faulty combinational logic networks. In this thesis, the power of a CGEM is demonstrated, with its various forms, through its application in the generation of fault functions and complete test sets for a network with stuck-at type faults. An upper bound on the number of possible fault functions, hence the number of possible fault classes, is established. Then, a straightforward procedure to find, without enumeration, all possible fault functions and the associated fault sets is presented. A complete test set can be found by covering the direct differences which are generated by enumerating all possible faults of the network. It is shown given a fault function and a complete test set of a logic network, one Lung—Hsiung Chang can either find the associated fault set or decide that the network cannot have degenerated into the given fault function. Methods of computing the fault functions for several kinds of bridging faults also are demonstrated. Four algorithms for generating near minimal complete test sets are presented. The first two are for multiple fault and single fault detection. The other two are the direct generalizations of the first two to fault location. A method for searching for a minimal complete detection test set for an irredundant network is also suggested. In general, one can find a smaller complete detection test set than that obtained by Poage's method. The generaliza- tions of the method to cover the general networks parallel the development of the algorithms. Furthermore, the existence of undetectable faults in a redundant network impose no restrictions on the test generation since we can modify the CGEM according to the fault before it is used in the algorithms. When detailed information about the logic network is not required, the Complete Gate Equivalent Model can be modified to describe LSI combinational networks in a manageable manner. Its use in generating tests for a sequential logic network has also been pointed out. FAULT ANALYSIS OF COMBINATIONAL LOGIC NETWORKS BY Lung-Hsiung Chang A THESIS . . Submitted to . Michigan State Univer51ty in partial fulfillment of the requirements ' for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1974 m .I .I’é .. :4! I Uni-I... ACKNOWLEDGMENTS I am grateful to Dr. Carl V. Page, the chairman of my guidance committee, for his guidance and encouragement during the course of this thesis. My thanks also go to Dr. Richard J. Reid, Dr. Julian Kateley, Jr., Dr. Edward A. Nordhaus and to Dr. Berhard L. Weinberg for serving on my guidance committee and for reviewing this work. Finally, I am deeply indebted to my wife Hsiu-Lan for her patience, understanding and encouragement. ii TABLE OF CONTENTS Page ACKNOWLEDGMENTS . . . . . . . . . . . . . . ii LIST OF TABLES . . . . . . . . . . . . . . v LIST OF FIGURES O O O O O O O O O I O O O 0 Vi Chapter 1. INTRODUCTION . . . . . . . . . . . . l 1.1 BACKGROUND . . . . . . . . . . 1 1.2 COMBINATIONAL LOGIC NETWORKS . . . . 2 1 o 3 LOGICAL FAULTS O o o o o o o o ' 4 1.4 FAULT DIAGNOSIS . . . . . . 5 1.5 CONTRIBUTIONS AND ORGANIZATION OF THE THESIS . . . . . . . . . 6 2. A COMPLETE GATE EQUIVALENT MODEL . . . . . 8 2.1 INTRODUCTION . . . . . . . 8 2.2 THE COMPLETE GATE EQUIVALENT ALGEBRAIC NETWORK MODEL (CGEM) . . . . . 9 2.3 CONSTRUCTION OF THE COMPLETE GATE EQUIVALENT MODEL FOR A COMBINATIONAL LOGIC NETWORK . . . . . . . . 19 2. 3.1 Transformation from the Combinational Logic Network ‘to an Equivalent Boolean Expression . . . . . . . 20 2.3.2 Reduction of Boolean Expression E to CGEM Form . . . . . . 26 2.4 THE COMPLEMENT OF THE BOOLEAN EXPRESSION E OF A COMBINATIONAL LOGIC NETWORK . . . . . . . . 27 2.5 CHAPTER SUMMARY AND REMARKS . . . . 32 iii Chapter 3. FAULT FUNCTIONS . . . . . . . . . . 3.1 INTRODUCTION . . . . . . . . 3.2 FAULT EQUIVALENCE . . . . . 3.3 GENERATION OF ALL POSSIBLE FAULT FUNCTIONS . . . . . . . 3.4 BRIDGING FAULTS . . . . . 3.5 DIRECT DIFFERENCE AND TEST GENERATION . . . . . . . 3.6 IDENTIFICATION OF FAULTS . . . . 3.7 CHAPTER SUMMARY AND REMARKS' . . . 4 . TEST GENERATION I O O O C O O O C O 4.1 INTRODUCTION . . . . 4.2 GENERATION OF NEAR MINIMAL COMPLETE DETECTION TEST SETS . . . . . . 4.2.1 Generation of a Near Minimal Test Set which Detects all Faults in a Combinational Logic Network . . . . . 4.2.2 Generation of a Near Minimal Test Set which Detects all Single Faults in a Combina- tional Logic Network . . . 4.3 GENERATION OF NEAR MINIMAL COMPLETE LOCATION TEST SETS . . . . . . 4.3.1 Generation of a Near Minimal Test Set which Locates All Faults in a Combinational Logic Network . . . . . 4.3.2 Generation of a Near Minimal Test Set which Locates A11 Single Faults in a Combina— tional Logic Network . . . 4.4 SEARCH OF MINIMAL COMPLETE DETECTION TEST SETS . . . . . . . . . 4.5 CHAPTER SUMMARY AND REMARKS . . . 5. CONCLUSIONS AND SUGGESTIONS FOR FUTURE WORK . 5.1 CONCLUSIONS . . . . . . APPENDIX . BIBLIOGRAPHY 5. 2 SUGGESTIONS FOR FUTURE WORK . . . iv Page 33 33 34 36 40 49 51 55 58 58 58 59 67 73 73 79 83 9O 92 92 93 95 103 LIST OF TABLES Table Page 2.1 All pl-path Sets and gl-literals for the Network of Figure 2.3 . . . . . . . . 14 2.2 The Functional Equivalents of gl-literals of Table 2.1(b). . . . . . . . . . . 16 2.3 The z.-1 and z.-o Sets for the Network of Figare 2.4 2 . . . . . . . . . . . 18 2.4 The GEM.-l and GEM.-O Sets for the Example of Taflle 2.3 .3 . . . . . . . . . . 19 Figure 1.1 1.2 2.1 2.2 LIST OF FIGURES The Elementary Gates . . . . . . . A Network and the Representations for the Exclusive-OR Function . . . . . . Two Different Labeling Schemes for the Same Portion of a Combinational Logic Network A Combinational Logic Network which Realizes X1X2X3X4 + Xlx2 3X4 . . . . A Combinational Logig_Netwo£k_which Realizes x1x2x3 + Xlx2 + Xlx3 . . . . The Logic Network for Example 2.3 . . . The Logic Network for Example 3.2 . . . The Irredundant Network for Example 4.5 . The AND/OR Graph Representation of Figure 2. vi 4 Page 11 ll 13 17 36 87 102 CHAPTER 1 INTRODUCTION 1.1 BACKGROUND In this chapter we present some background materials required for a study of faulty combinational logic networks. The basic assumption is that the combina- tional logic networks are comprised of single-output elementary gates. Further assumptions will be presented as the development of this thesis requires. Most studies of faulty combinational logic networks have concentrated on the network level rather than on the system level and have been concerned only with the effects of faults on the logical behaviors of the networks. This thesis will follow in this tradition unless otherwise indicated. The importance of the study of faulty combinational logic networks has been pointed out by several authors, e.g., Carter [6] and Kamal [22] and is evidenced by numerous related articles appearing in such publications as the IEEE Transactions on Computers. Furthermore, there have been three International Symposia on Fault-Tolerant Computing in the past three years and two textbooks devoted exclusively to fault detection and diagnosis of digital systems. The original contributions and organization of the thesis are discussed at the end of this chapter. 1.2 COMBINATIONAL LOGIC NETWORKS A Boolean function is elementary in argument X if the function can be expressed in the form X*-fl or x* + F2, where X* = X or i and f1 and f2 functions independent of X. A function is elementary if are any Boolean it is elementary in all of its input arguments. An elementary gate is a gate whose function is elementary. The commonly used gates such as AND, OR, NOT, NAND and NOR are all elementary gates while Exclusive-OR is not. This thesis will deal with combinational logic networks which are realized by elementary gates. Figure 1.1 shows the schematic notion that will be used to represent these gates. (a) AND (b) OR (C) NOT (d) NAND (e) NOR Figure 1.1. The Elementary Gates Combinational logic networks are used to realize combinational functions and are characterized by the absence of feedback. A combinational function may be represented by (1) a Boolean expression of input literals, (2) a truth table which specifies the value of the function for each combination of input values or (3) a Karnaugh map. Figure 1.2 (a) is a combinational logic network for the Exclusive-OR function. Two different representations of the function are shown on Figure 1.2 (b) and (c). (a) A Combinational Network for the Exclusive—OR Function. X1 x1 x2 Z 0 1 0 O O 0 0 1 l o 1 1 X2 -11 1 0 1 1 1 o l 1 1 o I M (b) Truth Table. (c) Karnaugh Map. Figure 1.2. A Network and the Representations for the Exclusive—OR Function. 1.3 LOGICAL FAULTS The faults that we shall be concerned with are logical faults. A logical fault is a fault which produces some changes in the logical behavior of the network. Hereafter the term fault will mean logical fault unless otherwise indicated. The class of faults to be considered in the study of faulty logic networks depends on the type of networks. However, most of the faults in contemporary networks can be represented by an input or output of some basic elements being stuck at one or stuck at zero. That is, an input or output of some basic elements may assume a fixed loqical value, independent of the inputs supplied to the logic network. All but one section of this thesis deals with stuck-at type faults. While stuck-at type faults deal with individual leads of the network, bridging faults are concerned with the faults due to the connection of two or more leads of the network. We shall investigate bridging faults exclusively in Section 3.4. A fault may be permanent or intermittent. A permanent fault is a fault which will not occur, disappear or change its nature during testing and its effect will exist throughout the period of interest. An intermittent fault may show its effect at one time and not at other times. We shall deal only with permanent faults. 1.4 FAULT DIAGNOSIS A combinational logic network is said to contain a fault if upon the application of an input vector Ti' the output vector of the network is different from that of fault-free network. We call such an input vector a EEEE' A test Ti is said to detect fault Fj if the output vectors for the fault-free network and the same network containing Fj are different when T1 is applied. A set of tests which detects all detectable single faults of the network is called a complete single fault detection test set. The single fault assumption implies the network cannot have more than one fault at any time. This assumption is justifiable only if testing is frequent enough so that the probability of the occurrence of more than one fault during the interval between test experiments is negligibly small. It is clear that the single fault assumption may not be valid for initial check-out of the networks. Even so, it does not mean the test generations under single fault assumption has to be simpler than that under the multiple fault assumption, as we shall demonstrate in Chapter 4. Two faults are distinguishable if there is a test that generates different output vectors for two instances of the same network containing the different faults. A set of tests which distinguishes every pair of distinguishable faults of the network is called a complete location test set. In general, a test can detect several faults and a fault can be detected by several tests. It takes several tests to locate a fault and it also takes several faults to specify a test. 1.5 CONTRIBUTIONS AND ORGANIZATION OF THE THESIS An algebraic model called the Complete Gate Equivalent Model (CGEM) which describes completely and precisely the physical and logical structures of a multiple output network is prOposed for the study of faulty com- binational logic networks. In this thesis, the power of a CGEM is demonstrated, with its various forms, through its application in the generation of fault functions and complete test sets for a network with stuck-at type faults. An upper bound on the number of possible fault functions, hence the number of possible fault classes, is established. Then, a straightforward procedure to find, without enumeration, all possible fault functions and the associated fault sets is presented. A complete test set can be found by covering the direct differences which are generated by enumerating all possible faults of the network. It is shown given a fault function and a complete test set of a network one can either find the associated fault set or decide that the network can not have degenerated into the given fault function. Methods of computing the fault functions for several kinds of bridging faults also are demonstrated. Four algorithms for generating near minimal complete test sets are presented. The first two are for multiple fault and single fault detection. The other two are the direct generalizations of the first two to fault location. A method of searching for a minimal complete detection test set for an irredundant network is also suggested. In general, one can find a smaller complete detection test set than that obtained by Poage's method [33]. In Chapter 2 the Complete Gate Equivalent Model is presented. Chapter 3 deals with fault functions and Chapter 4 describes the algorithms and the method of complete test generations. Chapter 5 concludes the thesis and recommends problems for further research. CHAPTER 2 A COMPLETE GATE EQUIVALENT MODEL 2.1 INTRODUCTION The problem of analyzing the relationships between network faults and output IOgic abberrationsraslalready been studied by numerous models and various techniques. However, a large number of unanswered questions remain in the area of fault detection and location. In order to solve these and other related problems, a logic network model which makes structural and logical interdependencies easier to recognize and express formally is still needed. The earliest model which embodies information about both structure and logical characteristics of an object network to aid in fault analysis was presented by Poage [33] in 1963. Poage's model uses three valued lead variables to explicitly represent the normal, stuck at one and stuck at zero conditions of each lead. This results in expressions which are notationally complicated and unwieldly even though the model is rigorously presented. Armstrong's enf (equivalent normal from) [1] offers a much more tractable notation than that of Poage, but it lacks both the completeness and preciseness of the latter. Clegg [11] developed the SPOOF (Structure and Parity- Observing Output Function) model to more completely des- cribe the network structure, by making internal network inversion explicit without providing a mathematically complete and rigorous basis. While Reese and McCluskey [36] utilized the SPOOF model to take advantage of its convenient notation and to provide mathematical rigor, it lacks both structural generality and logical completeness. The model to be deve10ped is an extension of Reese and McCluskey's model. 2.2 THE COMPLETE GATE EQUIVALENT ALGEBRAIC NETWORK MODEL (CGEMT A labeling scheme that accurately describes the structure of the network will be used in our model. The CGEMs describe both the outputs and the complement of the outputs of the multiple—output network, whereas the GEM describes only the output of the single—output network. Furthermore, a formal definition of the functional equiva- lent of CGEM will be added to the model. The logic networks we are going to study are finite, combinational networks comprised of single-output elemen- tary gates with all their leads properly labeled. The labeling scheme is as follows: 10 Procedure L (Lead-labeling) (l) Assign a distinct integer label to each primary input lead and the output lead of each elemen- tary gate. (2) To each of r fanout branches from a lead labeled p, assign a distinct label pv, where v is a letter in some alphabet other than the integers. (3) Repeat step (2) until all of the leads are labeled. Because the networks to be considered are finite, the labeling procedure will stOp in a finite number of steps. The reasons for explicitly labeling fanout branches are: (1) (2) (3) Under the single fault assumption, if a network model that does not faithfully represent the actual wiring topology is used to generate test sets, some real single faults may remain untested. For example, a failure along lead 3b in Figure 2.1 (a) may be modeled as a single stuck-at fault. However, this failure can not be represented by any single fault in the network of Figure 2.1 (b). Under the multiple fault assumption, fanout branches are checkpoints which play an important role in the generation of complete detection test sets. Fault analysis for certain kinds of failures, e.g., bridging faults, require the identification of fanout branches. 11 I') I 3ba 13b 3bb (a) Labeling that Preserves Physical Wiring TOpology. 3a 1 3 3b 2 3c (b) Labeling that Assumes Simple Fanout. Figure 2.1. Two Different Labeling Schemes for the Same Portion of a Combinational Logic Network. Example 2.1 Figure 2.2 is a network after applying Procedure L. 2a E>_ 3b ‘ [27 -1a m _3aa I)*JL—‘I r2; fl — l/ P\. 365‘ V '12 2 6b r L77 P—i )“ 11 , — Figure 2.2, A Combination§l_ngic Network which Realizes X1X2X3X4 + X X X X 1 2 3 4' 12 Definition 2.1 The inversion parity with respect to a path h of lead g is the number (modulo 2) of inverting elemen- tary gates between 9 and a network output Zj along the signal path h. The inverting elementary gates are: NOT, NAND and NOR. Since there is no inverting elementary gate between an input literal and the associated primary input lead, the inversion parity of an input literal will be the same as that of the associated input lead. Definition 2.2 A path set L = is an ordered set of labels describing some signal path h of a network with a network output literal as its last element. The ordering of the labels corresponds to the order in which a signal traveling along h would encounter them. a; = ar if the inversion parity of ar in the path is even and 2; = Zj or the inversion parity of ar in the path is odd and Zt='z’.. 3 J = 3 otherwise. r Definition 2.3 A gfliteral L = is a path set which has an input literal Xi as its first element. 13 From the above definitions that we know we can divide the g-literals and the path sets of a network into two disjoint subsets, one which possesses overbarred output literals, while the other does not. We shall call the latter "gl-literals" and "pl-path sets", the former "go-literals" and "pO-path sets". Example 2.2 For the single output network of Figure 2.3 we list all pl-path sets in Table 2.1(a). The pl-path sets of (a) which are also gl-literals are listed in Table 2.1(b). All po-path sets and all go-literals of the network are just their counterparts with all elements complemented. An input literal, an output literal or a lead label is overbarred if and only if it is complemented. Figure 2.3. A Combinational Logic Network which Realizes XlXZX3 + XIX2 + X1X3. 14 Note that a lead label may appear in several path sets and g-literals. Whether a particular label is complemented or uncomplemented depends on its inversion parity and the output literal of the path set or g-literal. Table 2.1. All pl-path Sets and gl-literals for the Network of Figure 2.3. (a) All pl-path Sets for the Network of Figure 2.3. L1 = <9,Z> L13 = <2,4,4a,7,9,z> L2 = <7,9,z> L14 = <3,4,4a,7,9,Z> L3 = <8,9,z> L15 = L4 = <1a,7,9,Z> L16 = <4,ZE,6,8,9,2> L5 = <4a,7,9,z> L17 = L6 = <5,8,9,z> L18 = L7 = <6,8,9,z> L19 = L8 = L20 = <§,Z,‘B,6,8,9,z> L9 = <4,4a,7,9,Z> 1.21 = <3,4,4—,6,8,9,Z> L10 = L22 = L11 = L23 = L12 = (b) Pl-path Sets of (a) which are Also gl-literals. L12 = L19 = L17 = L22 = L18 = <3,3,4, 4a, 7, 9, Z> L23 = 15 Since the purpose of introducing g-literals is to facilitate the study of faulty logic networks, it will be useful to assign the functional equivalent to a g—literal under the fault conditions of interest. Definition 2.4 A g-literal L = has a functional equivalent L(F) which depends upon the fault F which is present: L(F) = X3°a1/N'a2/N° ... -an/N * o o o + al/l a2/N ... an/N * o o o + al/O aZ/N ... an/N * o o o + a2/l a3/N ... an/N * o o o + a2/0 a3/N ... an/N + O O O + 33/1 + afi/O where ak/l, ak/O and ak/N represent leadak stuck—at l, 0 and fault-free respectively. All faults are elements of F. From the above formal definition, we can make following observations: The functional equivalent L(F) of a g-literal L depends both on the current input vector and on the fault affecting the network and is 4 (l) The first element of L if L does not contain any lead affected by F. 16 a; = ak is the last element of L for which is an element of F. *=- ak ak is an element of F. is the last element of L for which Table 2.2 illustrates this concept for the g-literals of Table 2.1(b). Table 2.2. The Functional Equivalents of gl-literals Table 2.1(b). L12(F1’ L17‘F1) L18(F1) L12(F2) L17(F2) L (F ) 18 2 (a) Fl = 9 x1 ; x2 , x3 ; (b) F2 = Ma/0,5/l,7/0] O 3 0 7 O , Definition 2.5 A set Q of g-literals is a Zjli set of one given outputs Zj (l) (2) of network N if: L19(F1’ L22(Fl) L23(F1) L19‘F2’ L22(F2’ L23(F ) of II II XI XI u XI II II xl P‘ u xl of the The output Zj takes on the value 1 whenever the functional equivalents for every gl-literal in Q has value 1, and If any member of Q is removed, then condition (1) no longer holds. 17 Definition 2.6 A set Q of g-literals is a gj-O set of one of the given outputs Zj of network N if: (1) The output Zj takes on the value 0 whenever the functional equivalents for every gO-literal in Q has value 1, and (2) If any member of Q is removed, then condi— tion (1) no longer holds. Table 2.3 lists the Zj-l and Zj-O sets for the example of Figure 2.4. The subscript j in Z. -1 and z. -0 is Jlk Jrk used to indicate the set is one of the Zj-l and Z.-0 sets, respectively, while k distinguishes between the elements in Q. Derivation of these sets will be illustrated in the next section. ‘ X2 2 9 3 7a " x3 ’ 7b 10 A z1 X 4 11a 4 e ‘ s [ [ 11b '21:. I7 Figure 2.4. The Logic Network for Example 2.3. Table 2.3. 18 The Zj-l and Zj-O Sets for the Network of Figure 2.4. (a) Zj-l Sets for the Network of Figure 2.4. (b) 22,4” [, 2,2,Ta'6'9'12'zl>’ [, 4,10,11,11a,12,Zl>] (X3'3pv’7—a—I9112,z1>] [] ] [, 4,10,11,11b,13,22>] <23,§,7,7b,11,11b,13,z2>, , 1 2 [' ] 2)! [, 2 ] Zj-O Sets for the Network of Figure 2.4. [, , , 1 [, , <:;,§',II, 11a,12',2’>] [, ?'§, 11,111a,12,zl>, [: (X;I4Ilollllllallzlzl>l ] [<2",,,‘1"‘1‘B§,‘1‘3‘,,<2‘2'> 2‘232,,2’E,,'§T§2'231 [1 [, to the path set L' = (3;! ai, ... , a3,23> will be denoted as a;&L, i.e., L' = a;&L. We shall treat each fanout branch as a single—input OR gate and each NOT gate as a single-input NOR gate. Algorithm G (Generation of an Equivalent Boolean Expression) Gl: Given a network N with primary input and network output literals, assign distinct labels to each lead of the network using Procedure L. 62: Form a pl-path set Ej for each of the m network outputs zj. Each path set contains only two elements, the first element is a network output lead label and the second element is the corresponding output literal. G3: Let j = 1. G4: Choose all path sets which are not g-literals from the current Ej expression. (1) If no such path set can be found from Ej for all j, where j = 1,2, ... ,m then the collection of all Ej's is the desired network expression E. 21 (2) Process this selection of path sets one by one: Denote the path set under investiga- . = < * no. tion by Lr ak: a* Z?>. In!) Replace all path sets in current E expression which have the same a* as Lr by a subexpression k formed according to the appropriate rule as follows: If ak is the output from and 1f ak in Lr appears Non—overbarred Overbarred AND gate R1 OR gate or fanout stem R2 NAND gate R3 NOR gate or NOT gate R4 R3 R4 R1 R2 Rules: In each of the following rules, let s be the number of leads which are the inputs to the gate or the fanout branches. The subexpression is R1: The conjunct of s new path sets, Li R2: The disjunct of s new path sets, Li - R3: The disjunct of s new path sets, Li ll OJ p. 2’ L'" '1 R4: The conjunct of s new path sets, Li - — where i = 1,2, ... ,s. (3) If j = m go to G5, otherwise by 1 and go to G4. increase j G5: Repeat G3 until all path sets in each Ej expression are g-literals. 22 Example 2.3 Let us use Algorithm G to construct an equivalent Boolean expression for the network of Figure 2.4. Step Gl: We label the leads of the network by Procedure L of Section 2. > for E . Step GZ: Form <12,Z 2 2 > for E and <13,Z 1 1 Step G3: (a) At the end of first iteration, we have I?! II <9,12,Z > + <1la,12,Z > 1 >'<8,13,22> 1 <11b,13,z I'll ll 2 (b) The result of the second iteration is E = <‘6‘,9,12,z >-<7§,9,12,z > + <11,11a,12,z > 1 > + <2b,8,13,22>) 1 1 E = <11,11b,13,22>°(<1b,8,13,Z2 (c) Beginning with the third iteration, we can take advantage of the fact that 21 and 22 share some degree of input circuitry and save some effort in the path set expansion process. At the end of the seventh iteration, we get E1 = (<fi,I,1‘5,€,9,12,zl> + <23,7,§'5,3,9,12,zl>) ° + 1 ° 4' 1 5,11,11a,12,Z > + ' + ) E2 5,ll,llb,13,Z2>) ° + which is not generated by Algorithm G. At Step G2 we form a set of two-element path sets which includes path set LS = . By Step G4, Ls will be chosen and expanded into three-element path set. Since no input lead has been neglected, one of them must be path set . If this is a argument we will generage gl-literal Li which contra- dicts our assumption. Hence all gl-literals of the network are generated by Algorithm G. Since each lead is labeled distinctly by Step Cl, and a u-element path set can only be expanded to (u+l)-e1ement path sets in one of the following three cases: (1) Expanded to distinct labels from the same path set for AND, OR, NAND and NOR gates. (2) Expanded to the same label from distinct path sets for fanout. (3) Expanded to a label from a path set for NOT gate. Hence all the path sets generated by Algorithm G are distinct from one another which implies each gl—literal in the resultant expression E appears exactly once. 25 The fact that all path sets appearing in the final expression are gl-literals is guaranteed by Step G4. Q.E.D. Theorem 2.2 Algorithm G transforms a given network structure into a Boolean expression which accurately and com- pletely describes the logical structure of the network. 23.22: The path set expansion rules used in Algorithm G are exactly the logical operations of elementary gates. The logical structure of the network is accurately described in each step of the algorithm by applying the prOper rule to each elementary gate and fanout point. The completeness of the final Boolean expression is guaranteed by Theorem 2.1. Q.E.D. Theorem 2.3 The Boolean expression E generated by Algorithm G is isomorphic to the physical structure and its corresponding input-output literals of the network to the level of interconnected gates. Proof Our labeling procedure completely and distinctly labels the physical structure of the network to the 26 level of fanout points and interconnected elementary gates. The rules used in the generation of E are the logical operations of fanout point and elementary gates. For each gl-literal Lr = we can find an input literal Xi together a2. The lead a must be a fanout branch of al or the 2 output lead of an elementary gate for which al is one of the input leads. Trace the elements of Lr one by one, we will finally find that an is a network output lead and Zj is the corresponding output literal. Thus, we have a physical path for each gl-literal in Expression E. For each physical path we can also find, using a similar argument as the proof of Theorem 2.1, a distinct gl-literal which describes uniquely and completely each lead in the path together with the input and output literals associated with the path. Q.E.D. 2.3.2 Reduction of Boolean Expression E to CGEM Form The second step of the construction of CGEM is to change the Boolean expression E of the network to a two- level sum of products expression E'. Example 2.4 Find the sum of products expression E' for the network of Figure 2.4. 27 Starting with Equation (3) of Example 2.3, only carrying it one step further using distributivity, we have >o 4II I I I2 1 3(3'7'77-5.’9'12,Zl> + - 5,11,11a,12,Zl> E' = -- {11 II 4I I I I2 + X111,1b, 8, 13, Z 5,11,11b,13,Z > 2 5' 2 2,2,2b,8,13,z2> ' > is fj= which is also a g-literal. Note that Definition 2.9 does not conflict with Definition 2.4 of Section 2.2. Since the complement of a g-literal L is a g-literal E with all elements of L complemented, the complement of a gl-literal is a go-literal and vice versa. We have defined the functional equivalent for a g-literal and it is not difficult to see that the func— tional equivalent of a Boolean expression of g—literals is just the Boolean expression of the functional equivalents of individual g-literals. Lemma 2.1 For a g-literal L = we have (L + E) (F) = 1 and (L'f)(F) = 0. Proof (L + E)(F) = L(F) + EKF) (x; + XE).a1/N.a2/N. ... .an/N + (ai/l + Ef/l)-a2/N-a3/N- ... °an/N + . o . + (ag/l + 5:71) + (aa/O + 5:70) 29 = (al/N + ai/l + ai/l + ai/O + ai/O) -a2/N° ... -an/N :I ‘1’ 'k “i? + az/l + a2/l + aZ/O + a2/O) °a3/N° ... °an/N + o o o + (as/1 + 33/1 + ag/o + Ei/O) (l) The first term of (1) equals to a2/N- ... ~an/N, this term disjuncted with the second term makes it a N-a4/N- ... -an/N. Continuing the operation we 3 * ’i * ‘7' ° ' will have an/N + an/l + an/l + an/O + an/O Wthh is l. (L-f)(F) = L(F)°E °'_ >° + - Complementing Eq.(2) of Example 2.3 of Section 2.3 and reducing it to the.sum of products form, we get E5 = “I'IE'E I3, T2 > + <§:,I,I6,II,IIE,I§,E; >~<§§,§,II,IIB,I§,E§> 31 The required expression is - — — T u: I I E (E1 E2) zj-o sets and GEMj-O sets of Figure 2.4 are listed in Table 2.3(b) and Table 2.4(b), respectively. Inspecting Algorithm G we can find that if we start with two-element pO—path sets at Step G3, call it Algorithm 6', we will end up with Boolean expression E. The following three theorems are the duals of Theorems 2.1-2.3 which we state without proof. Theorem 2.1' All go-literals for the combinational network are generated by Algorithm G'. Each appears in the resultant expression E exactly once, and all path sets appearing in the final expression are go—literals. Theorem 2.2' Algorithm 6' transforms a given network structure into a Boolean expression which accurately describes the complement of the logical structure of the network. Theorem 2.3' The Boolean expression E generated by Algorithm 6' is isomorphic to the physical structure and its corresponding input-output literals of the network to the level of interconnected gates. 32 2.5 CHAPTER SUMMARY AND REMARKS An algebraic network model which describes accurately and completely the physical and logical structure of an object logic network has been rigorously presented. It is a substantial extension of GEM of Reese and McCluskey, even though the name of their model is adopted. The differences between our model and theirs are: (1) Our model is for multiple—output logic networks, theirs for single-output networks only. (2) We added the rigorous definition of the complement of the Boolean expression of g-literals, without which the other side of the logical structure remains untold. (3) The functional equivalent of a g-literal is formally defined in our model. With this, the detailed information of a faulty network can be rigor- ously investigated. One may note that we mentioned nothing about the complemented input literals. This would not impose a serious restriction on the model since either the comple- mented inputs can be generated by the network or we can rename the input provided by the system. By substituting the functional equivalent of Defini- tion 2.4 for the corresponding g-literals in the expressions E and E, one can have more information about the logic network than that obtained by Poage's method. Finally, with all lead labels and output literals dropped from the Boolean expressions of g-literals we have the simplified cause- effect equations of Bossen and Hong [3]. CHAPTER 3 FAULT FUNCTIONS 3.1 INTRODUCTION In this Chapter we shall deal with fault func- tions and related topics. A fault function is a Boolean expression of input literals that a logic network realizes under the influence of a fault. In addition to stuck-at type fault we shall discuss how to find fault functions for several kinds of bridging faults. The difference between the fault-free function and fault function provides the tests. So, for a given fault we can first find the fault function, then a set of tests that detects the fault. If we have a complete test set and a fault function, we can also either find the corresponding fault set or decide that the network can not realize the given fault function. 33 34 3.2 FAULT EggIVALENCE The immediate application of the model developed in Chapter 2 is the determination of the fault function E(F) realized by the network in the presence of fault F. Since two different faults F1 and Fj may result in the same fault function, it will be convenient to put these two faults in a set and deal with the whole set or its representative in the studies of faulty logical networks. Definition 3.1 Two faults Fi and F3. in a logical network are said to be functionally equivalent, written as Fi"Fj' if and only if their fault functions for that network are identical, i.e., Pi ~ Fj <=> E(Fi) = E(Fj). Example 3.1 For the network of Figure 2.3 we have E = -- 1' 2' 3' + -( + <}'('3,3',I,IB,6,8,9,Z>) Consider two faults: Fl = 4b/0 and F2 = 6/1. The fault functions are E(F1) = X1X2X3 + Xl 35 Hence F1 and F2 are functionally equivalent in the network. The functional equivalence of faults is an equivalence relation which partitions the collection of all possible faults PI of a logic network into disjoint fault classes. Definition 3.2 A logic network is said to contain a redundant fault if and only if there exists a fault F1 6 PI such that i f O and Fi ~ F0, where F0 contains no fault. Example 3.2 In Figure 3.1 the logic network is a realization of Boolean function zB = xlx2 + x2x3x4 which has E' = -- 2' + <.X1,1,7,9,z>'(22,7,E,7,9,Z>“(X3p31616317191Z> + -<§<’ 5,5,7,9,z>- 2' 4' + <22,§,75,3,33,8,9,z>-<25,§,E}35,8,9,z> -<§A,I,§,§E}8,9,Z> For fault Fl = 6a/l the fault function is ' _ _ _._._ E (F1) - XIX2 + X2X3X4 - I _ "' "" "' "" — _. Since E (Fl) .- X1X2X3 + x1x2x4 + X2X3X4 - ZB we have F1 ” F0 which implies the logic network is redundant, i.e., it contains redundant faults. 36 The redundant faults cannot be detected. This fault-masking property has been used in designing logic networks where continuous operation is required for a specified length of time and repair is impossible. In general, the existence of redundancy can not be readily identified. The detection and location of redundancy usually are the by-products of test generation. Figure 3.1. The Logic Network for Example 3.2. Note that the fault 6a/0 in the above logic network can be detected. 3.3 GENERATION OF ALL POSSIBLE FAULT FUNCTIONS Given a logic network we can find all possible fault functions and associated fault classes by assigning all combinations of the single faults of the network. The possible fault functions are the collection of all distinct functions that the network degenerates into and each fault 37 class contains all faults of the same fault function. But, the astronomical number of all possible combinations of the single faults makes the enumeration method impractical. Before the presentation of a straightforward method for the generation of all possible fault functions, we first establish an upper bound on the number of fault functions a given logic network can possibly have. Theorem 3.1 The number of fault functions NF for a logic network is bounded by i N m 2 X m G + 1)] < o NF - Min [(2 ) , igl (2 where Nx is the number of input literals, m the number of output literals and G1 is the smaller number of the numbers of g-literals in E1 and ii. Proof 2Nx . . . There are only 2 distinct functions of Nx binary variables which any single output logic network can possibly realize. Hence, for a m-output logic net- N work NF 5 (22 x)m. For a Zi k-l term which has G; gl-literals we can I delete none, 1, 2, ... up KDG: - l gl-literals by substituting l for the gl—literals under consideration. We can also delete a 2i k-l term by assigning 0 to it. I If all the gl-literals in the term are distinct we Gi Gi have H2 k = 2 k ways of deleting gl-literals from a 38 Bi expression. In addition, any term in Ei which has a functional equivalent of 1 will drive output 1 Zi to 1. Thus, we have (2G + 1) distinct fault functions for output 21. Since there is a one-to-one correspondence between the fault functions of Bi and E5, the total number of fault functions for a network will be bounded by using ° l the smaller number of 61's from each pair of E; s in our computation. The arguments for E; parallel those of Bi in preceding two paragraphs. Q.E.D. Example 3.3 For the logic network of Figure 2.4 we have N = 5; m = 2; cl = Min (7,10) = 7 and N G2 2 X 19 Min (14,6) = 6. Since (2 ) g 2.97 x 10 and l 2 + 1)(2G + 1) = 8,385, the upper bound for the <2G number of fault functions for the network is 8,385. The bound computed from the number of input literals is very loose even for a moderate size, single output logic network. It is interesting to note that the number of all possible combinations of the single faults of the illustrative network is 321, approximately 1010. Directly from Definition 2.4 we can find functional equivalents of a g-literal and the Boolean expression of g-literals under a given fault set. When we want to find all possible functional equivalents, i.e, fault functions, 39 of a logic network, we simply let fault set F be unspecified and substitute the functional equivalent of each g-literal into the expression E, then reduce it into the sum of products form. Definition 3.3 The range of a Boolean expression of g—literals, written as R(-), is the disjunct of the conjunct of all possible fault functions of the expression over their corresponding fault sets. Example 3.4 The range of the term 2 '1 = - is 1 3' iiX3°(l/N°la/N°3/N'6/N-7/N-7a/N-9/N-lZ/N) + xi-(1/N-1a/N-3/1-6/N-7/N-7a/N-9/N-12/N + l/N °1a/N'3/N-6/N'7/0°7a/N‘9/N°12/N + l/N-la/N-B/N-G/N-7/N-7a/0-9/N-12/N) + X3°(l/0°la/N'3/N°6/N'7/N'7a/N°9/N'12/N + 1/N-1a/o-3/N-6/N-7/N~7a/N-9/N-12/N f l/N°la/N°3/N°6/O-7/N°7a/N-9/N-12/N) + 1-(i/o-ia/N-3/1-6/N-7/N-7a/N-9/N-12/N + 1/0'1a/N°3/N-6/N-7/0-7a/N-9/N-12/N + l/O'la/N'3/N'6/N'7/N°7a/0°9/N°12/N + la/O'3/1-6/N-7/N'7a/N'9/N'12/N + la/O°3/N°6/N°7/O°7a/N°9/N°12/N + 1a/0-3/N-6/N-7/N°7a/0°9/N'12/N 40 + 3/1'6/0'7/N'7a/N°9/N°l2/N + 3/N'6/0'7/0'7a/N'9/N'12/N + 3/N°6/0'7/N'7a/0'9/N'12/N + 9/1'12/N + 12/1) + (l/l'la/N'3/N'6/N°7/N'7a/N°9/N'12/N + la/l'3/N'6/N'7/N'7a/N°9/N'12/N + 7/1'7a/N°9/N°12/N + 3/O°6/N°7/N°7a/N-9/N’12/N + 7a/1°9/N'12/N + 6/1°7/N°7a/N°9/N'12/N + 9/0-12/N + 12/0) Investigating the above result we conclude that any fault that affects the 21.1-1 term will transform it into one and only one of the five possible fault functions. The computation of the ranges for Bi and E' is a trivial extension. The fault set associated with each fault function con- tains the representatives of the fault class. Any combina- tion of the single faults of a logic network that satisfies one fault in the fault set will transform the function realized by the network into the associated fault function. For example, there are approximately 3.5 x 109 combinations of the single faults which include lzd.that cause output Z of the network of Figure 2.4 to be stuck-at l. l 3.4 BRIDGING FAULTS While the stuck-at type faults deal with individual leads, bridging faults are concerned with the connection of two or more leads of the logic network. 41 Definition 3.4 A bridging fault is a short circuit between two or more leads of a logic network and wired logic is performed at the point of connection. We shall limit our studies to single two-lead bridging faults. The wired logic function is assumed to be either a wired AND or a wired OR. If a bridging fault affects two leads on the same path in a lOgic network, it is a feedback bridging fault. A non-feedback bridging fault can affect at most one lead on i one path. In order to find the fault function of a logic network under a non-feedback bridging fault, we can (1) express the network output E'(Fo) in terms of primary inputs and the lead variables of faulty leads. We call this the decomposition of the network output with respect to the lead variables; (2) express the lead variables of faulty leads in terms of primary inputs; (3) combine these lead variables with proper wired lOgic and substitute the result into the lead variables in the decomposed network output. The first two steps of the preceding procedure can be carried out by first treating the faulty leads as primary input leads to the succeeding part of the network and letting the unaffected portion remain unchanged, then as the network output leads of the preceding part of the network and dropping the remaining portion from consideration. 42 Since the Boolean expression E' of the g-literals of a logic network can be regarded as a network output expres- sion, one may want to know what is the decomposition of E' and how it helps us in finding the fault function realized by a logic network under the influence of a bridging fault. Definition 3.5 The decomposition of the Boolean expression E' of the g-literals of a logic network with respect to the lead variable Yi of lead i is obtained by: (1) W-OA-r-uiwm 110 W . Replacing the g-literals which have the form by , where the inversion parity of Yi is the same as that of lead 1. (2) Keeping the other g-literals in the expression unchanged. Let Bi denote the decomposition of E' with respect' 1 to Yi' It is not difficult to see that E; (F0) is indeed i the decomposition of the network output E'(FO) with respect to Yi. Since for a g-literal which contains no i* as one of its elements, it cannot be decomposed with respect to Yi and its effect on the network output remains unchanged. For a g-literal containing i*, the effect of lead variable Yi on the network output depends on the inversion parity of lead i. To express the lead variable in terms of the network primary inputs we can construct a Boolean expression for an 43 isolated portion of the network as pointed out, or obtain it from the E' expression of the network as follows: Lemma 3.1 The lead function Yi for lead i can be determined from the Boolean expression E' of the g-literals of the logic network by the following procedure: (1) For each 2. .-1 term which contains no (2) (3) Proof 1:] g-literal which has i* as one of its elements, replace this term by O. For each zi’j-l term which has at least one g-literal contains i*, replace each such g-literal by the correSponding input literal, replace the other g-literals in this term by 1. Set the result equal to Yi if i is non-overbarred, I: otherwise. Simplify the resultant expression by Boolean rules. Since only the inputs of the g-literals which have i* as one of their elements can have the effect on the lead variable Yi' all other g-literals can be neglected in the evaluation. We have to find Yi and Y: separately and treat i and I independentlybecause by definition i cannot generate ii and i cannot generate Yi' 44 While the stuck-at type faults have the effect of simplifying the logic topology, the bridging faults introduce connections and wired gates to the network and complicate the network topology. Definition 3.5 and Lemma 3.2 were established for a single lead. When two leads are involved as the case of bridging faults, we can deal with both the affected leads at one time if no g-literal contains more than one faulty lead, or decompose E' with respect to the lead variable whose lead is closer to the primary inputs, then subject 3". IF‘v—J—é‘ ..._,T.Z..‘ the decomposed expression to be decomposed with respect to another lead variable if two leads in the same g-literal are connected. Example 3.5 We denote wired AND between lead 1 and lead j by B(i-j) and wired OR by B(i + j). For the logic network of Figure 2.3 the fault function due to the presence of bridging fault F B(lb°6) can be 1 computed as follows: From Example 3.1 the sum of products expression of g-literals is E' = o 2' ‘(X 3,4,43,7,9,Z> 3’ + (x1,1-,IB,5,8,9,z>0(22,2,I,m,6,8,9,z> + - 45 (a) Since no g-literal contains both lead lb and lead 6, we can decompose E' with respect to Y and Y lb 6 at one time. The result is Eélb'YG = - - + -. The decomposed network output is ' _ _ E (F0) - X1X2x3 + YlbYG (1) Y1b'Y6 The lead variables in terms of primary inputs are found to be Y1b=XlandY6=X +X The output of the wired gate is Y=Y~Y=xi+xx (2) 9 lb 6 l 2 l 3 Substituting (2) into Y11) and Y6 of (l), we get the fault function El (b) We can also treat one lead at one time. The results are Eélb = ' - 3! 46 + E,5’8'9,Z>.<-x_2’§’.4-'ZB,6'8,9’Z> - lb' (4) E96 = ' ° + <§i,I,IE,5,8,9,Z>- ,6,8,9,z> (S) If we either decompose (4) with respect to Y6 or decompose (5) with respect to Y b' we will obtain 1 the same result as that of (a). The order of decomposition in the case of non-feedback bridging is of no importance, e.g., E' = E' . Ylb’Y6 Y6'Ylb A feedback bridging fault can be classified as inverting or non-inverting depending on whether the lead labels in the g-literal have different inversion parities or not. The following example will demonstrate how to find the fault functions caused by feedback bridging faults. Example 3.6 The logic network of Figure 2.3 will be investi- gated further in this example. (a) The bridging fault F = B(4-7) is non-inverting 2 because both lead labels in the second and the third g-literals of the first term of expression E' (see Example 3.5) have the same inversion parity. 47 Since lead 4 is closer to the primary input, we have to decompose E' with respect to Y4 first. E§4 = ° - + <§i,I,IE,5,8,9,z>o (1) E; (F0) = X1Y4 + iiY4 (2) .5 L“? Y = x x (3) Then, we decompose E; with respect to Y7 4 121'"; A“. E' = + o (4) Y + x Y4 (5) 3' (F0) = 7 1 Y4,Y7 Y = x Y (6) 7 l 4 The first wired gate output after the application of the primary inputs is Y =X 91 XX Let the superscript s of E; Y (F?) denote 4, 7 the sequence of output under the influence of bridging fault F2. Substitute (3) into Y4 of (5) and (6), then (6) into Y7 of (5), we have . _ _ _ BY Y (F ) - xlx2x3 + xlx + x (8) 4’ 7 X 2 l 3 which is the fault free output of the network. (b) 48 Since the wired gate output will remain at 4 and Y7 of (5), we get the right hand side of (8) again. (7), substituting (7) into both Y This implies (8) can be regarded as the required fault function. The fault F2 happens to be undetectable. ,P' The fault F3 = B(lb-8) is an inverting feedback bridging fault since lead lb and lead 8 have ‘3 different inversion parities in a g-literal of E'. ‘t‘f‘m‘m‘m ”m After a few computations, we have EYlb(Fo) = x1X2X3 + n¥2 + (n52 (1) Ylb = x1 (2) Eélb’Y8(Fo) = X1x2x3 + Y8 (3) Y8 = ilbszz + rug (4) Y9 = YlbY8 (5) The first output of the wired gate is obtained by first substituting (2) into Ylb of (4) and (5), then (4) into Y of (5), i.e., 8 Ygi = 3fx1xz + X1X3) = 0 (6) Substitute (6) into Y8 of (3), we have E' (F1) = x x x (7) Y 3 l 2 3 lb'Y8 49 The wired gate output will remain at (6), which in turn keep the network out at (7). (7) is the required fault function. In the above examples, all three bridging faults generated no sequential dependency in the logic network. In some cases, we may have to compute the network output for a number of feedback periods to establish the fault functions. fi‘mu—w ‘ ‘1 It is interesting to note that bridging fault F1 of [QT V" .‘V._)' r. ~ Example 3.5 is equivalent to bridging fault F3 of Example 3.6. Furthermore, the logic network of Figure 2.3 is redundant with respect to bridging faults since fault F2 of Example 3.6 cannot be detected, even though it is (irredundant when only stuck-at type faults are considered.' 3.5 DIRECT DIFFERENCE AND TEST GENERATION A fault in a logic network can be detected only if it causes the network to realize a function, called the fault function, which is different from the intended function, i.e., fault-free function. A fault can be located, to the level of interest, if it can be detected and the differences between this fault and all other faults of the network can be identified. 50 Definition 3.6 The direct difference Dij of fault Fi and fault Fj is B(Fi) G E(Fj), the exclusive-OR of the respec- tive fault functions. The solution of Doj = l is the test set which detects the existence of fault Fj. A set of input vectors which covers the solutions of Doj = l for all j # O of the network is a complete detection test set. A set of input vectors which covers the solutions of Dij = l for all i,j of the network and distinguishes each pair of the solutions is a complete location test set. Example 3.7 The logic network of Figure 2.2 (p. 11) realizes a ' - — .- the function E (F0) - xlx2x3x4 + X1X2X3X4. The Boolean expression E of the network is E = ('(23,3,33,5,8,12,z> + ) (x1,1,1b,'§,12,z> + <3E2,§,'2‘B,§BE,6,6a,'9’,12,z>.<23,§,§'5,'3'5T5,6,6a,§,11 ,z>) (<‘i2,§,‘5,7‘5,6,6b,1o,12,z> ~<§3,'§,‘E,?5‘,6,6b,1o,12,2> + ) (<‘i2,§,T,TB,7,‘I,12,z>o<§4,Z,Z'B,7,11,12,z> + ) For the fault Fl = 6/0, we have B(Fl) = x1x2x3x4. The solution of D01 = E(F0) 6 B(Fl) = X1X2X3X4 = l is 51 0000. This is the only input vector which can detect the existence of the 6/0 fault. To use the direct difference method in test generation, we have to know the fault sets, the fault functions, and the corresponding direct differences. This makes it impractical for the generation of complete test set. However, this method is still valuable in generating test set for a smaller number of the faults of particular interest, such as the 6/0 fault of above example and the bridging faults discussed in Section 3.4. The generation of a complete test set for a logic network will be discussed in Chapter 4. 3.6 IDENTIFICATION OF FAULTS Given a fault in a logic network we can find the corresponding fault function simply by substituting the functional equivalents of the g-literals into the Boolean expression E of the network. Conversely, given a fault function we can find the associated fault set if we have a complete test set for the network. Before we proceed to describe a procedure to find the required fault set, it is worth noting that if the range of the Boolean expression E is already found, the problem reduces to the identification of the fault function which conjoined with the associated fault set is a term of the range. -If we want to know whether there is a fault which 52 generates a particular fault function, the procedure is exactly the same except if there is no such fault the search of the fault function in the range will fail. Instead of computing the range of the Boolean expres- sion E then identifying the fault function to find the fault set, we can: (1) Substitute each g-literal in Ei by the range of the corresponding g-literal, then set the result equal to the fault function Ei(F). (2) Evaluate ; both sides of the m equations by a complete test set which contains t input vectors. (3) Solve the set of mt “W..." .-. . simultaneous equations. The solution is the required fault set. If there is no solution, we conclude that the logic network can not degenerate into the given fault function. The above procedure is straightforward and can be machine implemented. But to deal with every lead of the logic network the job will be enormous even for one of moderate size. Looking for the ways of simplification, we have the following theorem. Theorem 3.2 Any multiple fault in a combinational logic network can be represented by a combination of the faults in the distinct g-literals of the network. Proof From Chapter 2 we know each g-literal of the Boolean expression E generated by Algorithm G is 53 distinct. The expression E describes accurately and completely the logical and physical structures of the network. The effects of a fault on E, hence the network, is the Boolean expression of the effects of the fault on the distinct g—literals. Q.E.D. Since a g-literal can assume only one of the three states as a lead in the network, it will be convenient to assign a distinct number to a distinct g—literal and treat the simplified g-literal as a single lead g—literal. ' . 'L ".'-. 0 ‘d UWs*““*—“r1"* Definition 3.7 The simplified g—literal of a g-literal L = is the three element gmliteral L8 = , where A is a number representing the sequence of lead labels in L and it is overbarred if z; = 23' non-overbarred otherwise. In the above definition we treated the distinct g-literals in E as the complements of their counterparts in E. The Boolean expressions of the simplified g-literals will be denoted by the corresponding notations, with subscript s, used for the g-literals, e.g., Es' Eis' The range of the simplified g-literal L8 = is R(Ls) = XE-A/N + A*/l + A*/0 where A/N = al/N- ... -an/N, A/l = ai/B1°a2/N- ... -an/N + ... + an-l/Bn-l'an/N + afi/Bn where Bk = 1 if afi = ak, 0 otherwise. A/O = ai/C1°a2/N- ... -an/N + ... + a;_1/Cn_1'an/N + ag/Cn where Ck = 1 if a* = k 3*, 0 otherwise. Note that A71 = A/0 and 370 A/l. 54 Example 3.8 For the logic network of Figure 2.3, we find the fault set associated with the fault function B(F) = X1. Referring to Example 3.1 for the E expression of the network, assign l to 6 sequentially to each of the six distinct g-literals. Substitute the range of each simplified g-literal in the expression and set it equal to the fault function. We have (xl-l/N + l/l)(X2-2/N + 2/1)(X3-3/N + 3/1) + (fl-4m + 4/1) ((X2.5/N + 5/1) + (553-6/N + 5/1)) = X (l) l The set T = (001, 010, 011, 101, 111) of input vectors is a minimal complete detection test set for the network. Evaluating (l) by the elements of T, we get l/l°2/l'3/N + 1/1-2/1-3/1 + 4/N-5/N + 4/N-5/1 + 4/1-5/N + 4/1-5/1 + 4/N-6/1 + 4/1-6/1 l/l-Z/N-3/1 + 1/1-2/1-3/1 + 4/N°5/l + 4/105/1 + 4/N-6/N + 4/N°6/1 + 4/1-6/N + 4/106/1 = 0 (3) l/l-2/N-3/N + 1/1'2/N°3/l + l/l-2/1'3/N + l/l°2/l°3/l + 4/N°5/l + 4/l°5/l + 4/N'6/l + 4/1-6/1 = O (4) 55 l/N'2/1'3/N + l/N'2/1'3/1 + 1/1'2/1‘3/N + 1/1'2/1'3/1 + 4/1'5/N + 4/1‘5/1 + 4/1'6/1 l/N-Z/N'B/N + l/N°2/N'3/l + l/N°2/l'3/N + 1/1'2/N°3/N + l/N°2/1'3/l + l/l'Z/N°3/l + l/l°2/l°3/N + l/l-Z/l-B/l + 4/l°5/1 + 4/1-6/1 = l (6) The simultaneous solution of (2) to (6) is P8 = l/N-2/l-3/l-(4/0 + 5/0-6/0) (7) for the simplified g-literals which implies F = 4/1-(1b/l + 5/0 + 8/0 + 4b/l + 6/0) + 4a/l-(lb/l + 5/0 + 8/0 + 2/1-3/1 + 4b/l + 6/0) for the leads of the logic network. If the fault function is B(Fo), the fault free func- tion, the solution for the simultaneous equations may contain just one situation, i.e., all leads are normal, which implies the network is irredundant. If the solution contains situations other than all leads are normal, the network is redundant and the extra solutions tell exactly where the redundancies are. 3.7 CHAPTER SUMMARY AND REMARKS Through the fault equivalence defined in Section 3.2, we can treat the faults in fault classes instead of as individual faults. The upper bound on the number of possible 56 fault functions established in Section 3.3 gives us a rough idea how tedious it will be if we have to consider each fault function separately. However, we have a machine implementable procedure to find all possible fault func— tions and the associated fault sets. The feedback bridging faults not only can be identi- fied as suggested by Flomenhoft ep_al. [15], but the fault functions can also be computed as demonstrated in Section 3.4. In Section 3.5, we discussed how to find a test set if the fault function can be found. From a given fault we can find the fault function, conversely, given a fault function we can identify the associated fault set. For the faults which are essentially indistinguishable, we certainly do not have to compute their fault functions individually. In a network comprised of the elementary gates, they are: Gate Input leads ais Output lead aj AND any ai/O aj/O NAND any ai/O aj/l NOT ai/O aj/l OR any ai/l aj/l NOR any ai/l aj/O NOT ai/l aj/O :II’ III.) ‘Iu,ll’.] 57 In solving the simultaneous equations of Section 3.6 we can use the cubic intersection: a/O a/l a/N X a/O a/O 0 fl a/O a/l fl a/l fl a/l a/N g p a/N a/N X a/O a/l a/N X where 6 denotes empty and X denotes don't care. We can use the machine to solve a large set of simultaneous equations, but for a small number of equations solution by inspection may be faster. CHAPTER 4 TEST GENERATION 4.1 INTRODUCTION The Complete Gate Equivalent Model and its various forms will be used.h1this Chapter for the generation of complete test sets for the combinational logic network. Four algorithms for generating near minimal complete test sets will be discussed. The first two will be for multiple and single fault detection. The other two are the direct generalizations of the first two to fault location. A method of searching for a minimal complete test set for an irredundant combinational logic network also will be presented. 4.2 GENERATION OF NEAR MINIMAL COMPLETE DETECTION TEST SETS The generation of a complete test set for detect- ing stuck-at type faults in a combinational logic network will be accomplished in two steps: (1) Generation of a near minimal set of terms that detects all detectable faults. (2) Finding a minimal covering of the terms generated. 58 59 4.2.1 Generation of a Near Minimal Test Set which Detects AII Faults’in a Combinational Logic Network In the sequel we shall call E' under the fault free condition, but without any Boolean simplifications a simplified E' expression and denoted by E". The notation “-10 0: _ll II_ |:__ - ' E , Ei , Ei , zi,kl and Z1 ko W111 be used for their counterparts in E' and E'. A Z"-l or Z"-0 term is said to contain a conflict pair if it has xiii as its member. ' !l__ II_ ° A growth in a zi,k1 or 21 k0 term is the enlargement of the set of nodes covered by the term on the N-cube, caused by the presence of some faults. A shrinkage of a Zi'El or Zi'ip term is the reduction of the set of nodes I I covered by the term on the N-cube, caused by the presence of some faults. In the descriptions of the algorithms and the procedure in this Chapter, the alternative arguments will be put in the parentheses. Algorithm MFD (Multiple Fault Detection) Data required for this algorithm are the expressions E", E“, E'(Fo) and E'(FO). 1: Select either Ei' or E;' which contains the smaller number of input literals from each of the m primary outputs of the network. If both Ei' and E1' have the same number of input literals, choose one arbitrarily. 5: 60 o:__ I: ° 0: —ll - Separate zi,k1 (Zi;E0) terms in E (E ) into two different sets such that one contains the terms which have conflict pairs and the other does not. For those Z!'—l (Z!'—0) terms which contain no i,k i,k conflict pairs (a) Let i = l. (b) Compute _ II_ '71—:— Mu - (zi,kl) H (Zi,jl) all jfik (Mu = (255:0) n W - )) all jfk If Mu is nonempty put it in set M. (c) Repeat Step 3(b) for all z!'-l (Z!'—0) terms i,k i,k - II —II in Ei (Ei ). (a) If no Mu computed in Step 3 for Ei' (Ei') is empty, increase i by 1 otherwise go to Step 5. (b) If not all Ei' (Ei') selected in Step 1 are investigated,go to Step 3(b) otherwise go to — Step 6. Set M now contains the terms which detect any shrinkage of the coverings of the I __ I selected Ei' s and E1' 3. Let there by s Z!'-l (Z!'-0) terms in set S whose i,k i,k Mu computed in Step 3 for Ei' (Ei') are empty. (a) Set n = 2. 61 (b) If n is greater than the number of terms in S, increase 1 by l and go to Step 4(b). ' ' II II (c) For all combinations of n zi,El (zi,E°) terms from set S compute M = Z (Ziz'fil) H (Z.|I-7-1$ u i,j k selected j not selected = I I_ -—I—l_'——- (Mu Z (zi’km n (2130)) k selected j not selected (d) Put all nonempty Mu's in set M, delete the corresponding Z"-l (Z"-0) terms from set S and increase n by 1 go to (b). Set i = l and j = 1. Now we compute the terms which detect the growths caused by the faults. Let W denote a Zizgl (2;:T0) term with one or more of its input literals replaced by l. (a) Replace one input literal in ziiji (ZiIEO) by l. (b) Compute M. 3 w n E (F0) (1) (Mj I W FIE (FO)) If Mu is not empty put it in set M. (c) Repeat (a) through (b) for all input literals in this term. 62 8 (a) If no Mu computed in Step 7 for a term is empty increase j by 1 otherwise go to Step 9. (b) If not all terms in Ei' (Eg') are investigated go to Step 7 otherwise increase i by l and set j = l. (c) If all selected Ei' (Ei') are processed, stop. Set M now contains the terms which detect the shrinkages and the growths of the coverings of the selected Ei"s and Ei"s or else go to Step 7. 9: Let there be t input literals in set T whose Mu's are empty. (a) Let q = 2. (b) If g is greater than the number of input literals in T, delete all the literals from T, increase j by l and go to Step 8(b). (c) Replace all combinations of q input literals by l and compute Mu by Eq. (1) of Step 7. (d) Put all nonempty Mu in set M, delete the corresponding input literals from set T, increase q by 1 go to (b). Theorem 4.1 A minimal single covering of all Mu's in set M generated by Algorithm MFD is a near minimal complete detection test set that detects all detectable faults in the logic network. 63 12°23. The functional equivalent of a g-literal affected by a stuck-at type fault can assume only one of the two values 1 or 0. The functional equivalent of a zi’k-l or Zi'k-O term will be 0, i.e. false if at least one of its g-literals has functional equivalent 0. This results in a smaller number of vertices covered by the output 21 or the complement of 21. Hence it is a shrinkage. The shrinkage can be detected only if it is not covered by the fault free realization and the growth caused by the same fault due to the common lead label appearing with different inversion parities in different g-literals. we computed the terms that detect the shrinkages which are not covered by the fault free realization in Step 3 through Step 5. The result, more than the least number of terms required for detecting all detectable shrinkages is generated. A term which contains conflict pairs covers no vertices originally, so we can neglect it in the generation of the terms which detect the faults that cause shrinkages. If a g-literal in a term has functional equivalent of 1, it causes this term to cover more vertices than the fault free situation. Hence it is a growth. A growth will be detected if it is not covered by the fault free realiza- tion. This implies a detectable growth has a nonempty intersection with the complement of the original function. 64 A fault will be detected if it contains a detectable fault of smaller size on the N-cube, whether it is a growth or a shrinkage. We took advantage of this property to terminate the algorithm. Step 1 is to ensure that a minimal number of computa- tions is required. The fact that a minimal single covering is a near minimal complete test set is because the terms for shrinkages are more than necessary and the terms for growths of the same input literal in different terms are not merged into one subset. Hence they may be covered more than once. Example 4.1 Find a complete test set that detects all faults in the logic network of Figure 2.4. First, we use Algorithm MFD to generate the terms which detect all faults in the network. Step 1: Referring to Examples 2.4 and 2.5, we select E" and E“ for the computations, where 1 II_._ "‘ " E1 — xlx3 + x2x3 + x3x4 + x5 (1) and —II=-_ "' """" E2 XIX2 + X3X5 + x4x5 (2) i ill") ‘I 65 Step 2: Since no term in Eqs. (1) and (2) contains conflict pairs, all the terms have to be investigated in the generation of terms which detect shrinkages. Step 3: The first iteration processes 4 terms of Ei'. M = X1X3(X5X3)(X3X4)X5 = X1X2X3X5 M2 = x2x2(xlx3)(x3x4)x5 = x1X2X3X5 M3 = x3x4(xlx3)(x2x3)x5 = X3x4x5 4 _ —. .— _. _ ..- M - x5(x1x3)(x2x3)(x3x4) — x1x2x3x4 + x3x4x5 Step 4: All Mu's computed for Ei' are nonempty, ". The result of the so we can proceed to consider'E'2 second iteration of Step 3 is: = X1X3X4X5 + X2X3X4Xs N M M = 1X2X3X4 + X X 5 ; 5 1 2 6 M7 = x1§3§4§5 + x2§3§43€5 All Mu's computed in Step 3 for E2' also are nonempty, so put them in set M and go to Step 6. Step 6: In order to compute the terms that detect the growth of the network function, we have to consider all terms regardless of whether they contain conflict pairs or not. For the problem concerned they happen to be all the terms we investigated so far. 66 Step 7: The fault free functions to be used in the following computations are —' - — —-—' ...-._..— E (F0) - xlx2x3xs + x1x2x4x5 + x3x4x5 and x i’x + x x + x i’x + x x I E‘2“?0’ 134 15 234 25 Step 8: Since all terms computed from each single growth of all terms selected are nonempty, the algorithm terminates without going to Step 9. From XIX3 we have M8 = x3 0 E'(Fo) = x1x2x3§s M9 = 21 n'E'(Fo) = iiiéifiis and From this term The Mu's obtained 362x3 M10 = x1X2"3"?5 7 M11 = 22§3§4§5 SE3X4 M12 = x1x2x3x4'525; M13 = Yflags x5 M14 = Eiwo) iiiz M15 = xiii-53% + x129‘s ’ M16 = iixziéx4 + xliéxs x3i5 M17 = xlxéx4§s + x2i5x4is M18 = xlx3x5 + x2x3x5 i4i5 M19 = x1i3x425 + x2§3x4is M = x i x + x i'x 20 1 4 5 2 4 67 A minimal set of input vectors that covers all Mu's generated is (00101, 01000, 01010, 01110, 10000, 10110, 11101, 1110) which can be found by row-column dominance and other covering techniques. In reading the example above, note that it is not necessary to compute M if we recorded the growth of each 14 term and found there is a detectable growth in Ei'. We also do not have to compute M and M if we note that the 10 19 3 direction and the X5 direction have been investigated. Although these observations are feasible growths into the X for hand computations the tradeoffs necessary for machine implementation remain to be assessed. Since the covering set is found for all Mu's, some vectors of the set may detect both the growth and the shrinkage. 4.2.2 Generationgf a Near Minimal Test Seplwhich Detects AII Single Faults in a CombinationaI Logic Network Algorithm MFD certainly will generate all terms that detect all single faults in the logic network, but for a possibly smaller set of terms and a smaller complete test set, we can simplify it by means of the single fault assumption. In order to obtain some simplifications in Algorithm MFD we need more information about the structure of the logic network. The algorithm requires as data the lead labels in the g-literals. 68 Algorithm SFD (Single Fault Detection) Data required for this algorithm are the expressions E', E', E", E", E'(Fo) and E‘(F0). 1: Select either Ei or E; which contains the smaller number of g-literals for each of the m primary outputs of the network. If both have same number of g-literals, choose one arbitrarily. Separate zi,k1 (Zi,k0) terms in E; (E1) into two different sets. One contains the terms which contain g-literals have the same input literals with different inversion parities and the other does not. For those terms in Ei' (Ei') which contains no conflict pairs: (a) Let i = l. (b) Compute _ II... 1 ll— 5 all jyk = II__ '—I'I'_— (Mu ”i,k” n (2130)) all j#k If Mu is nonempty, put it in set M. (c) Repeat (b) for all terms in Ei' (Ei'). (a) If no Mu computed for each term is empty, increase 1 by 1 otherwise go to Step 5. (b) If not all Outputs of the network are considered to to Step 3(b) otherwise go to Step 6. Now set M contains the terms which detect any S: 69 shrinkage of the coverings of the selected Ei"s and Ei"s caused by any single fault in the network. Let there he 3 terms whose Mu's are nonempty and t terms whose Mu's are empty. Put their corres- ponding g-literals in set S and set T, respectively. (a) If all g—literals in a term of T are covered by some terms of S, delete this term from T. Repeat this investigation for every term of T. (b) For each common lead label, with same inver— sion parity, contained in two or more terms in T: Compute M = Z (zizfi) II ('z"-5-1) “ keK j¢K 1' (M = Z (2! '-0) II (2! '3. S) u keK i,k j¢K i,j where K contains the numbers of the terms which have the common lead label. (c) Increase i by 1, go to Step 3(b). Remove all g-literals from set S and T. Set 1 = l and j = 1. Let W denote a 21:31 (Zi:§0) term with one or more of its input literals replaced by l. (a) Replace one input literal in the ZE'?l (ZE'?0) 1’] 1'] term by 1. Compute 70 M -I 11 W n Eiwo’ (Mu w nEi(FO)) If Mu is nonempty, put it in set M. (b) Repeat (a) for every input literal in the term. (a) If no Mu computed for each input literal in a term is empty, increase j by 1 otherwise go to Step 9. (b) If not all terms in Ei'(Ei') are investigated, go to Step 7 otherwise increase i by 1 and set j = l. (c) If not all selected Ei"s and E{"s are processed, go to Step 7 otherwise stop. Set M now contains the terms which detect all single faults in the logic network. Let there be 8 input literals whose deletion generated nonempty Mu's and t input literals whose deletion generated empty Mu's. Put the corresponding g-literals in set S and set T, respectively. (a) Delete all the g-literals which are in both 8 and T from T. (b) For each common lead label contained in two or more g-literals, replace the corresponding input literals in the Zizfil (25:30) term by 1 then compute Mu by the pr0per equation of Step 7. Put each nonempty Mu in set M, delete the corresponding g-literals from T. 71 (c) Increase j by 1, go to Step 8(b). There is certainly much more information that can be obtained from Algorithm SFD, but since this information is useless in detection test generation, we delay its extraction until the generation of the complete location test set. Theorem 4.2 A minimal single covering of each Mu in set M generated by Algorithm SFD is a near minimal complete test set that detects all detectable single faults in the logic network. amt. A single fault can cause multiple shrinkages in several terms only if this fault is in the common lead which has the same inversion parity in the corresponding terms of E' or E' expression. If a term is jointly covered by other terms of the same output, the shrink- age of this term alone will not be detected. Further- more, if a covered term has its g-literals covered by those of uncovered terms, this term need not be inves- tigated for the possible joint multiple shrinkage. Because all the single shrinkages due to its member g-literals can be detected by the terms which detect the shrinkages of the covering terms. A multiple growth in a term is due to a single fault in the common lead label of several g—literals 72 in the corresponding terms of E' or E' expression. A growth of a g—literal in a term may be masked while the same growth in other terms may not. Each g-literal which is not masked in any one term need not be con— sidered further for multiple growth, since the multiple growth caused by a single fault in the g-literal will also be detected by the term generated to detect the single growth. Example 4.2 If we use algorithm SFD to generate a near minimal set of terms that detects all single faults in the logic network of Figure 2.4, we will end up with the same set of terms that was generated in Example 4.1 to detect all faults of the network. Hence a complete detection test set for single faults is also a complete test set for multiple faults in this particular network. In a multiple output network, a fault may be detected in one, two, ... up to all of the network outputs. If a fault is not detected by a complete detection test set we say that fault is undetectable and the network contains redundancy. An undetectable fault is a redundant fault as defined in Definition 3.2. 73 4.3 GENERATION OF NEAR MINIMAL COMPLETE LOCATION TEST SETS The generation of a complete test set that locates stuck-at type faults in a combinational logic network will also be accomplished in two steps: (1) the generation of a near minimal set of terms and the fault set detected by the terms. (2) Finding a minimal multiple covering of the terms such that every pair of distinguishable fault sets will be distinguished by the covering. 4.3.1 Generation ofpa Near Minimal Complete Test Set Which Locates aIl Faults in a Combinational Logic Network We shall call a collection of the subsets of single faults a multiple fault set if each fault in the set will cause (1) at least one g-literal to have functional equivalent of l, or (2) at least one Ziiel or 23:30 term _to have a functional equivalent of 0. ' A multiple fault of a multiple fault set is a non- conflicting combination of at least one single fault from one of the single fault subsets. For convenience, a multiple fault F = [al/O, a2/0, a3/l, a4/0, aS/l] will be written as [(al, a2,a4)/0, (a3, a5)/l]. Algorithm MFL (Multiple Fault Location) Data required for this algorithm are the expressions E', E', E", E", E'(Fo) and E'(F0). 1: Select either E5 or E3 which contains the smaller number of g-literals for each of the m primary 74 outputs of the network. If both have same number of g-literals.choose one arbitrarily. 2: For all Z!'—l (Z!'-0) terms which contain no i,k i,k conflicting pairs: Let i = l. (a) For all possible combinations of the terms II —II of Bi (Ei ), compute = ot___ T Mu Z (zi,kl) H (zi,jl) k selected j not selected = "... (Mn 2 (”i,k0’ H (z;j§5)) k selected j not selected (b) Put all nonempty Mu's and the associated multiple fault sets in set M. The multiple fault set at this stage is the collection of the subsets of single faults in the corres- ponding terms. These subsets contain the single faults whose effects on the shrinkages of their terms are not offset by the appear- ances of the faulty leads in different g-literals with different inversion parities. (c) Repeat (a) through (b) for all selected Ei' (Ei'). 3: For all terms in all selected Ei"s and E;"s. Let W denote a degenerate Zi:E1 (Zi:E0) term. (a) Set i = l and k_= l. (b) For all possible combinations of the growths of input literals in a term, compute = _I ' ' II Mu W n Ei(Fo) for growths in Ei 75 or Mj = W n Ei(F0) for growths in E;' (c) Put all nonempty Mu's and the associated multiple fault sets in set M. The single fault subsets of the multiple fault set now contains all single faults in the correspond— ing g-literals whose effect on the growth of the term is not masked by the fault free function. (d) Repeat (b) through (c) for all terms of the same output. (e) Repeat (b) through (d) for all selected Ei' (Ei'). 4: Group Mu's which have the same multiple fault set and multiple fault sets which have the same Mu. Stop. Theorem 4.3 A minimal multiple covering of Mu‘s generated by the Algorithm MFL which distinguishes each pair of multiple fault sets is a near minimal complete fault location test set of the logic network. Proof Algorithm MFL generates a set of terms that detects any detectable combinations of shrinkages and growths of the covering of the network function. 76 A single covering of each Mu of M is a complete detection test set follows directly from Theorem 4.1. A multiple covering which distinguishes every pair of Mu's will distinguish all distinguishable multiple faults. Because any multiple fault of the logic net- work is a combination of faults in the generated multiple fault sets, if any two combinations are dis- tinguishable the multiple fault will be distinguished by the covering which distinguishes between the elements of the combination. The non-minimal property of a minimal covering follows the same arguments in the proof of Theorem 4.1. Step 4 ensures there are no overlaps in the Mu's and in the multiple fault sets. When a single fault is investigated to determine whether its effect on the shrinkage of a term is offset by the possible growths in other terms, each vertex in the shrinking term has to be considered separately because the offset may be partial. The Mu and the multiple fault set then can be adjusted accordingly. Example 4.3 Find a near minimal complete test set that locates all multiple faults in the logic network of Figure 2.3. 77 First, we use Algorithm MFL to generate a near minimal set of terms which will distinguish every distinguishable pair of the multiple faults. Step 1: Refer to Example 3.1, E' is selected to be processed, where E' = -<§ 2I 3,4,4a,7,9,z> 2I 2,4,4a,7,9,Z> '2,E,45)6,8,9,z> + <2 ,I,1—b-,5,8,9,Z>‘ Step 2: Terms investigated x1x2x3 XI The result of this step is: M u M1 Multiple fault set F1 [(l,la,2,3,4 43:719)/0] [(1,1b7274b)/1. (5,6,8,9)/0] [(l,lb,3,4,4b) /l,(5,6,3.9)/0] 78 Step 3: We need E'(Fo) = XIX2 + XIX3 + x1x2x3 for computing the Mu's. The result is: Inputs Term replaced Mu Multiple fault set x1x2x3 x1 M8 = Silxzx3 F8 = [(l,la,7,9)/l] x2 M9 = x1§2x3 F9 = [(2,4,4a,7,9)/l] x3 Mlo = Xlx2§3 Flo = [(3,4,4a,7,9)/1] x1'x2 ' M11 = M8 + M9 F11 = [F8' F9] x1' x3 M12 = “3 + M10 F12 = [Fa' F10] X2' X3 M13 = Xli2 + xl§3 F13 = [F9' F10] All M14 = E'(Fo) F14 = [F8, F9, Flo] 2122 E1 M15 = x122 F15 = [E§:§?;{3il 22 M16 = 5"1"2X3 F16 = [§§:§:g?}{?' All M17 = E"Fo) F17 = [F15' F16] §1§3 i1 M18 = X1§3 F18 = P15 3('3 M19 = M16 F19 = [E2:g:g?}{?' All M20 = E‘(FO) F20 = (Fla, F19] Step 4: Since F18 = F15 we can delete M18 and substitute M15 by X122 + x135, which in turn equals M13. So M15 can be deleted and F13 replaced by [F9, F10, F15]. We can also remove M17 and M20 from set M, then replace F14 by [F8’ F9, F10, F15, F16' F18' F19]. 79 Finally, since M8 and M16 are equal, we can delete M16 and replace F8 by [(1,1a,6,7,8,9)/1, (2,4,4b)/0]. Now,a minimal multiple covering of remaining Mu's which distinguishes each pair of remaining multiple fault sets is found to be the all possible combinations of input literals, i.e. (000, 001, 010, 011, 100, 101, 110, 111) which is a near minimal complete location test set. 4.3.2 Generation of a Near Minimal Test Set which Locates AII Single Faults in a CombinationaI Log c Network The algorithm to be discussed is a direct extension of Algorithm SFD and bears some similarities with Algorithm MFL of preceding subsection. Algorithm SFL (Sipgle Fault Location) Data required for this algorithm are the same as Algorithm MFL. 1: Select either E; or E; which contains the smaller number of g-literals for each of the m primary outputs of the network. If both have same number of g-literals, choose one arbitrarily. 2: For all Zizil (Ziz—O) terms which contain no conflicting pairs: Let i = l. (a) Compute (b) 80 = II_ _. Mu (Zi,kl) II (zi,jl all jfk = II_ I (Mu (Zi’kO) II (21:30)) all j#k for each term in Ei' (Ei'). Put all nonempty Mu's and the associated set of single faults in set M. The set of single faults contains all single faults in the term that cause such a term to have the functional equivalent of 0 without considering the possibly masking growths caused by the same single faults. 3: For the terms of Step 2 which contain common lead labels. (a) (b) Compute M 11 Z (221-1) n 7377:33‘ keK l'k jtK 1'3 (M u 2 (2;:E0). n (2. e0 ) keK j¢K 1’3 where K contains the numbers of the terms which have common lead labels under investigation. Put all nonempty Mu's and associated single faults in set M. 4: Repeat Step 2(b) through Step 3 for each Ei' (EE') selected. 81 5: For all terms selected: Let W denote a degenerate Zi'El (Zi'EO) term. I I (a) Set 1 - 1 and j a l. (b) Compute 3 " - I I Mu Wll Ei(F0) for growths in E1 or Mu = W’n Ei(F0) for growths in E;' for each single and possible multiple growth in a term. (c) Repeat (b) for all terms in Ei' (El'). (d) Repeat (b) through (c) for all E£"s and §"'s selected. 6: Group Mu's which have the same fault set and group fault sets which have the same Mu. Theorem 4.4 A minimal multiple covering of Mu‘s generated by Algorithm SFL which distinguishes each pair of single fault sets is a near minimal complete test set which locates all single faults of the logic network. Proof The statements for the proof parallel those of Theorem 4.2 and Theorem 4.3. Q.E.D. 82 Example 4.4 Find a near minimal complete test set which locates all single faults in the logic network of Figure 2.3. Refer to Example 4.3 and use Algorithm SFL to generate the required Mu's and the single fault sets. Step 1: Select E‘ to be processed. Step 2: The result of this step is the same as the first three Mu's and Fu's of Example 4.3. Step 3: After this step, we obtain the M6 and M7 of the preceding example, but the single fault sets are F6 = [(5,6,8,9)/0] and F.7 = [9/0]. Step 4: The network has pnly one output, so this step is skipped. Step 5: We get M8' M9, M 0' M and M of l 13 14 Example 4.3 for the x1x2x3 term except that F13 = [(4,4a,7,9)/l] and F14 = [(7,9)/l]. For the term of 5, M and M = [(8,9)/l]. From 16 17 and M20 = [(8,9)/1]. 15 and M18 as before except the xlx2' there are M1 X1X3 we have M18' M19 Step 6: Delete M new Fl3 is [(4,4a,5,7,8,9)/l, (l,lb)/0]. For the removal of M17 and M20, the new F14 = [(7,8,9)/l] is introduced. Finally, delete M16 and make F8 equal to [(lllaI6I7I8I9)/1I (2I4I4b)/0]° We do have a smaller set of Mu's for single faults than that for multiple faults. However, the near 83 minimal complete location test set found is no smaller for this particular logic network. 4.4 SEARCH OF MINIMAL COMPLETE DETECTION TEST SETS In this Section we shall search for a minimal set of terms such that a minimal single covering of these terms is a minimal complete test set which detects all faults in the combinational logic network. The logic networks will be assumed to be irredundant. The generalization of the procedure to be presented in this Section to general networks parallels the algorithms dis- cussed in Section 2 and will not be repeated in this Section. Lemma 4.4.1 Any multiple fault in a combinational logic network can be represented by a combination of faults in non-fanout primary input leads and the fanout branches of the network. 2922 Any multiple fault that includes the output lead of the elementary gate is equivalent to the single fault in the output lead only. But a stuck output of an elementary gate is equivalent to a stuck input leads or lead of the gate. For a stuck fanout stem lead the fault is equivalent to stuck branches. 84 Tracing back from the primary output leads of the network and repeating the above arguments, we have the lemma. Q.E.D. We shall call the non-fanout primary input leads and the fanout branches the checkpoints of the network. Procedure MTG (Minimal Test Generation) (1) Find a minimal number of Z! —1 (Z! —O) terms i,k i,k that covers all the checkpoints of the network. (2) (a) Compute = II_ _ ll Mu (zi,k1) H (ziijl) for terms from Ei all j¢k = II II "II Mu (Zi,k0) H (21,30) for terms from E1 all j¢k (b) If Mu is empty, go to Step 1. (c) If Mu is nonempty, but at least one check- point is a selected term is masked by a growth and the deletion of this checkpoint destroys the property of coverage obtained in Step 1, go to Step 1. (3) (a) Find a minimal number of g-literals in E; (Ei) which covers the complement of lead labels not covered by the terms selected in Step 1. (b) Compute (4) (5) (6) (a) (b) (e) (d) 85 M —I 11 W (1 Bi (F0) (Mu W n Ei(F0)) for each g-literal selected in (a), where W is the disjunct of the degenerate Zizfil (Zi1E0) terms of which the input literal of the g-literal in question is replaced by 1. Find a minimal number of terms in E; (Ei) which covers all the checkpoint labels that are not covered by the terms selected in Step 1. Compute Mu by the proper equation of Step 2(a). If Mu is empty, go to (a). If Mu is nonempty, but at least one check- point label in a term is covered by a growth and the deletion of this checkpoint destroys the property of coverage obtained in (a), go to (a) . Repeat Step 1 through Step 4, start Step 1 for the terms in E‘. For both E' and E': (a) Find a minimal single covering for Mu's generated in Step 2 and Step 3. (b) Find a minimal single covering for Mu‘s (C) generated in Step 2 and Step 4. Select one which contains a minimal number of input vectors from the four coverings found in (a) and (b). Stop. 86 Theorem 4.5 The set of input vectors selected in Step 6(a) of Procedure MTG is a minimal complete detection test set for an irredundant network. 2:22: The purpose of Procedure MTG is to detect the stuck-at type faults at all checkpoints of the network. Since the network is irredundant, every shrinkage caused by a g-literal will be detected. In particular, the shrinkages of the g-literals in the selected terms of Step 1 will be detected, hence Step 1 can be satisfied. For a checkpoint, both stuck-at l and stuck-at 0 faults can cause a shrinkage in the network function if the checkpoint has different inversion parities in the different terms selected in Step 1. It is necessary and sufficient to cover the checkpoint labels which are not covered by Step 1. Step 3 and Step 4 serve this purpose. Step 5 searches the complement of the network function. After four possible minimalities are com- puted, we get a minimal complete detection test set for the network by selection. Example 4.5 Find a minimal test set which detects all faults of the logic network of Figure 4.1. 87 Figure 4.1 The Irredundant Network for Example 4.5. The E' and E' expressions of the network can be found by using Algorithm G of Chapter 2. They are: E' = - «I? ,3,6,_6_a_1,7,9,ll,z> + (X 'l's'églgll-IIZ>.(xz'glsliilgl11IZ> 1 ° + <§i,:}§,§§,8,10,ll,z>- . 4'— + (KZ’ZIE'E’8[10,11]Z>. o and E' = <§1,L5',E,'§,II,_>~<§3,§,6,63,T6,II,2'> + <"'1,I, ,53, ,II,'z'>-<'}'{'4,_4_','6,EE,IU,II,'Z’> -_,'8‘,IIY,II,§> 2I 1,155b3—Ullz> . where the checkpoints are underlined. Step 1: Select the first and the third terms from E'. The checkpoint labels covered by this selection are: l,I,2,3,3,4,5a,55,63,6b. Step 2: The Mu's obtained are: M1 = XIXZXBX4 and M2 = X1X2X3X4. Both terms are nonempty and no checkpoint is covered by any corresponding growth. Step 3: One of the minimal number of g-literals which covers the checkpoint labels 2,4,5a,55,6§,6b contains the second and the third g-literals of the first term and the first and the third g-literals of the third term. The Mu's computed are: M3 = 111x23?3 + xlx2x4; M4 = xlx2x3x4, +XXX4 2 3 89 Step 4: One of the minimal number of terms in E' that covers the checkpoint labels 2}T}5§,5b,6a,65 contains the fourth and the fifth terms of E'. The Mu's that detect the shrinkages of these terms are: M6 = x1X2X3X4 and M7 = X1X2X3x4. There is no check— point covered by the corresponding growth. Step 5: Start from Step 1 by picking the first and the fifth terms of E‘. These two terms cover the checkpoint labels 1,I,2,3,3,4,53,56,6a,6“. The Mu's are M8 = X1X2X3X4 and M9 = X1X2X3X4. Then we choose the first and the second g-literals of the first term and the second and the fourth g-literals of the fifth term. The result 13: M10 = X1X2X3 + x1x2x4, M11 = X1X3X4 + X2X3X4, M12 = X1X2X3X4and M13 = X1X2X3X4. Finally, use the second and the fourth terms of E' 14 = x1X2x3x4 and M15 = x1X2x3x4' Step 6: The result of this step is: to get M The Mu's to be covered A minimal covering (M1, M2, M3, M4, M5) (0010, 0111, 1001, 1101, 1111) (M1, M2, M6, M7) (0111, 1010, 1101, 1111) (M8, M9, M10, M11, (0101, 1011, 1110, 1111) M M ) 12’ 13 (M8, M9, M14, M15) (0101, 1011, 1110, 1111) We can choose either the second or the third set of input vectors as a minimal complete detection test 90 set for the network. Note that the fourth test set is the same as the third set. 4.5 CHAPTER SUMMARY AND REMARKS The power of the CGEMs, with its various modified forms, in generating the complete test sets was demonstrated in this Chapter. Two algorithms for generating near minimal complete test sets and two algorithms for generating near minimal complete location test sets were presented. As the examples illustrated, the generation of complete test sets under the single fault assumption is sometimes no simpler than that with the multiple fault assumption. A method of searching for a minimal complete detection test set for an irredundant network was also suggested. Applying this method to a network, i.e. The network of Figure 4.1 we found a smaller minimal complete detection set than that obtained by Poage's method. This is due to the fact that we used a "better" model than that of Poage‘s. In reading the searching method, i.e. Procedure MTG, one may note that all the algorithms discussed were not intended for the generation of minimal complete test sets. Rather, we tried to simplify the computations as much as possible and at the same time kept the test sets at a reasonable small size. Therefore, these algorithms can easily be modified, with the aid of Procedure MTG, to conform to one's particular situation. 91 When applied to a redundant network, the algorithms presume no redundant faults exist. For a redundant net- work with the presence of redundant faults, we can: (1) Substitute the g-literals which are affected by each of the possible combinations of the redundant faults by apprOpriate functional equivalents. (2) Find a complete test set Ti I ' .— for each of the modified E' s or E' s. The disjunction of Ti's is a complete test set. CHAPTER 5 CONCLUSIONS AND SUGGESTIONS FOR FUTURE WORK 5.1 CONCLUSIONS This thesis presents an algebraic model which describes accurately and completely the physical and logical structures of a combinational logic network com- prised of elementary gates. The model also provides a large degree of flexibility for expressing the interdepen- dencies of the physical and logical structures of an object network. After the model is constructed by an algorithm, it is used for (l) analyzing stuck-at type faults and bridging faults and (2) generating complete test sets. The fault functions realized by a network under the influence of the stuck-at type faults or the bridging faults were rigorously investigated. The generation of complete test sets was studied by four algorithms and one procedure. The algorithms and the procedure are straightforward and can be modified to satisfy one's particular situation. The memory require— ments are minimized by taking advantage of the flexibility of the model. 92 93 5.2 SUGGESTIONS FOR FUTURE WORK Many conjectures from the articles of fault diagnosis and test generation can be confirmed or disproved using the model discussed in this thesis. For example: Armstrong's [1] conjecture: There exist at least one set of literals [L] and an associated set of tests [T] that tests an appearance of every literal in [L] for s-a-l and s—a—O and also detects every fault in the net. This is true if we consider the set of literals of Armstrong is the set of all distinct g-literals of the network. We may have an even smaller set of g-literals by Theorem 4.5. Bossen and Hong's [3] conjecture: Any strategy based on checkpoint verification seems infeasible for redundant networks. This can easily be diSproved by viewing the detection of a shrinkage and a growth in Algorithm MFD is the verifi— cation of checkpoints in a g-literal of the network. There are some interesting problems which remain to be solved. The problem of detecting and locating stuck—at type faults, both permanent and intermittent, in sequential logic networks has not been satisfactorily solved. This is due to both the large number of state transitions and the length of test sequence which brings the network to a required state. I conjecture that by cascading the combi— national equivalent of a sequential network and generating 94 test set for first, first two, first three, ... time frame sequentially, removing the checkpoints which are investi- gated and adding checkpoints from the new time frame the computational burden may remain manageable and the problem can be more satisfactorily solved. The design of easily testable networks without adding logic circuits for testing purpose is another interesting problem. From Chapter 4 we know if the shrinkage of each term and the growth of each g-literal are detectable, then the algorithms can be terminated earlier and the test set will be smaller. A more general network structure other than two-level and tree realizations remains to be dis- covered. A retrospective study of this thesis may shed a little light on this problem. Even if all functional units can be modeled in terms of elementary gates and the checkpoints can be used ade- quately in the model to describe a MSI or a LSI logic network, one may still want to develop a model in terms of other small functional units for a LSI network. The possible consequences are (l) The model cannot be used to detect redundancy in the network, (2) the preciseness of the parity of each label in an information path.wi11 be lost, hence the computations for test generation will be much more complicated. APPENDIX APPENDIX J A DATA STRUCTURE FOR ALGORITHM G OF SECTION 2.3 For the machine implementation of Algorithm G a doubly linked list structure can be used to represent the equivalent Boolean expression of a logic network. Each node of the list represents a distinct lead label together with the addresses of its predecessors and successors. The size of a node depends on the properties of the logic network. In terms of number of bits, it is the sum of the following four items: 1. For the lead label flog2 (The largest number of the lead labels)1 + rlogzl(Maximum numb er of fanout branches with the same labeling integer) + 1]1 bits. where [x1 is the smallest integer z x. 2. For indicators a. The label is barred or non-barred: 1 bit. b. The lead is a network output, a primary input or an internal lead: 2 bits. 95 h\\ 96 c. The lead is the output of an OR gate or an AND gate: 1 bit. 3. For the addresses of predecessors [(Maximum number of input leads for an elementary gate) + 1(for endmarker)] X [flog2 (Total number of leads of the network)1 + 1(indicating whether the label is barred) + 1(indicating whether it is a predecessor or a successor)] bits. 4. For the addresses of successors [(Maximum number of fanout branches from a fanout stem) + 1(for endmarker)] X [Flog2 (Total number of leads of the network)1 + 1(indicating whether the label is barred) + 1(indicating whether it is a predecessor or successor)] bits. For a network of 2,000 gates with 40 primary inputs, let the maximum number of fanout branches with the same labeling integer be 6, the maximum number of fanout branches from a fanout stem be 3 and the total number of distinct leads of the network be 5,000. It requires 168 bits to represent a node. Counting both barred and non-barred labels, a memory size of 30K 60-bit words is needed. In order to illustrate the data structure discussed, Example 2.3 is recomputed as follows: 97 For the network of Figure 2.4 the node of List requires 53 bits which is divided into 11 fields: Field Length Descriptions (in bits) 1 5 Represents the integer part of lead label. 2 2 0 for non-fanout, l for fanout a and 2 for fanout b. 3 l 0 for non-barred, l for barred. 4 2 0 for network output, 2 for primary input and l for internal lead. 5 l 0 for OR gate, 1 for AND gate. (primary input lead use 0.) 6-8 7 each For the addresses of predecessors which will be represented by the labels with or without overbar. E for endmarker and M for not used. 9-11 7 each 'For the addresses of successors which will be represented by the labels with or without overbar. E for endmarker and b for not used. The node describing label p will be denoted by Np where p either barred or non-barred. Two more Lists will be introduced to keep track of path expansion process. List A stores the non-primary input label and its address from the end and its head element is to be removed for expansion. After expansion the label and the primary input 98 label introduced together with the corresponding addresses are stored in List B. The starting state after the network is labeled by Procedure L is N12: 12,0,0,0,0,9,lla,E,E,b,b N13: 13,0,0,0,l,llb,8,E,E,b,b A(0): 12,13 B (0) : (empty) The first step is to remove 12 from List A then generate N9 and N11. Since 9 and 11 are not primary input lead labels, they are put at the tail of List A. 12 is put at List B. Note the integer in the parentheses after A or B denotes the number of expansions completed. N9: 9,0,0,1,1,6,7E,E,12,E,M Nlla: 11,1,o,1,o,11,E,p,12,E,U A(l): 13,9,lla 3(1): 12 The further results are: Nllb: 11,2,0,l,0,11,E,b,13,E,b N8: 8,0,0,l,0,1b,2b,E,13,E,b A(2): 9,11a,llb,8 8(2): 12,13 N6: G’O'IIIIO'E'E'Epng’M N7a: 7,1,1,1,o,7,s,p,9,s,b 99 A(3): 11a,11b,8,6,7§, B(3): 12,13,9 N11: 11,0,o,1,o,1o,5,E,11a,E,h A(4): 11b,8,6,7§,11 B(4): 12,13,9,lla For the fifth step 11b is extended to 11 which is in A(4), so we update N11: N11: 11,0,0,1,0,10,5,E,11a,11b,E A(S): 8,6)75,ll B(S): 12,13,9,11a,11b Nlb: l,2,0,1,0,l,E,M,8,E,b N2b: 2,2,0,l,0,2,E,fl,8,E,b A(G): 6,75,11,1b,2b 8(6): 12,13,9,11a,11b,8 N33 lllIlIlIOIIIEIMI-é-IEI” N53: 2I1I1I1IOI§IEIMI€IEIM A(7): 73,11,1b,2b,I3,§E' 5(7): 12,13,9,11a,11b,8,6 N7: 7,0,1,1,o,3,E,M,73)E,M A(8): 11,1b,2b,IE,§E,7 3(3): 12,13,9,11a,11b,3,6,7§ N10: l0,0,0,l,l,7b,5,E,ll,E,b N5: 5,0,0,2,0,E,M,b,ll,E,M A(9):, 1b,2h,I§,§3,7,1o 8(9): 12,13,9,11a,116,8,637§,11,5 100 Note that lead label 5 is a primary input lead label. It can be extended, so put it into B(9) rather than attached it to A(9). N1: 1,0,0’2'0,E'M,”'1b A(lO): 2b,IE,§E,7,10 B(lO): B(9),lb,l where the notation B(9),lb,l is used to represent the insertion of lb and 1 into List B(9). N2: ZIOIOIZIOIEIbIbIZbIEIb A(ll): IE,§§,7,10 B(ll): B(9),lb,1,2b,2 NI: lrorlrzloIEIbIMITaIErb A(12): 23,7,10 3(12): B(9),1b,1,2b,2,I3,I NE: ZIOIlIZIOIEIMIKIEETEIb A(13): 7,10 B(13): B(9),1b,1,2b,2,I§,1,23,2 N3: 3I0I0I2I0IElblwl7IEIb A(14): 10 3(14): B(9),1b,1,2b,2,I3,I,§3,§,7,3 N7b: 7,2,0,1,0,7,E,p,10,E,M N4: 4,0,0,2,0,E,p,b,10,s,p A(15): 7b 3(15): B(9),1b,1,2h,2,I§,I}7§,§,7}3,10,4 101 N7: 7,0,0,1,0,3,E,M,7b,s,8 A(l6): 7 B(16): B(lS),7b N3: 3.0.1.2.0.E.)6:)6:7.E.)6 A(l7): (empty) 3(17): B(lS),7b,7,3 The program will stop at the eighteenth step, since the empty A(l7) implies the path sets generated are g-literals. In the above computations the input to the program is assumed to have all the information needed. The network information can be compactly stored and easily fetched if they are arranged in an appropriate order. For a large network one may like to sort the nodes in List B in the manner that will save the searching time. The procession of List A is similar to the breadth—first search method in artificial intelligence. The size of List A may be reduced by using the depthvfirst method but, in general, for a network of various lengths of geliterals the reduction will not be appreciable. The AND/OR graph representation of the network of Figure 2.4 is depicted on the next page. One may note with a little effort the sum of products form of the g-literals and the functional equivalent of the network can be obtained. Furthermore, with the interpretations of AND and OR, barred and non-barred interchanged it is the complemented form of the network. 102 - C e as s Figure A.l. The AND/OR Graph representation of Figure 2.4. BIBLIOGRAPHY [l] [2] [3] [4] [5] [6] [7] [8] [9] BIBLIOGRAPHY Armstrong, D. B. "On Finding a Near Minimal Set of Fault Detection Tests for Combinational Logic Nets," IEEE Trans. Electron. Comput., Vol. EC-lS, pp. 66-73, Feb. 1966} Arnold, T. F.; Tan, C. J.; and Newborn, M. M. ”Iteratively Realized Sequential Circuits," IEEE Trans. Comput., Vol. C-l9, pp. 54—66, Jan. . Bossen, D. C.; and Hong, S. J. "Cause-Effect Analysis for Multiple Fault Detection in Combinational Networks," IEEE Trans. C9mput., Vol. C—20, pp. 1252-1257, Nov. I971. Breuer, M. A. "Testing for Intermittent Faults in Digital Circuits," IEEE Trans. Comput., Vol. C-22, Ball, M.; and Hardie, F. "Effects and Detection of Intermittent Failures in Digital Systems,“ in 1969 Fall Joint Co ut. Conf., AFIPS Conf. Proc., VoI. 35, pp. 329-355. Montvale, N. J.: AFIPS Press, 1969. Carter, W. C. "FaultuTolerant Computing: An Intro— duction and a Viewpoint," IEEE Trans. Comput., V010 C-22' pp. 225-229, Mars 1973. . Chang, H. Y. "An Algorithm for Selecting an Optimum Set of Diagnostic Tests," IEEE Trans. Electron. Comput., Vol. EC-l4, pp. 706-711, Oct.’l965. . "A Distinguishability Criterion for Selecting Efficient Diagnostic Tests," in 1968 S rin Joint Co ut. Conf., AFIPS Conf. Proc., VoI. 32, pp. 529- 34. Washington,D.C.:_TEOmpson, 1968. Chang, H. Y.; Manning, E.; and Metze, G. Fault * Qiagnosis of Dig%tal Systems. New York: Wiley— Interscience,II 0. 103 [10] [11] [12] [13] [14] [15] [16] [17] [13] [19] [20] [21] 104 Clegg: F. W. "Algebraic Properties of Faults in Logic Networks," Ph.D. thesis, Stanford Univ., 1970. . "Use of SPOOF's in the Analysis of FauIty Logic Networks,“ IEEE Trans. Comput., Vol. Dwyer, T. F. "Comments on 'Fault Testing and Diag- nosis in Combinational Digital Circuits,'" IEEE Trans. Comput., (Corresp.), Vol. C-lB, p. 760, Aug. 1969. Farmer, D. E. "Algorithms for Designing Fault— Detection Experiments for Sequential Machines," IEEE Trans. Comput., Vol. C-22, pp. 159-167, Fe O O . "A Strategy for Detecting Faults in Sequential Machines Not Possessing Distinguishing Sequences," in 1970 Fall goint Comput. Conf., AFIPS Conf. Proc., Vol. 37, pp. 493-501. Montvale, N. J.: AFIPS Press, 1970. Flomenhoft, M. J.: Si, S. C.; and Susskind, A. K. "Algebraic Techniques for Finding Tests for Several Fault Types," in Digest 1973 International Symp. on Fault-Tolerant Computimg, pp. - . Friedman, A. D. "Fault Detection in Redundant Circuits," IEEE Trans. Electron. Comput., Vol. EC-16, pp. 9- , Fe . . . "Diagnosis of Short Faults in Digital Circuits,” in Digest 1973 International Sympj on Fault-Tolerant Computing, pp. 95F99. Friedman, A. D.: imDigital Circuits. Prentice-Hall, 197I. and Menon, P. R. Fault Detection J/ Englewood Cliffs, N. J.: Gault, J. W.; Robinson, J. P.; and Reddy, S. M. "Multiple Fault Detection in Combinational Networks," IEEE Trans. Comput., Vol. C—21, PP. 31-36, Jane 0 Hannigan, J. M.; and Master, C. 6., Jr. "Redundant System Test Point Allocation and Mission Relia— bility Estimation Procedures," IEEE Trans. Comput., Vol. EC-16, pp. 591-596, Oct. 1967. Hsieh, E. P. "Checking Experiments for Sequential Machines," IEEE Trans. Comput., Vol. C—20, pp. 1152-1166, Oct. 1971. [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] 105 Kamal, 8. "Diagnosis of Intermittent Faults in Digital Systems," Ph.D. thesis, Michigan State Univ., Jan. 1973. Kautz, W. H. "Fault Testing and Diagnosis in Com- binational Digital Circuits," IEEE Trans. Comput., V01. C-l7' pp. 352-366! Apr. lggg: Switching and Finite Automata Theory. Kohavi, z. _p McGraw-Hill, 1970. New York: Kohavi, 1.; and Kohavi, 2. "Detection of Multiple Faults in Combinational Logic Networks," IEEE Trans. comEUt., V01. C-ZI, pp. 556-568, Jun. 1972. Kohavi, 2.; and Spires, D. A. 'Designing Sets of Fault-Detection Tests for Combinational Logic Circuits," IEEE Trans. Comput., Vol. C-20, pp. 1463-1469, Dec. I971. Kubo, H. ”A Procedure for Generating Test Sequences to Detect Sequential Circuit Failures," NEC Res. Develop., Oct. 1968. Marinos, P. N. "Derivation of Minimal Complete Sets of Test-Input Sequence Using Boolean Differences," IEEE Trans. Comput., Vol. C-20, pp. 25‘32, Jan. I97I. McCluskey, E. J.: and Clegg, F. W. "Fault Equivalence in Combinational Logical Networks," IEEE Trans. Comput., Vol. C-20, pp. 1286-1293, Nov. I97I. Mealy, G. H. "A Method for Synthesizing Sequential Circuits," Bell System Tech. J., Vol. 34, pp. 1045-1080, 1955. Mei, K. C. Y. "Bridging and Stuck-at Faults," in' Qigest 1973 International Symp. on Fault-Tolerant Computing, pp. 91-94. Moore, E. F. "Gedangen Experiments on Sequential Machines," in Automata Studies, Annals of Math. Studies, No. 34, Shannon, C. E.; and McCarthy, J., eds., pp. 129-153. Princeton, N. J.: Princeton Univ. Press, 1956. Poage, J. F. "Derivation of Optimal Tests to Detect Faults in Combinational Circuits," in Proc. Symp. on Mathematical Theopy of Automata, Polytechnic InsE. of Brooklyn, pp. 483-528, I963. Reddy, S. M. "Easily Testable Realizations for Logic Functions," IEEE Trans. Comput., Vol. C-21, PP- 1183-1188, Nov. 1972. [551 [36] [37] [38] [39] [40] [41] [42] [43] [44] 106 . "A Design Procedure for Fault-Locatable Switching Circuits," IEEE Trans. Comput., Vol. C-21, (Short Notes): pp. 142141426, Dec. 1972. Reese, R. D.; and McCluskey, E. J., Jr. "A Gate Equivalent Model for Combinational Logic Network Analysis,” in Qigest 1973 International Symp. on Fault-Tolerant Computing, pp. 79-84. Roth, J. P. "Diagnosis of Automata Failures: A Calculus and a Method," IBM J. Res. Develop., Vol. 10, pp. 278-291, Jul. 1966. Roth, J. P.; Bouricius, W. G.; and Schneider, P. R. "Programmed Algorithms to Compute Tests to Detect and Distinguish between Failures in Logic Circuits," IEEE Trans. Electron. Comput., Vol. EC-16, pp. 567- 589, Oct. I967: Russel, J. D.; and Kime, C. R. "Structure Factors in the Fault Diagnosis of Combinational Networks," IEEE Trans. Comput., Vol. C-20, pp. 1276—1285, Nov. I971. Schertz, P. R.; and Metze, G. "A New Representation for Faults in Combinational Digital Circuits," %%EE Trans. Comppt., Vol. C-21, pp. 858—866, Aug. 72. Schneider, P. R. "On the Necessity to Examine D-Chain in Diagnostic Test Generation—-An Example," IBM J. Res. Develpp., Vol. 11, p. 114, Jan. 1967. Sellers, F. F.; Hsiao, M. Y.; and Bearnson, L. W. "Analyzing Errors with the Boolean Difference," IEEE Trans. Comput., Vol. C-l7, pp. 676—683, JuI. I967. Seshu, 3.; and Freeman, D. N. "The Diagnosis of Asynchronous Sequential Switching Systems," IRE Trans. Electron. Compgp., Vol. EC-ll, pp. 459:465, Aug. 1962. Su, S. Y. H.; Chang, S. J.: and Breuer, M. A. "Location of Multiple Stuck-Type Faults in Combinational Networks," IEEE Comput. Soc. Reposit. R-72-l96, 1972. 107 [45] Su, S. Y. H.; and Cho, Y.~C. "A New Approach to Fault Location of Combinational Circuits," IEEE Trans. COEEUt.’ V01. 0-21, pp. 21-30, Jan. I972. [46] Williams, M. J. Y.; and Angell, J. B. "Enhancing Testability of LSI Circuits and Additional Logic," IEEE Trans. Comput., Vol. C-22, pp. 46-60, Jan. I973. MICHIGAN STATE UNIV. LIBRARIES IIHI(HIIMIIHIIWIIIINIHIHIIII[IIHHIWIIIHIHII 31293101731770