THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING ERROR CHECKING AND THE STRUCTURE OF BINARY ADDITION By Harvey. Louis Garner A dissertation, submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan 1958 July, 1958 IP-05o

15SDo Doctoral Cormnittee: Professor Alan B. Macnee, Co-Chairman Professor Norman R. Scott, Co-Chairman Professor Arthur W. Burks Professor Harry H. Goode Professor Gunnar Hok

ACKNOWLEDGMENT The author wishes to express his gratitude to all the members of his doctoral committee. In particular, the author is indebted to the committee for the critical review afforded the first draft copy of this dissertation. The author wishes to express his gratitude for the encouragement and aid given by his wife during the period in which this dissertation was being written and prepared for publication. Last, an expression of thanks is due to the Industry Program of the College of Engineering for the excellent services rendered in the preparation and reproduction of this dissertation. ii

TABLE OF CONTENTS Page ACKNOWLEDGMENTS.......... o...... i*..... i LIST OF TABLES......O.......... o.......................... v LIST OF FIGURES......................................... vi NOMENCLATURE.................................. --............ vii I. INTRODUCTION....................................... 1 II. GENERALIZED PARITY CHECKING............................. 7 Introduction........................ 7 Congruences....................................... 8 Generalization of Parity.... 9 Arithmetic Invariance of the Digital Parity Checko. 12 Examples of Arithmetic Checking (m=b=lO)..... 18 Numerical Checking, Mod m(m/b), of Arithmetic Operations......~ ~.............................. 20 The Diminished Base Numerical Check................ 21 The Augmented Base Numerical Check................ 23 Examples of the Augmented Base Check................ 25 Conclusion........ 0 O.. * 00 0.~..~~o O ~~ 26 III. VECTOR SPACES AND BINARY ADDITION..o................... 27 Introduction.o.......o....................... 27 The Elementary Concepts of Vector Spaces......... 28 Vector Representation of Binary Numbers............ 34 Vector Length and Parity..................... 37 The Vector Space of Binary Addition...o...........o 39 The Carry Vector........................... 42 Methods of Generation of the Carry Vector......... 46 Synthesis by Vector Space Operations............... 54 Numerical Relationships,..................... 57 Addition Algorithms..........................~ 60 Constraints and Some Properties of the Addition Algorithms...........................O..... 62 Evaluation of the kp and the Vp Logic............ 69 IV. THE ERROR STRUCTURE OF BINARY ADDITION AND THE EFFECTIVENESS OF THE PARITY CHECK....o0*.........*..... 73 Introduction..................................... 73 The Error Structure of the Carry Logic of Standard Addition............................... 75 iii

