■M ISffi HH8H bBBbH h IHSB1 ■ r ■ ■ ** * ■ ■ m ■ ■ I LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 5/0.84 iJKor no. 590-594 Digitized by the Internet Archive in 2013 http://archive.org/details/designoftotallys593pitt yu.5£3 uiuCDCS-R-73-593 /na^ui DESIGN OF TOTALLY SELF-CHECKING ASYNCHRONOUS SEQUENTIAL MACHINES by DANIEL AVERY PITT September 1973 UIUCDCS-R -73-593 DESIGN OF TOTALLY SELF -CHECKING ASYNCHRONOUS SEQUENTIAL MACHINES By DANIEL AVERY PITT B.S., Duke University, 1971 Urbana, Illinois ^Submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 1973- ACKNOWLEDGMENT I wish to thank my adviser, Dr. Gemot Metze, Professor of Electrical Engineering and Research Professor at the Coordinated Science Laboratory, for his guidance, thought, and assistance in the preparation of this thesis. His foresight in asking all the right questions and his ability to project technical problems in their proper perspective are greatly appreciated . In addition, I would like to express special gratitude to my father, Hy Pitt, for supplying me with most of my motivation and encouragement and without whose example of earnestness I would probably have achieved far less than I have. IV TABLE OF CONTENTS Page ACKNOWLEDGMENT iii LIST OF FIGURES v INTRODUCTION 1 1. TOTALLY SELF-CHECKING MODEL 2 2. OPERATION OF SELF-CHECKING CHECKERS 3 3. DESIGN OF TOTALLY SELF-CHECKING CHECKERS FOR k-OUT-OF-2k CODES 5 4. DESIGN OF SELF-CHECKING ASYNCHRONOUS SEQUENTIAL CIRCUITS . . 7 4.1 Asynchronous Machine Model 7 4.2 Internal Design for Self-Checking Characteristics . . 7 4.3 State Assignment Procedure 9 4.4 Examples 14 5. ADAPTING THE SEQUENTIAL MACHINE TO THE CHECKER 19 5.1 General Problems 19 5.2 Methods Which Do Not Work 20 5.3 Technique for Cycling Through Additional States ... 23 5.4 Examples 25 6. DESIGN EQUATION CONSIDERATIONS 31 7. CONCLUDING REMARKS 32 LIST OF REFERENCES ■ 33 LIST OF FIGURES Figure Page 1. Flow table for example A 15 2. Flow table for example B 15 3. Flow table for example C 17 4. Maximally specified expanded flow table for example B. 27 5. Minimally specified expanded flow table for example B. 27 6. Maximally specified expanded flow table for example C. 29 7. Minimally specified expanded flow table for example C. 30 INTRODUCTION A totally self-checking asynchronous sequential machine is one which detects and indicates its own internal faults in real time. Methods have been developed, most notably by Maki e_t a_l. [lJ, for designing asynchronous machines that indicate faults by entering illegal states. To detect these faults, one must use some sort of combinational circuit to determine if the present state, represented by the binary vector of the state variables, is a valid one. Faults in this combinational circuitry can cause illegal states to be interpreted as valid, thus masking the error in the combina- tional network as well as the one which produced the erroneous state. The value of having a totally self-checking network is that faults in this combinational portion are indicated, as well as faults in the sequential portion. Thus erroneous information can never be passed on to succeeding networks . The method presented herein is that of designing a totally self- checking network consisting of two portions, a sequential machine and a checker, each of which is (and must be) totally self-checking. For any network to be self-checking both its inputs and outputs must be encoded so that it can distinguish between valid and invalid codewords. For the sequen- tial portion the encoded input will be the present state and the output will be the next state. This encoded output will be the encoded input to the checker, whose output is a simple l-out-of-2 code. 1. TOTALLY SELF-CHECKING MODEL A totally self-checking circuit is defined by Anderson [2] according to the way in which it maps inputs into outputs, as follows: Do i'ini tion : A circuit is self- testing if, for every fault from a pre- scribed set, the circuit produces a non-code output for at least one code input . Def i nit ion : A circuit is fault-secure if, for every fault from a pre- scribed set, the circuit never produces an incorrect code output for code inputs . Definition : A circuit is totally self-checking if it is both self-testing and fault secure. The set of faults which is considered here is the set of all single faults on gate inputs or outputs. The fault model is that of a line being either stuck-at-one or stuck-at-zero , with the fault being either transient or solid (permanent). A totally self-checking check circuit is also code- disjoint, in that when there are no internal faults it always maps non- codewords into non-codewords and codewords into codewords. 2. OPERATION OF SELF-CHECKING CHECKERS Self-checking check circuits have been investigated by Anderson and Metze [3] and operate by mapping input codewords onto a l-out-of-2 out- put code, where the output functions, denoted as f and g, are independently implemented from the inputs. Thus valid input codewords result in outputs of fg = 10 or fg = 01, while non-codeword inputs are mapped onto fg = 00 or fg = 11. Furthermore, single or unidirectional faults in the checker also result in outputs of fg = 00 or fg = 11. Monitoring these outputs is required to initiate the repair process in the case that a fault occurs. It is assumed that this monitoring is done so that each fault is repaired before another has a chance to occur. Methods of monitoring the checker are discussed by Anderson [2J. Self-checking checkers have not yet been designed to check arbitrary input codes, but have been developed for parity codes and certain classes of m-out-of-n codes. In the latter case, the most clearly stated tech- niques are for the case where n = 2m. Codes of this type are called k-out- of-2k codes, and it is this kind of code which will be used in this paper. Certain m-out-of-n codes can be converted to k-out-of-2k codes using a self-checking code-disjoint translator, but designing self-checking asynchronous machines to yield these special cases in their state assign- ments is much more difficult than presenting a general design algorithm which yields a k-out-of-2k state assignment, where k may be any integral value . As the self-testing property of totally self-checking checkers implies, every internal fault has at least one corresponding input codeword which, when applied to the checker in the presence of that fault, yields a non-code output, namely fg = 00 or fg = 11. Thus the code space of all the input codewords is sufficient to check the checker for the presence of all inter- nal faults. The size of this code space is the number of binary words of 2k length 2k in which k bits are ones, or ( ) . As will be shown later, 2k checkers with certain internal structure may require fewer than ( ) JtC codewords . 3. DESIGN OF TOTALLY SELF-CHECKING CHECKERS FOR k-OUT-OF-2k CODES This design method presented by Anderson and Metze [3] requires dividing up the input bits into two groups A and B of k bits each, denoted by A = {a n , • • • ,a, }, B = {b n ,''-,b, }. Thus a word in a 4-out-of-8 code 1 k 1 k would be represented by a, a^a„a. b, b„b„b . . Let k and k. denote the number 12341234 a b of ones occurring in each group, respectively. Define the majority func- tion T(k > i) to have the value 1 if and only if the condition inside the a — parentheses is true, in this case if group A has at least i ones. If i = 1 for example, then T(k > i) = (a 1 +a„ + - • «+a ) . The two output functions f EL J. £m K. K. and g are given by k k f k = 2, T ( k a >i)- T ( k b > k -) i=0 i odd 8 k = ^ T(k a >i).T(k b >k-i) . i=0 i even Note: M +" denotes the OR function; "•" denotes AND. Example: for k = 3 f = T(k > 1)-T(k u > 2) + T(k > 3)-T(k t . > 0) 3 a— b— a— b — = (a 1 +a 2 +a 3 )(b 1 b 2 +b 1 b 3 +b 2 b 3 ) + {a.^^^,-! g 3 = T(k a > 0)-T(k b > 3) + T(k a > 2)-T(k b > 1) = l-(b 1 b 2 b 3 ) + (a 1 a 2 +a 1 a 3 +a 2 a 3 )(b 1 +b 2 +b 3 ) . Each output function must be independently implemented from the inputs and may not share any logic with the other. Since f and g are both positive functions, any number of decreasing (one- to-zero) faults in the input code or in the checker results in fg = 00 and any number of increasing (zero- to-one) faults results in fg = 11. 4. DESIGN OF SELF-CHECKING ASYNCHRONOUS SEQUENTIAL CIRCUITS 4. 1 Asynchronous Machine Model The model with which we will deal here is that of a standard asyn- chronous sequential machine operating in the fundamental mode, initially with single transition- time (STT) assignments. We will therefore assume single input changes. Operation of the machine is described by means of a flow table and we will assume that before this design process is begun the table has been reduced completely. The faults which are under con- sideration here are those faults which affect the internal mapping of inputs and present state into next states; we will not be concerned with faults in the output circuitry. Furthermore, it is assumed that, for the purpose of assuming single faults, and to check the checker, the machine will visit all of its internal states in a time less than the mean-time- between-failure (MTBF) . 4.2 Internal Design for Self-Checking Characteristics As the encoded output of the sequential machine is in the form of next-state values, any fault-detection capabilities must appear as changes in the next-state assignment. By avoiding redundancy in the next-state equations the circuit can be designed so that any fault will, for some present-state input, produce a next-state value which is different from normal. The difficult task is to assure fault-security, i.e. guarantee that the abnormal next state is not itself a valid codeword representing another state, but is rather a non-codeword. Therefore the set of error states (those state variable vectors produced by internal faults) and the set of proper next states must be disjoint sets. This is achieved by using 8 a code such that the distance between codewords is greater than the dis- tance between a given codeword and any of the error states to which it may be converted by any fault from the prescribed set. Recall that normal design of an asynchronous machine requires that, for every pair of states between which there is a transition, there must be at least one state variable which partitions those states from the remainder of the states. To achieve the distance between codewords required for fault-security, Maki e_t al_. [l] have shown that it is necessary and sufficient to provide two state variables which partition a given tran- sition path from the others in the same input column. Then to assure that this distance is greater than that by which a codeword can be changed by a fault, the two partitioning variables must be implemented independently so that a single fault cannot affect them both. Finally, to prevent a transition from an error state to a valid state before the input changes again, and thus before the checker has had a chance to detect the illegal state, the next-state entries for the error states must be specified to be equal to their present-state values for the partitioning variables between transition paths. The operation of the machine is then such that any fault will cause the machine to enter an illegal state and remain there long enough to be detected. The state assignment procedure presented by Maki achieves this desired performance but it does not produce a state assignment which is compatible with known self-checking checkers. Hence the following procedure is presented which supplies the required partition- ing and in addition yields a code, using as few state variables as possible, which may be checked by an easily designed self-checking checker. Consider first the following essential definitions. Let S be the set of states of the machine, and let N be the number of states in S. Definition : A k-set (Unger's [5] "destination set"), determined from an input column, is a subset of S consisting of a stable state and those states which have unstable entries in that column leading to that stable state. Definition : A n-partition (Maki's [l] "column partition") is the collec- tion of all the k-sets from a given column. If the column has no don't-care entries, then the n-partition will be completely specified, i.e. the union of the (disjoint) k-sets will be S. Part of the following pro- cedure will convert all incompletely specified tt- partitions to completely specified ones. Definition : A T-partition is a two-block partition of the members of S. Each TT-partition will require one or more T-partitions to cover it, i.e. for a given n-partition, it must be true that for every pair of k-sets in it, there exists a T-partition that separates the pair into different blocks of that T-partition. Each T-partition will be completely specified over S and will ultimately ' determine two state variables, each of which partitions those states in one block from those in the other block. 4 .3 State Assignment Procedure Goal : Given a reduced flow table, produce a k-out-of-2k state assignment preserving fault-security. Step 1 : Starting with those columns containing no don't-care entries list all the "-partitions by listing all the k-sets from each column. To minimize the number of k-sets, note the following definition and theorem. Definition : For a given input column, a bachelor state is a stable state with no transitions to it under that input. Theorem 1 : For a given input column, all bachelor states may be placed in the same k-set. 10 Proof : Let S. and S„ be two bachelor states in a given input column. If S. and S_ are in different k-sets under a different input then the required partitioning is taken care of in that TT-partition , and there is no need to repartition S 1 from S« . Thus they can be grouped together in the same k-set for this column. If S, and S 9 do not appear in different k-sets for any other input column then they are equivalent states and should be merged together and a new reduced flow table formed. This completes the proof . Step 2 : For a column containing an unspecified (don't-care) entry, first list the k-sets without including the state whose entry in that column is unspecified. Then add this state to one of these k-sets so that as many k-sets as possible in this n-partition match identically those in another n-partition. This merely helps minimize the number of state variables needed. Adding the state to a given k-set corresponds to placing in the don't-care entry an unstable entry of the stable state of that k-set. Step 3 : Delete any n-partition which contains only one k-set, or which is covered by another n-partition. Step 4 : For each remaining n-partition, determine a set of T-partitions which cover it. Unger [4] and Tracey [5] offer techniques of determining minimal covers, or one may proceed according to the following method. Let n be the number of k-sets in a given n-partition. Then the number of T-partitions required to cover TT, n , is given by n T = |log 2 (n k )l where x i means "the least integer not smaller than x." We will describe a technique to be used when n = 2 for some integer j. For 2 < n, < 2 11 the technique is the same, with the excess 2 -n, k-sets k disregarded . Given 2 J k-sets in some arbitrary initial order. Generate the T-partitions t t ••• in sequence as follows: t has the first 2 k-sets in its first block, t he second 2 k-sets in its second block, J-2 t has the first 2 " k-sets from each block of t in its first block, the second 2 k-sets from each block of t in its second block. t. has the first, third, ■••, (2i-3) groups of 2 J k-sets from each block of T. in its first block, and the second, fourth, •••, (2i-2) groups of 2 k-sets from each block of T, in its second block. This process continues until i = j, since with i = j we are now simply picking alternate k-sets from T. (group size 2 =1). Thus the last T-partition is T • , so j = log 9 2 = log„ (n ) is the number of T-partitions j 2 2 k required to cover a TT-partition containing n = 2 J k-sets. K. Examples : Let A,B, ,- *,P be generalized k-sets. n k = 2: t = (A,B) n k = 3: T l = (AB,C) n k = 4: t l = (AB,CD) n = 5: T - (ABC,DE) n R = 6: t = (ABC,DEF) n = 7: t = (ABCD,EFG) n = 8: T = (ABCD,EFGH) T 2 = (AC,B) t 2 = (AC,BD) t 2 = (ABD,CE) T = (ABD,CEF) t = (ABEF,CDG) t = (ABEF,CDGH) t 3 = (ADE,BC) T = (ADE,BCF) T = (AECG,BFD) T = (AECG,BFDH) n = 16: t = ( ABCDE FGH , I JKLM NOP ) T = (ABCDLJKL,EFGiMNOP) T = (ABIJEFMN,CDKLGHOP) T = (AIEMCKGO,BJFNDLHP) . 12 In the last example, the underlined k-sets in T , i=l,2,3 are those that go in the first block of T . . Note that in every example, any two k-sets appear in different blocks of at least one T-partition. For n > 2, the above choices are only suggested, not unique, and choices should be made wherever possible to find T-partitions which help cover more than one n-partition. An example of this follows. Example: Given S = {a,b,c,d,ej and the following set of n-partitions: n = (ab,cde) n = (ade,bc) n = (ae,bcd) n 4 = (a,bc,de) tt is covered by T = (ab,cde) n is covered by T = (ade,bc) TT is covered by T = (ae,bcd) n is covered by any two of the following three T-partitions: T = (a,bcde) T = (abc,de) t 6 = (ade,bc) . It is immediately seen that T, = t so t„ can be used to partition a from o 2 2 be and de_ from bc_ (all derived from TT ) . All that is needed then is a T-partition which partitions a from de_. This is already done by t , so in this example T , T and t cover all four n-partitions. Step 5 : Suppose we now have all TT-partitions covered and have N unique T-partitions. We now generate N = 2«N state variables by associating two unique state variables with each T-partition as follows: 13 Y. = 1 for all states in the left block of T. , i l Y. = for all states in the right block of t. , l l Y XT . = ~ , i=l, • • • ,N . N +1 i ' ' t T For those columns producing only two k-sets, this method produces the same state variables as Maki ' s [l] method since, although this method requires two state variables per T-partition, Maki ' s technique would have two "re- partitions for each two-k-set ff-partition. In general, Maki requires only one state variable per T-partition since he produces one T-partition per unique k-set; this method yields two state variables per T-partition, but requires fewer T-partitions to cover all the k-sets in their respective TT-partitions . With the Y's in order from Y to Y_ this yields a k-out-of-2k state T assignment with k = N . Furthermore, the state assignment is such that each state vector can be divided, into two groups A and B containing equal numbers of bits with b. = a. where a. = Y. and b. = Y„ ., i=l ,• • • ,k. l l 11 i N +i ' T Finally, each k-set is partitioned from every other k-set in its TT-partition by two state variables. A bound on the number of state variables can be computed directly from N , the total number of n-partitions , and n, , the number of k-sets i in TT. a i=l,*--,N , and is given by N v <^ 2flog 2 (iy)] i=l with equality occurring in the case where no T-partition helps cover more than one TT-partition (i.e. when the mapping of T-partitions onto n-par- titions is one-to-one). u 4.4 ExampLes We will now illustrate the state assignment procedure with several examples . Example A : Consider the flow table in Figure 1. List the ^-partitions : n L = (ac,bd) n 2 = (abed) H 3 = (ad, be) n = (a,bc,d) = (ad, be) from Theorem 1. tt and TT can now be eliminated according to Step 3. Determine T-partitions : t l = (ac,bd) t 2 = (ad, be) Assign state variables: h Y _2 h \ a = 1 1 b = 1 1 c = 1 1 d = 1 1 Example B: Consider the flow table in Figure 2, which was adapted from Maki ' s machine A by merging states b and c and adding an additional input column. List n-partitions : tt = (ae,cd) from columns 00 and 01 tt = (ac,de) from column 11 tt = (ad,ce) from column 10 . 15 X 1 X 2 00 01 11 10 © b d ® ® ® c c a b © © b b @ © Figure 1. Flow table for example A, X 1 X 2 00 01 11 10 © e © © © © a © - c © a a © d c Figure 2. Flow table for example B. 16 List T-partitions : T = (ae,cd) t 2 = (ac,de) t 3 = (ad,ce) Assign state variables: Y l Y 2 Y 3 \ Y 5 Y 6 a = 1 1 1 c = 1 1 1 d = 1 1 1 e = 1 1 1 Example C : Consider the flow table in Figure 3. List the Tr-partitions : TT = (ae,bcd) from columns 00 and 01 TT = (ac,b,de) from column 11 tt = (ad,b,ce) from column 10 . List the T-partitions: t = (ae,bcd) covers tt T = (abc,de) helps cover tt T = (ad, bee) helps cover n T = (b,acde) helps cover tt and TT . Here the maximum number of T-partitions required to cover the three tt- partitions (five) has been reduced to four through the sharing of one T-partition. 17 X 1 X 2 00 01 11 10 b e © c ® © a © c © a d c Figure 3. Flow table for example C, Assign state variables L8 v l Y 2 V 3 \ Y 5 Y 6 Y 7 Y 8 a = 1 L 1 1 b = 1 L i L c = L 1 L 1 d = 1 1 i 1 e = 1 1 L 1 When attaching this to a self-checking checker, the checker's output functions f. and g would be implemented according to the design equations presented earlier, with a •••a. = Y • • -Y. and b •••b. = Y ■••Y„. 14141458 19 5. ADAPTING THE SEQUENTIAL MACHINE TO THE CHECKER ■ 5. 1 General Problems Having now achieved a state assignment employing a code for which we can easily design a self-checking checker, we must now attack the problem of implementing the checker. According to the design equations for a k- out-of-2k checker given earlier, any realization of the functions f and K. g will yield a self-checking checker. However, a two-level realization K. requires the presentation of all the codewords in the code space to the checker to check for all of its possible internal faults. Since our code- words are states of a finite state machine, we have available only those codewords which are assigned to states of the machine. In most cases this is far fewer than the number required to check the checker. To overcome this, we can start by choosing a realization of the checker 2k that will enable it to be checked by fewer than the ( ) codewords that ma ke up the code space. Anderson [2] showed that when the checker is implemented directly from the equations, resulting in a four-level realiza- tion, it can be checked using only a special set of 2 codewords, namely those in which the rightmost k bits are the bitwise complements of the leftmost k bits, i.e. y . = y. , i=l,--«,k. The state assignment procedure just presented does in fact yield codewords with this property, so we are k 2k therefore lacking only 2 -N codewords, rather than ( ) - N codewords. D K. o Note that of the three examples presented above, only example A has suffi- cient codewords on its own. This problem of insufficient codewords is a serious one and cannot be ignored, for if certain faults in the checker go undetected because we do not have the codewords to check for them, then our single fault assump- tion is no longer valid. With an undetectable fault in existence, the 20 occurrence of another fault, which ordinarily might be detectable, may produce a situation whereby the two faults combine to destroy the checking properties of the checker. Most notably, they could destroy the code- disjoint property, and cause a non-code input to yield a code-space output. Since preventing inaccurate transmission of data of this nature is one of the primary values of having a real-time self-checking network, to allow such an error to occur would negate any value the checker adds to the con- fidence of the network. 5.2 Methods Which Do Not Work Several methods of attacking the problem of insufficient codewords were considered. One idea was to use only the available codewords and eliminate those portions of the checker which check for the occurrence of the unavail- able codewords and which are themselves checked for internal faults by the same unavailable codewords. This method was found not to work, however, since by eliminating those portions of the checker which check for the occurrence of the codewords we are not using, we lose the power to check for increasing (zero-to-one) faults in the codewords we are using. Thus the checker must remain intact, and the only solution lies in somehow making all the necessary codewords available to the checker. The idea of using a special test input which when switched on would feed the proper codewords onto the checker input lines was considered but also rejected because the test input must itself be testable, and the addition of the logic it requires makes that too difficult to be practical. A third consideration, also ultimately rejected, was to use the method of multicode STT assignments presented in section 3.3.4 of Unger [5J. This 21 technique, commonly called state-splitting or row-splitting, assigns several different codewords to a given state, the maximum number being the number of columns in which that state is stable. Hence if a state A is stable in three columns, it may be represented by A 1 , A_ , and A~ . As is shown in table 3.16c in Unger [5], A , A., and A would then be stable in every column in which A was originally stable, with transitions to A in the first column in which it was stable now going to A 1 , and similarly for A_ and A- . Actually, these transitions need not be so constrained, and can in fact go to any A., but having all those in a given column go to the same A. means that the other split versions of A are bachelor states in that 1 column, and hence at most one new k-set must be added to the existing k-sets from that column. The flow table now has a number of new stable states added to it, and even though the additional states in each column are bachelor states, this leads to problems of partitioning. To understand this, consider the situation from an abstract point of view. We started with an original flow table which produced a set of partitions and a state assignment. This assignment defined a code space and, along with the codewords assigned to existing states, a number of new codewords which must have states assigned to them. This additional assign- ment implies an expanded flow table and essentially a new machine, which is subject to two major constaints. First, it must operate the same as the old machine in mapping input sequences into outputs. And second, it must be such that if its flow table were simply taken as an original flow table, it must yield a state assignment identical to the one which has already been specified. In light of these constraints, how can these split states be partitioned to preserve the essential properties? If the split states are considered 22 equivalent by virtue of their having been derived from the same original unsplit counterpart, then they need not be partitioned from each other. Thus they will all be assigned the same state assignment and will be of no use in producing new codewords. If, on the other hand, they are considered independent and partitioned like any other stable states, then in almost every case this new partitioning will require a new state assignment code of the form (k+j )-out-of-2 (k+j ) for some non-zero j equalling the number of new T-partitions. This new code will in turn require more state-splitting to supply even more codewords. This will not converge to a feasible assignment. The only case in which new partitioning does not require a new state assignment code is the case where each column produces its own unique TT- partition, no TT-partition contains a number of k-sets that is a power of two, and no T-partition helps cover more than one TT-partition. However, even in this case state-splitting will not work because the number of new states created by splitting every state that is stable in more than one column into ultimately as many states as columns in which it is stable will still be less than the number of new codewords required to reach 2 . This is verified by the following argument. Let m be the number of input columns and x be the number of states of the machine. m and x are both positive integers, and for the sake of simplicity and maximum state splitting assume they are both even numbers. my With maximum state splitting, the maximum number of total states is —, and the number of T-partitions is m* log 9 (—) . Therefore to have at least as many total states as codewords required, it must be true that m * | log 2 ( ^f' > I S* >2 2 23 which implies log^^y-) > m log 2 (j) | . Since j log 2 (-) | > log 2 (-) , then the above implies log (^ >m-log (j) which implies log (— ) > log- (— ) and hence (— )-m > (— ) . '2 V 2 ' - 6 2 v 2 '2 v 2 ' — J " w ' 6 2 v 2 / ' a,llu " ss "*-° \t / ' »' ^ v^ With the above constraints on m, x, and the machine (for example x > 4 since x < 4 means that every rr-partition will have n equalling a power of K. two), the final inequality cannot possibly occur, and therefore state- splitting will not work. Hence the following method seems to be the only valid technique for acquiring additional codewords. This technique involves the assignment of the additional codewords as unstable states which may be cycled through during transitions between the. machine's original stable states. This allows the partitioning dictated by the 2 codewords to stand unimpaired, as transitions in a given column may pass through any states having a value of 1 for the state variable originally created by the T-partition for those transitions in that column. It is assumed, of course, that the time during which the machine is in these unstable states is sufficient to check for the corresponding faults in the checker for which the new codewords are required. Note that the machine is no longer operating with STT assignments. 5.3 Technique for Cycling Through Additional States Step 1 : List the additional codewords underneath the original ones in any order. Step 2 : Label the new codewords with state names similar to the original state names. Step 3 : Now, paying attention only to the leftmost k columns in the state assignment, corresponding to Y. ' ' 'Y, 3 recall that each column was determined X K. by a unique T-partition. The new states must be added to the T-partitions 24 so that if the T-partitions with these additions were taken a_ priori then they would produce the state assignments which we now have and cannot change. Therefore add those new states that have 1-entries in column i (i.e. Y.) to the left block of T . and those that have O-entries to the i 1 right block of T. , i=*l,»»»,k. When this has been completed for all k T- k-1 partitions, each T-partition will now have 2 ' states in each block, regardless of how many it had in each block initially. Step 4 : The new states in a given block of a given T-partition may now be cycled through as unstable states in the transitions that occur among the original states of that block, provided such transitions exist. Blocks originally containing only bachelor states cannot be used, nor can implied transitions caused by a don't-care entry in the flow table. Blocks con- taining valid transitions will be called "viable blocks'*. Example: Suppose a block originally containing S 1 and S„ (among others) now has S. , and S 19 added. If the original transition was S_-S 1 , it may be replaced by S -S -S -S . To achieve the greatest speed, it may be desirable to include each new state in only one transition. In the above example, if S.. _ is in a viable block in another T-partition then it may be used in a transition there, and the above transition may be reduced to S -S -S 1 . Referring to the original flow table and the new T-partitions, include each new state in some legitimate transition. This dispersal of the new states throughout the transitions of the original machine requires the assumption that under normal operation all of these transitions will occur, and in a time period less than the assumed MTBF. In cases where certain transitions are known to occur more frequently than others, it may be wise to include as many new states as possible in those transitions. 25 Step 5 : The flow table must be modified to reflect the addition of the new states. For a given column, those transitions which are to be replaced by sequences of transitions involving the new unstable states are modi- fied by placing in the row of each state in the sequence an unstable entry of the next state in the sequence. Those states which are not involved in transitions under that input may have don't-care entries placed in the table under that input. No stable state entries are added to or deleted from the original stable entries in the original flow table. 5.4 Examples To illustrate this procedure, we will continue with the three examples which served to illustrate the state assignment procedure. Example A : The state assignment for the machine whose flow table appears 2 in Figure 1 was shown to be a 2-out-of-4 code. This requires 2 =4 code- words. Since the machine has four states and their code is such that Y, . = Y. no additional codewords are needed to check the checker, k+i l Example B : The state assignment for machine B whose flow table appears in 3 Figure 2 is a 3-out-of-6 code and thus requires 2 =8 codewords, of which we have only four. ' The additional four codewords we need are the four remaining binary combinations of Y..Y Y . Assign and label new codewords: Y i Y 2 Y 3 Y 4 Y 5 Y 6 a = 1 1 1 c = 1 1 1 d = 1 1 1 e = 1 1 1 26 f = L g = L 1 1 h = 1 L L i = L L 1 Add new states to ^-partitions : T = (aefg,cdhi) T 2 = (acfh,degi) t 3 = (adgh,cefi) . Note for example that Y„ = 1 for those states in the left block of t„. Modify flow table: The first modification of the flow table, illustrated in Figure 4, uses all the new states wherever a transition is available. This maximally specified flow table produces a slow but sure machine. Looking under column 00 for instance, one may see that the original e-a transition has been replaced .by e-f-g-a, as is indicated by the first block of T . The second modification of the flow table for machine B, illustrated in Figure 5, uses each new state in only one transition. For machines whose transitions occur with uniform frequency this minimal specification is the more efficient method. Example C : The state assignment for machine C, whose flow table is illus- 4 trated in Figure 3, is a 4-out-of-8 code requiring 2 =16 codewords to check the checker. Hence we must add eleven new states. Assign and label new codewords: 27 X 1 X 2 00 01 11 10 © f © © © f © - h © g f © g f 8 g h i a e i h - i a a c d c Figure 4. Maximally specified expanded flow table for example B X 1 X 2 00 01 11 10 © g © © © © h © - c © a f a © d i e - - - - a - - - - c Figure 5. Minimally specified expanded flow table, for example B 28 Y i Y 2 Y 3 Y 4 Y 5 Y 6 Y 7 Y 8 a = 1 1 1 1 b = 1 1 1 1 c = L 1 1 L d ■ 1 1 1 L e = 1 1 L 1 f = 1 1 L 1 g = 1 1 1 1 h = 1 1 1 1 i = 1 1 1 1 J = 1 1 1 1 k = 1 1 L 1 £ = 1 1 1 1 m = 1 1 L L n = 1 L 1 1 o = 1 1 1 1 P = 1 1 1 1 . Add new states to T-partitions : T = (aeghi ^mn,bcdf jkop) T = (abcgj imo,defhiknp) T = (adhjk&io, beef gimp) t = (bfikimno,acdegh jp) . Note that the first block of r, is not a viable block and therefore cannot 4 be used to cycle through any new states. Modify flow table: The maximally specified flow table is illustrated in Figure 6; the minimally specified flow table is illustrated in Figure 7. X 1 X 2 29 g h i J k i m 00 01 11 10 © g © © © f © © f © g © - o © h 8 © f f J J h g h h J i i i i J i I k m k k I k o c n I m' m m n n n o P a e P o P P a a b c d c Figure 6. Maximally specified expanded flow table for example C, 30 X 1 X 2 a b c d e f g h 00 01 11 10 © i © © © k © © f © i c 1 i © m 1 8 1 © n P 1 1 J 1 - - - J k m Figure 7. Minimally specified expanded flow table for example C, 31 6. DESIGN EQUATION CONSIDERATIONS The only remaining aspect of the design process is the generation of the design equations for the state variables. For those machines which have 2 original stable states and generate a k-out-of-2k state assignment, such as in example A, Maki's short-cut method of producing design equations by inspection may be employed. For those machines requiring the addition of unstable states to supply additional codewords, conventional methods may be used. As that is simply a mechanical exercise, it will not be illustrated here. In either case, for any Y. , i=l,***,2k, the term y.I. must be included or covered, where I. is the input column (or the OR of the input columns) which determined the T-partition from which Y. was generated. This assures that during a transition any error-free partitioning variable will retain its present value so that if the other partitioning variable is affected by a fault the machine will assume an error state and remain in one at least until the input changes. Finally, whatever realization is chosen, the next-state variables must be independently implemented from the inputs and present-state variables. This is absolutely essential to main- tain fault-security-. 32 7. CONCLUDING REMARKS A design method has been presented here for the construction of totally self-checking asynchronous sequential machines. These machines include a check circuit which not only detects errors in the state-deter- mination logic of the sequential portion but which detects errors in its own internal circuitry as well. All checking of the entire system is therefore done in real time, thus obviating interruption of normal opera- tion simply to check for faults. The necessary state assignments are easily generated and the remainder of the design procedure is rarely more difficult, and sometimes easier, than standard techniques. The price of the self-checking property is sometimes paid for in logic, and the deter- mination of whether this feature is worth the price is ultimately left up to the individual designer. 33 LIST OF REFERENCES 1. D. W. Sawin, III, G. K. Maki, and S. R. Groenig, "Design of Asynchronous Sequential Machines for Fault Detection," Digest 1972 International Symposium on Fault -Tolerant Computing , Newton, Mass . , pp. 170-175, June 1972. 2. D. A. Anderson, "Design of Self-Checking Digital Networks Using Coding Techniques," CSL Report R-527, University of Illinois, Ph.D. Thesis, October 1971. 3. D. A. Anderson and G. Metze, "Design of Totally Self-Checking Check Circuits for m-Out-of-n Codes," IEEE Trans , on Computers , Vol. C-22, pp. 263-269, March 1973. 4. S. H. Unger, Asynchronous Sequential Switching Circuits , Wiley- Interscience, N.Y., 1969. 5. J. H. Tracey, "Internal State Assignments for Asynchronous Sequential Machines," IEEE Trans , on Electronic Computers , Vol. EC-15, pp. 551- 556, August 1966. BIBLIOGRAPHIC DATA SHEET 1. Report No. uiuCDCS-R-73-593 3. Recipient's Accession No. 4. Title and Subtitle Design of Totally Self -Checking Asynchronous Sequential Machines 5. Report Date September 1973 7. Author(s) Daniel Avery Pitt 8. Performing Organization Rept. No - UIUCDCS-R-73-593 9. Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. ll2. Sponsoring Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 13. Type of Report & Period Covered Master of Science The si 14. 15. Supplementary Notes 16. Abstracts Techniques have been developed for designing asynchronous machines that indicate faults by assuming error states. Design methods have also been found for the construction of self -checking combinational networks which indicate errors either in their coded inputs or in their own circuitry. This paper presents a means of uniting these two methods to yield asynchronous sequential machines which are self -checking . The problems inherent in the individual design procedures for the two methods as well as those which arise in making the two methods compatible are discussed. 17. Key Words and Document Analysis. 17a. Descriptors Fault-detection Sequential machines Self -checking 17b. Identifiers /Open-Ended Terms 17c. COSATI Field/Group 18. Availability Statement Unlimited Release 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 37 22. Price FORM NTIS-35 (10-70) USCOMM-DC 40329-P71 ft» z o\*»* UNIVERSITY OF ILLINOIS-URBANA 510 84 IL6H no COO? no 5B0 584(1(73 O.ilgn ol totally tell chicking iiynchro 3 0112 088400897 ■ ■ ■ **^v^ 1 I ■ # , H , MM J* ■ .Jw.* 4 ■ .1/ I