TABLE OF CONTENTS (CONT' D) Page The Nature of the Propagated Error............... 82 The Average Length of Carry Propagation..........0 86 The Error Structure of the k, p and V Generating Logic for Standard Addition................... 89 The Error Structure of the rc Sum Logic........ 96 The Effectiveness of Parity Checking,.....,,..... 98 V. THE RESIDUE CODE..,o....o....... *..................... 105 An Extension of Numerical Checking................ 105 Residue Addition and Multiplication.................. 110 Subtraction and the Representation of Negative Numbers...................................... 114 Conversion From a Residue Code to a Normal Number Representationo...... ~...O............... 117 Greater Than or Less Than Relations for Residue Codesoo.. o........... oo..o.o.o....1........ 120 Redundancy..... O ooo...ooo................o..... 125 Division, o..OO..OO..O.O.OO...o......oo....O......... 135 Conclusions,. O. O.O.O. O......O.O.O............. 139 VI. CONCLUSIONS AND RECOMMENDATIONS......................... 141 APPENDIX....*............................................. 148 Sign and Overflow Convention for One's and Two's Complement Arithmetic..o....oo..oo.o...oo..o.... 148 BIBLIOGRAPHY............................................... 153 iv

LIST OF TABLES Table Page I Relation Between aj b, and vj, k o.. * o.........0 57 II Frequency of Occurence of Different Types of Carry Logic Malfunctions........o o. o o........ 79 III Summary of Errors., ~............................. 99 IV Error Type..o...<...........o.................. 100 V Error Distribution (Normalized),..,o..,..,....oo o.. 100 VI Redundancy of a Non-Relatively Primed Base Representation, o...oooo. o eoooooo..oo.oo.oo.o.ooo. 106 VII Natural Numbers and Corresponding Residue Numbers.. 108 VIII Number of States and Digits Associated with a Residue Representation o........0000o.00o.o0000000o 109 IX Mod 2 and Mod 3 Sums and Products..O,,o...,00...o,. 111 X Residue Code Efficiency o... o...,... o. o. 133

LIST OF FIGURES Number Page 1 Venn Diagram o.........................,,..............,, 32 2 Carry Vectoro.........,.................. o.. 43 3 Logic for Independent, Sequential Generation of One Carry Element................ o.. o...... 49 4 Standard Carry Logic Cog ooooo...........oooooooo 53 5 Sum Dependent Carry Logic ~..oo O..,.o...o....... 56 6 Half Adder,.....,.o,........................... 70 7 Realization of the kp Addition Algorithm,.......... 70 8 Carry Logic for the Standard Addition Algorithm.... 71 9 Carry Logic for the vp Addition Algorithm......... 71 10 Adder Logic,............................ 74 11 Probability that ci = lo,...o o................ 78 12 Carry Logic o o... o.ooo. o......60000. oo 80 13 Flow Diagram for the Average Length of Carry Propagation.. 0 o O 0 o ^.. o...... o..... o.... o o 88 14 Logic for the Determination of the Greater or Less Than Relationship., o.....,....................... 124 15 Relative Efficiency of the Residue Code o.......... 134 vi

NOMENCLATURE [A] - the matrix A [A-1] - the inverse matrix of A [At] - the transpose matrix of A D(x) - the dimension of x dlo - diode number one, open dls - diode number one, short eq - is equivalent to [G] the metric matrix gij - an element of the metric matrix k - the result of X @ Y kj - an element of k p(a) - the probability of n one digits in a vector a p(rj) - the probability that r., and element of the vector is zero P (cj+l) - the probability that cj+l, an element of the carry j=1 vector, is unity when rj is constrained to a value of unity p( A Cj+l) ( -c- the probability that cj+j, an element of the carry rJl vector is changed due to a constraint rj=l p(A* cj) - the probability that the last element altered by a propagated error is cj P_ (ki ) r(ki) - the probability that ki = 0 if ri = 0 rj - an element of'p s - an element of a vii

NOMENCLATURE (CONT'D) u - mean (statistical) V - the result of X v Y v - the connective for inclusive disjunction vj - an element of V var, - variance (statistical) x - diminished radix complement, also the bar is used to indicate logical negation x - radix complement or additive inverse Z zero or null vector 5ij - Kronecker delta e - "an element of" p - the result of X O Y a - the sum vector - congruence relation A a mod b reads A is congruent to a modulo b - modulo addition sign, also the symbol is used to indicate the exclusive disjunction which is addition modulo 2 G - modulo multiplication or logic conjunction which is multiplication modulo 2'c- <- is replaced by - is in one to one correspondence with - material implication connective; AHB is read if A then B ^^)- ~ - and gate ) ~- or gate 3^~ -e exclusive or gate ~^(^/- - negation element viii

CHAPTER I INTRODUCTION The modern electronic digital computing machine owes its origin to the concepts presented by Charles Babbage in 1835. (1) However, it was not until 1946 that technology reached, a s' fficiently advanced state to permit the development of a large scale digital electronic computer o The ENIACa () completed, in 1946, consisted, in part, of 18,000 vac-uum tubeso Successful computation was performed on the ENIAC during an era in which some difficulty was encouuntered in obtaining consistent operation of radar and communication circuitry consisting of two hundred or so vacuum tubes. The state of the art in regard to computer reliability has made tremendous advances in recernt yearso The efforts to obtain more reliable computing systems have followed three general lines of attack. (1) The past decade has witnessed the introduction of new devices which offer increased component reliabilitya Furthermore, the operational components of a computer such as the flip-flops have been subjected to a thorough engineering studyo The results of such detailed engineering studies have led to optimeal deesign techniques in terms of known tolerance levels (2) A second basic approach to the problem of inereased. reliability is throagh t:he use of red-oimdant coponents0 The work in this field ranges from consideration of increased reliability obtained by duplication up o n-tu-plication considered by Von Neumanrni3) The efforts in this area are divided roughly into two general classes' those which employ circuit redundancy with no error

-2detection capability and those which use redundant circuitry employing error detection schemes. The error detecting schemes frequently utilize a majority element which must function perfectly. The majority element determines the correct output on the basis of the majority output of the redundant circuits. It has been shown that the redundancy is most effective if applied at the lowest level. (3) The third approach to increased computer reliability is the utilization of redundant codes. The subject of redundant information coding has received considerable attention in recent years. (49) However, most of the effort in this field has been directed toward error detecting and correcting schemes pertinent to communication systems. Error detection and correction for arithmetic operations in a digital computer require a code which is arithmetically invariant. This is not a characteristic of most of the error correcting and detecting codes developed for communication applications. One exception is the Hamming code. (5) Error correction by means of the Hamming code for a general purpose computer of the Princeton class has been studied by Robertson. (10) Another class of arithmetically invariant codes, the residue code$ was used in the RAYDAC, The checking procedure used in this machine has been described by Blod, (ll12) but effectiveness of the check is not considered in this paper, The material of this thesis provides further information on the utility of the residue code. * (RAYDAC) Raytheon Digital Automatic Computer.

-3There have been many computers which have incorporated a simple parity checking system. Without exception the parity check has been used only to determine the validity of the computer storage mechanism and no attempts have been made to utilize the arithmetic invariant properties of the digital parity check. In fact, it appears that the true nature of the digital parity check has not been clearly understood. This is largely due to a cumbersome definition involving the oddness or evenness of the number of one digits of the representation. The main problem attacked in this thesis is concerned with the effectiveness of parity checking procedures in the detection of errors in the arithmetic operations of a binary computer. In the course of the investigation certain topics pertinent to the process of binary arithmetic were discovered and this material is also included. Particular emphasis is given to an extension of the numerical parity check which leads to an arithmetic system without carry. In Chapter II two types of parity checks are defined. The checks are the digital check which is a function of the digit symbols and the numerical check which may be a function of both the digit symbols and the positional weights. In this chapter congruence notation is introduced and the arithmetic invariance of the digital check is proved for the operation of addition. The results are then extended to the other arithmetic operations. The class of errors detectable by either type of check is discussed and examples are presented. Also in Chapter II congruences are used to generalize the concept of the digital parity check to include non-base-two number systems.

-4It is necessary to determine the error structure of the binary addition process before the effectiveness of the parity checking schemes can be evaluated. The binary addition process is complicated by the fact that the sum digits are not independent. The lack of independence is due to the propagated carry which is a feature of all weighted number systems. In Chapter III the structure of binary addition is investigated with particular emphasis given to the carry process. The mathematics of vector spaces was found to be particularly appropriate to the study of this problem. The general concept and properties of vector spaces are introduced and the mechanisms of binary addition are defined in terms of vector space concepts. Considerable use is made of matrix notation. The carry process is completely defined by a particular matrix. A study of the carry matrix is made and various circuits yielding different degrees of carry element independence are presented. Specific configurations are considered and it is shown that in general the price that must be paid in terms of time and equipment to obtain independence of the carry digits is too high. All of the different carry schemes which have been used in binary arithmetic units are derivable from the carry matrix presented in this chapter. The use of vector space concepts in connection with binary number representations sheds new light on certain problems. In particular, the conversion from one number code to another may be regarded simply as a change of basis. The length of a vector in an n dimensional space which corresponds to an n digit binary numer is shown to be equivalent to the magnitude of the digital parity check.

The concepts of dimensionality of vector spaces are used extensively to define possible checking procedures and also to provide alternative definitions of the addition algorithm. In particular, it is shown that identical sums are obtained from: (1) the binary addition of two operands (2) the binary addition of the conjunction of the two operands and the inclusive disjunction of the two operands. (3) the binary addition of the exclusive disjunction of the two operands and two times the conjunction of the two operands (4) the binary subtraction of the exclusive disjunction of the two operands from two times the inclusive disjunction of the two operands. It is shown that the carry process associated with the last two definitions has different characteristics than the carry process associated with the standard addition algorithm, but performance-wise the new algorithms offer no advantages not associated with the standard algorithms. In Chapter IV the results of Chapter III are applied to the detailed error structure of the binary addition process. The error structure is considered for the standard addition algorithm. The effects of logical malfunctions of the components which comprise the arithmetic circuitry are considered and classified. The probability of success of specific digital and numerical parity checks is determined in respect to the different classes of errors due to circuit malfunctions. It is found that the numerical check is 100% effective for single addition operations, The concept of the numerical check is extended in Chapter V. If a sufficient number of numerical parity checks are employed, it is

-6possible to obtain a representation consisting of the numerical parity check digits which may be substituted for the original representation. In fact, the use of an excess number of parity check digits leads to an alternative representation containing redundancy. A number representation so derived is termed a residue code. The arithmetic properties and the utilization of redundant information are considered. In Chapter VI conclusions and recommendations are presented. Appendix I is a description of a binary arithmetic sign and overflow convention pertinent to the material of Chapter IVo

CHAPTER II GENERALIZED PARITY CHECKING Introduction The concept of the parity check(5) is widely known and has frequently been used. to detect and. in some cases to correct errors in digital systems. The parity check is obtained by associating with each representation of information an auxiliary digit or group of digits known as the parity check digit (s). The proper choice of the relationship between the check digits and the information digits permits the establishment of mathematical operations, which may indicate erroneous digits or provide correction datao Parity checking is usually defined. for the binary system in terms of the odd or evenness of the number of ONE digits in a specified block of binary digits o If the number of ONE digits is even the parity check digit is a zeroo If the number of ONE digits is odd the parity check digit is a one, This definition is sufficient for most practical applications of the parity concepto However, the definition gives no insight into the fundamental principles of parity. A restatement of parity in termLs of linear congruences provides a mathematical basis for the parity concept and permits a generalization which includes number sysetems of radix r j 20 Congruence notation aLso provides the mathematical tool required to prove the parity check invariant to addition for any consistently weighted number system if the carries are processed, correctlyo -7

-8Congruences The remainder of this paper will make considerable use of congruence notation. A short presentation of pertinent concepts and relationships is included at this point. Additional material on the subject may be found in any standard text on Number Theory. The congruence A- o( Mod b is read "A is congruent to c( Modulo b." The congruence relationship states that the equation A- o- + bt is valid for some value of t, where A,o, b and t are integers. c< is called the residue and b the base or modulus of the number A. As examples of congruences consider: 10- 7 Mod 3 10 4 Mod 3 10 1 Mod 53 In these examples the integers 7, 4 and 1 form a residue class of 10 Mod 3. Of particular importance is the least positive residue of the class which in this example is one. The least positive residue is that residue for which 0(<b.,** * Hardy and Wright() gives an excellent presentation on congruences. * The equality sign may exist on only one side of the inequality.

~9Unless otherwise specified the term residue as used in the remainder of this paper will mean the least positive residueo Congruences for the most part may be treated in the same manner as the equality sign in ordinary arithmetic The main exception pertains to division. The following properties of congruences will be used in this paper and are presented below without proof. 1 Congruences to the same modulus may be added and the result is a valid congruence. n n -Ai (oCi) Mod b i=l i-=l 2o Congruences to the same modulus may be multiplied and the result is a valid congruenceo n n WTAi A (TT )N Mod b i-l i=l 35 Congruences are transitive If A E B and B = C then A - Co o0 TEhe following congruence relationships provide a basis for numerical checking procedures (a) CTbn= 6Mod (b-l) (b) a bn- +-CMod <b+l) n even ~ -OMod (b+l) n odd Generalization of Parity A parity check need not necessarily include every digit of the number0 In the general case multiple parity checks may be employed,

-10each check concerning only specific digits However, for purposes of simplification, only the case of a single parity check over all digits will be considered here. The parity of a number from a consistently weighted number system is now defined. Consider the number r ~-;1 o o o- 1 This is the usual shorthand notation for the polynomial representation of a number N in a consistently weighted number system, base b: N e n&bn-1 + nlbn2+o+2bI + lbe The parity check digit p associated with number N is defined by: F(N) = p Mod m where p is the least positive residueo In this paper two different functions of N will be considered. The first function is F(N) = N and the parity check digit p is given by N p Mod m m b This type of check is based directly on the numerical properties of linear congruences and the check digit is a function of the magnitude of the number No This type of check is called a numerical parity check. If the check base m is identical to the number base b then N - (l Mod b The check is unsatisfactory because it is a function of only the low order digit of the number representation, This is due to the fact that "ibn - 0 Mod b n > o

-l-1 A check for the case m = b is obtained if F(N) - Cn +,n- + -o~ + 2 + 6i The parity check digit, p, for this type of check which is termed digital checking is defined by the relation n Z i - p Mod b i-=l An equivalent definition may be given in terms of ring addition. Ring addition modulo b is specified by the symbol $. Ring addition is simply normal addition without carry, for example (b-l) 1 = -0 In terms of ring addition modulo b the parity digit p is given as p = Cn $ (6nl $ oo. a2 (1Yl If the number system is binary, and the check base is two then the previous definition for the digital check provides a parity digit which makes the total number of one digits of the number plus check representation even in correspondence with the usual parity procedureso The definition is easily extended to an odd parity check, For this case the parity check digit is given by p, the diminished radix complement of p defined as pp p=b- 1 As an example of the parity definition for m = b, consider the following: Given 12894, a number in base 10 then (1 + 2 + 8 + 9 + 4) p Mod 10 or p = 1 2 0 8 0 9 = 4 4

-12' Both types of parity checks are restricted in application to the detection of certain classes of errors in the number representation. Error correction is not possible unless multiple parity checks are employed, The digital parity check. m = b, detects all alterations except the alterations in which the sum of the digit perturbations is congruent to 0 modulo bo Let the decimal number of the previous example be corrupted by 5 in the first column and by -5 in the third columno The result is an erroneous representation but the error is obviously undetectable e 2 e 3 9e 9 ~ 9 = - p 4 A numerical parity check Mod n,m m / b, is insensitive to an error if the magnitude of the error is congruent to zero Mod m. Thus the error is detectable only if the check base m is not a divisor of the magnitude of the error. The magnitude of the error in the previous example is 495, The error is not detected by Mod 35 5, 9 or ll checks. Parity checks are particularly effective in detecting errors for which only one digit has been modified. For this class of errors a parity check m = b is always effective If m is less than b then perturbations congruent to zero modulo m are undetectable. Arithmetic Invariance f thheDigital Parity Check In the arithmetic system employed in most digital machines a one-to-one correspondence is established between the machine digit representation and a set of positive and negative fractions. The rules of machine arithmetic operations are set up in such a way as to preserve

-13 - this one-to one correspondence under the operation of addition Addition is the fundamental arithmetic operation of the machine and the other arithmetic operations, subtraction, multiplication and division are defined in terms of addition and the auxilliary operations, shift and complement It is obvious that the digital parity check is invariant to the shift operation if no digits are deleted or added to the representation. This is true because the digital parity check is a check function of the modulo sum of the individual digit rather than a function of magnitude. Also, the parity check is independent of the position of the radix point. For this reason the remaining discussion will not explicitly consider whether the representations are in, correspondence with fractions or integers o Consider now the addition of two consistently weighted numbers in base be representation. The check base is, of course, also equal to b. A + ) = S or a o o a1 dn o o dl Cn+ln "Is1 now Si = ai $ di $ ci and (ai + di + Ci) = Si + Ci+lb c = 0 ci = o or Ci = 1 if i > 1

-14The parity check digit p for the sum is given as cn+l $sn $Sn-1 -ooeSl=PS or cn+ an 0 dn a cn P...e al d = pS but an ooo al p.A and drl ooo d p therefore Cnl1o.oC. c PA c P =P The last expression provides a means of checking the addition operation in terms of the parity check digits of the sum, the addend, — i ~*w ag edn atnd -te generated earrie&, Altera a-tively thte parity caeak may be in terms p, the radix complement or additive inverse of p defined as p' p = 0 If p' is used as the check digit rather than p the check procedure for addition is given as Cn c... cl 1A D The class of addition errors detected by the digital parity check is the same as the class of representation errors defined in the previous section. However, it must be remembered that the logic of the usual addition circuits is such that the various carry digits are not independent. The parity checking procedure is valid only if the carry digits are correcto

-15Consider the decimal addition of the following numbers: P 6 6 9 4 1 6 669416 32 4 5 1 5 993922 Due to the occurrence of one carry, the check of addition is 6e51=2 The check of the complement operation is straightforward. The diminished radix complement of a representation d is obtained by substituting for each digit (i the diminished radix complement, (1i. ri ( Ci =b-l given: 0r n Q1 = ps the n <~ -n e ~~ $ (1 4 61 = Ps1 n' Cn1 let (Tn ~ ~~ 0 a1 ~ Ps= PE a Ps = f then f a n(b-l) mod b (f+n) = nb mod b (f+n) -0 md b then Ps + pg + n = 0 mod b or p0, pge n mod b = 0 A check of the diminished radix complement consists of the modulo b sum of the parity check of the normal representation, the parity check of the complemented representation and the number of digits comprising the representation. In the special case where b = 2, the

-16check of the complemented representation is equal to the check of the normal representation if n is even and opposite if n is odd. A check of the radix complement operation is somewhat more complex than that required for the diminished radix complement. The complications are due to the definition of the radix complement rather than to the nature of the parity check procedure. Two checking procedures are possible The first is based on the fact that the radix complement s& is obtained from the diminished radix complement s by the addition of one to the lowest order digit This method requires cognizance of the carries produced when the one is added to the lowest order digits The check is given by the relationship n+l ps = 1 0 pP a ci Mod b i=2 The second procedure for obtaining the radix complement check is based upon the well-known rule for obtaining the digitwise radix complement: "Starting with the low order digit, radix complement the first non-zero digit; the remaining higher order digits are changed by diminished radix complementation." This method requires a knowledge of the number of zeros preceding the first non-zero digit. Let this number be q, Given e C. = p n 1 s then n 0 n.o. e 0(q+l 0 (+l q0 CQ.. p, B -^ 0... 0 ^ Ps n ~ i q+l i 0 if i = q

-17Ps3 ='n 0 0 Oq +2 0a C +1 s + P, [(n —l)(b-l) + b] Mod b Ps + PS + (n - q) 1 Ibd b or p $ P0p 0 (n - q) Nbod b = 1 Multiplication consists of repetitive addition with appropriate shift operationso The result is a double-length producto The digital parity of the double-length product is found from consideration of the addition operations since parity is not affected by the shift operation. The linear congruence is multiplicativeo The check procedure for the product P A x D is Pp -(PA ~ PD) 0Z i Mod b or (PA x p) + ci -pp Mod b The symbol @ indicates multiplication, modulo bo It is observed that the digital parity check provides no protection against faulty shift operations. Parity protection against this type of error is obtained if multiple checks are employedo The division algorithm commonly employed is easily explained in terms of the remainder theorem. Consider X Q + R or X= QY + R R = X QY

-18where Q = bn-l +... q jbJthen R = X - (nbn +... gqjb-) Y The subtraction of Y from X, qi times is accomplished by the addition of Y, qi times. Carries which are generated must be considered. The parity check expression is given as PR = PX (PQ 0 PY) 0 L c1 Mod b This check may be employed for each division operation or only as a check of the overall division process. In any case the check is insensitive to shift errors. Examples of Arithmetic Checking (m = b = 10) Addition n3^ 4 6 0() O the circled digits are the check digits + 4 5 8 () Check PA 4 PD Z ci Mod b = Ps 3 0 7 2 2 Complement nines coWplement A = 0345 ( A = 96540 Check PA 4 PA 0 n Mod b = O 4 e2 4 =0

-19ten's complement A = 034500 ( A' = 965500 ( Check PA 0 PA'$ (n -) Mod b = 1 5 2 4 =1 Product 346 Q 213- Q) 346 346 692 346 1038 5 carries 346 generated 4498 346 39098 346 73698 ( Check p = (PA @ PD) e - ci Mod b 3= (3 e6) 5 3=8e5 =3 Division Q= 073699 = x 0346 ( Y the ten's complement of 0346 Ois 9645 Q

-20Carries 073699 2 Carries 9654 039099 2 357 9654 001 ~~~~~96-13954 004499 00-1 969899 9655 04499 3 9654 001 010Check P (PQ 21) ci Mod R=l 1039 1 9654 3 965341 - _ _ (6_04) e3 9654 Check PR = PXO (Pq p-) ~ _ ci Mod b = 4 e (6 e 4) e 3 Numerical Checking, Mod m (mo b), of Arithmetic Operations The modulus of the numerical parity check is not the same magnitude as the radix of the number representation. Congruence relationships are valid for any modulus. However, only certain moduli yield procedures which permit straightforward computation of the parity digits. There exist in particular two interesting and useful checks based on procedures congruent modulo (b-l) and congruent modulo (b+l). These checks will be called the diminished base numerical check and the augmented base numerical check respectively. The simplest checks of the numerical class depend directly on certain congruence relationships. Numerical checking has one very desirable feature not associated with digital checking procedures. Numerical checking procedures do not require a tally or cognizance of the carries generated by the addition process.

-21The Diminished Base Numerical Check The diminished base numerical check is dependent on the following properties of linear congruences: Tibn " i Mod (b-l) This relationship permits parity calculation independent of the digit position or weight. Consider the sum X+Y=S X +Y = S X = xnbnl + o.. + xI b~ Y = ynb + o.. + ylb S = cn+lbn + snbnl +... + slbo Since congruences are additive we have n n X = xib-1 - xi Mod (b-l) The parity check digit pX associated with the representation X is defined by the term xi reduced to the least positive residue of the class. The parity check digit pX may also be defined by X = n... X X1 for either definition n i-l X = I xibis X Mod (b-l) i=l The check digit py is given as n Y = yibi py Mod (b-l) Linear congruences are additive, therefore: X + Y = (Xi + yi) bil- - (P + y) Mod (b-l) and PS = PX ~ py

-22The modulo (b-1) check is numerical and hence does not require cognizance of the generated carries. The check is, nevertheless, sensitive to errors in carry generation and propagation. The check detects all digit alterations for which the modulo (b-l) sum of the changes does not equal zero. This is equivalent to the statement that an alteration is detectable only if b-i is not a factor of the magnitude of the arithmetic error, A single carry failure causes an alteration of minus one and is therefore detectable, However, the error is not correctable on the basis of the parity information. A check of the complement operation is obtained from the basic definition of the complemented representation. The definitions which follow are for representations of n + m + 1 digits, The representation has n digits to the left of the radix point, m digits to the right of the radix point and one sign digit. The diminished radix complement of X is X where X + bn+l bm X+X=b -b The radix complement XI is given as X + X = bn+l The usual congruence relationships are defined for integer values. It is, therefore, convenient to consider the radix point on the extreme right of the representation. The check is obtained by observing that bm(bn+l - b-m) 0 Mod (b-l) and b mn+l 1 Mod (b-l) Then the check for the diminished radix complement is P 0 pO = O

-23and the check for the radix complement is PX-0 PX = 1 Congruences are multiplicative. Therefore, a check of the product P = Rx S is given simply as p =PRI P with no cognizance of carries required. A check involving the division of congruences is not practical since the correct division procedure is dependent upon whether the divisor and (b-l) have any common factors. However, this is of little consequence since machine division is usually obtained by a process consisting of repetitive add and shift operations. X R Y Q+ X = QY + R The check of the division process is independent of carries and must be true at every step in the division process. The check is P= (PQ Py) The Augmented Base Numerical Check The diminished base numerical check avoids the need for carry cognizance and for that reason offers a simpler check procedure than is obtainable by means of digital checking. However, for the binary number system the diminished base check is meaningless. One solution is the

-24augmented base check. This system is also carry independent and parity check digits are relatively easy to obtain. The augmented base check is dependent on the following property of congruences. i bj + Y. Mod (b+l) if J is even — i Mod (b+l) if j is odd The check digit for representation A is given as (,.. + a5-a4 + a3- a2 + al) - p Mod (b+l) where A =... ab4+ ab b + ab + ab+ a2bl + alb The checking procedures employed for the arithmetic processes are identical to the procedures for the diminished radix except that ring addition e and ring multiplication 0 are defined modulo (b+l). In the binary case the number base is two and the check base is three. The parity of a representation A is given as (... + + 2a4 + a + 2a2 + al),- p Mod 3 or... a a a4 ~ a0 2a2 e a, = p Direct subtraction is avoided by using the radix complement of one with respect to the base three. Note that for the binary case the augmented base check is identical to the diminished base check, base four.

-25Examples of the Augmented Base Check Let b = 2 then check is modulo 3 Addition X + Y = S 000 0 1 1 10 1 Check 0 1 0 1 0 1 0 1 PX P3 e = PS 0 1 1 1 0 0 1 0 10 01 = 00 Complement A = 00011101 d) Diminished Radix Complement A 11100010 ) Check PA 0P'A = 0 10. 01 = 00 Radix Complement A' = 11100011 @ Check PA ~ PA' = 1 10 0 10 = 01 Multiplication R x S = P 1011 x 1001 Check 1011 PR PS =Pp 101100 1100011 R 10 00 00 Division X Q + Y Y 0 110011 Check 1 0101 Px (Q ey) PR 0 000111=(oieio)~oi O 000111 00 = (01 0 10) a 01 = 10 e 10 = 00 The above is a check of the first step in the division process o

-26Conclusion The congruence notation used in this paper provides a fundamental basis for the concept of both the digital and the numerical type of parity check. Congruence notation also provides the mathematical tools needed to consider the arithmetic properties of the parity checks and the extension of the parity check concept to non-binary systems. In the final analysis the effectiveness of a parity check is dependent upon the error structure of the carry process. It is necessary to consider in detail the mechanism of binary addition before the effectiveness of the parity check may be evaluated. The process of binary addition is investigated in the next chapter and the effectiveness of the parity check is discussed in Chapter IV.

CHAPTER III VECTOR SPACES AND BINARY ADDITION Introduct ion The concepts, representations and operations associated with vector spaces are particularly appropriate to the study of the process' of binary addition. Vectors or n-tuples correspond to binary numbers. The vector addition of two vectors corresponds to the logical addition of two binary numbers. The length of a vector is shown to correspond to the digital definition (m=b) of parity. A study of the dimensionality properties of vectors facilitates the establishment of various numerical relationships pertinent to checking procedures. These and other relationships are discussed in the material which follows. The application of the vector space concepts and the use of matrix notation represent a basic and unified approach to the subject of binary addition. The vector space approach to binary addition shows clearly that the basic problem of binary addition from the viewpoint of both error structure and speed of addition is the generation of the carry. The different logical configurations employed to generate the carry may be obtained from the matrix representation of the carry process. This particular approach also facilitates the study of the differences in the expected performance of the various known methods of carry generation. The representation of binary numbers as vectors is not a new concept. Extensive use of vector space concepts has been made by -27

-28Muller(22) in the problem of logical design and coding. Reed(8) has used vector space concepts to discuss a particular code. More recently Campeau(21) has made extensive use of Boolean matrices as a logical design tool. The earliest application of matrices to the problem of synthesis of different logic configurations is due to Lunts(l9). The study of binary addition by means of vector spaces presented in this chapter is new as are the applications of the concepts of dimensionality and length. In the next section the basic properties of vector spaces are considered. The application of these concepts to the problem of binary addition is considered in the remaining sections. The Elementary Concepts of Vector Spaces Ordered n-tuples of scalar functions, ai of a field F, are termed vectors of n dimensions if the operations of scalar multiplication and vector addition are closed. A set of n-tuples in which vector addition and scalar multiplication are closed is called a vector space. The dimension of the space is equal to the number of elements of an n-tuple. Given n-tuples OCand 6 and a scalar k o= (al, a2, a3 -.. an) = (b1, b2, b bn) k F Scalar multiplication is defined in terms of the multiplication operation, @, of the fieldo k O"C = (k ~ al, k $ a2, k O aj,... k 0 an)

-29" In order to secure compactness of notation, multiplication appropriate to the field under consideration will be assumed and the notation for scalar multiplication abbreviated to the form koC (ka2l ka2, ka oo 3 kan) Vector addition is defined in terms of the rules of addition of the field elements (scalars)o O0CA = (al e bl, a2 0 b2, ooo an X bn) Algebraically the vectors and the scalars of a vector field are associative, commutative, and distributive with respect to the operations of vector addition and scalar multiplication. This follows from the definition of the operations and the fact that the field has the associative, commutative and distributive properties. A vector of an n dimensional space is usually specified as a function of the basis of the vector space The basis may be any set of n linearly independent vectors. A set of n vectors ol_ o.O (n, is linearly dependent if there exists in F, n scalars kl.oo kn, not all zero^ such that: oklol O k2~2 0... o koCnn = 0 or klall e k2a21 0 o oo knanl = 0 klal 1 k2a22 ooo knan2 = kla13 a k2a23 $ o. knan3 = o o o el o a klaln k an 0 Ho knnn = 0 a

-30Note, in particular, that a suitable basis requires only linearly independent base vectors. The base vectors need not be orthogonal. If the inner product is defined, then the conditions for linear dependence may be written in matrix notation as [A] k =,Z Z denotes the null vector The convention used in this paper for matrices is as follows: An m x n matrix A is bracketed, IA]. A row or column matrix or vector is not bracketed. This convention eliminates needless brackets and leads to more readable equations. The expression [A] k always represents a matrix product and should not be taken as a scalar product. In general vectors are represented by letters from the Greek alphabet. The inner product of two vectors, oC and ~, with respect to a basis S is defined as =(all l... 0 anin) (blYl... 0 bnn) = n n i aib( i -('j i aib jgi i,j=l i,J=l The result is a scalar function. If the basis is orthonormal then giJ =sij and = alb1 0... I anbn The inner product is associative, commutative and also distributive with respect to addition. The inner product of a vector oC with itself in vector space spanned by an orthonormal basis defines the square of the vector length.

-31The inner product gives the sum of each orthogonal component squared. o<c< = alal a2a2 X... 0 anan The basis may be changed by a not necessarily orthogonal linear transformation. ~( 1 - A] o then =[< A c1 otL^ = o IA] [A <" A let G = [A-]tA-] The square, of the vector length defined by the inner product remains invariant if oCLc ( 2i aiaj g:, where gij E [G] The length as such may not be obtainable since this requires the inclusion of the square root in the field. The inner product may be used to determine the orthogonality of a pair of vectors. A vector pair is orthogonal if and only if the inner product vanishes. This follows from the definition of the inner product given as -1 = l1 151 cos e A theorem concerning the dimensionality of vector spaces which will be used later in this paper is now considered. The dimension of a vector space or subspace is equal the minimum number of base vectors required to span the space or subspace.

-32Theorem: If S and T are any two subspaces of a vector space Q, then the subspace dimensions satisfy D(S) + D(T) = D(SOT) + D(SvT) Figure 1. Venn Diagram. This theorem is readily verified. Consider the Venn Diagram shown in Figure 1. The objects of class sj are contained by the left-hand circle, the objects of class tj by the right-hand circle. The objects common to both classes are contained by the conjunction of sj and tj designated as sj 0 tj. The objects of either class sj or tj, written sj v tj, and called the inclusive disjunction may be calculated by summing the number of objects in class sj and the number in class tj and subtracting the number objects contained by the conjunction. The subtraction of the conjunction is required since it has been summed twice. The result is N(sj v tj) = N(sj) + N(tj) - N(sj 0 tj) A formula of the above form could be written for every base vector under consideration. A given base vector either spans or does not span a

-33particular vector subspace. Therefore, N(x) may have only two values, zero and one. If the resulting set of equations are summed the result would be m m I N(sj v tj) = 2? N(sj) + E N(tj) - ZE N(sj 0 tj) J=l j=1 j1 j=1 The dimension of a vector subspace is defined as m D(x) = N(xj) j=l so D(SvT) = D(S) + D(T) - D(S@T) A single vector is a vector subspace. Therefore, the fundamental dimensionality relationship, which involves two vector subspaces, must be valid for vector pairs. The dimension of a single vector, with elements from the binary field is equal to the number of: elements having the value one, The dimension concept can be extended to include the vector addition connective D(SOT) = D(SvT) - (SOT) A simple and rapid proof of the above relationship is obtained from consideration of the definition of the connectives or the Venn diagram and by virtue of the fact that the dimension relationships must be valid for any set of bases including a single base. Two additional dimensional relationships are obtained by linear combination of the previous dimension formula D(S) + D(T) = D(ST) + 2D(SOT) = 2D(SvT) - D(SOT) The preceding material has presented informally the concepts of the vector spaces necessary for an understanding of the remainder of

-34this paper. For a formal presentation of this material the reader is referred to aly standard text on the subject of vector spaces. Vector Representation of Binary Numbers The binary number system as employed in the digital computer is closed. The digit symbols are the elements of the modulo two field. Vector addition and scalar multiplication are obviously closed. Therefore, the closed set of binary numbers may be represented by a set of vectors in a vector space of finite dimensions. The basis of the vector space may be any set of linearly independent vectors. The basis employed in the usual binary number representation is orthogonal. The base vectors are the set of n-tuples or binary numbers representing the powers of two from zero to m-l, where m is the dimension of the vector space. The number of binary digits is also equal to m. Let the base vectors be designated JLi. Then the familiar polynomial representation of a binary number A A = a2n- + an12n-2 +.. + a2b + alb is in one to one correspondence to the vector = a ann 0 an-lnl ~. e a2 2 al See for example Birkhcf and MacLane.(14)

-35where A1 = (00... O O O O 1) A2 = (O 0 0... O 00 1 0) o ~ An-l= (o 10... 00 O O 0) 4n = (1 0 0...- oo o 0) In both expressions the ai coefficients are elements of the modulo 2 field. The cyclically permuted binary code is now considered as an illustration of a non-orthogonal basis. C =[T oC C1 1 1 0 O....000 a1 2 0 1 1 0... 0 0 0 00 1 o.. 000 Cn-l O 0 o.. 1 1 an-l cn 0 0 oo. 0 01 an Each column in the T matrix is one of the base vectors. The vector representation of the cyclically permuted number is C = an1n 0 an-ln-l ~ a262 $ al11

-36where 81 = (O 000... 0001) 2 = ( 00... o 1 1) 63 = (O0 0 0.. O 1 1 0) Sn2= (0 0 1 1.. 0000) Sn-l= (O 1 L 1... O O O 0) n_l= (O 1 0... 000 O) sn = (1 i o... o0 O 0) The conversion from a cyclically permuted code to a binary code is defined by -= IT'I C 1 111... 1 1 1 0111.. 1 1 1 where [T-1] = 1 1..1 1 1 ~ 0 0 0 0 0...0 1 1 0 0 0 0 00 0 0 1 000. O O o O0 1 Thus the binary number A is also in one to one correspondence with n = C`nn - Cn-l-n-1 i o-o $ C2E2 0 C1I where E1 = (000... 001) 2 = ( 0 oo o 0 1 ) Cn-1 = (O1 1... 11) En = (1 1 1...1 1 1) The vector representation of the binary number is unique. Therefore, A *- VO and A - ~ = X

-37The o<- and I vectors are identical and are representations of the same number A with respect to different bases. Vector Length and Parity The square of the length of a vector K is given by the inner product of o with itself. Let us consider the vector representation, o, of a binary number, A, with respect to an orthogonal set of bases, Let A = an... a1 then = ann $... 0 alAn and = L2 =anan e... alal The last equation expressed in congruence notation is n 2 E akak - L Mod 2 k=l The only elements of the mod 2 field are zero and one. Therefore, the length and the square of the length are identical. The length, L, of the vector representing the binary number, A, is identical to the parity of A modulo 2. (oCoC) eq (L2) eq (L) eq p The square of the length of a vector,', with respect to a non-orthogonal basis is n VY = i aiaj gii

-38As an example the length of the vector with respect to the cyclic permuted code basis is determined. 1 1 1 1 1 1 1 0 111111... 100000 CG][T] [T-1] 101000... 101011... 1 0 1 0 1 0 101... The G matrix is symmetrical, gij = gji It follows from the symmetry of the G matrix and the identity k k = 0 that the off diagonal matrix elements do not contribute to L2. The diagonal elements have a value i = gii Mod 2 The length of the vector in terms of the cyclically permuted code basis is L = c1 0 c3 0 c5 Q.~. which must be equal to L = al O a2 0 a3 0... a = p * The G matrix is the metric matrix. A good reference is Brillouin L.(15)

-39The invariance of the length permits a check of the operation of conversion from one number system to another. A check procedure involving the even digits of the cyclically permut ed bode may be obtained if cl and al are deleted from the respective representations by a replacement of the formo ai -- ai+l ci ~- ci+l a2 and c2 are the low order elements of A and C respectively. Therefore, the following relations must be valid L' = c2 0 c4 e C6 0. L' = a2 a3 0 a4..o. 0 an The Vector Space of Binary Addition The standard procedure for the addition of two m digit binary numbers may be described in a vector space in terms of the vector addition of three vectors. The three vectors are the augend vector, oc, the addend vector, e, and the carry vector, y. The sum vector is denoted by or =<e A e = e 1 If the basis of the vector space is orthogonal and in one to one correspondence with the powers of two from zero to m + 1, then the carry vector may be defined recursively as C = 0 C2 = alb1 cj+l = cj(a; 0 bj) 0 ajbj= cjrj $ k

-4owhere rj = aj 0 bj and kj = ajbj In column form the addition process is rm.0... r.r2rl 0 cm+l Cm...eO. C3c2c1 Sm+l j *-**- S3S2S1 siM+1 sm...... s~s2s1 Practical arithmetic circuitry is often designed to accept a c1 element of unity. For example the insertion of a one digit in the low order column facilitates two complement arithmetic in a parallel machine. However, the arithmetic structures considered in this paper will be the type for which cl is always equal to zero. Let the augend and the addend vectors have a maximum dimension of m. The vector addition of the addend and augend vector is closed and the partial sum, e has a maximum dimension of m. The carry vector as defined above has m + I elements but the first element of the carry vector, cl, is always equal to zero. Therefore, the maximum dimension of the carry vector is m. The sum is obtained from the vector addition of the partial sum vector and the carry vector. The actual dimension of the vector addition of the partial sum vector and the carry vector is at most m - 1 since cl = 0 and rm+l = 0. The sum vector, C, has a maximum dimension of m + 1. The elements of the

sum vector are sm+l = rm+l m + 1 s -r ~c s1 = r1i j m+l Sj = r, 0 Cj A vector space of dimension m + 1 is requi.red if the augend vector, the addend vector and the carry vector are to be considered simultaneouslyo It is seldom necessary to consider all three vectors at onceo The vector space usually considered in the remaining sections will be a subspace and have a dimension of m or m - 1. The need for a dimension of m + 1 to represent the sum is in exact correspondence with the binary additionr of two m digit binary nimbers. The m + 1 dimension corresponds to the m + 1 dig-it which is the overflow digi.to The actual mechanization of the process of binary addition is relatively straightforward except for the generation of the carry vector The logic required for the formation of the partial sum by the vector addition of the addend and augend vector, and the vector addition of e and the carry vector 9 is essentially singularo The absence of intercoordinate relationships is characteristic of the process of vector additionr Ihe carry vector elements on the other hand have a high degree of intercoordoinate dependence for j+1 = F(ajp bj o o, al, bl) The lack of independence of the carry elements is the basic factor to be considered in the design of a binary addero The logic of various

-42digital parallel adders differs only in the means used to generate the carry. Furthermore, the error structure of the adder is determined primarily by the characteristics of the carry vector. The Carry Vector The recursive definition of the carry vector is adequate for many applications including the design of certain binary adders. However, for the purposes of this paper the expression of the carry vector in matrix notation has considerable utility and constitutes a unified approach to the problem of carry generation. In matrix notation the carry vector Y is given as X = [D] k The matrix equation in expanded form is shown in Figure 2. The fact that the k vector and e vector are always orthogonal is an important characteristic of the process of carry vector generation. The proof of this orthogonality is as follows: By the definition of P and k we have rj = 1 kj = 0 kj =l r. = 0 )J J Both statements, by the definition of implication, are equivalent to, rj v k =1 The proof is completed by application of De Morgan's Theorem. rj kj = 1 rjkj = 0

-43c2 1 k1 c3 r2 k2 3 2^3 ^ ^34 c4 Ir2r r3 1 k3 235 | |r2r r r3r4 r4 k4 Cs I^3"'r5 "3'4rg'qrg... k5 c6 r2...r5 r3r4r5 r4r 5 k5 C7 |=-r2 r6 3r3..r6 r4r5r6 k6 n r2"..rn-l r3*..rn-l r4* nl ~*. 1 C+n l r2...-rn_ 3~n 14. rn...rn... 1 k| where rj = aj $ bj and kj = a bj Figure 2. Carry Vector.

Therefore: ek 0 The form of cpj the jth element of the carry vector is cj = k2j1 Q kj_2Prj_ $ kj3rj-2rjl $ kj4rj 3rjj_2rl $ o It may be concluded from the orthogonalitPy of the k and. e vectors that at most only one term in the above expression for cj may be different from zero. This fact is seen immediately if cj is expressed in the following form, cJ - ^1 rj 1{kj 2 [j 3 49 rj^ 4 In addition to giving information of the structure of the carry vector, the orthogonality of the e and k vectors has very practical consequences. In particular, since the conjunction of p and k never occurs, the convenient mathematical connective, ring addition or exclusive disjunction 0, may be replaced by the physically simpler connective, inclusive disjunction. The recursive definition is then Cj. = (aj b j) cj v ajbj The recursive definition may be further simplified by the use of the identities aj $ bj - (aj v bj) ajband xy v y y v y The result is jl1 = (aj V b) cj v ajb

-45The physical logic associated with this definition is somewhat simpler than that associated with the definition of the carry using exclusive disjunction connectives. In fact the carry definition in terms of the inclusive disjunction is the most frequently used definition and might have been chosen as the starting point for this work. This was not done for two reasons. First the definition in terms of exclusive disjunction is mathematically more convenient. The convenience is primarily due to the fact that a variable is self inverse for the exclusive disjunction connective. Secondly, the definition in terms of the exclusive disjunction is more restrictive than the definition in terms of inclusive disjunction. Thus, more is learned about the carry vector structure if the most restricted case is considered first. Later the restrictions may be removed one by one and the effects observed. Let vj denote the inclusive disjunction of the jth augend and addend elements. If rj is replaced by v. then any particular row of the carry matrix may contain more than one, ONE element since cj = kjv-1 k2 v kj_3vj_2vjl v J jj4 vj-3-2j- v... and kn - vn In the discussion which follows e and V may usually be used interchangeably. Special note will be given to situations where interchangeability does not exist.

-46Methods of Generation of the Carry Vector The matrix relationship I = [D] k completely defines the generation of the carry vector in terms of the k and the e or V vectors. Essentially instantaneous generation of the carry vector is achieved if the elements of the physical logic correspond one by one to the logical connectives found in the matrix definition of the carry vector. This particular realization of the carry logic is characterized by the fact that the elements of the carry vector are independent. The elements of the carry vectors are independent in the sense that if k and e or V ate correct then a single error in the structure of the carry logic will cause an error in at most one element of. Unfortunately, for all practical purposes the number of logical elements required to realize an instantaneous and independent type of carry is prohibitive. A study of the carry vector reveals that, in addition to the logic required to generate the elements of e or V and k, the carry logic required of each cj element is one OR gate and j-2 AND gates; jj3. Let m be the number of elements comprising the augend and addend vectors then kj must drive m + 1 - j gate inputs and rj or vj must drive (j-l)'(m+l-j) inputs. The last formula is not valid for j = 1. rl does not influence the carry process and is not considered, rl is identical to the sum element slo The total carry logic of the instantaneous and independent type of carry requires

m - 1 OR gates with m(m+l) - 1 inputs 2 m(m-l) AND gates 2 m+l with 1 Z (j j -2) = (m+l)(m+2)6 - m inputs j=3 The number of the logical elements required for the instantaneous and independent carry can best be illustrated by a numerical example. The equipment needed for the carry logic of a 30 bit binary adder is 29 OR gates with 464 inputs 435 AND gates with 4930 inputs kl drives 30 gate inputs k2 drives 29 gate inputs o o o 0 drves 1 gate inpu k32 drives 2 gate input *72 drives 29 gate inputs r V9~ 56 "' ~ 0 81 r 11 225 "'r 1" 224 " o o rj or vj

-48r29 drives 56 gate inputs r " 29 " The independence of the elements of the carry vector may be maintained and the number of logical elements reduced if the instantaneous feature of the previous carry logic is not required. The elements of any row of the D matrix may be generated sequentially. The logic for one carry digit cj is shown in Figure 3. The logic required for each cj is 2j-5 AND gates and one OR gate. For m digits the total carry logic consists of m-l OR gates with a total of m(m+l) inputs and 2 m+l L 2j - 5 = (m+l) (m-3) +4 j=3 AND gates. Each AND gate has exactly two inputs. An element of kg, j, and an element of e, rj, must each drive m-j+l inputs. This scheme of carry generation requires the following components if m is equal to thirty as in the previous example. 29 OR gates with 464 inputs 841 AND gates with 1682 inputs kl drives 30 gate inputs k3o01 1 *2 29 rj or v; 3 1 r~

-49rj - ri-2 rj^3 rj-4 ri-5 - ri) - T -C T r - ~ ki-2 ki kj~-4^ ~) kjy ) l now vj may kj — V*''- replace rj Cji+ Figure 3. Logic for Independent, Sequential Generation of One Carry Element. It is observed that realization of a carry, with independent elements, by the above procedure is by no means economical. Furthermore, the method suffers considerable time -delay due to the sequential method employed to generate the elements of the D matrix. The sacrifice in time does permit a significant reduction in the required drive capabilities of the ri or vi elements. All in all a high price is paid in terms of either components, or time, or both, to achieve independence of the carry elements. The generation of the carry vector in a synchronous logical structure in general leads to more extensive logic or requires more time than a corresponding asynchronous circuit which permits carry

-50rippling. This problem of carry generation for synchronous circuity has been studied by Weinberger and Smith. (16) The paper details a particular technique used to simplify the logical configuration of the D matrix. There is no indication that the technique used by Weinberger and Smith is optimal though the results are reasonable. The carry vector may be considered to be composed of a set of sub-carry vectors according to the following relationship Y= Ym 0 Ym-l ~ ~ - 2 Ill1 In particular let Xj be chosen as the jth set of diagonal elements from the matrix definition of the carry. Then X = (km, km-_,....................... k2, kl, 0) 2 = (km-lrm, km_2rm-l'............... klr2 O, 0) 3 = (km-2rm-lrm, km-3rm-2rml, klr2r3, 0O 0O 0) Xm = (klr2r -., r 0, 0, o.e.. 0, 0, 0) The set of carry sub-vectors as defined above form an orthogonal set and therefore the sum of the sub-vector may be obtained by the inclusive disjunction connective. = Ym v Ym-l v... v2 v 1i is replaceable by V if and only if the inclusive disjunctive connective is used to sum the sub-carry vectors, The sub-carry vectors may be defined recursively. The recursive definition of the sub-carry vectors corresponds to a carry realization procedure economically feasible in equipment but time consuming. The recursive definition is

-51-, = [23 k = t21 ( j2] k ) = [21 ( Y1e) = [2] ( J-ie) The notation, [2J, corresponds to a left shift of one element. In matrix notation 1 O... 0 1 0. 0 0 1 0 o. 0 1 0 The multiplications specified in the recursive definition of the subcarry vectors are non-associative. The product ~j-. is formed first, followed by the left shift of one element. An addition process which obtains a carry vector by means of operations utilizing the sub-vectors is sometimes termed "programmed addition" because the process can easily be executed on a basic automatic computer in the absence of an addition instruction. The generation of the carry vector from the sub-vectors was employed by Robertson(lO) as a means of preventing the propagation of errors. Error propagation is prevented if suitable error detection and correction procedures are applied after the creation of each partial sum of the carry vector. Robertson employed a Hamming

52 Code (5) to obtain the redundancy needed to detect and correct single errors which might occur at each step in the carry generation procedure The simplest logic which generates the carry vector is obtained if the logic corresponds to the recursive definition of the carry vector. c2 k1 cj Ce- j -1-1 v kj1 or cj Cj_lvj_1 v kj_ This definition may be represented by the matrix equation k [D-l X' D-1 is the inverse of the D matrix which has been used previously to define the carry process. The inverse matrix exists only for the defition of D in terms of 1 0 o r2 1 0 D-1 0 r3 1 0 0 r4 1 0 r5 The logic of this type of carry generation is shown in Figure 4. The logic is characterized by the interdependence of the carry digits and by the fact that different carry sequences may propagate simultaneouslyo The carry digit interdependence is completely characterized by the k and

-53vectors. In all cases a propagation of carries is triggered by a kj element equal to one. The carry is propagated through the successive elements only if successive elements of 0t are equal to one. The carry propagation sequence stops at rj+n, the first non-unity element of the 0 vector succeeding rj. Of course, a carry sequence may have been initiated by kj+n but this constitutes a new carry sequence and not a continued propagation of a carry sequence. Due to the orthogonality of the C and k vectors no carry sequences overlap. If ki initiates a carry then ri must stop the propagation of any previous sequence. If V is substituted for Q then the sequence may propagate through points of carry generation. This will affect the error structure of the adder but will not affect the ordinary addition process. It has been shown in Burks et al. (17) that if m is equal to 40 then the average length of the maximum carry propagation is 4.62 elements. The characteristics of the carry propagation and generation is considered in a later section. r, k2 r3 k3 r4 k5 vj may 1 1 m o replace r C2 C3 C4 C5 Figure 4. Standard Carry Logic.

-54Synthesis by Vector Space Operations The process of binary addition for all sum digits except the first is completely defined by the matrix equation In the language of vector spaces the binary addition process consists of an affine transformation of the vector k. The vector k is rotated as a result of the multiplication of k by the D matrix. The result of the multiplication is then translated by the vector addition of the e vector. The whole process is complicated by the fact that the D matrix is a function of the o vector. New logical configurations for the process of binary addition may be synthesised by either of two procedures: (1) by the factorization of the D matrix and (2) by a change of basis transformation over the whole addition process o.The different logical configurations discussed in the previous section. were obtained as a result of different factorizations of the D matrix. One factorization of the D matrix follows from the definition of the D matrix as n1l n D = l1 [ The resulting carry logic has a logical circuit depth of two. If a value of n equal to 5 is chosen the resulting logic is considerably simpler than instantaneous carry logic but not as simple as the multidepth logic proposed by Weinberger and Smith (16) A factorization in this manner can lead to fast carry logic which is economical in terms

-55of the number of logical components. However, the factorization does not lead to a carry logic particularly appropriate for error checking. The difficulties encountered when a change of basis transformation on the whole addition process is attempted is due to the fact that the D matrix is a function of the e vector. Consider the following transformation [T] = (Tc] [T1 [D1 k While C, (e and k may be considered in terms of a new basis the elements of the D matrix are given with respect to the original basis. Thus the transformed addition process defined as = * 4 [D] k' cannot be expected to lead to a simpler definition of the carry process because of the functional dependence of the D matrix on the e vector. Thus the transformed addition process is to be regarded in terms of the original basis. A simple transformation of this type and in all probability the only practical transformation of this type is obtained if the transformation matrix is identical to the inverse D matrix. The multiplication of the matrix definition of the sum by the inverse D matrix yields [D~-l -= [I-r ) 0 k The indices have the same range as specified above. The matrix equation involving the inverse D matrix specifies a recursive definition for the sum elements.

-5652 = r2 - k1 s3 = r2 (1 0 s2) 0 r3 5 k2 s = rj_l (1 sjl) O r kj_l As a result of the orthogonality of k and e the equations are reduced to the form si = (rj_lS j_l kj1_) X rj The logic corresponding to this particular method is shown in Figure 5. The circuit has a very prominent weakness. A propagated carry must pass through four logical elements per stage rather than the two elements per stage required in the conventional scheme of Figure 4. The count is four logical elements per stage rather than three because the usual realization of the exclusive disjunction requires a cascade of two logical elements. The circuit was included here to illustrate a particular method of generating alternative logical structures by matrix manipulation. 2 r r4 _F k, k, __. St S So Figure 5. Sum Dependent Carry Logic.

-57Numerical Relationships In this section the dimensionality concept is used to establish particular numerical relationships which exist between the results of specific logical operations. One important consequence of the existence of the numerical relationships is the feasibility of using numerical checking and correcting procedures to control the errors produced by faulty elements in a logical structure. The numerical relationships will be used in the next section to specify alternate algorithms of the addition process. Consider the dimensionality relationship D(^) + D(6) = D(V) + D(k) where V = oC v 6 and k = oC R The dimensionality relationship must' be valid for any set of coordinates. If a single coordinate is considered then the following relationships exist between the values of a., b and vj kj. TABLE I RELATION BETWEEN a, bj and vj, k ab.v.. aj bj Vj kj O 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1

-58Digitally the difference between ai, bi and vi, ki is a possible zero and one interchange between columns as shown in row two of Table I. The interchange occurs if vj and kj are substituted for aj and bj but there is no numerical effect since 0+ 1- 1+0 Therefore, the dimensionality relationship implies the numerical relationship = oC t + = V + k A second numerical relationship is obtained from the dimensionality equation. D(e) + D(k) = D(V) where e = oC A The numerical relationship is +k = V The validity of this equation is established by the following argument. The e and k vectors are orthogonal and therefore the magnitude of the sum of a particular coordinate, rj + kji cannot exceed unity. The addition of e and k can never produce a carry. This fact and the implication kj: vj assure the validity of the numerical relationship between 9, k and v. The dimension relationships may be expanded to include more than a pair of variables. In particular, the following dimension equation is obtained by considering a Venn diagram with three overlapping classes or by application of the previously derived dimension

-59formula of two variables. D(oevivX) = D(+ ) + D() ) + D( Q(^ ) - D( o(b) - D (^8) + D((B58) The corresponding numerical relationship is (Xv6v ) = O+ / + 8 - -06 6 -i +6 ^ The following examples are given to illustrate the numerical relationship previously described. Let oC = (1 0 1 0 1) = 45 and. = (1 110 0 1) = 57 then V = (1 1 1 1 0 1) = 61 k = (1 0 1 0 0 1) = 41 = ( 1 0 1 0 0) = 20 now oc + = V + k 45 + 57 = 61 + 41= 102 and e + k = V 20 + 41 = 61 Now let us consider the extension to three variables, Let 8 = (1 10 0 1 0) = 50 then (<v 8 v 6) = cK+ 4 + 8 - - 8t -, a + RS 63 = 45 + 57 + 50 - 41 - 32'- 48 + 32 63 = 63 In this section we have shown the existence of two relationships which can be employed to check the generation of the?, k and V elements which are functions of the addend and augend elements. The most important characteristic of the derived checks is the fact that

-60the checks are numerical. This means that the checks may be applied on a digit by digit basis, as a check on certain parts of a representation or as a check of all elements of the representation. Both check processes are of the type which detect the occurrence of a single error. The check oC + = V + k will detect malfunctions in the V and the k elements if the QC and 3 elements are correct. Likewise the check +k = V may be used to check errors in the e elements only when the k and the V elements are correct. It is logical to ask whether similar check procedures exist for the carry generation process. Unfortunately the answer is no. The checks given above owe their existence to either the absence of carries or the presence of identical carry processes appearing on opposite sides of the equality sign. The carry generation process is characterized by the presence of constraints and the dependent nature of the elements of the carry vector, A check of the carry generation process can only be made by either duplicating the carry generation or by partitioning the carry generation process into checkable parts as is done for the carry generation process used in programmed addition. Addition Algorithms The numerical relationships derived from the dimension concept in the previous section may be used to obtain alternate algorithms for binary addition.

-61The relationship 6 = C +, =V+k V = oC v 3 k = oC 3 states that the sum of the augend and addend is identical to the sum of the disjunction and the conjunction of the augend and the addend. The same carry vector is associated with either algorithm for e -o C = v ) k k = ( = kV The numerical relationships = C+ = V + k and + k = V may be combined linearly to give two binary addition algorithms of the form = k + k + e = 2k + = V + V - e = 2V- In the remaining part of this paper the following terminology is adopted. The addition algorithm described by the first equation above is called ke addition. The second process is called Ve addition. The usual addition procedure is called standard addition and defined by 6 = d + o The process 0= V + k is termed Vk addition. The concept of dimensionality has led to the definition of alternative algorithms for addition. The important aspect of the k

-62and V e algorithms is that the carry or borrow vectors associated with these processes differ from the carry vector associated with the standard and the Vk addition processes. The fact that the k carry vector and the Ve borrow vector are different from the standard carry vector is sufficient reason to investigate in detail the addition algorithms. The characteristics of the carry or borrow vector determine both the propagation of errors and the average addition time of a parallel type binary adder with asynchronous carry. Constraints and Some Properties of the Addition Algorithms ConStraints play an important role in the determination of the characteristics of the k and Ve addition processes. The constraints and some of the effects of the constraints are discussed in this section. The constraint of the ke addition process is kJ ej = O Consider the addition process as expressed in column form....... k3 k2 k +......... r4 r3 r2 r1......... s4 s3.% s4 s3 s2 s1 The sum of any column is given by the vector sum of the k, and carry elements. S = 2k 0 e 4

-63The effect of the constraint is to limit the number of elements with a value of one in any column. The number of ones in any column cannot exceed two. The proof of this statement is obtained by considering the following situation. Let kjl and rj both have a value of one so that a carry is generated. Then rjl must be equal to zero and no carry from a coordinate or column less thani-J-l is propagated through j-lo It is also obvious that a carry cannot be generated at column J-1. The number of ones in columns j-l and j is at most two. In column j+l, kj is constrained to a value of zero and cj+l the carry element of the column has a value of one. If rj+1 is equal to zero the j+l column has only one digit of value one. If rJ+1 is equal to one there are two one digits in the column. Thus, three one digits never occur in any column and a two input type of adder is sufficient. However, no overall saving of components results since a two input adder is required to form each, k element pair. One other effect of the constraint in 1. 6 type addition is that carry propagation is determined solely by the elements of o If the carry is propagated then rj+l must be equal to one. But if this is true, then kj+l is equal to zero and rj+2 must equal one to propagate the carry. The carry continues to propagate until rn is equal zero.

The following example is presented as an illustration of the k 9 algorithm Given: o = (1 1 0 0 1 10 1) 3-= (1 10 000 101) then = (00 0 1 1 0 0 0) k= (1 1 0 000 101) the sum is obtained by the addition r =-2k + ( 000 011 000 1 100 001 01. 1 1.00 100 010 the carry vector of the process is = (O 000 110 00) For this example the carry vector associated with standard addition is (1 100 I11 01) The Ve algorithm uses subtraction to obtain the sum, It is therefore appropriate to discuss the generation and propagation of borrows rather than carries A borrow is generated only if -the minuend element has a value zero and the corresponding subtrahend element a value one, The borrow propagates through succeeding elements if the subtrahend and minuend elements have identical values. The borrow hj is given the equation h = (x- 1 eq Yl) hl v x;_ Y _l

-65The above form of the equation is appropriate for probabilistic consideration since the causes of the propagation and the generation of the borrows are separated. In practice a more convenient logic is hj = (xj-1 v Yj_l) hil v %jl Yj1 The VC addition process is constrained by the relations: rj vj or rj v v = 1 In column form the addition process is represented by 00000. v3 v2 v1...... r r rr 4 3 2 1 oo...... s 3 s2 s1 The constraint has the following effects. A borrow is generated if vj 1 r 1 The borrow propagates the succeeding column if rj+l is of value unity. vj does not influence the borrow propagations since the value of v; is constrained to one if rj is equal to one. Thus the constraining relationship propagates with the carry. In the normal subtraction process the borrow is propagated if equality exists between the minuend and the subtrahend elements. In the V^algorithm a borrow is propagated only if both the minuend and the subtrahend are unity. In practice only a two input subtractor is required but a two input adder is required to generate each pair of p and V elements.

-66The previous example is considered in terms of the VP algorithm. o = (1 1 O 1 1 1 01),=(1 o 000 1o 01) =(ooo 1 1 0l 0) V = (l O 11 101) 1 100 111 01 000 011 000 1 100 100 010 In this example the borrow vector was the null vector. Consider as a second example oC= ( 1 1 11 0) f = (O O 1 00 1) p= (1 1 0 1 1 l) V = (l1 11 1) 1 111 11 1 110 1 1 1! 1 0 1 1 1 1 000 111 The borrow vector H is H = (0 O 1 1 1) An additional algorithm for binary addition consisting of both kf and V addition processes may be verified by the comparing

-67of the carry and borrow characteristics of k o and Vi addition respectively. The new algorithm will be called ke V addition and is now described. The process requires the generation of vectors e' 2k and 2V. The addition process is started with the k e algorithm at the low order column. The k e algorithm is applied to succeeding columns until a column is found which would generate a carry. Either the k e sum or the Ve sum is recorded for the carry generating column but the next column is summed using the V C algorithm. The Vc algorithm is used until a column is found which generates a borrow. The k e or the Ve sum is recorded for this column but the sum for all succeeding columns, until a carry is generated, is found by the k 4 algorithm. At the columns which generate a carry or a borrow both k and V e addition give the same result. The procedure is continued until the final digit is summed. The validity of the algorithm is seen in terms of the constraints of the kv and Ve addition processes. The first column never generates a carry for the k C algorithm since no element of 2k corresponds to rlo The k e algorithm is then applied to the second column. Let us assume that column j will generate a carry, i.e., (rj = 1, kj_1 = 1)o The constraints dictate that vj_l = 1, rj_1 = 0 and vj = 1. For column j the k and V e algorithms give the same sums since rj Q kj_1 = rj vj_-1 = 0 The V e algorithm may be substituted for the k e algorithm at the jth column only if there is no borrow propagation into the jth column.

-68This is assured since rj,1 = 0 and vj_2 = 0 if no borrow is propagated from the j-2 column and v 2 = 1 if a borrow is propagated from the j-2 column. The k f algorithm may be substituted for the V P algorithm when a borrow occurs at the pth column if there is no carry propagation into the pth column. The borrow occurs when rp = 1 and vp1 = 0. Therefore, k-l = 0, and r_1 = 0. If k = 1 there can be no carry sequence into the p-1 or the p column. P-2 Thus it has been shown that due to the constraint the specified algorithm change is valid. At the moment the k P V algorithm is only of academic interest. No practical logical configuration has been found for the k e V algorithm which is not identical to some simpler algorithm. In fact the circuits examined contained unnecessary redundancy. However, the k e V algorithm does constitute an interesting description of the addition process. An example of the k e V algorithm is now given Let o = (1 0001 0 1) A= (0 1 1 1 0 11 0) then k= ( 0100010 1 0) V = (1 1 1 0 1 1 1 1) e= (1o 1 1 0010 o1) O1 00 0 1 10 2k 11 1 1 1 1 10 2V 101 100 101 e 1001 111 001 0kp -~ — Vpe

-69Evaluation of the k and the V? Logic The generation of the k, V or e elements required by the k( or the Ve addition processes can easily be realized by the conventional half adder circuitry shown in Figure 6. Additional logic must be provided to generate and propagate carries or borrows and also to perform the vector addition of the k, e, and carry elements or the vector subtraction of the V, g, and the borrow elements. Due to the effect of the constraints the vector addition or subtraction operations require only one modified half adder or modified half subtractor per adder stage. The logic required for the k algorithm is shown in Figure 7. The logic required for the V9 algorithm is shown in Figure 9. It is necessary to compare the kp and the Vp logical configurations with the standard adder configurations in order to determine whether the new algorithms have any merit. The logic of a standard adder configuration is shown in Figure 8. A comparison of the logic shown in Figure 8 and that of Figure 7 reveals immediately the minor differences between the kp logic and the standard logic. The difference is in the point at which the carry is obtained from the carry logic. For the kp logic the carry is obtained from the output of an AND gate, For the standard logic the carry is obtained from the output of an OR gate' The change in the point at which the carry is derived has no effect on the performance of the adder circuit. We conclude therefore that the kP adder offers no advantage over the standard adder

-70xj _ kj Yj xi' *( r yj. Vj Figure 6. Half Adder. r2 k2 r3 k3 r,, l S2 r 1S3 Figure 7. Realization of the kp Addition Algorithm.

-71J X St. S r Figure 8. Iogic for the Standard Addition Algorithm, S~r~, Figure 9 gic for the p Addition Algorithm Figue 9. Loic flor the vrp Addition Algorithm.

-72configurations. The same is true of the Ve adder when compared against standard half adder - half subtractor configurations. However, the change in the point of carry derivation does change the statistics of the carry generation process. An analysis of the statistics of the carry process for ke or Vf addition would reveal that the probability of carry initiation is equal to 1/8 and the probability of carry propagation is equal to 1/2, For the standard addition algorithm the probability of carry initiation is 1/4 and the probability of carry propagation is equal to 1/2. However, these statistics can be very misleading. The probabilities associated with the inputs to the AND gate from which the sum element is obtained are identical for all the addition algorithms. In view of this we must conclude that the new addition algorithms presented here form interesting alternate discriptions of the addition process. But no logical configurations have been found which differ substantially from the standard logical configurations. In view of this the discussion n the next chapter is restricted to the standard addition algorithm,

CHAPTER IV THE ERROR STRUCTURE OF BINARY ADDITION AND THE EFFECTIVENESS OF THE PARITY CHECK Introduct ion The sections which follow contain a detailed investigation of the effects of logical malfunctions on the correct sum representation for standard binary addition. The carry logic is the most important single factor which determines the error structure. If it were not for the carry process, the sum elements could be completely independent and the error structure of the addition process would be extremely simple The logic of binary addition is divided into three parts. The first part consists of a half adder circuit which obtains the k, r and v elements from the addend and augend elements. This logic will be referred to as the generating logic. The second part of the logic of the adder is the carry logic. A standard carry logic will be considered. The carry logic requires one AND gate and one OR gate per dil'.ito Initially the carry logic is assumed to have no logical elements in common with any other part of the adder logic. The third part of the adder logic performs the vector addition of a carry element and an element of the e vector to produce the sum element and is called the rc sum logic. The form of the standard adder logic under consideration is shown in Figure 10.o Conventionally gates g5 and g6 are combined since -73"

-74the output of gate g6 provides the required input to gate g4. In the immediate discussion which follows the separation of g5 and g6 will be assumed, though consideration will be given to the possibility that the input of g5 is either ri or vi. In the last sections of this chapter the effectiveness of both digital and numerical error detecting methods is considered for the different error structures associated with particular malfunctions of circuit components. a, bi ai b, (, 92 (V GENERATION j > < >LOGIC 0*g, go CARRY C ~ ~~ ( —I / ~ ~C, LOGIC 9g rc SUM V L LOGIC Si Figure 10. Adder Logic.

-75The Error Structure of the Carry Logic of Standard Addition In this section the effects of various malfunctions in the standard carry logic are considered. The matrix representation of the carry logic is particularly appropriate for the study of the carry error structure. The elements of the vectors of the addition process are considered as random variables. The probability that an element ki of the k vector equals one is 1/4. The probability that an element ri of the P vector equals one is 1/2. If these values are substituted into the carry matrix shown in Figure 2 the result will be the matrix shown in Figure 11. The matrix defines the probability p(ci) that a given element ci of the carry vector has a value of unity. The matrix representation of the carry vector in terms of the k and 10elements is particularly appropriate for probabilistic studies since the elements of any row of the carry matrix are mutually exclusive. The probability that a given carry element is of value unity is obtained simply by summing the corresponding row elements and multiplying the sum by l/4o If the carry matrix were defined in terms of the k and V elements it would be necessary to consider the fact that the matrix elements in terms of k and V vector elements are not mutually exclusive. However, the values for p(ci) would be identical, since the same carry vector must be obtained regardless of whether the carry matrix is defined in terms of P and k or V and k vector elements. It is simpler to use the carry matrix in terms of k and P vector elements because of the mutually exclusive properties. However,

-76the carry vector determined by k and e vector elements will have a different error structure from the carry vector defined in terms of k and V vector elements. Both definitions provide the same results if there are no logical malfunctions. It is only when circuit malfunctions are present that the difference in the error structure of the two schemes becomes apparent. For reasons of mathematical convenience the present studies of the error structure of the carry vector are continued in terms of elements of the e and k vectors. p(ci), the probability that ci = 1, obtained from the matrix representation of Figure 11, is p(c) = 1/4 (2 - 2-i+2) 1/2 - 2i 2 - i < m+l Consider the carry logic shown in Figure 12. The logic represents that required for standard addition. The logic is implemented using semi-conductor diodes. A study of the circuit will reveal that the following correspondences exist between open diodes and ki or ri constraints d40 corresponds to ki = 30 dd~ri = dl0 i But ci = 1 if ki_ = 1 Thus the effect of a certain diode malfunction may be analyzed by a constraint on the ki or ri elements.

-77The result of diode shorts is now determined for the carry logic of Figure 12. In the practical circuitry the parameters ki and ri are usually derived from voltage sources. The effect of a short is, therefore, somewhat dependent on clipping levels. If d4 is shorted the effect is the same as obtained for d3 open. If d3 is shorted, the result is indeterminate since the circuit will probably continue to function until d2 or d4 malfunctions. A short in d2 renders the succeeding carry elements independent of the previous carry elements and ci+l becomes a function of only ri and ki which are orthogonal or mutually exclusive. The same effect is obtained if dI has an open. If d1 shorts, the carry propagation of the ith stage in the carry logic is independent of ri and is equivalent to d2 open. The effects of shorted diodes are now summarized. d4s corresponds to ri = 0 d3 indeterminate 3s d2 corresponds to ki_ = 1 dls corresponds to ri = 1 Let the probability of a short or an open be identical and neglect the inferred result of a short in d3. The frequency of occurrence of particular values of ki1, ki and ri in correspondence with the diode malfunctions is shown in Table II1

-78P(2) 1/4 p(c3) 1/2 1 1/4 p(c4) 1/4 1/2 1 /4 p(c5) 1/8 1/4 1/2 1 1/4 p(c6) 1/16 1/8 1/4 1/2 1 1/4 p(ci) 2-n+2 2-n+3 2-n+4 2-n+5 2-n+6 00 0 0 0 0e0 0 o o 0 O 6 o o P(Cm+I) 2-m+ -m+ 2-m+j 2 2-m+ 5.1 i/ Figure 11. Probability that ci = 1.

-79TABLE II FREQUENCY OF OCCURRENCE OF DIFFERENT TYPES OF CARRY LOGIC MALFUNCTIONS Element Value Frequency k = o 1/8 ki=1 = 1 1/4 ri = 01/4 ri = 1/4 no effect 1/8 The changes in the carry error structure if V is substituted for are simple. In reference to the diode logic of Figure 12 only one circuit malfunction is sensitive to the replacement of p by V. If diode d4 is open, 1/8 of the time an error will not be observed. This is due to the fact that if ci = 1 and ki = 1 then vi = 1 but ri = O. The value of p(ci) = 1/2 and p(ki) = 1/4. The probability that the malfunction does not cause an error is the product p(ki) p(ci) and is equal to 1/8. The result of the substitution of V for e is a change in the frequency of occurrence of the ki = 0 and the "no effect" type of error. The frequency of ki = 0 is 7/64 and the frequency of the "no effect" condition is given as 9/64.

-80+ E C -ki d, CI+I -E Figure 12. Carry Logic. A malfunction in the carry logic does not necessarily cause an error in the element of the carry representation. A malfunction which does produce at least one error is termed effective. We now proceed to calculate the effectiveness of the various logical malfunctions in terms of the ki or ri constraints. In the following equations p(Aci+l) denotes the probability that the i + 1th element of the carry vector is changed due to a malfunction represented by some constraint.

-81ri = 1 type of malfunction P(c+l) = p(ki) + p(ri) p(ci) ri =1 then P (ci+l) = (ki) + P(C) - p(ki) P(C) ri=l P C(ci+l) = P(Ci) - p(ki) P(Ci) - P(ri) P(Ci) ri=l = p(Ci) ( 1 - p(ki) - p(ri) - p(C) { 1 -p(ki) + P(ri)j = 1/4 p(ci) - 2-2(2-1 - 2-i) 1/8 ri = 0 type of malfunction P(Ci+l) = P(ki) + P(ri) P(Ci) ri = 0 then p (Ci+l) = P(ki) ri=O p (ci+l) = p(ri) p(ci) = (2 - 2 - ) - 1/4 ri =0 ki = 1 type of malfunction P(ci+l) = p(ki) + p(ri) p(ci) P (Ci+l) = 1 ki-= P (ci+l) - 1 - p(ki) - P(ri) P(Ci) ki. =l = (2k1 + 2-i-) 1/2 ki = 0 type of malfunction P (ci+l) P(ri) P(Ci) ki =0 k. =O

-82The Nature of the Propagated Error In the remaining sections of this chapter a number of different logical malfunctions will be considered. All malfunctions of the adder logic may result in a propagated error. We shall at this time investigate the characteristics of the propagated error. The mechanism for the propagation of an error is independent of the cause of the error. The type of malfunction does determine whether a zero or a one is propagated. Constraints of the type ri = 1 and ki = 1 may initiate erroneous one elements while the constraints ri = 0 and ki = 0 initiate erroneous zero elements in the carry vector representation. An element ci+2 of the carry vector succeeding an erroneous element ci+l is also in error, if ri+l = 1 and no carry is initiated by ki+1. If ri+l = 1 then ki+1 is constrained to zero. Hence, propagation and initiation never occur simultaneously at the same element. The condition for error propagation is simply ri+l = 1 and the probability of propagation is one half. The probability of not propagating is also equal to one half. The probability that an error initiated at the i+lth element by a ri or ki type malfunction propagates to the jth element of the carry vector and no further is p(i+l........j) = 2-j+i j i+l An error in the jth element of the carry vector caused by a malfunction of the ki or ri type implies an error in all carry elements between and including i+lth element and the jth element. Thus P ( cj) = P i+) 2-+i i+l

-83The asterisk is used to indicate that the propagation of the error stopped at the jth element. The probability that the error includes the j element is p(^cj) =p(Acj+l) 2-j+i+l If only effective malfunctions are considered the expected number of carry elements in error is a function of the mechanism of carry propagation and is independent of the frequency of occurrence of effective errors of each type. Then p(X*cj) = 2-J+i Consider an effective malfunction in the ith stage of the carry logic. The carry element ci+l is then in error. The error propagates only if ri+l = 1 regardless of whether the erroneous ci+l element has a value of one or zero. The propagation of the error is halted if ri+n = 0. This situation is illustrated below. An erroneous carry element is denoted by c and an erroneous sum element by s. ri+5 0 1 1 1 ri ci+5 Ci+4 Ci+3 Ci+2 Ci+l ci Si+5 si+4 si+3 5i+2 si+l Si The sum elements in question may assume one of two representations where one representation is correct and the other is erroneous. Which is erroneous and which is correct depends on the correct value of the ci+l element. For our purposes the question of which representation is correct is of no importance. The two representations are

-84-... si+5 0 1 1 1 i' Type A error 1 s. Oil s.. Type A error 0.. si+5 1 00 Si.' Type B error If the error doesn't propagate then ri+ = 0 and only one element of the sum is changed. One other situation must be considered. This is the case where the error propagates to the last element of the representation. There exist only certain conditions for which an error may propagate to cn+l, the last element of the sum representation. The element cn+l is usually ignored if negative numbers are represented in two's complement notation but the cn+l digit may not be ignored if a numerical check is used. If the negative numbers are represented in one's complement notation, then cn+l indicates the need of the end around carry associated with the ones complement addition of two negative numbers or with the addition of positive and negative operands which produce a positive sum. The nth element of the representation is the sign element. An overflow may be detected for either system of negative number representation by an examination of the sign digit of the sum. The details of the problem of an overflow representation are not elaborated at this time but are presented in Appendix I. In regard to the addition of two numbers the following obtains for two's complement arithmetic.

-85addition of two positive operands normal rn=O overflow rn=O n n cn=O Cn=l Cn+l=O Cn+l=0 addition of two negative operands normal rn=O overflow rn=O cn=l cn=O n+l=l Cn+l=l addition of a positive and a negative operand positive sum rn=l overflow cannot occur cn=l Cn+l=l negative sum rn=l n=O Cn+l=l For one's complement arithmetic the following situations obtain before the end-around carry correction. The addition of two positive operands results in the same value of rn, cn and Cn+l as specified above for two's complement arithmetic. addition of two negative operands normal rn=O overflow rn=O cn=O or 1 cn=O dn+l=l Cn+l 1

-86addition of a positive and a negative operand positive sum rn=l cn=l Cn+l=l negative sum rn=l cn=o Cn+l=O If an effective malfunction in the carry logic occurs in the nth stage a single carry digit cn+l will be in error. A malfunction which occurs prior to the nth stage cannot propagate an error to the n+l carry element unless rn=lo The only time the element rn=l is for the addition of a negative and a positive pair of operands. This is true for both one's complement and twos complement addition. For this special case where the error may propagate to the end of the representation the resulting erroneous representation is either a Type A or Type B error. In short, if the cn+l element is considered as part of the sum representation it is impossible to propagate an error consisting of all ones or zeros to the end of the representation. This fact is of little significance for the digital check but is of paramount importance for the numerical check. The Average Length of Carry Propagation In order to indicate the general range of effect of a propagated error we shall consider here the average length of the propagated

-87carries resulting from the addition of two m digit binary numbers. The carry sequence is initiated by a unity element of the k vector and is propagated if the successive e vector elements are equal to unity. The average length of carry propagation is defined by the total number of digits involved in the propagation divided by the total number of propagation sequences. Note in particular that a carry initiation not followed by propagation is not counted as either a propagation sequence or as a propagation digit. A carry initiation followed by propagation is counted as a propagating sequence, but the carry initiation digit is not counted as a propagating digit. The calculation of the average length of carry propagation involves the consideration of various conditional probabilities. The problem is easily described in terms of a flow diagram such as that shown in Figure 13. The flow diagram may be considered as a representation of the process of examination of m augend and addend digit pairs. The examination procedure starts with the lowest order digit and proceeds consecutively toward the higher order digits. State I corresponds to carry initiation. State P corresponds to carry propagation. State 0 corresponds to digit pairs which are not a part of either the carry initiation or propagation process. The square boxes on the flow diagram which have been labeled A and B are counters. The counter A indicates the total number of propagation sequences while the counter B indicates the total number of digit places involved

-88in the propagation minus the total number of propagating sequences. Thus the ratioA+B is the average length of carry propagation. A CI Figure 13. Flow Diagram for the Average Length of Carry Propagation. The calculation of the average length of carry from the flow diagram is complicated by the fact that the sequence of digit pairs under consideration is finite rather than infinite. It is readily seen for an infinite sequence that the expected value of B for each unit of A is one half. Thus for infinite sequences A+B = 1+0.5 = 1.5. One would A.1 expect the truncation of the'sequence to have very little effect on the value of the average length of carry propagation. This is indeed the case. All possible propagating sequences for m digit pairs, for m

-89equal to 3 and m equal to 4 were examined and the average propagation length was computed. For m equal to 3 the average propagation length is 1.33. For m equal to 4 the average propagation length is 1.43. For computer applications the range of m is typically 30 to 50 digits, The effects of truncation are certainly negligible and the average length of carry propagation is very nearly 1.5 digits. The Error Structure of the k, p and V Generating Logic for Standard Addition. In the previous sections the effect of malfunctions in the carry logic has been considered in detail. The analysis is now extended to consider the effects of errors in the logic which generate the ki and ri or vi elements. The input to the generating logic is, of course, the addend and augend elements. The generating logic is implemented with a basic half adder circuit. Each stage of the generating logic is independent of every other stage and the dependence of the sum elements is a function of only the carry logic. However, the various outputs of one stage of the generating logic are not necessarily independent. The generating logic may produce ri, vi and ki and the exact dependence of the, k and V elements is a function of the type of half adder circuit employed. For the moment, the possible dependence of the outputs of the generating logic is ignored and the effect of single 9 or k malfunctions on the sum representation is considered. An error in a particular ki element can disturb only the carry vector. Therefore,

-90the sum error structure resulting from a faulty ki element is identical to the sum error structure previously associated with a malfunction in the carry logic of the ki type. If the carry logic is a function of e and k then an error in a ri element can yield an erroneous e vector and may also cause an error in the carry vector. An effective ri element error results in at least one erroneous sum element si and the error may propagate to element i+n in precisely the same manner as the error due to a ri type of carry logic malfunction. The sum element si is the vector sum of ri and ci while ci is a function of ri, ki 1 and cil. If ci = 0 the error in ri affects only si. If ci = 1 the error affects si and also propagates. The propagation of an erroneous one requires ri = 0 -- ri = lo The erroneous sum element si is then zero and if error propagation occurs it is of Type B. The propagation of an erroneous zero requires ri = 1 *- ri = 0 and the erroneous sum element si is a one. The propagated error is of Type A. The probability that an ri = 0 element type of malfunction is effective is one half. The probability that the ri = 0 malfunction changes si+l is given by the probability that ci = 1, which is approximately equal to one half. P(Asi) = p(ri) = 1/2 P(6si) = p(ri) p(Ci) 1= 1/4 P(Asi+l) = p(ri) p(ci) 1/4 P(;si+) = p(ri) p(ci) P(ri+l) 1/8

-91The following probabilities are obtained for an element malfunction of the type ri = lo p(ASi) = P(Pi) = 1/2 P(asi) = P(ri) P(ci) + P(ci) P(ki) = 1/2 [l/2 + 1/2 (1/4)] ^5/16 P(Asl+l) = P(i) P(ci) p (Ri) 3/16 P(Asi+l) - P(Asi+) P(ri+) 3/32 There exist half adder circuits which yield independent e and k elements. However, typical of the half adder circuits used to generate the ri, vi and ki element is the circuit shown in Figure 6o For this circuit, errors in the vi and ki elements are independent of the ri element but the ri element is dependent on both vi and kio If vi is erroneous then ri is erroneous unless ki = lo The probability that ki = 1 is 1/4 so 3/4 of the time an errorin vi will also give rise to a ri element error. Similarly, if ki is in error ri will be in error unless vi = O0 P(Vi) = 1/4o The error in ki affects the ri element three fourths of the timeo The constraining relationships associated with the particular half adder under discussion are described by the following relationships (1) ki = ri =0 and cit = 1 (2) ki - 0 ri Vi (3) vi 1 ori ki (4) vi ~0' ri 0

-92We consider first an adder which employs only e and k elements. The form of the sum errors resulting from an element error ki = 1 which constrains ri to a value of zero is now determinedo An error occurs if the correct ri element has a value of one, p(ri) = 1/2. If ci = 1, p(ci) - 1/2, the result is an erroneous sum representation in which only one element si is in error. For this situation the ki = 1 constraint initiates the proper carry element at ci+l and hence corrects the error in the carry vector due to ri = Oo If ci = 0, p(Q) = 1/2, then an error si = 0 occurs and a faulty carry sequence is initiated at ci+l1 Error propagation, if present,is Type B. If the correct value of ri is zero the effect of a type ki = 1 malfunction is the same as that associated with a ki = malfunction for the carry. The following probabilities are associated with an element generating malfunction of the type ki 1 which constrains ri to a value of zero. P(ai) = p(ri) = 1/2 p(&*si) = P(ri) P(ci) 1/4 P(6si+l) - - P(ci+) 1/2 P~(Si+li) 1/4 The malfunction of type ki =0: ri =v. will result in an error only when the correct value for ki is unity. ri will then have an erroneous value of unity since ki = vi. The carry ci+l which is required will not be initiated unless ci = 1. So if ci = 1 only one sum element, si, is in error. If ci = 0 then si is erroneous with a value of one and the required carry is not initiated at ci+1. Error'propagation if present, is Type Ao

-93The error probabilities associated with the ki = 0 O ri = vi type of constraint are p(si) = p(ki) = 1/4 P(Ssi) = p(ki) P(ci) = 1/8 P(Asi+1) = p(ki) p(ci) = 1/8 p(s ) i+) 1/16 The form of the errors resulting from a malfunction of the type vi = 1 = ri = ki may be described in terms of a single ri = 1 element error though the probabilities associated with the error are changed. The constraint results, in an error whenever the correct value of both ri and ki is zero, p(Lsi) = p(ri) p(ki) = 1/4 P(Asi) = (r) r) (ki) P(ci) = 1/8 p(A si+l) 1/8 p(Asil) - 1/16 The errors due to the constraint vi = 0 ri = 0 are identical with the errors resulting from a generating element malfunction of the type r. = 0. The preceding discussion of constraints has been in terms of an adder logic employing only k and e elements. However, if the four constraining relationships are considered in terms of an adder employing k, e and V elements the same error structure will be obtained.

-94One aspect of the structure of the errors associated with the generating logic must yet be investigated. This is the error structure due to malfunctions in the input logic of the generating circuits. The input logic is identified in Figure 10 as gates gi and g2. The input logic is symmetrical with respect to the input addend and augend elements ai and bio It is therefore sufficient to consider the results of constraints applied to only one of the variables. The results obtained apply equally well to the other variable. The input logic in terms of the addend and augend elements is described by the following equations: (aivbi) (aibi) = ri aibi = ki If ai is constrained to one then ri= bi ki = bi and if ai is constrained to zero ri = bi ki = 0 The malfunction of type ai = 1 is effective only when the correct value of the element ai is zero. Two different types of error result. The type of error is determined by the value of bi. If bi = 0 then the correct value of ki is obtained but the result ri = 1 is in error. The resulting error in the sum representation consists

-95of only one altered element if ci = O. If ci = 1 the error may propagate. If propagation occurs the error is Type B. The probabilities of the error process are P(ksi) = p(ai) p(bi) = 1/4 p( *s i) = ps() p(ci) 1/8 P(si+l) = P(Asi) P(Ci) - 1/8 p(As^^)= p(s) p(c )' 1/8 p(s i+l ) = P(Asi+l) P(ri+l) - 1/16 If bi = 1 then both ki and ri assume erroneous values, ki = 1 and ri = 0. When ci = 1 only one element si is changed. When ci = 0 the malfunction may p ropagate an error of Type B. The probabilities associated with the error process are p(Asi) = p(ai) p(bi) = 1/4 A(LSi)= P( SI) P(Ci)- 1/8 P(Si+i) = P(Asi) p(c i) 1/8 p(_Asi+) = p(Asi) p(cr) i 1/8 P( il) = i+l) Pf i+l) The malfunction of the type ai = 0 is effective only when the correct value of ai is one. If at the time of the constraint the value of bi is zero the resulting error is the generating element type ri = 0. If bi = 1 both the ki and the ri outputs will be in error. The erroneous outputs are ki = 0 and ri = 1. The resulting error may be described completely in terms of the constraint ki = 0 D ri = v which has already been discussed.

-96The Error Structure of the rc Sum Logic In reference to Figure 10 the rc sum generating logic consists of gates g6, g7 and g8. The error structure of the rc sum logic is perfectly straightforward if the carry logic and the re sum logic are separated as shown in Figure 10. For this configuration a malfunction in the re sum logic may cause at most one error in the sum representation. The propagation of errors is determined only by the carry logic and this preceeds the rc sum logic. In the usual logic of the binary adder the rc sum logic and the carry logic are not independent. In Figure 10 both gates g5 and g6 generate the conjunctive function needed for the carry logic. Thus g5 may be eliminated and g6 is then part of both the carry logic and the re sum logic. Malfunctions in g6 may affect both the carry vector and the rc sum process. The effect of a malfunction of the gate g6 on the carry vector is completely described in terms of the results of carry logic malfunctions. We shall now consider the possible carry vector errors due to malfunctions of the components of gate g6. The carry vector error and the rc sum process error combined determine the sum error. The diodes associated with gate g6 are diodes dl and d2 shown in Figure 12. In a previous section the following correspondences were obtained between diode malfunctions and representative constraints of the carry logic inputs

-97dls... ri = 1 d2s... Ci =1 2s i dlo... -0 d10 oe * Ci = 1 d20.... ri = 0 The malfunction represented by ri = 1 applied only to gate g6 is effective only if ri = 0 and ci = 1. The resulting sum error is Type B. If ci = 0 no error is produced. p(Asi) = P(ri) p(ci) - 1/4 p(Asi) = 0 P(OSI+1) = p(~sI) 1/4 p(Asi+l) = p(Asi) = 1/8 Malfunctions corresponding to the constraint ci = 1 result in one erroneous sum element si if ri = ci = O. If ci = 0 and ri = 1 a Type B error is produced by the constraint ci = 1. p(&si) = p(ri) p(Ci) - 1/4 P(asi) = 0 p(Asi+l) = p(si) 1/4 P(a*Si+l) = P(si) P(ri+) 1/8 The malfunction represented by the constraint ri = 0 produces an error only when ri = 1 and ci = 1. The resulting propagated error is Type A.

-98The Effectiveness of Parity Checking The effectiveness of the digital and numerical parity checks is found by considering the probability that a logical malfunction will cause an undetectable change in the sum representation. The effectiveness of a checking procedure can best be evaluated in terms of effective malfunctions. In this case only the form and the propagation of errors are considered and the rate of initiation of errors is ignored. A summary of the characteristics of the logical malfunctions associated with the logic of a binary adder is given in Table III. The table was compiled from the information derived in the previous sections. The information needed to study the effectiveness of the various parity checks is the normalized error distribution. The error distribution i\*si+n is the probability that the sum elements si to si+n have been modified due to some effective error. For our purposes the important aspect of the error distribution is the ratio of the various A*s. values. It is convenient to normalize the error distribution so that t ~Z xn'i+n = 1. Then A*nsi is the probability that the malfunction n=o produces an error in only one element. Atnsi+l is the probability that the resulting error disturbs two and only two successive elements of the sum. A*nsi+2 corresponds to only three successive errors, etc. Four different error distributions have been found. The different distributions shown in Table IV are designated E.D. 1, E.D. 2, E.D. 3 and E.D. 4. In the calculations which follow the error distribution series are considered infinite in length. The approximation is valid since the

-99TABLE III SUMMARY OF ERRORS Constraint Otherns Error Type Distribution Conditions GEM vi = 0 or CIM ri = 0 A 1 GEM vi = 1 or CIM ri = 1 B 1 GEM or CUM ki = 0 A 1 GEM or CM ki = 1 B 1 GEM ri = 0 or ci = 1, ki = O A and si = 1 1 GEM vi = O=ri = 0 c = 0 si = GEM ri = 1 ci = 1, ki = 0 B and si = 0 2 ci = 1, ki = 1 si = Ci = 0 O GEM ki = 1ri O ri i= = ri = ci = 0 B and si = ri = B 1 GEM ki = Orri = vi ki = Ci = 1 si = 0 ki = 1, ci = 0 A and si = 1 1 GEM vi = lrri = ki ki = ci = O Si =1 ki = 0, C = B and si = 0 GEM ai = 1 ci O = ci = 1 B and Si = 1 GEM ai = 0 bi = O same as GEM ri=O with ki=O bi = 1 same as GEM ki = O r = v 1 CGM ri = 1 ci = 1 B and si = 3 CGM ci = 1 ri = 0 = 1 ri = B and s = 0 3 CGM ri = 0 ci = 1 A and si =1 3 GEM generating element malfunction CIM carry logic malfunction CGM common gate malfunction

l100TABLE IV ERROR TYPE Shi+n Si+n-1 l,..si+2 Si+l - sum element A 0 lo o o o l 1 B 1 0......0 0 TABLE V ERROR DISTRIBUTION (NORMALIZED) -~ 1.11 1 1 1 11 1 1 1 1 1 1 1 II n A * Sln A* n A *sn i 1+li+2 s i+32. 3 1 1/2 /4 1/8 1/16 2 5/8 3/16 3/32 3/64 3 0 1/2 1/4 1/8 4 1/3 1/3 1/6 1/12

-101number of elements usually involved in computer arithmetic operations is thirty to forty bitso The fact that the series is not truncated will affect most severely the error distributions resulting from the initiation of errors in the first few high order elements. The number of elements so affected is small compared to the total number of elements involved. The effectiveness of a simple digital parity check employing one check digit is dependent on the probability that the error in the sum representation involves an odd or an even number of elementso If the number of erroneous sum digits is even the check failso The check is successful if the number of erroneous sum digits is odd. The probability that the check succeeds p(S) or fails p(F) for each of the four error distributions is (S) = 1/2 + 1/8 1/32 +... - 2/3 p (F) 1/4 + l/l6 1/4 + e - 1/3 P (S) 5/8 + 3/32 + 3/128 +. 3/4 P2 (F) - 3/16 + 3/64 + 3/256 + o =1/4 p (S) 1/4 + 1/16 + 1/64 i +oo 1/3 p (F) / 1/2 + 1/8 + 1/2 +... = 2/3 p4(S) =1/3 + t6 + 1/24 +. -5/9 p4(F) - 1/3 + 1/12 + 1/48 + oo = 4/9 The effectiveness of a digital parity check consisting of two digits is now determinedo The check is constructed so that elements in odd positions are incorporated, in one check and the elements in the even positions in the other check The check is judged successful if as a result of an effective error either check failso

-102P(S) =1/2 + 1/4 + 1/8 + 1/32 + 1/64 +... = 14/15.92 p (F) =1/16 + 1/256 + 1/4096 +... = 1/15 p2(S) = 5/8 + 3/16 + 3/32 + 3/128 + 3/256 + 3/512 +.. = 19/20 95 P2(F) = 3/64 + 3/1o24 +.. = 1/20 p3(S)= 0 + 1/2 + /4 + 1/16 + 1/32 + 1/64 +... = 13/15 -.87 p3(F) = 1/8 + 1/128 +... = 2/15 p4(S) = 1/3 + 1/3 + 1/6 +... = 41i/45,91 p4(F) = 1/12 + 1/192 + = 0 4/45 The effectiveness a any simple digital parity check constructed as above and consisting of n check digits may be found by evaluating a recurring binary fraction consisting of repeated groups of 22n-1 one digits and one zero digits The magnitude of the non terminated fraction is pl(S). PI(S) for a representation of the type oo 1111.o 10 1111 oo 10 1111 o. O 10. is 2n p (S) = 2'2 for n check digits 22n1L P2(S), p3(S) and p4(S) are obtainable if pl(S) is known. p2(S) = L/4 + 3/4 p (S) p3(S) = 2 P1(S) -1 p4(S) = 4/3 p(s) 1/4 Numerical checking requires the residue of the sum representation with respect to the check base. Check?asesof magnitude 2n -1, n>0, are particularly appropriate for binary representations.

-103The process of numerical checking requires the assignment of a check weight associated with each element of a representation. The check weight is the least positive residue of the normal element weight with respect to the check baseo The following examples illustrate the weighting scheme for several possible check basesO a 0 0. 2 1 2 1 2 1 n - 3...212121 m=3. 4 2 142 1 m 7 o 0 2 1 4 2 1 m- 15 It is observed that an error in a single digit is detectable by any numerical check. Furthermore, it has been shown that the errors due to logical malfunctions which change more than one sum element are restricted in form. The permitted error forms consist of all zeros except the last erroneous sum digit which is a one, Type B, or an erroneous representation consisting of all ones except the last digit which is a zero, Type Ao The permitted error forms are always detectable by a numerical check with a check base of 2nlo Consider the following example which employs a modulo 3 numerical checko S = 11 00 01 10 11 10 = xy = x+y' 0 11 00 01 x Q parity 1 1 00 10 1 y digit 1 10 00 11 p 11 10 00 0 c 10 00 00 11 S ~ Consider now an error in ann the carry logic such that the error propagates to cn+l, for example, an effective malfunction which changes cn.

-104It follows then that cn-l is also changed since in this example rn = 1. The erroneous carry representation is 00 10 00 0 and the erroneous sum is 01 00 00 11o The modulo 3 parity check bit associated with the erroneous sum is clearly one and the error is detected, As a result of the various constraints which exist in the process of binary addition the simple modulo 3 numerical parity check is 100% effective if the cn+l element of the sum is considered. The check requires only two bits. For operations consisting of repetitive addition such as multiplication or subtraction, the numerical parity check is 100% effective only if applied at each addition step. It is possible to obtain an accumulated error due to several addition operations which is undetectable by the numerical check.

CHAPTER V THE RESIDUE CODE An Extension of Numerical Checking If a sufficient number of numerical parity checks are employed in a number system the parity check representation may ultimately contain as much information as that possessed by the number system being checked. If this is the case it then is possible to replace the original number representation by the check representation. The extended check representation is termed a residue number system. We shall now proceed to study the construction and properties of the residue number system. The first requirement for a residue-number system is that the bases of the different elements of the representation must be relatively prime. If the residue number system is considered as an evolution of the numerical checking procedures the above statement may be reinterpreted as a requirement that the different check bases be relatively prime to each other. If a pair of bases are not relatively prime the effect is the introduction of redundancy. The following example will illustrate this fact. Contrast the combination of a modulo 2 and a modulo 6 check against the combination of a modulo 3 and a modulo 4 check. In the first case the two check bases are not relatively prime while in the second case the check bases are relatively prime. The combination of a modulo 2 and a modulo 6 check is unique for only 6 states while the combination of the modulo 3 and moldulo 4 check provides a unique residue representation for 12 states. This is further clarified by Table VI. -105

-106TABLE VI REDUNDANCY OF A NON-RELATIVELY PRIMED BASE REPRESENTATION Least Positive Residue Number Mod 2 Mod 6 Mod 3 Mod 4 0 0 0 0 0 1 1 1 1 1 2 0 2 2 2 3 1 3 0 3 4 40 1 0 5 1 5 2 1 6 0 0 0 2 7 1 1 1 3 8 0 2 2 0 9 1 3 0 1 10 0 4 1 2 11 1 5 2 3 12 0 0 0 0 13 1 1 1 1 14 0 2 2 2

-107If the bases of the residue number system are relatively prime then the number of states uniquely represented without redundancy is equal to the product of the magnitude of the bases. The most efficient residue number system representation is obtained by a consecutive sequence of prime numbers starting with the integer two. Since only a relatively prime relationship is desired between the bases it would be possible to employ one base equal to a non-prime integer as long as this base is relatively prime to the other bases. However, there are certain advantages which are associated with the prime number base but are not associated with the non-prime base. In particular, the residues with respect to a non-prime base form a ring, while the residues with respect to a prime base form a field. The characteristics of rings and fields which are important to the present discussion are the following: Two operations, multiplication and addition are defined for both rings and fields. Also an additive inverse exists for both rings and fields. This means that subtraction is possible as well as the defined operations of addition and multiplication. The ring does not require a multiplicative inverse. The field must contain a unique multiplicative inverse for every element. Furthermore, the field admits the solution to linear algebraic equations. The residue number system differs from the standard consistently weighted number systems in many ways. The most important difference is that the residue number system, being based upon a number of

-108fields or rings, has two defined operations. It will be recalled that arithmetic operations in the consistently based number system usually employed in the digital computer are based upon the definition of one operation, that operation being addition. The other difference is that the residue representation possesses digital independence of the elements comprising the representation. There exists no carry to constrain the elements. The absence of a carry plus the fact that multiplication is defined gives rise to the expectation that the residue number system should be amenable to simple error detecting and correcting schemes. It should also be possible to execute rapid addition and multiplication. An example of a residue number system is presented in Table VII. The number system shown in Table VII uses the prime bases 2,3,5 and 7. The number system therefore contains 210 states. The 210 states may correspond to the positive integers 0 to 209. Table VII shows the residue number representation corresponding to the positive integers 0 to 29. Additional integers of the number system may be found by TABLE VII NATURAL NUMBERS AND CORRESPONDING RESIDUE NUMBERS N.N. 2357 N.N. 2357 N.N. 2357 0 0000 10 0103 20 0206 1 1111 11 1214 21 1010 2 0222 12 0025 22 0121 3 1033 13 1136 23 1232 4 0144 14 0240 24 0043 5 1205 15 1001 25 1104 6 0016 16 0112 26 0215 7 1120 17 1223 27 1026 8 0231 18 0034 28 0130 9 1042 19 1145 29 1241

-109congruence operations. Let a,b,c and d be the digits associated with the bases 2,3,5 and 7 respectively, The following congruences define a,b,c and d for the residue representation of the number N: N - a Mod 2 N b Mod 3 N c Mod 5 N - d Mod 7 The residue number system is readily extended to include more states. For example, if a basell is added to the representation it is then possible to represent 2310 states. Table VIII shows the product and sum of the first ten consecutive primes greater than or equal to 2. The product of the primes indicates the number of states of the number system while the sum of the primes is a measure of the size of the representation in terms of digits. Table VIII also includes the number of bits required to represent each prime base in the binary number system. TABLE VIII NUMBER OF STATES AND DIGITS ASSOCIATED WITH A RESIDUE REPRESENTATION n n i Pi P Pi Pi Pi rPi i=1 i- bits bits 1 2 2 2 1 1 2 3 5 6 2 3 3 5 10 30 3 6 4 7 17 210 3 9 5 11 28 2,310 4 13 6 13 41 30,030 4 17 7 17 58 510,510 5 22 8 19 77 9,699,699 5 27 9 23 103 223,092,670 5 32

-110Residue Addition and Multiplication The residue number representation consists of several elements and is assumed to be in one to one correspondence with some positive integers of the real number system. The elements of the residue representation are the least positive residues of these real positive integers with respect to the different moduli which form the bases of the residue representation. It follows as a direct consequence of the structure of the residue number system and the properties of linear congruences that the operations of addition and multiplication are valid in the residue number system subject to one proviso. The proviso is that the residue system must possess a number of states sufficient to represent the generated sum or product. If the residue number system does not have a sufficient number of states to represent the sums and the products generated by a particular finite set of real integers then the residue system will overflow and more than one sum or product of the real number system may correspond to one residue representation. For a residue number with a sufficient number of states an isomorphic relation exists with respect to the operations of addition and multiplication in the residue system and a finite system of real positive integers. Each element of the residue number system is obtained with respect to a different base or modulus. It follows therefore, that the rules of arithmetic associated with each element will be different. For example, the addition and multiplication of the elements associated with the modul 2 and 3 follow rules specified in Table IX.

-111TABLE IX MOD 2 AND MOD 3 SUMS AND PRODUCTS 0 0 1 0 0 | ~o 1 2 o0 0 2 O O 1 2 o O O O sum Mod 2 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 1o. o sum Mod 3 product Mod 3 1 0 I product Mod 2 No carry tables are necessary since the residue number system does not have a carry mechanism. Addition of two residue representations is effected by the modulo addition of corresponding elements of the two representations. Corresponding elements must have the same base or modulus. Modulo addition of elements which have different bases is not defined. Multiplication in the residue system is effected by obtaining the modulo product of corresponding elements. The operations of addition and multiplication of two residue numbers are indicated by the following notation: S = A 0 B S=AOB p =A B Consider a residue number representation with base 2,3,5 and 7. We assume an isomorphic relation between the residue number system

-112and the real positive numbers 0 to 209. An isomorphic relation then exists for the operations of multiplication and addition only if the product or sum is less than 209. The following examples employing residue numbers illustrate the addition and multiplication operations and the presence of an isomorphism or the lack of isomorphism in the case of overflow. Residue numbers will be distinguished by the use of parentheses. 29 + 27 = S = 56 29 (1 24 1) 27 (1 0 2 6) 56 *- (0 2 1 0) (12 41) (1 0 2 6) (O 2 1 0) The following operations are considered in performing the addition of the two residue representations. 1 + 1 0 Mod 2 2 + 0 2 Mod 3 4 + 2 1- Mod 5 1 + 6 0 Mod 7 Consider the addition of two numbers which produce a sum greater than 209. S = 100 + 200 (0 1 0 2) (0 2 0 4) (o 0 o 6)

-113The residue representation(0006)corresponds to the real positive number 90. In this particular example the sum has overflowed the residue representation. The resulting sum is the correct sum modulo 210. 300 - 90 Modulo 210 Finite real number systems and residue number systems have the same overflow characteristics. The sum which remains after the overflow is the correct sum with respect to a modulus numerically equal to the number of states in the finite number system. The following is presented as an example of the process of residue multiplication. p = 10 x 17 = 170 10 *(O 1 0 3) 17.(l 2 2 3) 170 4(o 2 0 2) (o 1 03) e (1223) (0 2 0 2) The process of multiplication involved consideration of the following relations for each element. 1 x 0 0 Mod 2 1 x 2 2 Mod 3 Ox2 0 Mod 5 3 x 3 2 Mod 7

-114An overflow resulting from a multiplication is no different than the overflow resulting from an addition. Consider the product obtained from the residue multiplication of the real numbers 10 and 100. The result in the modulo 210 number system corresponds to the real number 160 which is 1000 modulo 210. Subtraction and the Representation of Negative Numbers The process of subtraction is obtainable in the residue number system by employing a complement representation consisting of the additive inverses of the positive residue representation. Since the elements of the residue representation are elements of a field, the additive inverse always exists. There is no basic problem associated with the subtraction operation. There is, however, a problem associated with the representation of negative numbers. In particular, some mechanism must be included in the number system which will distinguish positive and negative differences. This problem will be discussed in detail in a later section. The additive inverse of a residue number is defined by the following: a Q a' = 0 The formula may be considered to apply to an element of the residue system or equally well to the whole residue representation. Consider the following examples with reference to the modulo 210 residue number system. a = (1241) then a' = (1 1 1 6) since (1 2 4 1) e (1 116) (O O O 0)

-115The following examples have been chosen to illustrate the subtraction process and to some extent the difficulties associated with the sign of the difference. D = A B = Ae B' We consider first the case where the magnitude of A is greater than B. Let A = 200 B = 100 In residue representation then B' = (0 2 0 5) and (02 0 4) 0 (0205) ( 1 0 2) The residue representation of the difference corresponds to positive 100 in the real number domain. We consider next the case where the magnitude of B is greater than the magnitude of A. A' = (0 1 0 3) then D = A' 3 B and (0 1 0 3) 0 (0 1 02) (02 0 5) The difference (0 2 0 5) is the additive inverse of (0 1 0 2). Unless additional information is supplied the correct interpretation of the representation (0 2 0 5) is in doubt. (0 2 0 5) may correspond to either +110 or -100. The difficulties associated with whether a residue representation corresponds to positive or negative integer can be partially

-116removed by the division of the residue number range into two parts. This is exactly the scheme that is employed to obtain a machine representation of positive and negative natural numbers. For the system of natural numbers two different machine representations of the negative numbers may be obtained and are commonly designated the radix complement representation of negative numbers and the diminished radix complement representation of negative numbers. The complement representation for a residue code is defined in terms of the additive inverse. Thus the representation of negative A is A' where A @ A' = 0, and the range of A is restricted to approximately one half of the total possible range of the residue representation. This can be illustrated by consideration of a specific residue code. The residue representation employing bases of magnitude 2,3,5, and 7, is divided into two parts. The residue representations corresponding to the natural numbers 0 to 104 are considered positive. The residue representations corresponding to the natural numbers 105 to 209 are considered negative. The range of this particular number system is from -105 to +104. The arithmetic rules pertaining to sign and overflow conventions for this particular number system are the same rules normally associated with radix complement arithmetic. The complement representation does eliminate in principle any ambiguity concerning the sign of the result of an arithmetic operation. However, there is a practical difficulty. The determination of the sign of a residue representation requires the determination of the

-117magnitude of the representation relative to the magnitude of the representation which separates the positive and negative representations. The determination of relative magnitude for a residue representation is discussed in a later section. It will be shown that the determination of relative magnitude is not a simple problem. Conversion From a Residue Code to a Normal Number Representation It is frequently desirable to determine the natural number associated with a particular residue representation. The need for this conversion occurs frequently when investigating the properties of the residue system. The residue representation is constructed in such a manner that magnitude is not readily obtainable. The presence of column weights in the normal number representation greatly facilitates the determination of magnitude. It is possible to assign a weight to each digit of the residue representation in such a manner that the modulo m sum of the digit-weight products is the real natural number in consistently weighted representation. m is the product of all the bases employed in the residue representation. The conversion technique is known as "The Chinese Remainder Theorem". The material which follows describes the conversion technique but omits the proof. A simple and straightforward proof is found in Dickson.(20) The proof does not refer specifically to residue number systems but rather to a system of linear congruences. If so regarded, a system of congruences defines a component of a residue number system.

-118Consider a residue number system with bases m.... mt. The corresponding digits are labeled al.... at. The following equations define the conversion process. a1 A1~ +..+m a=m BSMod m al Al m +., + at At E - Mod m It where Ai m 1 Mod mi l mi t and m = f mj j=l The conversion formula for a particular residue number system is now obtained. m = 2 m2 = 3 m3 = 5 m4 = 7 105 A1 lMod 2 so A = 1 70 A2 1 Mod 3 so A2 = 1 42 A 1 Mod 5 2 A 1 Mod 5 so A = 3 3 3 30 A4- 1 Mod 7 2 A4 = 1 Mod 7 so A = 4 105 a1 + 70 a2 + 126 a3 + 120 a4 - S Mod 210 The conversion formula is now used to determine the natural number corresponding to the residue representation (1 2 0 4). 105 (1) + 70 (2) + 126 (0) + 120 (4) = 725 725 - S Mod 210 s = 95

-119Other conversion techniques exist. In particular it is possible by means of a deductive process to determine the magnitude of a particular residue representation. This requires both a knowledge of the nature of the residue system and the natural number representation associated with at least one residue representation. Due to the deductive nature of the process it is more suitable for human computation than for machine computation. The process is explained using the residue number of the previous example (1 2 0 4). The knowledge of the residue representation for unity which is (1 i 11) is assumed. Consider the effect of changing the second digit from one to two. The change adds the product mlm3m4 =70 to the number since 70 is congruent 1 modulo 3. The resulting residue representation(l 2 1 1) corresponds to 71. The effect of changing the third digit is to change the magnitude by some multiple of the product mlm2m4 = 42. The correct change in magnitude is 42x where 42x - 4 Mod 5. So 42x = 84 and the residue representation 1 2 0 1 corresponds to 155. The fourth digit is modified by the addition of a three. The effect of this change is determined by 30x - 3 Mod 7. The magnitude change is 150. The sum of 150 and 155 modulo 210 yields the correct result 95, in correspondence with (1 2 0 4). The conversion formulae provide a possible means of achieving conversion from a residue code to an analog representation. The conversion would involve first the transformation of the residue code to a normal weighted representation and then a transformation to analog represention by means of standard techniques. Alternatively the conversion

-120process need not involve the normal representation if the analog equipment were capable of precise subtraction of multiples of m where m is the product of the bases. A third conversion process would employ counters for both the residue system and the normal number system. Comparison would be employed to determine the accumulation of the desired number of counts. At the time of comparison one set of counters would contain the residue representation and the other the desired normal representation. Greater Than or Less Than Relations for Residue Codes Some of the arithmetic operations for the residue code are dependent on the determination of a greater than or less than relationship. A possible technique might involve the conversion techniques described in the previous section. Such a scheme would involve the standard comparison techniques associated with the determination of the relative magnitude of two numbers represented in a weighted representation. The procedure described in this section does not require an explicit conversion from residue code to normal representation. Consider a residue code consisting of t digits. The t digits of the residue code are associated with t congruence relationships as follows: S ai Mod 1 i Ci t

-121S is the magnitude of the number expressed in normal representation. It is also possible to express the number S as S = ai + Ai mi Ai is the integer part of the quotient of S divided by mio In regard to a greater or less than relationship, the determination of Ai divides the range of the residue representation into m/mi parts. We proceed to calculate Ai from the set of t equations given above. Let S = at + At mt < mt This equation is then used to replace S in the remaining t-l equations, yielding t-l equations of the form Atmt - (ai + a~ ) Mod mi 1 < i <- t-l or At (ai + a ) /mt Mod mi i At - dt Mod mi where /mt is the multiplicative inverse of mt with respect to base mi. The multiplicative inverse is defined as xt/xt = 1 Mod mi dt is the least positive residue of (ai + a, )/mt with respect to base i, at is the additive inverse of at. Let At be expressed as t-lI At = dt + At m_ tl mAtl < m mtmt.

-122If this expression is substituted for At a set of t-2 equations remain. The equations are of the form At + (dt - ) /t Mi Mod 1 < i t- 2 At_1 di 1 Mod mi The system of equations shown below is generated by repetition of the above substitution process until no equations remain. S at + Atmt t- l \iAt - dt + At<1mt t -2 At- = dt-1 + At-2t-2 3 =cd+ A2m2 A- d Moda i 2 2equation e om to The equation are combined to yield:

-123S = at + mt 4-1 + mt-li E 4i + mt2 (d + - la mtml +tmalt1 - at + t + mmt- r1m1 + tt-2d +t where At < mt t -n-1 t-n < mt-n-l Therefore, S is never equal to or greater than m and d2 divides 2 the range into m1 parts, d3 divides each of the m1 parts into m2 parts, d3 divides each of the m2 parts into m3 parts, etco The determination of the less than or greater than relationt-n-l ship consists of the successive comparison of the dt-n constants corresponding to two residue representations. Let the representations be designated E and F. The first step of the greater than or less than determination is the comparison of d (E) and d (F)o If the two constants are different the process may be terminated and the larger number is associated with the larger constant~ If the constants are equal in value the comparison process must consider the pair of constants d3(E) and d2(F)o The process is contirred in this manner until a set of nonidentical constants are foundo If all of the d constants are identical a final comparison is made on the basis of the pair of t th digits of the two residue representations. The formulae which define the greater than, less than process may be applied recursively to obtain a formula for a greater number of digits. The process has been extended to five variables and the results are shown in Figure 14.

-124a5 a, a2 03 04 /m5 /m5 /m m; /m-( ) /m2(02) /m-03) /m-(04 dN4 d /m3 0) /m-(02 2 d3 SYMBOLS ~~ MOD.m.)^^~~ (g ~ ~ADDER k /m; MOD. i7 MULTIPLIER d RADIX ( ) COMPLEMENTOR MOD. m~ Figure 14. Logic for the Determination of the Greater or Lese Than Relationship.

-125Admittedly the process required to obtain a greater than or less than relationship leaves much to be desired. One presumed advantage of the residue number was the absence of a carry process. The greater or less than process is essentially sequential and is in many ways similar to the carry process. Redundancy A residue code contains redundant information if the product of the bases exceeds the number of states required to represent a specific range of numbers. In particular, if sufficient redundancy is introduced the residue code may be made independent of one or more digits. Redundancy is obtained by adding one or more additional digits to the structure of a residue code sufficient to represent the desired number range. Consider the addition of a prime base nm to a residue code with bases ml.....mt. The resulting code is redundant. Any one digit of the code may be deleted and the code will still contain the required amount of information. Furthermore, any number of digits may be deleted if the product of the remaining bases is greater than the magnitude of the represented number. This means that normally it is possible to delete more than one low order digit but in general only one high order digit may be deleted. Any degree of redundancy is obtainable by the addition of more redundant digits. Redundancy in the residue code is easily obtained. The real problem concerns the realization of the procedures for error correction and detection. This problem may be considered from the viewpoint of

-126the Chinese Remainder Theorem. A residue representation of t+l digits has one redundant digit. The Chinese Remainder Theorem may be applied using only t digits of the residue representation. In fact the theorem may be applied once for each of the t+l combinations. Each combination consists of t digits. t+l solutions are obtained and if the redundant residue representation contains one erroneous digit then only one of the t+l solutions is correct. The correct solution is, of course, the solution which does not involve the erroneous digit. Unfortunately, there is no way in which the correct and the incorrect solution may be distinguished within the framework of the residue code with a single redundant digit. We now consider the question of whether two of the incorrect solutions may be identical. Given a residue code with bases ml.... t+l, we assume the jth digit aj is erroneous by d units. The t erroneous solutions obtained by means of the Chinese Remainder Theorem deviate from the correct solution by Awhere A-^ d Mod mj xim mjmi Let the correct solution be S and a pair of erroneous solutions Si and Ski then xim S + iL- Si Mod m mjmi mi xkm S +, = Sk Mod m mjmk mk S + = Si + a s < m m ami mi xkm mm S + Jk = Sk + b^ S < m Ajmk mk mk

-127a 2; b<2 a = 0, 1; b = 0, 1 Assume Si = Sk then Xi Xk a b X_= _m __] m. mi tmk mimk We consider the four combinations of values of a and b (1)i _ k = O if Xi = mif mi mk Xk = mkf f is an integer (2) mj mi (3) - j mk (4) i f k mj mj mi mk mi mk ximk - xmi = mjmk - mjmi mk(xi - m) = mi(xk -mj) The equality is satisfied if Xi = mj + mif f is an integer xk = mk mj + mif) d Mod mj m mJmi mJ + mkf \ m mjmk J M- OM Mo d mj m --- M 0 Mod mj mi - 0 Mod m mk

-128Thus both equations reduce to mf -= d Mod m. mJ J The same solution is obtained for xi = mif and xk = mkf (combination one) therefore: xi Xk (m or O xi mk mim mk J implies a single value of d and hence Si = Sk only if di = dk. It follows that none of the solutions are identical. However, unless some auxiliary error detecting scheme is employed it is impossible to separate the correct from the incorrect solutions. If two redundant digits are employed it becomes possible to distinguish between the correct and the incorrect solutions. The representation consists of t+2 digits and the number of solutions is the number of combinations of t+2 digits taken t at a time. When only one digit is in error the number of correct solutions will be equal to the number of combinations of t+l things taken t at a time. The number of correct solutions is t+l. Since the total number of solutions is (t+l)(t+2) the ratio of correct to incorrect solutions is given as 2 t2-. We shall now show for a residue code with two redundant digits that none of the erroneous solutions are identical. Typically A is of the form xik m A i mkm d Mod mj mjmimk

-129A pair of erroneous solutions Sik and Srs are defined by S + = Sik + a mjmimk mimk + Xrs = Srs + b mJmrms mrms a = 0, 1; b = 0, -1 Let us assume Sik = Srs then Xik Xrs amj bmj mimk mrms mimk mrms If i = r then the relationship becomes xik Xrs = a bmj mk ms mk ms This situation has already been considered for the case of one redundant digit. We need, therefore, only consider the case where i / r. Four combinations exist since the possible values of a and b are zero and one, (1) uik_ Xrs mimk mrms m. (2) # m mi~k (3) f- mj m mj (4)..i mmk mrm The first combination is satisfied only if Xik = f mirk Xrs = f mrms

-130The fourth combination is satisfied only if Xik = mj + f mimk Xrs = mj + f m ms The results indicate that identical erroneous solutions must correspond to the same d. Erroneous solutions are not identical. Since the erroneous solutions are not identical, the presence of two identical solutions is sufficient to indicate the correct solution. It is then possible to use a smaller set of solutions involving less computation. The set of solutions is chosen so that for every base there exist at least two solutions which are not functions of that base. Let the total number of digits of a residue code be designated as no This includes both information and redundant digits. If n is even the above requirement may be met with n properly chosen solutions. If n is odd then n+l solutions are required. There exists considerable flexibility in the choice of the solutions. If the number of solutions used is somewhat more than the required minimum the range of the representation is extended. This fact may be illustrated by an example. Consider a residue representation of six digits. The bases are consecutive primes. The lowest base is two. Six solutions are chosen with the following base pairs deleted: ala6,a2a6,ala5,a2a4,a3a35a3a4 The range of the representation is given by the expression O <R< m mimj

-131where mimj is the largest product of bases corresponding to the deleted pairs of digits. For this example the largest product of deleted base digits corresponds to m3m5 and is equal to 55. The range of the representation if six solutions are used is zero to 551. If the code does not have the property of single error correction the largest number represented is 30030. The range of the representation can easily be extended by the addition of only one solution. The solution which did not involve a3 and a5 is replaced by a solution deleting a5 and al or a2 and a solution deleting a3 and al or a2 is added. By the addition of one solution the largest number represented for the example above is (m/m2m6)-l which is equal to 770. The maximum range of the representation of an n digit residue code with single error correction is given as 0 Rm< m m2mn An upper limit for the number of solutions required to realize this range is obtained by considering the deletion of the digits a3 to an with the deletion of a1 and a2, This scheme will yield 2n-4 solutions and represents the absolute maximum number of solutions required to realize the above range. Usually the required number of solutions will be less than the maximum, The efficiency of the residue code for the correction and detection of single digit errors is now compared with the theoretical efficiency predicted by Shannon's theory. (4 It is known that a single error detecting and correcting code of the Hamming type obtains the

-132maximum theoretical efficiency if the total number of digits of the representation is 2m-1, where m is any non zero positive integer. The Hamming code is least efficient when the total number of digits is equal to 2m. The residue code will be considered from two viewpoints. First, the number of represented states will be translated to bits without regard to the form of the final code, Secondly the residue code will be considered in terms of a corresponding binary code for each residue digit. The binary coded residue representation does not use the information capacity of the binary code in the most efficient manner. However, the binary coded residue representation is one form in which the residue code would be used in practice, The data of Table X indicates the efficiency of a residue code constructed from consecutive prime bases starting from two. The code has error detecting and correcting properties and the efficiency is defined as the ratio of the logarithm base two of the number of states of the representation corresponding to information to the logarithm base two of the total number of states of the representation. The theoretical maximum efficiency for single error correction and detection is obtained for the assumption that for an m digit code m+l events may occur with equal probability. The possible events are any single digit in error or no error.

-133TABLE X RESIDUE CODE EFFICIENCY Efficiency Number of Efficiency of the Bin.ry Residue of the Encoded Residue Digits Residue Code Representation 4.43 -37 5.55.47 6.65.56 7 o70.60 8.75.64 9 ~ 78.68 10.80.71 11.83.74 The following formula due to Shannon specifies the maximum efficiency. m+l C = log2 N - I pi log2 Pi i=l The bits of information per binary symbol is given by C i = 1 1 log2 Pi The results of Table X and the above formula are compared graphically in Figure 15. The graphical presentation permits a rapid comparison of the relative efficiencies of the various codes in spite of the fact that the total number of binary digits varies. The variation in the number of binary digits associated with a particular number of residue digits is due to the inefficient use of binary digits when each digit of the residue code is expressed by a binary code.

.9.8 -.7 0 0 00 0.6 @ w.5 00 CL I 0 l l.4 $-* THEORETICAL 12~~~ 3 F^~~~~0 RESIDUE CODE C.2 I. 0.l 5 10 15 20 25 30 35 40 46 50 TOTAL BINARY DIGITS Figur 15. Relative efficiency of the Residue Code.

-135Division In any number system the operation of division is a problem. This is particularly true of the residue system. Every element of a field except zero is associated with a unique multiplicative inverse. This is one of the requirements which must be met by a mathematical system if it is to be a field. The multiplicative inverse of a field element x is denoted by /x and is defined by the following relationship x/x 1- Mod mx The definition also requires closure. The division process for residue codes is complicated by two factors. The first is the absence of a multiplicative inverse for the zero element. The second difficulty is the fact that residue division and the normal division process are in one to one correspondence only when the resulting quotient is an integer value. We shall consider first the problem of residue division of the elements of a single field and shall consider later the elements of several fields considered as a residue code. The division process represented in equation form as a = _ b implies the following equation: a = bq The difference between normal arithmetic and residue arithmetic is that in residue arithmetic the product bq need not necessarily be equal to a, only the congruence of a and bq is required, bq - a Mod mn

-136Multiplication by the multiplicative inverse of b obtains *~ -,^/q b IbMod, miB The correct interpretation of q in the above equation is that the number a is obtained by forming the sum consisting of b, q representations. The sum is carried out in a closed number system of base mn. Thus q corresponds to the quotient only when the quotient has an integer value. Examples may be obtained from the consideration of a modulo 5 fieldo 4 2q - 4 Mod 5 q = 2 Mod 5 4 3q 4 Mod 5 q - 3 Mod 5 note 3X3 4 Mod 5 3 q 4q 3 Mod 5 q 2 Mod 5 In the above examples q corresponds to the quotient only in the first example.

-137The residue code representation of a number consists of many elements. Each digit of the representation is associated with a different prime base. In other words each digit of the representation is an element of a different field. The division of two numbers in residue code may be expressed by a system of congruences. The solution A = (ql-q2<....n ) must satisy all the congruence relationships of the system. A zero digit in the divisor B = (blb2, *.bn) must be given special consideration. The congruence corresponding to any bi = 0 must be removed from the system. The deletion of the congruences for which bi = 0 is consistent with the residue definition of division given above. In general, if some bi equal zero then QB ^ A Mod m For the special case in which bi = 0 and QB A Mod m it is also true that Q has an integer value. The deletion of the congruence associated with bi = 0 results in a relationship of the following form if there are no elements b = 0. QB1 - Ai Mod m n mi The examples which follow are presented to clarify the process of residue division. Consider a residue code with bases 2,3,5 and 7. Since some confusion might exist between the normal number representation and the residue representation the residue representations

-138are enclosed in parenthesis. q = 9 (1042) = (q) (1042) = q(0144) 4 (o144) q - (x014) in terms of congruences 4q- - 9 Mod 105 324 = 9 Mod 105 q 29 () (1241) (1142) 4- 79 11 (1214) 79 x 11 29 Mod 210 q 7 (q) =(1120) = (xx 20) 6 x 7 7 Mod 35 -24 (q) (0043) (x 223) " 8 ^^ _(0231) (23 8 x 3 24 Mod 105 The process of residue division has certain interesting properties and quite possibly has applications in respect to special problems. Unfortunately, the residue division process is not a substitute for normal division. It appears that the only way in which division can be effected in the residue code is by the utilization of techniques similar to those employed for division in a consistently weighted number system. The division process then requires trial and error subtraction or addition and the greater than or less than relationship. The division algorithm could also include trial multiplication since in the residue system addition and multiplication require the same period of timeo

-139Conclusions The material of this chapter forms a preliminary investigation of the applicability of residue number systems to the arithmetic operations of digital computers. The residue system has been found attractive in terms of the operations of multiplication and addition. It is possible to realize practical logical circuitry to yield the product in the same operation time as for the sum since the product is not obtained by the usual procedure of repetitive addition. The main disadvantages of the residue number system are associated with the necessity of determining absolute magnitude. Thus the division process, the detection of an overflow and the determination of the correct sign of a subtraction operation are operations which at this stage of the investigation seem to involve considerable complexity. Nevertheless there are certainly many special purpose applications well suited to the residue code.. In particular there exists a class of control problems characterized by the absence of the need for division, the existence of a well defined range for the variables and also by the fact that the sign of the variables is known. For the problems of this class, the use of the residue code should result in a reduction of the overall computation period and give a computer with a higher bandwidth than obtainable with the conventional number system. It seems that one appropriate application of the residue code would be in the design of a concurrent or parallel digital differential analyzer.

-14oIt has been shown that the residue code with redundancy can never obtain the theoretical efficiency predicted by Shannon. The code does have the obvious advantage that an erroneous digit does not result in a propagated error. It is not unlikely that the residue code could have important applications in the field of communications. This statement is based on the fact that a sine wave may be residue encoded by phase modulation, The ultimate usefulness of the residue code will probably be determined largely by the success of the circuit designer in perfecting circuitry ideally suited for residue code operations. In this respect there is one recent development in permanent storage devices which should revolutionize some of the standard concepts of computer design. It is not unlikely that the computer of the future will consist in part of a large number of addressable permanent tables. The standard computer operations would be executed by a series of table look-ups. The designer of such a computer should give serious consideration to the use of a residue code. It appears that the combination of residue coding and permanent addressable tables obtains numerous advantages. The combination would permit arithmetic without carry and the inclusion of the redundancy needed for error detection and correction. The permanent storage tables would greatly simplify the problems associated with the determination of signs and relative magnitude and the error correcting and detecting routine.

C HAPER VI CONCLUSIONS AND RECOMMENDATIONS This thesis has dealt primarily with techniques appropriate to error checking in a computer arithmetic unit. Particular attention has been given to the logic and error structure associated with the binary adder. The conventional digital parity check has been shown to have the properties of arithmetic invariance required to check arithmetic operations. The digital parity check has been applied previously to storage and transmission systems but to the author's knowledge the check has never been applied to an arithmetic system. Previous applications of the digital parity check in computer systems have determined the parity of the result of an arithmetic operation by a means independent of the parity of the operands. A parity checking scheme which provides a check of the arithmetic operations requires cognizance of the number of generated carries. This fact is one decided disadvantage of the digital checking system. The digital parity check is not necessarily restricted to binary number systems. The digital parity check may be defined and applied to check arithmetic operations for any consistently weighted number system regardless of the base. The essential features of the digital parity check are the dependence of the check on the magnitude of the symbols of a number representation and the independence of the check on the magnitude of the weight associated with the symbols. The -141

-142definition of the digital parity check in terms of the sum of the symbols modulo b where b is the base of the number system is a much more fundamental definition than the usual definition of the digital parity check given for the binary number system. The usual definition of the digital parity check is given in terms of the oddness or the evenness of the number of ones contained in the representation. The numerical check is based on the concept of linear congruences. The check base may therefore be any number except the magnitude of the number base. The main advantage of the numerical check is that carry cognizance is not required. The check is, however, sensitive to carry malfunctions. The question of the effectiveness of the different parity checks in the detection of errors is closely related to the logical structure of the adder. A cursory examination of the problem reveals immediately that the maJor difficulty is associated with the propagation of carries in the addition process. If it were not for carry propagation it would be easy to obtain independence of the elements involved in the addition process. If the elements were independent then the simple digital parity check would be one hundred percent effective against single component malfunctions. It is possible to design arithmetic structures in which each carry element is determined independently. However a severe penalty in terms of time and equipment is associated with structures of this type. For example the carry logic normally associated with a 30 bit binary adder with non-independent carry elements consists of 29 AND gates and 29 OR gates each gate

-143having two inputs. The generation of instantaneous and independent carry elements would require 29 OR gates with 464 inputs and 435 AND gates with 4930 inputs. One example of a non instantaneous but independent carry logic requires 29 OR gates with 464 inputs and 481 AND gates with 1682 inputs. These figures illustrate the high price paid to obtain independence of the carry elements. There may exist some carry logic design in between the extremes illustrated by the examples given. In particular it should be possible to design a carry logic for which the carry elements are not completely independent but are less dependent than the carry elements of the standard carry logic. It should be possible to synthesize carry logic of this type by an extension of the vector space concepts which have been used to investigate the structure of binary addition. The extension of the vector space concepts to the problem af the synthesis of arithmetic structures has been given only brief consideration and should be an important area for future work. Vector space concepts have been found particularly appropriate for the analysis of the process of binary addition. The author found that the study of the binary addition process by means of vectors tended to clarify the problems associated with the structure of the binary adder. In particular the introduction of the carry matrix permitted a unified approach to the study of different configurations of carry logic. A natural extension of the vector space concept of measure has resulted in the specification of three new addition algorithms.

-144IThe algoritlI-oms prov'ide an inrteresting description of the addition proc e b ss b1ut dco not lad to logical circuits having any advantage over the conventional circuits. The study of the structure of the errors for a standard parallel adder has shown that the propagated errors due to single logical element malfunctions exist in only two forms The two forms are a series of zeros terminated by a one or a series of ones terminated by a zero, The form of the error sequence is due largely to the fact that the propagation of ar.n error to some element 8i+l requires that ri = 1, Error propagation is halted when some element of the? vector, rj = 0, where j > i o The probability of error propagation has been found to be a function of the type of malfunction which initiated the error. The study of the error structure of the standard adder has revealed the existence of only four different classes of error propagation probabilities corresponding to all of the possible single logical malfunctions. Thus the effectiveness of the digital parity check is a function of the type of malfunrction. A simple digital parity check consisting of only one parity chec bi t has a probability of success of 2/3, 3/4, 1/3 and 5/9 for each of the four possible error propagation probabilities. The digital check may be considerably more effective in the detection of errors of more than one parity check digit is employed. For example if t-wo digits are employed irn such a.manner that alternate digits are assoc-iated with one check bit and the other digits with the other check digit then the probabilities associated with the success of the check

-145become 14/15, 19/20, 13/15 and 41/45 respectively. The extension of the digital check to include additional check digits is not particularly fruitful since the numerical parity check has been shown to be 100% effective. Furthermore the numerical check has the advantage of not requiring carry cognizance. The figures which have been stated for the effectiveness of the various checks apply only to the results of single addition-like operations. Multiplication and division, which consist of repetitive addition, must be checked at each addition step in order to obtain the parity check effectiveness stated above. The parity effectiveness for a sequence of addition operations has not been investigated in this paper. This would be an excellent topic for future study. The numerical check is superior to the digital check for the purposes of error detection. However there are certain difficulties associated with numerical checking if error correcting properties are desired. The extension of the numerical check to include additional check digits will not provide the information needed to correct an erroneous representation unless the check representation contains all of the information of the original representation. In this case it becomes possible to carry out the arithmetic operations in terms of the check representation and the original representation may be ignored. We have called the numerical check representation for this case a residue number system. There appears to be a fundamental limitation in regard to the application of numerical checking procedures for the purposes of error correcting since the numerical check is dependent on

-146 — magnitude. For example a numerical check modulo 35 consisting of check bases 7 and 5 would provide error correction information for any error of magnitude less than 35. If the magnitude of the error is greater than or equal to 35 the correction data is ambiguous. It would seem that there exists an interesting possible combination of error detecting techniques used in conjunction with a reasonable amount of circuit duplication. The residue number system has been investigated in detail. The main advantage of the number system appears to be the complete independence of the digits of a residue representation. Addition and multiplication are both defined operations and are executed without carry between the residue digits. However, complete element independence may not be obtained within a residue digit when the digit is represented in binary code unless special logical circuitry is employed, Independent addition elements must be employed within the adder logic of a single residue digit to give complete bit by bit independence. Also if standard carry logic were employed within a residue digit the addition time while still less than that of the standard adder would not be significantly less. Multiplication in a residue code would be significantly faster than that presently achieved by standard techniques even if standard carry logic were employed within the residue digits. However, it is doubtful that the residue number system will ever be used extensively for general purpose computation due to the difficulties involved in performing the division operation. The basic difficulty

-147pertains to the determination of magnitude. The ultimate success of the residue code for general purpose computation is very much contingent upon the development of special components suitable to the residue code. At the present time the most probable application of the residue code is in the realm of special purpose computation. The residue code is unique in the sense that the residue digits are independent. Furthermore, the code may obtain error correcting capabilities simply by the addition of more residue digits providing of course that the base of the added digits is relatively prime to the bases of the other digits. The error correcting routine required by the residue code is moderately complicated when considered in terms of equipment. The success of the residue code as a means of error correction is dependent on the development of components suited to the properties of the residue code. It appears that the control of computation errors due to circuit malfunctions may be obtained by means of error detecting and correcting codes which are arithmetically invariant. In this thesis the simple digital parity check and the numerical parity check have been considered in detail. While the numerical check is very effective in error detection it is not particularly suited for error correction in a general computing system. It is suggested that perhaps the most effective control of errors is to be obtained by the use of a hybrid system employing both component redundancy and error coding.

APPENDIX SIGN AND OVERFLOW CONVENTION FOR ONE'S AND TWO'S COMPLEMENT ARITHMETIC The following material is a detailed description of one possible sign and overflow convention for binary arithmetic. The material is pertinent to the discussion of the form of errors which occur in the process of binary addition. This subject was discussed in Chapters V We consider here the ad.dition and the subtraction processes for both ones complement and twoas complement arithmetice It is conventional to speak of a binary representation to the left of the radix point as consisting of n digits plus a signo In this case the sign would be the nth plus one digit and the last digit or element of the carry vector would be the nth plus two digit. However, the convention adopted in Chapter III is somewhat different than this. The convention of Chapter III will be used in the remaining discussion. In this convention the number including sign is represented by n digits or elements to the left of the radix point and m digits to the right of the radix pointo For two's complement arithmetic the complement representation of a negative number -A is defined by the following relationship A' = 2n -A where lAl<2n-1 In twos Complement arithmetic zero is represented as a positive entity. The largest negative number is _2n-l and is represented by 2n-l in the two's complement representation0 The largest positive number representable by the n+m elements is 2n-1 -2mo We now proceed to examine -4l8

-149the results of the addition process for four different augend, addend combinations. Consider first the case where both the augend and addend are positive. The resulting sum must also be positive. Therefore, any sum which carries to the nth element constitutes an overflow of the representation. It is readily verified that every sum of two positive operands which overflows will cause a one to appear in the nth element of the sum. The smallest overflow is 2n-1 while the largest overflow obtained by the addition of the two largest positive numbers representable by n digits is 2n -2-m+l. Both of these overflow sums contain a one in the nth digit place. We consider next the addition of a positive and a negative operand. In regard to the overflow problem there is no difficulty since an overflow is not possible. An important question is whether the last carry element may assume a value of unity. The last carry element corresponds to the nth + 1 element of the sum. It is obvious that if the resulting sum is negative then the nth + 1 element cannot equal zero for the nth element of the sum is a one and rn equals one and cn must equal zero. It is therefore, impossible for cn+l to equal unity. On the other hand if the resulting sum is positive it is possible for the cn+l digits to have a value of unity. Normally in twos complement arithmetic this digit is ignored. The positive sum obtained by the addition of a pair of positive and negative operands extends over a range defined by the addition of the largest positive

-150number and, in absolute magnitude, the smallest negative number to the number zero. Zero is obtained by the addition of a positive number and a negative number identical in absolute magnitude. 2n R < 2n + 2n-1 - 2-m It is observed that the nth + 1 element is always a one over the range of the positive sum. Furthermore, the nth element has a value of zero. The last case is the addition of two negative operands. In this case the nth element of both operands has a value of unity And hence, the nth + 1 element of the sum and the carry vector will always be unity. The investigation here concerns the behavior of the nth digit. The sum of two negative operands can overflow. We consider first the range of the non overflow sum obtained by the addition of the two smallest negative numbers (absolute magnitude) and the sum of any two negative numbers which produces the largest (absolute magnitude) negative number which can be represented. This range is given as 2n-14 R < 2n - 2-m If the sum of the two negative operands overflows the result must lie in the range specified by the sum of the two negative numbers largest in absolute magnitude and the sum of the largest negative number in absolute magnitude and minus one. 2n 0 < 2n + 2n-1 - 2 It is observed that if no overflow occurs the nth digit of the sum is correct. The sum is negative and the nth digit is a one. If an overflow occurs the nth digit becomes a zero which is the incorrect sign. The nth + 1 digit is a one for both situations.

-151In oneds complement arithmetic the minimum negative number in absolute magnitude is zero given as 2n - 2-m. The magnitude of the largest negative number is 2n-1 - 2-m and is represented as 2n - 2n-1 The largest and smallest positive numbers are 2n-1 - 2-mand 2-m. The overflow representation, due to the addition of two positive numbers, lies in the range 2n-l 0 _ 2n _ 2-m+l The overflow does not affect the n+l digit but does produce a one in the nth digit. The overflow is detected by the erroneous sign. The normal addition of two positive operands produces a sum in the range 2-m+l < R < 2n-1 -m The addition of two negative numbers always requires an end around carry correction. Before correction the range of the correct sum and the overflow sum are n- m <n+l n- 2-m+l 2 -2 2 -m (2 2 2n+l - 2n < o <2n+l - 2n-l 2-m+l Before correction the overflow representation and the normal representation will always have a one value for the correction digit. The sign digit for the correct representation is either a zero or a one. The sign digit of the overflow representation is always zero. After correction the overflow and normal range of the sum is 2n+l - 2n-1 R < 2n+l _ 2-m 2n+l - 2n + 2-m < o < 2n+l - 2n- - 2-m After correction the correction digit remains a one for both the normal and the overflow representation. The sign digit for the normal sum is

-152a one while the sign for the overflow representation is a zero which is incorrect. The addition of a positive and a negative operand can never produce an overflow but the sum may be either positive or negative. If the sum is positive an end around correction is required. This is verified by S = A + B where IAI > B I = 2n B- 2m + A A_ 2n-1 2-m 2n S 2n + 2n-l - 2-m+l Thus an end around correction is always required for a positive sum and the sign is correct both before and after the correction. After correction the representation is in the range. 2n + 2-m <_ S < 2n + 2n-n _ 2-m The negative sum is obtained for S = A + B,::f IAI IBI 2n-1 < S - 2n - 2-m The negative sum obtained has a zero value for the correction digit and a one value for the sign digit. End around carry correction is not required.

BIBLIOGRAPHY 1. Babbage, H., Calculating Engines, E. and F. N. Spon Co., London, Eng.; 1889. 2. Goldstine, A., Goldstine, H. H., "The Electronic Numerical Integrator (ENIAC)," Mathematical Tables and Other Aids to Computation, Vol. 1, pp. 97-110; July, 1946. 3. Von Neumann, J., "Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components," Automata Studies, Edited by Shannon C. E. and McCarthy, J., Princeton University Press, 1956, pp. 43-98. 4. Shannon, C. E., Weaver, W,, The Mathematical Theory of Communications, University of Illinois Press, Urbana, Ill., 1949,pp. 44-48. 5. Hamming, R. W., "Error Detecting and Correcting Codes," The Bell Telephone System Technical Journal, Vol. XXVI, No. 2, pp. 147-160, April, 1950. 6. Golay, M. J. E., "Notes on Digital Coding," Proceedings of the I.R.E., Vol. XXXVII, No. 6, p. 657, June, 1949. 7. Ulrich, W., "Non Binary Error Correcting Codes," The Bell Telephone System Technical Journal, Vol. XXXVI, No. 6, pp. 1341-1387, Nov., 1957. 8. Reed, I. S., "A Class of Multiple Error Correcting Codes and the Decoding Scheme," Transactions of the 1954 Symposium on Information Theory, I.R.E. Professional Group on Information Theory, pp. 38-49, Sept., 1954. 9. Golay, M. J. E., "Binary Coding," Transactions of the 1954 Symposium on Information Theory, I.R.E. Professional Group on Information Theory, pp. 23-28, Sept., 1954. 10. Robertson, J. E., "Error Detection and Correction in Binary Parallel Digital Computers," Electronic Digital Computer, Internal Report No. 37, University of Illinois Digital Computer Laboratory, pp. 70-81, 1952. 11. Block, R. M., Cambell, R. V. D., Ellis, M., "The Logical Design of the Raytheon Computer, Mathematical Tables and Aids to Computation, Vol. III, No. 24, pp. 256-296, 317-323, Oct., 19k4. 12. Block, R., Patent #2,634,052. -153

BIBLIOGRAPHY (CONT'D) 13. Hardy, G. H o. Wright, E. M., An Introduction to the Theory of Numbers, Oxford University Press, London, England, 1956. 14. Birkhoff and MacLane, A Suvey of Modern Algebra, Macmillan Co,, New York, No YO, 1948. 15. Brillouin, L., Les Tensuers en Mecanique et en Elasticite, Chapter VI, Dover Publications, New York, N. Yo, 1946. 16. Weinberger and Smith, "One Microsecond Adder Using One Megacycle Circuitry," I.oR.E Transactions on Electronic Computers, Vol. EC-2, No0 2, Juune, 1956. 17. Burks, A, W., Goldstine, H. Ho, Von Neumann, J., "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" Part 1, Vol. 1, pp. 10-11, Princeton: Institute for Advanced Study, 1947, Second Edition. 18. Gilcrist, B., Pomerene, J. H,, Wong, S. Y., "Fast Carry Logic for Digital Computers," Transaction of I.oRE Professional Group on Electronic Computers, Vol. EC-4, No. 4, December, 1955. 1.9o Iants, A. G. "The Application of Boolean Matrix Algebra to the Analysis and Synthesis of Relay Contact Networks, Doklady Akademii Nank SSSR 70, ppo 421-23, 1950. 20. Leonrard, E o D., Modern Elementary Theory of Numbers, p. 19, University of Chicago Press, Chicago, Ill., 1939. 21, Csalga0, J. 0*, "The Synthesis and Analysis of Digital Systems by Boolean Matrices," Transactions of the I.R.E. Professional Group on Electronic Computers, Vol. EC-3, No. 3, pp. 6-11; September, 1954. 22. Muller, D.E,, "Application of Boolean Algebra to Switching Circuit Design and to Error Detection," Transactions of the I.R.E. Professional Group on Electronic Computers, Vo EC-3, N pp' 6-11' Sept., 1954. UNIVERSITY OF MICHIGAN I1I IIIIIII I 1111111lllll III II1I 1 I 3 9015 02826 0852 -154