THE UNIVERSITY OF MICHIGAN THE GENERAL PROPERTIES OF FINITE WEIGHTED NUMBER SYSTEMS Thammavarapu R. N. Rao A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan Department of Electrical Engineering 1963 IP-654

Doctoral Committee: Professor Harvey L. Garner, Chairman Professor William M. Brown Associate Professor Bernard A. Galler Assistant Professor John H. Holland Professor Norman R. Scott ii

ACKNOWLEDGEMENTS I wish to acknowledge my indebtedness and gratitude to Professor Harvey L. Garner, whose patient guidance and interest resulted in many improvements in a number of areas and made this work possible. I thank all the members of the doctoral committee for the discussions, and the useful criticisms and corrections of the manuscript. I also wish to thank Dr. R. F. Arnold for the many stimulating discussions in the area of modules and the structure of non-redundant weighted systems. The stimulating environment of the Information Systems laboratory and the discussions with its members R. Gonzalez, P. Dauber, T. F. Piatkowski have made an important contribution to this effort. Last but not the least, I thank my wife Rajyalaxmi, for her patience and understanding during the course of this work. This dissertation was supported by the United States Air Force under Contract AF-33-657-7811. iii

TABLE OF CONTENTS Page ACKNOWLEDGEMENTS.... i.......i................,,....,.... iii LIST OF TABLES......................................... vi NOMEN.CLATURE............ooo......,.......................... vii I INTRODUCTION AND BACKGROUND.,D....,,.....,............. 1 1.1 Consistently Based and Mixed Based Number Systems.... 1 1.2 p-matrix or Weight Matrix..........,............ 2 1.3 Finite Non-redundant Number System Weights...,.... 3 1.4 Relation Between Digit Weights and Triangular Forms,, 4 II FINITE NUMBER SYSTEMS: LINEAR AND NON-LINEAR CATEGORIES... 6 2.1 A Finite Number System.,.,.,.,,,,.,,,,,,,,... 6 2.2 Fundamental Definition of Linearity................. 7 2.3 Non-weighted Codes,,...,,. 9,,,,...,,....,,..,.o 8 2.4 Digitwise Sum...,.,,,...,,,,,,,,,,,,,,e,, 11 III THEORY OF MODULES OVER INTEGERS,....,.......,.........,., 16 3.1 Algebraic Preliminaries...................... 16 3.2 The Number Systems as a Quotient Module,,......*,... 22 IV NON-REDUNDANT WEIGHTED SYSTEMS...................,...... 25 4.1 Some Useful Theorems on Determinants..~..~o,,...,,,. 25 4.2 Triangularity of the Carry Matrix of Non-redundant Weighted Number Systems....*........................ 36 4.3 Examples of Quotient Module Structure..,......,.....39 V GENERAL WEIGHTED SYSTEM STRUCTURE AND CANONICAL TRANSFORMATIONS.......................................o... 43 5.1 Brief Introduction....,....,....,............. 43 5.2 Condition on the Determinant of the Carry Matrix.,.,, 46 5.3 Canonical Forms and Transformations............. 47 5.4 Some Examples of Redundant Systems and Their Canonical Forms..........................,. 49 VI REDUNDANCY IN RESIDUE NUMBER SYSTEMS.....,..,....,....... 57 6.1 Introduction and Results..,..*.................,..... 57 6.2 Necessary and Sufficient Conditions on the Digit Weights of a Residue System*........,.......,..,..... 57 iv

TABLE OF CONTENTS (CONT'D) Page 6,3 Number-of-Acceptable Sets-of Digit Weights of a Residue System with Moduli that are not Relatively Prime, 0..0................ o a e. 0... o.. 60 6.4 Condition on the Range M of a Residue System,......, 65 VII ERROR CHECKING IN RESIDUE ARITHMETIC.........,......,.. 74 7.1 Introduction....e. O,.,,,.....,,. o o e. 74 7.2 Residue Representation..,.....4,,, 0........ 74 7.3 Pairwise Relatively Prime Moduli....,.,..... 4,.,. 75 7.4 Moduli that are not Pairwise Relatively Prime: Error Checking......... 9............. *,.......**e*. 79 7.5 Binary Coded Residue Systems............,.... 80 7.6 An + B Type Coding of Residues........... 84 7.7 Suitable Moduli for Residue Computation............,. 86 VIII CONCLUSION................................ 88 8.1 Review of Results and Conclusion.....,......,..... 88 APPENDIX......*....,..................... 90 BIBLIOGRAPHY................................................... 92 v

LIST OF TABLES Table Page I Representations for Codes N1 and N2.....,... o..,.. 9 II (kxk) Determinent Dk, with Triangular (k-1 x k-l) Minor..4 00 o a... o a.......... *. 34!! III Digitweights and Corresponding Values of m, m2, m3..... 0... 0....*................ 71 vi

NOMENCLATURE Z ring of integers ZM integers modulo M IXIM least non-negative residue of x modulo M Ixi absolute value of x asE^~ ea is an element of 5 a4t a is not an element of 5 3 such that CCK C is a subset of K ~/C If C is a subgroup of i, 5/C is a quotient group A B A and B are isomorphic bV x~e for any x in 5'3 xc- there exists an x in e K=-{xEx l(x)=o} K is the totality of elements in i, which are mapped by 0 to 0 -0:S —ZM 0 is a mapping of 5 into or onto ZM <ml, m2,.., mn> least common multiple of the integers m m, m...,mn (ml, m2,..., nn) greatest common divisor of the integers ml, m2,...,mn xly x divides y ~<=:> ~ if and only if xty x does not divide y x Ix -XY] ~ the greatest integer less than or equal to [Y_ y C1.' Cln matrix (cij) determinent C Cnl * ~ Cnn vii

I. INTRODUCTION AND BACKGROUND 1.1 Consistently Based and Mixed Based Number Systems A finite number system is a set of n-tuples of integers. These elements of the n-tuples are called the digits and they correspond to the n-moduli of the system. The term modulus as used in this dissertation refers to the cardinality of the digit set. The cardinality of the number n system with moduli ml, m2,..., mn is equal to IN mi. If there is a i=l mapping of this system onto the integers 0, 1, 2,..., M-1 (denoted hereafter as ZM ), then the system is said to represent ZM, and M is said to be the range of the system. Clearly the range M must be less than or n equal to i mi, in order that all integers in ZM may have a representai=l tion in the system. Such systems are said to be complete. For a consistently based system, since ml = m2 =... = mn = r, the range M is equal to rn. If the digit weights P!i, P2' *', Pn are such that pi = ri- then the system can represent ZM for M = rn nonredundantly. This is not the only possible set of digit weights, but it is the set normally encountered in practice. In contrast, a residue number system must have moduli mi, m2,..., mn that are pairwise relatively prime in order that the system can have a range n M = I mi. The residue number systems are classified as weighted, since i=l weights pi, p2,..., pn can be attached to the corresponding moduli in such a way that (x1, x2,..., xn) represents an integer xeZM if and only if x = I= xi x i (1.1) i= M -1 -

-2Since 1EZM must have a representation of the form (c1, c2,.., Cn), CieZmi in the system, ciPi M = 1, which implies (P1, P2..., Pn' M) = 1. This is a necessary condition for all weighted systems. If 1EZM has a representation (1, 1,..., ) as in the system of residue classes iZ P = 1, then any xeZM is represented by i=l M i M (x1, x2,.'", Xn), (1.2) where xi = |x| 1''mi 1.2 p-Matrix or Weight Matrix (3) Rozenberg, in his work on the "Algebraic Properties of Residue Number Systems," has shown that the residue system is a pseudo-vector space or an R-space, since the system obeys the axioms of a vector space except for the uniqueness of representation with respect to the generator elements. Also the scalars here are integers instead of field elements as required for a vector space. For a weighted system with moduli mli m2 n.., mn which are pairwise relatively prime, and Pi, p2, P,, pn the corresponding weights, the nxn array or matrix of the form Pll P12. Pin P22 P22 ~ ~ P2n Pnl Pn2 nn where pi = p| P, is called the p-matrix or weight matrix. It is shown that Jp l

-3the row elements of the p-matrix are the generators of the weighted system and also span the R-space. In a non-redundant system of residue classes, (or in the residue system in which (, 1,... 1) represents 1),. we have Pij = 1, i = j =0, i 4j, and the p-matrix is an Identity Matrix. For a general residue system, the p-matrix is diagonal with the diagonal element satisfying (Pii, mi) = 1. It is shown in Rozenberg's paper that a sufficient condition for a non-redundant system is that the p-matrix be triangular (or can be made triangular by row and column permutation) and the diagonal elements satisfy (Pii, mi) = 1, for i = 1, 2,..., n o However, the necessary condition was not established. Such systems with triangular forms are residue related systems. An important one in that category is a mixed base system with conventional carry propogation. 1.3 Finite, Non-redundant Number System Weights For a general non-redundant weighted system using any set of n moduli, the necessary and sufficient conditions are given by Garner's theorem(6). These conditions are (pl, M), ml (P ^ "ml = -';> (1.3) and (Pmn) m 1 (, and (Pn'mn) = 1,

-4for some ordering of the moduli ml, m2,..., mn Using these conditions for a special case of pairwise relatively prime moduli, it is shown that the p-matrix is triangular, and (pii,mi) = 1. Unfortunately, the p-matrix cannot be constructed similarly when the moduli are not relatively prime. 1.4 Relation Between Digit Weights and Triangular Forms For a system with any set of n moduli, the structure could be expressed by the relations between the digit weights pi, P2,..., p and the range M * There exist n independent relations between the variables Pi' P29''' Pn and M. This set of relations gives rise to the rules for carry generation. As an example, consider a consistently based system, i-l having all mi = r and weights Pi, P2,..., Pn where Pi = r. This system has the n independent relations as below. r 0 0.. o P 0 -1 r 0... 0 Pn 0 0 -1 r,. 0;~~~[ | | | -| |(mod M = rn) O 0 0 0..-1 1 r 0 The (nxn) matrix above gives the carry propagation rules, and is called the carry matrix. For a residue system with moduli mi, m2Q,... mn, the relations are given by

-5m1 0 0....0 1 0 m2 0....0 0 0 0 m3..... (mod M). O O O e e P m 0 0 0... m p 0 n n Since there are no carries between digits, the (nxn) carry matrix above is appropriately diagonal. The triangular form of carry matrix is the crucial property of non-redundant systems. Triangularity means that the carries are propagated in one direction, and an ordering on the moduli is possible. Also, the termination of carries is guaranteed once they are propagated up to the highest ordered digit. In contrast, the carry matrices of redundant systems need not be triangular and thus a more elaborate arithmetic process is expected. Another complication associated with redundant number systems is the tranformation of equivalent representations to the preferred representation. This is the canonical reduction problem.

II. FINITE NUMBER SYSTEMS: LINEAR AND NON-LINEAR CATEGORIES 2.1 A Finite Number System Here we define the concept of a number system which heretofore has been left to the intuition of the reader. A number system could well be considered as a method of representing or assigning names to the integers. Let a system N, be a cartesian product of n digit sets. N = D1 x D2 x.. x Dn where Di = { 1, 1,..., mi-l} and is called the i-th digit set and m. the i-th modulus. Then N will be called a number system if 1) N is closed under addition: x, yeN > x + yeN (closure law) 2) 3 OeN such that x + 0 = 0 + x = x (identity). It will be proved later that, in addition to the above two, the other axioms of an abelian group are obeyed by non-redundant linear number systems. 3) 3 a mapping w: N - ZM and w is a function of the n variables, such that w(x+y) = w(x) + w(y) (mod M) for all x, yeN This function, which we will call hereafter the weight function, is the most significant property of the number system and is the major factor determining the arithmetic and carry properties of N. We will observe -6

further that the division of number systems into different categories is based on this function. The following definitions,* which are quite familiar, are included as a basis for further discussion on number systems. Definition 1. A number system N (obeying the three axioms stated above) is complete > w is onto ZM. This is to say that for all aZM, 3 x eN such that w(x) = a n Also M > rnmi4=4> N is incomplete. Definition 2. N is a redundant system 4 —x,yeN such that x $ y and w(x) = w(y) The above two definitions can be combined to obtain the lemma: Lemma 1. A number system is complete and non-redundant - w is an isomorphism. This lemma permits the seperation of number systems into redundant and non-redundant tyres. 2.2 Fundamental Definition of Linearity Definition 3. N is said to be a linear system if and only if w is a linear function of n variables, the coefficients coming from ZM Definition 4. A number system N is weighted 4> 3 PiCZM for i = 1, 2,, n such that for any x = (x1,..o, xn)eN n w(x) = 1 Pixi The weight function for weighted systems is a linear M homogeneous function. Thus all the weighted systems are linear. However, not all linear systems are weighted. The two examples is Section 2.3 illustrate the above statement. Definitionsl, 2, and 4 are made by Garner in his earlier work.(6)

-82.3 Non-weighted Codes Before we go into the advantages of weighted and non-weighted systems, we shall examine the weight functions w of some non-weighted codes. Given below is a table of representation of the code known as excess three representing Zl(N1 - Z10), and the four-bit reflected binary code for Z16(N2 - Z16) 0 It is well known that the excess three code has the advantage over the binary coded decimal system (which is linear homogeneous) in that the 9's complement is obtained by interchanging O's and l's, The advantage of the reflected binary code is that it is a unit distance code. Thus any single digit error causes a change of one in magnitude. We shall show that the weight function of the excess three code is linear and non-homogeneous, and that of the reflected binary code is non-linear. Let N1 and N2 be two non-redundant number systems representing Z10 and Z16 respectively. Let the weight functions N1 - Zl and N2 - Z16 be defined as shown in Table I. Both of these mappings are (1-1) and onto, and hence for all X, YeN, we have X + Y = [w(Y) + w(X)o This shows closure under addition. The existence of an identity element is obvious. We can easily find that the weight function for the excess three code is such that for

-9TABLE I REPRESENTATIONS FOR CODES N1 AND N2 Excess Three Code N1 Four-bit Reflected Binary Code N2 Z10 X4 X3 2 x1 1 Z16 X4 X3 x2 X1 0 0 0 1 1 0 0 0 0 1 0 1 0 O1 0 0 1 2 0 1 0 1 2 0 0 1 1 3 o 1 1 o; 3 o o 1 o 4 o 1 1 1 4 o 1 1 o 5 1 0 0 oo 5 0 1 1 1 6 1 0 0 1 0 1 o 1 7 1 o 1 o 7 0 1 o o 8 1 o 1 1 8 1 1 o o 9 1 1 0 0 9 1 1 o 1o 11 0 1 1 1 o 12 1 1 1 13' 1 0 1 1 14 1 0 0 1 15 i1 0 0o

-10X = (X1, X.2, X3, X4) w(X) = 23X + 22X + 2X3 + X - 3, where the coefficients 23, 22, 2, 1, M - 3 are in ZM. Thus w is a non-homogeneous linear function on the variables X4,..., X1. However, for the reflected binary code, the function w is not so straightforward to obtain. From Table I we have that w(O, O, 0, 0) = 0, w(O, O, 0, 1) = 1 = p, w(O, O, 1, 0) = 5 = 2, w(O, 1, 0, 0) = 7 = P, w(l, 0, 0, 0) = 15 = p4. For an n-bit code w(0, 0,..., 0,,,...o) = 2i -1 = ith place. Next we denote the weight function for the n-bit reflected binary code as f. Taking note of the alternate negation in the weights of the digits in the positions where 1's are present, we can write as below: In the case of a 1-bit code fl = w(X1) = PlX = X1, and for a 2-bit code f2 = w(X2, X1) = X2p2 + X1Pl - 2X2XlPl = X2 + (1 - 2X2)fl.

-11For a 3-bit code f3 = w(X3, X2, X) = X3P3+ X2p2 + X1p1 - 2X3X2p2 -2X2Xpl - 2X3Xlp+ 4x3X2X1p1 = X p + (1 - 2X3) (X2p2 + (1 - 2X2)X1pl) = X3P3 + (1 - 2X3)f2 Then f4 = w(X..., X1) = X4p4 + (1 - 2X4)f3 and fn = W(Xn, **' X ) = Xnn + (1 - 2Xn)fn-_ XnPn + (1 - 2Xn)XnlPn-1 + (1 - 2Xn)Xn-2Pn-2 + p. e.. + (1 - 2Xn)(1 - 2Xn_)... (1 - 2X2)Xlpl (2.1) which is clearly a non-linear function of order n 2.4 Digitwise Sum In a non-redundant system (w is a (1-1) mapping), the addition in N is defined by w, This is because w(X + Y) = Iw(X) + w(Y) IM for all X, YeN (X + Y) = w-1 [Iw(X) + w(Y) IM] -1 and w is (1-1) and, Z is an additive abelian group, so is N M

-12An important property of all linear homogenous systems is that for all X, YeN w(X+Y) = w(xl + Y1l x2 + Y2, o o, Xn + Yn) (2.2) This is trivial if xi + Yi < mi for all i = 1,..., n. In which case X + Y = (X1 + Yl, x2 + y2'...J Xn + Yn)eN. But when for any i, x + Yi mi, then (x1 + Y1' *''' Xn + Yn),N. However, (2.2) still holds. w(X) = Ixp1 + X2P2 +... + XnPn w(y) = ylPl y + y2p2 + Y + nnM w(X+Y)= w(X) + w(Y) = |(x1 + y1) P1 +..* + (Xn + Yn)PnlM = w(xl + Y1,..', xi + Yi,..', Xn + Yn) ~ Conversely let w(xl, x2,..., Xn) + w(yl Y2,', Y ) = w(xl + Y1', *. Xn + Yn) Then replacing yi = 0 for i = 1, 2,.. n we get w(xl, x2,..,, Xn) + w(0, 0,..., 0) = w(x1 + 0,.o., Xn + 0) = w(xl, x2,.'., xn) ~ Therefore, w(0, 0,..., 0) = 0,

-13Also for any integer a e ZM w(ax1, ax2,..., axn) = w(x1, x,..., xn) +... + w(xl, x2... xn) a times = aw(xl, x2,..., xn) Let w(O, 0,..., xi, o., 0) = fi(xi), then fi is a homogeneous function on xi. Since w(O,..., xi + Yi, *.., 0) = fi(xi) + fi(Yi), fi is a linear homogeneous function on xi. w(xl, x2,..., xn) = w(xl1 0,..., 0) + w(0, x2, x3,..., xn) = w(xl, 0,..., 0) + w(o, x2, 0,..., 0) + w(0, 0, x3,..., xn) =w(xl, 0,..., 0) + w(0, x2, 0,..., 0) +... + x(0,..., xn) n -= fi(xi), i=l1 Where fi is a linear homogeneous function of xi, for i = 1, 2,,.,, n Therefore w is a linear homogeneous function on n variables X1 X2... Xn. Thus we have proved the following:

-14Theorem 1. N is a linear homogeneous system with a mapping w:N -4 Z if M and only if w satisfies the digitwise sum rule given by (2.2). In the excess three code N1, which is non-homogeneous X = (x4, x3, x2, x1) Y = (y4' y3 Y2, Y1) w(X) = 8x4 + 4x3 + 2x2 + xl - 3 w(Y) = 8y4 + 4y3 + 2y2 + Y1 - 3 w(X+Y) = w(X) + w(Y) = 8(x4+y4) + 4(x3+y3) + 2(x2+y2) + (x+yl) -3 - = w(x + y4 x3 + yY, x2 + Y2' x1 + Y1) - 3. Thus w(X+Y) / w(x4 + y4, x3 + Y3, x2 + y2, xl + y1) ~ In the reflected two-bit binary code (N2 - Z4) X = (x2 x1) Y = (Y2, Yl) w(X) = 5x2 + x - 2x2x1 w(Y) 5y2 + Y1 - 2Y2Y1 ( wX+Y) = w(X) + w(Y) = 5(x2 + Y) + (x2+Yl) - 2(x2xl+y2yl) ~ w(x2 + y2, x1 + yl) In linear homogeneous systems, we proved that digitwise addition can be carried out. If any digit sum is > the corresponding modulus, then the result is not in the number system. Conventionally this is taken

-15care of by carry generation and assimilation. For a general weighted number system, the carry generation and assimilation process is characterized later by using the theory of modules.

III, THEORY OF MODULES OVER INTEGERS In this chapter the concepts of free module, submodule and quotient module are presented. The theorems of module theory relevant and necessary for our study of weighted number systems, are stated here. In Section 3.2, similarities are examined between the structures of a non-redundant weighted system N, and a quotient module S/S over integers. This leads to the concept that the quotient module t/S, where the submodule S of 5 is constructed from the carry generation rules of N, stands as an abstract model for N 3.1 Algebraic Preliminaries Let Z be the set of all integers. Algebraically, Z satisfies the axioms of a ring, integral domain and also an Euclidian domain. Let t be n tuples of integers of the form (x1, x2,..,, xn), xieZ. Let addition in { be defined as follows: x = (x1, x2,..., Xn) y = (Yl' Y2''', Yn) x+y = (X1 + Yl, x2 + Y2'..., Xn + Yn) Let scalar multiplication of xc~ by any integer aeZ be defined as a(x1 x2,..., xn) = (ax, ax2,..., ax n) If 5 satisfies the axioms of an abelian group (the axioms Al to A5) with respect to addition, and the mapping of Z x - -, called scalar multiplication obeys the axioms M1 to M4 and Gl, then t is called a module over Z, or a Z-module, -16

-17(Al) x + yce (A2) x + (y+w) = (x+y) + w (A3) x + y = y + x for all x, y, wEg (A4) 3 O0e such that x + O = x (A5) 3 x'eg such that x + x'= 0 (Ml) a(bx) = ab(x) (M2) a(x + y) = ax + ay for all x, y~( and a,bcZ (M3) (a + b)x = ax + bx (M4) lx = x (Gl) There exists a set {el,. e,..., e; ei such that for any weg E there exist integers wl, w2,..., wn n such that w = Z Wiei * The set {e1, e2,.., en} is icalled the generator set. In connection with the above axioms Al to A5, M1 to M4, and Gl, it must be pointed out that (1) a module need not necessarily be defined over integers. A general definition of a module can be over any ring with an identity. And (2) a module is a generalization of a vector space in that (i) a vector space is defined over a division ring and more often over a field, and (ii) a module may not have a basis. If a module has a basis, then it is called a free module. For a module to have a basis, the axiom Gl must be replaced by a strengthened form, G2 (G2) There exist a set {el, e2,..., en} ei~e such that for any weg can be written in one and(Cony one way in the form Wlel + w2e2 +... + wnen for some wieZ.

-18It is now possible to observe that t as defined above is a free module having a basis {el, e2,..., e}, where e. = (0, 0,..., 0, 1,,..., 0). i —th place for all i= 1,2,..., n. Definition 5. If C is a subgroup of ~ and for all sEC, aeZ _ asEC, then C is said to be a submodule, From the above definition, the totality {x} of multiples ax of the fixed element x in 5 and for all aeZ is a submodule generated by x. Also, C = {cl, c2,..., ck} is the submodule generated by the set c1, c2,..., ck, ci~~. For all xeC x = Z aici for some aiEZ (4) In this connection, awell-known - theorem stated and proved in standard textbooks of modern algebra will be stated as follows. Theorem 2. If t is a free Z-module with a basis of n elements, then any submodule C of i is also free and has a basis of m < n elements. Definition 6, is a free Z-module and if C is a submodule, then the quotient group t/C satisfies the axioms of a module over Z. Thus, //C is a Z-module, called the quotient module or difference module. The following notation will be used hereafter for the modules i, C and /C: (1) 5 = Z x Z x... x Z n terms and the basis {eI, e2,..., en} ei = (,.., 1,... 0) i-th place

-19(2) A submodule C with k generators cl, c2,..., ck, ci~q is written as C = {cl, c2,..., Ck) where n ci = cije i = 1, 2,., k (3.1) and written as (cil, ci2,... cin) with respect to the basis (el, e2,..., en). Hence, the submodule C can be written as a (k x n) matrix cil c. c Cll o.. Cln C = {c1, c2,..., ck}= (3.2) Ckl " ckn (3) //C is denoted as cil ~ *. Cln / ccl Z + Z +... + Z kl.' ckn Any (kxn) matrix over integers represents a submodule generated by the k rows of that matrix, and each of the rows are an element of the module' with respect to the basis {el, e2, o.., en} If {fl, f2, ~.' fn} is another basis in t such that n ei = t ifj for i=l,2,.,n (3.3) j=l'33 the right multiplication of C by the (nxn) matrix i gives C' with respect to the new basis (fl f2,.,. fn) of.

-20By considering the change of basis from (f, f2,'' fn) to (el, e2,..., en), another (nxn) matrix p' can be obtained such that 1' = identity matrix. Thus, t and A' are both invertible and so must have determinant = + 1. Similarly, it can be shown that a change of basis of the submodule can be effected by a left multiplication of C by a (kxk) invertible matrix. We still have the same submodule but the basis for representation of the submodule is different. Also, the row representation is altered by a new basis of ~. Hence we may state the following. Theorem 3. If C is a (kxn) matrix over integers representing a submodule of, then C' = uCv also represents the same submodule with respect to a different basis in ~ where u is a (kxk) and v an (nxn) invertible matrices over Z. By definition we shall use the term equivalence for (kxn) matrices if there exists u, v as defined above such that C' = uCv. If C is an (nxp) matrix, then the absolute values of determinants C and C' are equal, since the invertible matrices have determinants equal to + 1. Also we need the following important theorem. Theorem 4. If C is a (kxn) matrix with elements in Z, there exists a matrix C' equivalent to C which has the diagonal form as below,

-21a1 0 0 0 a2. 0 0 ar 0 0 C = 0 0 0 0 0 0 O 0 r < k < n ai + 0 and ai divides aj for i < j and r is the row rank of submodule. (This is a theorem in Jacobson, Vol. 2, Chapter 3, p.79.)( The row rank of a matrix coincides with the number of basis elements of the submodule represented by that matrix. If r = k = n then Idet C| = Idet C'I = i ai Let E be a Z-module with a basis {el, e2,..., en}, and C be a submodule with a basis of n elements c, c2, o.o c where Ci = (Cil, Ci2, **' Cin) with respect to (el, e2,..., en). That is n Ci = Z cijej i = 2,., n o j=l Then C is an (nxn) matrix. The diagonal equivalent matrix C' of the Theorem 4 will be of the form a1 0.. 0 c1 = O 2 0 a2 0 C0 O O. an

-22Then //C' in this form can be recognized as a group with cardinality equal to |al a2... an. Since C is the same submodule as C' except that the representation is with respect to a new basis, the cardinality of //C is also equal to lal a2.oo an! = |det C. Hence we proved the following theorem. Theorem 5. Let 6 be a Z-module of basis {el, e2,..., en} and C be a submodule with a basis {c1, c2,..., c n where n Ci = cijej for i = 1, 2,.., n such that C can be represented as an (nxn) matrix. Then the cardinality of the S/C module is equal to the absolute value of the determinant C. 3.2 The Number System as a Quotient Module Let N be a non-redundant weighted system with moduli mi, m2,.., mn and the corresponding digit weights Pl} P2,''' n p Then N = D1 x D2 x oo x Dn where Di= {o, 1, 2,..., ml} n and the cardinality of N =iL mi. Also (xl, x2,.., xn) represents n 1 li. xiPiIM in ZM Let the digit weights be related by the following equations or congruences.

-23ml1 i c12P2 + 13P3 +. *. + ClnPn m2p2 - C21P1 + c23P3 + *' + C2nPn — "2 P2~~~. c l+23(Mod M) (3.4) a a * mnPn - CnlP1 + Cn2P2 + Cn3P3 +'+Cnn-lPn-l+ The form of the above equations is justifiable from the following. Since the system N is closed under addition, the sum of any two elements of N, having a digitwise sum equal to (0, 0,..., m,..., O), must have an equivalent canonical form in N. Let this be (il, ci2,..., in) Then 0 < cij < m. Also if cii 0, then (0, 0,..., mi-cii..., 0) and (Cil, ci2,..., 0,..., in) are equal. Since N is non-redundant, this is contradictory. Therefore, cii = 0. Hence we can rewrite (3.4) in the form below. ml -c12.' -Cn 0 -C21 m2. -cn P2 0.. (mod M) (3.5) for 0 < cij < mj - nl -Cn2 m n 0 The (nxn) matrix in the above form will be called the carry propagation matrix, or simply, the carry matrix of the system N. It will be shown below that the carry matrix is identical with the submodule S, such that it is possible to define a structure of a quotient module S/S for N as follows.

-24Let the i-th row of the carry matrix be si, i.e. i = (-il, -Ci2' **'' -cii-1, mi -ci,i+l'' -Cin) for i = 1 2,.., n. Also, let sl, s2, oo.,sn be considered as elements of ~ with respect to the basis {el, e2,..., e} That is, n i i=l -cije where Cii = -mi. Let the free submodule with basis {sl, s2'..., sn} be S. We can then give the following definition. Definition 7~ Let N be a weighted system with moduli ml m2,.., m and corresponding digit weights pi, p2,.., Pn with the relation on the digit weights yielding n independent equations that can be expressed in the form (3.4). Let C be the (nxn) matrix of (3.5), and S be the submodule of t generated by the rows of C, then N is said to have the structure of ~/S By the above definition, if N has a structure of I/S, then S specifies completely the carry propagation in N, This idea will be further studied in the next section. * The quotient module structure for number systems was first conceived by R. F. Arnold,(12) who gave a similar structure to linear number systems. The main difference in his work is that 1 is a finite module over ZM instead of Z o

IV. NON-REDUNDANT WEIGHTED SYSTEMS We have discussed in the preceding chapter a quotient module I/S structure for a non-redundant system N. While the cardinality of N is the range M and is equal to I mi, the cardinality of S/S is equal to the absolute value of the determinant of S. Besides the structural similarity between the system N and its model S/S, we will in this chapter, establish the conditions on the system, for the existence of an isomorphism between the two. Two theorems on determinants are derived in sec. 4.1 in order to establish a property of the carry matrix of the non-redundant weighted systems. This property is that the determinant of such a matrix is less than or equal to the product of the main diagonal elements, and the equality holds if and only if the matrix has a triangular form. 4.1 Some Useful Theorems on Determinants Let C be a (kxk) matrix of the form shown below: ml C12. cln c21 m2. 2n Cnl n cn1. mn ml, m2,..., mn are used for the principal diagonal, so that they are easily distinguished from the rest. A diagonal permutation on C is a column and row permutation as defined below. -25

-26Definition 8. If i-th and j-th rows are exchanged, followed by an i-th and j-th column exchange, then the matrix is said to be diagonally permuted. Such row and column permutations are said to be diagonal permutations. Diagonal permutations satisfy the following: (1) The set of elements ml, m2,..., mn of the matrix C remains on the principal diagonal after a diagonal permutation and also after any number of repeated diagonal permutations. (2) The determinent of C is unaltered in sign and magnitude by diagonal permutation. (3) Every diagonal permutation has an inverse diagonal permutation. Definition 9. If a (kxk) matrix C can be made (lower or upper) triangular by a necessary number of repeated diagonal permutations, then C is said to be triangularable. Lemma 2. If a (kxk) matrix C is triangularable, then there exists a j < k such that c ji = 0 for j + i Proof: The lemma in essence means that there must exist a row in C in which off-diagonal elements are zero. ml c12 clk c21 m2 * 2k Now let C Ckl Ck2 mk Ck2 mk

-27Let C' be the (lower) triangular matrix obtained by diagonal permutation on C m1' 0. 0 cki m 0. 0 C21 m2 O O Then CT = Ckl e. ek1 iD mk C' can also be diagonally permuted to obtain C (as the diagonal permutations have inverses). The first row of C' has at most one non-zero element. Column permutations of C' do not change the number of non-zero elements of any row. A row permutation involving the first row (which has at most one non-zero element) and j-th row would leave the j-th row with one non-zero element. Hence, there will always be a row having m' on 1 the diagonal with that row satisfying the required condition. Since C is obtained by repeated diagonal permutation of C, C satisfies that condition; hence, the lemma is proved. From here on, all the matrices and determinants are over integers. Theorem 6. Let C be a determinant as shown below: m1 -C12.. -Cln -c21 m2 * -C2n C = -Cnl. e e m.

-28where cij is any non-negative integer, and mi > 0 for i = 2, 3,..., n. Then n C < H mi (4.1) - i=l Proof: For n = 1, 2 the theorem is true. Assume the theorem is true for n = 1, 2.., k-1. Claim. Theorem is true for n = k m! -C12 *. -Clk -c21 m2 -C2k C = -Ckl -Ck2 k k ji-i C = m An- Z cilA i(-1) i=2 k = ml A+ 2i (-1) cilki. (4.2) A11 is a (k-1 by k-l) determinant satisfying the conditions of the theorem so by the induction hypothesis k Al11 - i= i2 mal <_ i=2 m If (- i f i=1 l i If it is shown that (-i) cAi1l is < 0 for i = 2, 3,..., k, then determinant C = mlA11 + (-1)i ci_,lAi < mlAll <_ ml m2... mk and thus proof will be complete. Therefore consider (-1) c-ilA1 where

-29-C12 -13. -Cli -Clk m2 C-23.. -2i -C2k - 32 m3.-. -3k A-1 = -ci -.2 mil -Ci i -Ci k il ij-C l,2 i-i -, Ci-l,k i+12 C+i mi+l -Ci+l,ki+li+l -Ck,2 -k3 -Cki k This minor does not have m terms on the diagonal. By shifting the i-th column to the place of the first column, a new minor A1i is obtained i-2 such that A1 = (-1) 1. Also, the Ail has all off-diagonal elements negative and all terms except the first on the principal diagonal > 0, thus satisfying the induction hypothesis. Therefore, A = (-) Thrfeil (-1) Ai where -li 12 -Ik -C2i m2... -c2k =1- m -Ci il = i-li i* m-1 * -i-lk -Ci+li mi+l -i+l k -Cki -Ck2.. mk

-30From the induction hypothesis we have 1 -< -Cli m2 *. mi- mii+l'.. mk < 0 as Cli, mj are all non-negative for j = 2, 3,..., n. Therefore, the summation term cl (-1) (_1)i-2 A il Cil (-1) 2-2A and so has the same sign as A ii Therefore, (-l)icijil < 0 for i = 2,.,., n. Therefore determinant k C < Ij m. -j=l 3 Hence, the theorem is proved. Lemma 3. Let there be two determinants ck_, Dk such that m C-12. -l,k-1 -C21 m2 -c2,k-1 Ck-1 k-ll mk-_ ml 0 0. 0 -d21 m2 -d23 -d2k and Dk = -d31 -d32 m3 -d3k -dkl' mk

-31all Cij >, dij > 0 and mi > 0 i = 2,.., k mi any non-zero integer. Then if k-l ckl = I m. - Ck-l is triangularable, then k Dk = II mi Dk is triangularable. Proof: Dk = mlll m2 -d23. -d2k -d32 m3 -d3k where 1 = -dk,l. mk k = mliAl mi m2.. mk 11 = m2.. mk Zq1 is a k-l by k-l determinant whose determinant is equal to the product of the principal diagonal elements. Thus A1 is triangularable. Diagonal permutation of Dk, so that A1 is triangular, would leave the first row of Dk unaltered, (since the zeros are permuted). Hence, we will have a Dk in triangular form. The proof is then complete.

-32Theorem 7. Let m1 -C12 -Cln -21 m2 * C2n D = n -Cnl -Cn2 n such that all cik> 0, and mi > 0 for i = 2,..., k, m1 is any non-zero integer. Then n D = II mi n il 1 if and only if Dn is triangularable. Proof: Let Dn be triangularable. Then let Dn be the triangular form of Dn. Therefore we have DI = Dn Since Dn is triangular and the diagonal is only permuted, we have D = D =m m. m. Therefore, n n 1 2 n Dn is triangularable =- Dn = m! m2... mn Yet to be proved is Dn = ml m2... mn — > Dn is triangularable. Proof by Induction: Induction step: For n = 1, it is trivial. For n = 2, m -c12 n ml m2 -c21 m2 -— > C21 c12 = _Z> c12 or c21 = 0. Hence, D2 is triangular.

-33Induction Hypothesis: The theorem is true for n = 1, 2,..., k-1. Claim: The theorem is true for n=k. ml -C12. -clk -c21 m2. -C2k Dk = -Ckl mk k =k,11 i=2 il il ml m2 * m2 -c23 -C2k -32 m3 -C3k A11 = mk2 mk From Theorem 6 we have Al1 < m2 m3... mk and as all the terms in this summation are negative n mAll + i-2 (-1) cilAl = ml m2... mk i=2 — > 4Ai1 = 0 for i = 2,..., k. and A11 = m2... m k From the induction hypothesis, A1 is triangularable. Hence, let Dk be diagonally permuted so that All is lower triangular. Now reordering the subscripts (as m2, mk are all arbitrary) we have Dk as shown in Table II.

-34TABLE II (kxk) DETERMINENT Dk, WITH TRIANGULAR (k-1 x k-l) MINOR ml -C12 -c13 -Clk-l Clk -c21 m2 0 0 0 0 -C31 -c32 m3 0 0 0 Dk = |. Dk ck-l 1e * mk-1 0 -Ckl... mk If there exists a row that has all zero terms, except the diagonal element, then we can bring that row to the top by diagonal permutation. The resulting determinant then satisfies the hypothesis of lemma 3, and so Dk is triangularable, and the theorem will be true. Therefore, we can assume that there does not exist in Dk a row having all zero off-diagonal elements. From Table II, k k Dk k a11 == i2 mi, CliAli = 0, for all i = 2,... k Case 1: Let c12 #, then A12 = 0 = -c2l m3... mn

-35Since m3... mn are greater than zero, c21 = 0. This implies that the second row has all zero off-diagonal elements. This is a contradiction, therefore c12 = 0 Case 2 Let j be the smallest integer such that Clj 4 o Then lj Now by shifting the first column to the j-th position, we obtain Alj in the form ml 0 0 0. 0 -lj -Clj+l. -Clk m2 0 0.. -c2. 0 * -c 32 m3 0.. -c31 0 * l0 -^c2 -c43 m4 0. -c41 ~ ~ 0 * - jc 2 6 0 * -cj3l O O -cj,2... r, 0 mj+l ~0@~~~~~~ i e..mk Alj * * * ml... aj = m+l... mk A' = 0, therefore A' = 0, where A' is top left j-1 by j-1 determinant shown within the lines.

-36A' _ m2 m3 m4 *.. mj_l- (-cj,) Since m2... mjl are all greater than zero, we have cjl = 0. A' is j-l by j-l matrix whose determinant is equal to the product of diagonals with off-diagonal terms non-positive. It is triangularable, and so from lemma 2, there is a row in Dk with zero off-diagonal elements. This implies in Table II a row with all off-diagonal elements equal to zero. This is a contradiction. Hence, clj = 0. So for all j=2,..., k, Clj = 0. Therefore, we have a triangular form. Hence, the theorem is proved. 4.2 Triangularity of the Carry Matrix of Non-redundant Weighted Number Systems Let 5 be a free module over Z with a basis {el, e2,..., en}, as before and cp be a mapping of 5 onto ZM such that c(ei) = Pi ] for i = 1, 2,.. n.(4.3) Pi EZM Now, for any x, y~e, let x = (X1, X2,..., Xn) and y = (Yl Y2 *-'.. Yn) with respect to the basis {el, e2,... en}. Then n p(x) = Z Pi xi M i M

-37since p(x+y) = c(xl+yl, x2+Y2,..., Xn+Yn) cP(x+y) == | pi(xi+yi) i=l M n n i l PixiM i Pii M = cp(x) + cp(y) Therefore cp is a homomorphism of | onto ZM. Now consider a nonredundant number system N, with moduli ml, m2,,.., mn, and digitweights P1, P2,...Pn Then the carry relations of (3.4) are n mipi j= ijJ miPi = for i = 1, 2,..., n jfi and 0 < j < mj The carry relation of (3.4) are equivalent to c(Cil, ci2, ** ci, i-l, -m i, i+l, *, Cin) = 0 for i = 1, 2,..., n P1 has a representation (1, 0,..., O) EN and M-P1 must have some representation of the form (c1l, c12,.., Cln) EN, so that 0 < clj < m-l.. Since the ring sum of pl and M-pl is zero the digitwise sum of their representations (cll+l, c12,... Cln) is in N, if c1l < mj-2. This is contradictory. Therefore, 11 = and c((ml, c12,..., cln) = 0 (4.4) This form with all non-negative entries for si is important for this proof and was contributed by H. L. Garner.

-38Therefore the carry relation between the digit weights can be written in the modified form as below in (4.5). ml c12 c13 Cln PI l -c21 m2 -c23 ~ -c2n P2 0 P3 = (mod M) (4.5) -Cnl -Cn2 mn Pn where 0 < cij < mj Let the new carry matrix of (4.5) be S, and let the i-th row be denoted as siE~, and cp(si) = 0 for i = 1, 2,..., n. The totality {csi} for aeZ is a submodule of 5 and denoted as {si}. The generator si is minimal in the sense that no smaller integer than mi can generate carries from the i-th digit, and the submodule {si} is maximal, for all i = 12,.., n. Furthermore, if the determinant of S is non-zero, then the n generators {sl,s2,...,sr are independent, and they generate K, the kernel of c. Consider now a matrix S' obtained from S, by multiplying the first row of S by -1. Then det. S' = - det. S S' has now all off-diagonal elements non-positive, and except for the first one all diagonal elements are positive. Therefore from Theorem 6, det. SI < -n: m (4.6)

-39So det.S' and det.S are both non-zero and this establishes the independence of the generator set {sl, s2,.., Sn}. Thus S is identical to K Since cp is a group homomorphism of ~ onto ZM, /K is isomosphic to ZM and from Theorem 5 on modules M Idet. KI = M = Idet. SI (4.7) This is consistent with (4.6) only if det. S = M. Therefore, det. S' = -M Since S' satisfies the hypothesis of Theorem 7, S' must have a triangular form. So S also must have a triangular form. By diagonally permuting and reordering the subscripts we can obtain a triangular form of the carry matrix S. Thus we have proved the following important theorem. Theorem 8. The carry matrix of a non-redundant weighted number system has a triangular form. Since S and K are identical, //S is isomosphic to ZM Since the non-redundant system N is also isomosphic to ZM, we have that the system N is isomosphic to its mathematical model |/S 4.3 Examplesof Quotient Module Structure Example 1 n A conventional non-redundant n-digit decimal system, having a range M=10, will have a carry matrix

-4010 0.. 0 -1 10.. 0 S = 0.. -1 10 Since the digit weights are = l1, P2 l-2,., Pn-l = 10, Pn = 1; the digit weight relations satisfy the condition below. 10 0 0. O 0ln 0 -1 10 0. 1 0 0 0 -1 10. 0 (mod 10n) 10 0 0 0 -1 10 1 0 Thus the n digit decimal system can be given a structure of a quotient module /S Example 2 A consistently based system of k digits with all moduli mi = r, having a range M = rk, can be given a structure of r 0 0,. 0 -1 r 0.. 0 0 -1 r a/S = Z ++.. + 0 0. -1 r

41Example 3 A residue system with moduli 2, 3, 5, 7 (which are pairwise relatively prime) can represent integers modulo 210o The carry matrix 2 0 0 0 0 3 0 0 S = 0 0 5 0 0 0 0 7 is diagonal, indicating that there are no carries generated by this system. The weights are Pi = 105, P2 = 70, p3 = 126, and P4 = 120 such that the condition 2 0 0 0 105 0 0 3 0 70 0 (mod 210) 0 0 5 0 126 0 0 0 0 7 120 0 is satisfied giving a structure of Z + Z + Z + Z/S to the system. Example 4 A redundant representation of integers modulo 7, using three binary digits, can be constructed as follows: N = D1 X D2 X D3 Di = {0,1} for i = 1, 2, 3. Let the digit weights be p3 = 1, P2 = 2, p1 = 4 as in conventional binary. Then the digit relations give a carry matrix

-422 0 -1 S= 1 2 0 0 -1 2 such that condition (4.8) is satisfied. That is 2 0 -1 4 0 -1 2 0 2 - (mod 7) (4.8) 0 -1 21 N is a redundant system, since 0 has two representations (0, 0, 0) and (1, 1, 1). Two properties should be noted. (1) The determinant of C = 7, and (2) S is not triangular.

V. GENERAL WEIGHTED SYSTEM STRUCTURE AND CANONICAL TRANSFORMATIONS 5.1 Brief Introduction The discussion here is generalized to include the redundant number systems. Let N be a system with moduli ml, m2,..., mn having a range M < nI mi. (Note: M < II mi makes the system redundant.) Since N is closed under addition, the sum of two elements in N, having a digitwise sum equal to (0, 0,..., mi,..., 0), is in N and is of the form (Cil, ci2,..., Cii,..., Cin) for 0 < cij< mj and for all i = 1, 2,..., n. In the non-redundant case we proved in Section 3.2, that cii should be zero. But here cii need not be zero. Thus if mi - cii = ci for i = 1, 2,..,, n, the relations between the digitweights p1, p2,.'', pn and the range M of the system can be expressed as below in (5.1): cl -c12. -Cln P1 0 -c21 c2 ~. -c2n P2 0 -. _(mod M) (5.1) -cnl -Cn2 n Pn ~ where 0 < cij < m, for i, j = 1 2,..., n The (nxn) matrix of (5e-) can be called the carry matrix as before The (nxn) matrix of (5.i1) can be called the carry matrix as before and the structural similarity between N and ~/S, (where the submodule S is constructed as earlier), can be established. The main difference from -43

-44the non-redundant case is that S is different from K, the kernel of the mapping cp: -4 ZM. The importance of K and the basis elements of K for understanding the arithmetic process in redundant weighted systems will be seen later when the canonical transformation and canonical reduction methods are dealt with. However, to make clear the distinction of the subgroups S and K in redundant systems, the following two examples are provided. Example 5 Let N be a residue system with moduli 6 and 15. The cardinality of N is 90. Since the moduli are not relative prime, they can represent integers ZM, where M < 6, 15 = 30. Let M be 30. Since there are no carries generated in a residue system, the carry matrix will be K 5. Assuming that (1,1)EN represents 1, digit weights can be 0 15_ P! = 5, P2 = 26, satisfying (mod 30), 0 15 26 0 P1 + P2 = 5 + 26 - 1 (mod 30) in this example is pairs of integers, and the mapping cp: -, Z30 is such that cp(Xl, x2) = 5x1 + 26x23 Trivially, cp(6,o) = cp(o,15) = O.

-45However, (6,0) and (0,15) cannot be generators of K since cp(-2,5) = -2.5 + 5.26 = 0 mod 30, and (-2,5) is not in the submodule generated by (6,0) and (0,15). On the other hand, (2,-5) and (0,15) generate K. Equally well (6,0) and (2,-5) generate K Example 6 Let N be a system with moduli m1 = m2 = m3 = m4 = 2 representing Z5 and let = 1, p 2 2 = 22 = 4, p = 23 = 3 (mod 5). Carry matrix C can be written as 2 0 0 -1 -1 2 0 0 C = l' 0 -1 2 0 0 0 -1 2 Also we have the relations between the digit weights as follows: 2 0 0 -1 3 0 -1 2 0 0 4 (mod 5) 0 -1 2 0 2 O 0 0 -1 2 1 0 It can easily be seen that C is not equal to K = kernel (p where cp: - Z5 such that CP(x1,x2,x3,x4) = 3x1 + 4x2 + 2x3 + x4 for all xieZ. This is because (0,1,0,1) = 0o + 4 + 0 + 15 = and (0,1,0,1) is not in the space generated by the row elements of C.

-46However, it can be observed that the row elements of the matrix -1 2 0 0 0 -1 2 0 0 0 -1 2 0 1 0 1 generate K. K certainly contains C, since (2,0,0,-1) can be obtained readily from the rows of the K matrix. It is also interesting to observe that determinant C = 15 and determinant K = 5, showing that ~/C has cardinality 15 and S/K is isomorphic to Z5. This example will be further investigated in later sections where the arithmetic process in redundant systems is explained, 5.2 Condition on the Determinant of the Carry Matrix In weighted systems the digit weight relations expressed in the form of (5.1) govern the arithmetic process. Some significant results can be obtained from the following theorem relating to the condition (5.1). Theorem 9 The n independent linear congruences expressed below as Cll c12. Cln x1 0 c21 c22. C2n x2 0 (mod M) (5.2) cnl cn2 cnn xn 0

-47have solutions xi = Pi where (Pi, P2,..., Pn, M) = 1 if only M divides the determinant of the (nxn) matrix above. A conventional proof of the above theorem can be found in the Appendix. A module theoretic proof will be provided here, to exhibit the usefulness of module theory as such to weighted systems. Proof: Consider a weighted system N with n moduli and corresponding digit weights satisfy the linear congruences as in the theorem C1Pl1 + c12P2 +... + ClnPn c21P1 + a22P2 +..... + c2nPn > (mod M) (5.3) CnlPl + Cn2P2 +.. + cnnPn Then from the definition made earlier, M can be a given structure of a quotient Z-module t/S where S is the submodule represented by the (nxn) matrix of (5.2). Let cp: ~ -e ZM be defined as in (4.3). It is proved in Section 4.2, that cp is a homomosphism and S/K is isomorphic to ZM' so has cardinality equal to M. Since S is a subroup of K, and ~/K is a subgroup of t/S, the cardinality of the set E/K divides the cardinality of E/S Therefore it is evident that M divides determinant S 5.3 Canonical Forms and Transformations Let N be a redundant weighted system defined as in Section 5.1. The relations between the digit weights of N can be expressed as (5.1).

-48Also let cp: p -4ZM be defined as before in Section 4.2. Since NCt p is a mapping of N onto ZM. Define an equivalence relation N in N such that V x,yeNy xNy 4=4 cp(x) c= (y). (5.4) This amounts to saying that all such elements in N representing any particular element in ZM are considered equivalent. Since the map Cp of N is onto Z, (in order that N be a complete system) there are exactly M equivalence classes in N, Whenever these equivalence classes contain a large number of elements, there may be a few elements with some advantages. Some elements may have fewer l's (when expressed in binary coded form) than the other members of the class. Or in certain other examples, some other interesting properties could be sought for. In any case, such a desired form for elements in N will be called the canonical form or canonical property. The totality of elements in N having a canonical property is said to be a canonical subset C A necessary condition on the canonical form is that there exist at least one element in canonical form in each equivalence class. However, there exists some difficulty with this setup. The arithmetic sum of two elements in C, obtained by means of the carry transformation associated with the rows of S may not satisfy the closure law. That is, there may be elements x,yEC such that x + yeN but x + y~C. The additional transformations necessary for putting the result in C are called canonical transformations. Recovery of any element in an equivalence class to the canonical form is called canonical reduction. If T is the set of all canonical transformations, then teT must satisfy the following criterion.

-491) (V )xeN t(x)rx or t(x) = x (mod M) 2) (3)ycN, yEC, t(y)eC (5.5) 3) (V)ZEC, t(z)EC. Carry transformations satisfy the above criterion, but they are not sufficient for taking any digitwise sum into the canonical form. The major problem of canonical reduction is finding the exact compound transformations which take every possible digitwise sum into canonical form. This can be obtained for any particular system by investigation of the transformations derived from the basis or generator elements of K instead of S Since K n S and determinant of K = M, by theorem, the basis transformation of K must be sufficient for reducing any element of into the required form. In particular, if the basis of K is triangular for the system N, then the transformations associated with the row elements of K, will simplify the canonical reduction. The exact nature of the transformations can be given and the time taken for the implementation of the canonical reduction can be estimated. This type of system could be conceived for practical use. The following simple examples demonstrate the canonical reduction problem and in each case the necessary canonical transformation is suggested. 5o4 Some Examples of Redundant Systems and Their Canonical Forms Example 7 Example 6 will be reviewed here. N is a system with moduli

-50ml = m2 = m3 = m4 = 2. N is a set of 16 elements, starting from (0,0,0,0), (0,0,0,1),..., up to (1,1,1,1), representing Z5. The digit weights of the system are given as P4 = 1 P3 = 2 P2 = 14 P = 8 - 3 (mod 5) o Since p4 2pl (mod 5), an end around carry exists in the system. The set N divides into 5 equivalence classes, representing integers 0,1,2,3, and 4 as below. 0 1 2 3 4 00o o00 o o l0 1 11 01 ilo 1 0 0 0 101 0 1 1 0 0 1 1 1 0 01 0 0 1 1010 1011 1100 1101 1110 1111 If we define that the canonical form has not more than a single 1 among the four bits, then there are exactly five elements in the canonical subset C, one in each equivalence class, shown within the enclosures in the table. The muliplication of any two elements in C is carried out by a suitable shift and the result is also in C. This multiplication is very simple and correspondingly faster compared with a conventional binary notation. The addition of two elements in C may result in two l's, then the result is not in C. A simple canonical transformation will then be necessary. If addition of two non-zero elements in C does not generate a

-51carry, a canonical transformation is necessary. If they produce a carry, the result is already in canonical form. One canonical transformation tl will replace two nonadjacent l's by O's. It is so because cp(l,0,,) = 0 = c(0,,,1). Another transformation t2 will transform two adjacent l's into zeros followed by a 1 in the next place to the right. 0110 1 0001 1100 0- 0010 t2: 1001 - 0100 0011 -1 1 0 0 0 These transformations can be constructed without much difficulty, but in view of the simpile example, the desirability of the transformation and therefore the usefulness of the code is questionable. But multiplication is far simpler than in any other known weighted code representation for integers modulo 5. Example 8 Let N be a residue system with moduli 6,15 and 21, and (1,1,1) be a representation for 1 in the system. N can represent integers modulo M where M = Least Common Multiple of the moduli = < 6,15,21 > = 210, It will be shown in Section 6.2 that the following two conditions on digit weights Pi, P2, P3 have to be satisfied:

-521) 6 0 6 Pi 0 0 15 0 P2 mod 210 0 0 21 3 10 (556) 2) P1i + P 3 1 (mod 210) It will be proved later in Section 6.3, that there are 15621 = 9 dif210 ferent sets of digit weights satisfying the above conditions. One of the nine sets of digit weights is (35,56,120), as they satisfy (5.6): 6 x 35 = 15 x 56 = 21 x 120 0 (mod 210) 35 + 56 + 120 = 211 - 1 (mod 210) N is a set of 6 x 15 x 21 = 1890 elements representing Z210 ~ The subset HCN, containing all elements generated by (1,1,1), constitute the non-redundant system representing Z210. The system H has interesting error detecting properties, due to the fact that the moduli are not relatively prime. 3 divides all the moduli 6, 15, and 21. If YEZ210, then Y has a representation in H as (Y1, Y2, Y3 where yi _ Y (mod mi) i = 1,2,3. = Y - aimi for some integers ai Yi - j = - imi - (y - ajmj) = a.m. - a.m. JJ j 1 Since 3 divides mj and mi, 3 divides the ajmj - aimi so also Yi - YjJ

-53If the residues of H are coded in binary form, a single error in the bits would result in a change of 1, 2, or 4, etc. Since 3 is not a factor of the error, it can be detected. Thus, if H is considered the canonical subset of N, any single error would take it out of the canonical form. Error correction could be used to put it back in its canonical form. This particular code is obviously unsuitable for error correction, since the error does not keep it in the equivalence class. On the other hand, if C is a canonical subset, containing all the elements of the form (xl, x2, x3) where 0 < xi < 7, then any element in its canonical form needs only 3 bits for each digit. Carry transformations based on the rows of 6 0 0 S = 0 15 0 0 0 21 are not sufficient for canonical reduction, since there is no way to continue if the sum in the second or third digit exceeds 7. This is where the canonical transformation is required. 6 0 0 If T =2 5 0 is the associated matrix of submodule T of A, 0 0 7 then.6 0 0 35 0 -2 5 56 0 mod 210 O 0 7 120 0 Thus, if cp: -e Z210

-54such that cp(Xl,x2,x3) = 35x1 + 56x2 + 120x312 then p: T - 0 and T S. It can be seen that the row elements of T provide the transformation that is sufficient for canonical reduction. However, one of the canonical transformations involves a carry propagation of 2, into the first digit, whenever the sum in the second digit exceeds 4. These canonical transformations can also be viewed as a homomorphism of the redundant sustem N onto a non-redundant weighted system C of moduli 6, 5, and 7. Thus, the cardinalities of N, H and D are: (N) = 1890 (H) = 210 and (C) = 210 Thus, if H is considered as a system representing Z210, single error detection in H is possible, A mapping of N to C can be carried out by canonical reduction based on the row elements of T Example 9 Consider a system N with moduli ml = m2 = o o = mk = r+l and the digit weights pk = 1, Pk-1 = r, ~'O, P2 = rk2 P1 = rk-1 representing integers modulo r o This system has the same set of digit weights as a consistently based system with mi = r o The digit weight relations satisfy the condition (4.5).

-55r O O O rk- 0 -1 r 0. rk2 0. - e _ (mod rk) r O 0 0 e e 1 0 If the submodule generated by the rows of the above square matrix is S, then N has a structure of s/S. N is a redundant system with k k cardinality = (r + 1) > r Addition of two numbers in N is possible by carry generation based on the structure of |/S. The increase by 1 of the moduli, can be used to restrict the carry propagation to at most one level. On this basis it can be said that the addition is totally parallel. Totally parallel addition is defined to be the case when a digitwise sum produces a carry and partial sum, the carries getting absorbed without producing further carries. Based on this idea there are some interesting redundant (3) systems such as signed digit representation( in which any digit can be negative or positive, and carries or borrows can be propagated to higher ordered digitso Of particular interest is symmetric signed digit representation(3 in which each digit position can take a value from -k to +k where 2k + 1 < r + 2. Even though the addition is complicated by canonical reduction, the symmetric signed digit representation was shown to have many computational advantages besides totally parallel addition. Then preceding examples are meant to explain the arithmetic process in redundant systems and codes. The logical advantages of these coding methods depend largely on the canonical reduction methods.

-56Although the carry assimilation and the canonical reduction can be combined and the arithmetic operation can be obtained in one step, it will be desirable sometimes to treat them separately. Since the coding simplifies the carry process, which is the first stage of the operation, it can be performed and the canonical reduction can be left for some other convenient time. It might be possible to do canonical reduction in parallel with other operations. In this way some time sharing techniques can be usedo Also redundant codes for residue number systems can be shown to be advantageous. The other aspect of redundant systems is error checking in arithmetic operations. This problem has been studied and several coding methods have been suggested for consistently based number systems by other researchers (8,9) Methods of error checking in residue arithmetic are covered in Chapter VII.

VI, REDUNDANCY IN RESIDUE NUMBER SYSTEMS 6.1 Introduction and Results This chapter investigates the conditions for a finite, redundant residue system using the moduli, ml, m2,o.o, mn to represent integers modulo M. It will be proved that for a general residue system (without any restriction on moduli) it is necessary and sufficient that M be a divisor of the < m-L m2,.. o m > in order that the system be redundant and weighted. M need not be a divisor of Timi for redundant, non-residue systems (refer to example 4 on page 41). It will also be proved that for a residue system, if M = < ml, m2,.., m >, there exist exactly d sets of digit weights for the system where d is called the factor of redundancy and is given as n mi m2... m d = i=l 1 (601) < ml, m2,.. mn > M These results are useful in the discussion of the methods of errorchecking in the arithmetic of residue systems as described in the next chapter. 6.2 Necessary and Sufficient Conditions on the Digit Weights of a Residue System Lemma 5. p1, p2,.o., p is a set of digit weights for a general residue system N with moduli mi, nm2ooo, mn, and range M, if and only if -57

-58i = 1, 2,,..., n miPi - 0 (mod M) (6.2) (P1' P2,'' pnM) = 1 The reader should note the distinction between the greatest common divisor (x1, x2..., xn) and an element of N or i indicated as (Cl, c2,..., Cn) c N or r. Proof: N is a residue system with moduli ml, m2,..., mn and the corresponding weights Pl, P2,^',' Pn representing ZM. Since there are no carries in the system, mipi = 0 (mod M) for i = 1,2,...,n. If (a1,, a2,., an) represents 1 in the system, then Z aiPi = 1 M This implies (P1, P2.''' Pn, M) = 1. Conversely, if a residue system N with weights (Pl, P2', " pn) satisfies (6.2), then a a2'... a n+l such that n aiPi + an+l M = 1 i=l1 Therefore, n Z aid = 1 i=l M So (al, a2,.., an) represents 1 in the system. For an xeZM there exists (x1, x2,..., xn)eN such that

-59xi = X ai m. and z XiPi = x M Also, x, yZ, x y. Then x. = xai, x = xiPi mi M Yi = yai, y =. yiP m. M So (X1, x2,.' Xn) and (Y1, Y2.'' Y n) have to be distinct. Thus, all integers in ZM have a representation in N and that completes the proof of the lemma. The residue system in which (1, 1,..., 1) represents 1 e ZM is sometimes called the system of residue classes. In such systems n Z pi - 1 (mod M) i=l and the necessary and sufficient conditions of (6.1) are modified as pm - 0 (mod M) for i = 1, 2,..., n n K- (6.53) Z pi = 1 (mod M) i=l

-606.3 Number of Acceptable Sets of Digit Weights of a Residue System with Moduli That are Not Relatively Prime The following theorems are for residue systems which have a representation (1, 1,..., 1) for 1, and so (6.3) applies. However, they can all be proved for the general case by using (6.2). Theorem 10. A necessary and sufficient condition that a congruence n M Z i Mi = 1 (modM) i=l 1 where M = < mi, m2,..o mn > is solvable for kl,..., k is that n (M/ml, M/m2,..., M/m, M) = 1 (64) If d is defined as in (6.1), then there are exactly d sets of solutions to kl, k2.**,, kn such that 0 < ki <mi -1. mlm2 Proof: Let (ml, m2) = d12, M12 m= d12 mlm2m3 (M12, m3) = d3, M1 dld mlm2m3 (M1, m4) = d14, m14 = 131 14 ) ='dl2d 13d14 (Mln-l, n) dln, M -M = mmn - m, n d12d115 *** dln

-61d in the theorem is now obtained by mlm2... mn md = -— = 12 13 in The first part of the theorem stating the necessaryand sufficient condition for solvability is well established and proved in most of the textbooks on number theory.5 However, we will show that the condition (6.4) is true. Let (M/ml, M/m2,..., M/mn, M) = d then (M/(m1d), M/(m2d),..., M/(mnd), M/d) = 1 M M/ M/ / M _(/m1.d /mn2,.., d/m, M/d) = 1 So m I M/d for i = 1, 2,...n Therefore M/d is a common multiple of ml, m2,..., m n The least common multiple, M divides all common multiples of ml, m2,..O. mn. Therefore M divides M/d, and so d = 1 Thus we have proved the condition (6.4). We have the congruence k k M +... + kn M 1 (mod M) From the definition of d d we have From the definition of, d we have

-62ml m2 mn- ( m2.. mn mlm3 *. mn mlm2. * mn-2mn> dl2. din d12d13 dln d2di3 diln Using the formulas (1), (2) and (3) given below (1) If (ml, m2) = d12 then (m2, -) = 1 dl2 dl2 (2) (a b) = (); (ta, tb) = t(a,b) t t t (3) (x, x2,'.. ) = (.. (((xi, x2), x3), x4),..., x) we have m2 o. mn mim...e mn mn @ m dl i dln d12 in dln d3... dln d " L Jmn mlm 2m4 m n m 4.. m dl3.in d 2 d 3 din dl4.. din because (M12 m3 1 (M mim M (M12 m3) d13 d2 12 d13 d3 - d12

-63Continuing the process, we get ( mn- mn mlm2... mn_2mn _ mn n n-ldln d12d13 * dn din because 1n-1l Ml n-lA mdl,-1 dl,n- Therefore ( M M, M) = M2 mn-1 dln k + + kn -M + k 1 (mod M) M 2m2 mn-l mn From the above two equations and from (6.4) we have kmn dn and k m_ 1 (mmo mn/dn) n k has exactly one solution mod m /dln; however, it has d solutions n n 1n ln mod mn or 0 < kn < mn_1. Now substituting for kn one of the dln possible values we obtain a congruence in n-l variables k L + k + k -mM 1 - k -) (mod M) Mi 2 n-l

-64This equation is divisible on both sides by n dln Thus we have M Ml,n-l + M1 n-{ M1, n-l ki Mn- + k2 Mln-.. + kn1 l.- = Cn-1 (mod M ) ml m2 mnl,n-1 1 2 n-i Repeating the same step (ln-1 M1 n-l Ml,n-l Mn ) m m2 mn_2 dn-l we can show that kn-l has exactly dln1 solutions modulo mn.l and kn_2 has dln 2 and so on. This proves that we have a total of dn dln-l dln-2.. d12 = d solutions for kl, k2,..., kn, such that 0 < k.i m - 1. Hence the theorem is proved. From the above theorem the congruence n M k m - 1 (mod M) Z =1 i m. i=l i has d sets of solutions for kl,..., kn& such that 0 < k < m.. Now applying (6.3) on the digit weights of a residue system N with the operating moduli ml, m2... mn we have pi = ki M/mi n n 7 Pi = 7 k. M/m. 1 (mod M) 1 1 1 1

-65which has d sets of solutions for kl,..., kn, 0 < ki < mi Thus we have proved the theorem stated below. Theorem 11. For a residue system N with moduli ml, m2,... mn representing integers modulo M where M = < mi, m2,..., mn > there are exactly mlm2... mn d =M sets of digit weights. Example 10. Consider a residue system N with moduli 6, 10, 21 representing Z210 Then d = 610 21 = 6; m = 6, m = 10, m = 21. 210 3 The six sets of digit weights are given below. Pl P2 P3 0 21 190 35 126 50 175 126 120 + P + P3 1 (mod 210) 70 21 120 105 126 190 mlP1 2P2 m 3P3 = 0 (mod 210) 140 21 50 6.4 Condition on the Range M of a Residue System Theorem 12. ml m2,..., mn are the moduli of a residue system N. N can represent integers modulo M, if and only if M is a divisor of < mi, m2..., m >.

-66Proof: If N is a residue system, then 3 P, P2,..., pn ZE satisfying the condition (6.3). For any i, if (mi, M) = 1 Pimi 00 mod M = k. M 1 MIPimi (M, mi) = 1 Therefore M p. Therefore Pi = Ci M for some integer c. - 0 (mod M) This means that for any modulo that is relatively prime to M its digit weight is zero. Such digits exist in the system as purely redundant digits. Assume there are r such bits where 0 < r < n. If r = n then pi = 0 for i = 1, 2,... n and Z pi E 0 (mod M) which contradicts condition (6.1). Now reordering the moduli so that the last r moduli mn-r+lt mn_-r+2,.. mn are the ones that are relatively prime to M, let (M., m) = di for i = 1, 2,..o, n-r and N M M- = M' d. 1 1 d. > 1 Then applying the first part of (6.3), we have Pimi = 0 (mod M) = k.M 1

-67Dividing by d. mi M i = k. 1i di m. t M Let i = m.; M di 1 d such that (mi', Mi ) = 1 k..p. = M= c M for some integer ci mi d1 for i = 1, 2,... n-ro Applying the second part of (6.3), we have n-r M c M- CM = 1 i 1 di This equation has solutions for p. if and only if ( M M M = 1 \1 ld2 dn-r This is possible only if M = < dl, d2... dnr > < ml m2 m l m2 n-r which implies that M < m,, m.., m2n-r >

-68and so divides < ml, m2,... mn > Now, if M divides < m1, m2,..., mn > it is necessary to prove the following. Claim. N represents ZM. If we can show that ~ P1' P2' *', Pn satisfying (6.3), then we will have completed the proof. We know that N with moduli ml, mi2,.~, mn represents Zt where t = < ml, m2,..., mn > Let pl, P2,. pn Zt be the digit weights of the weight functions W:N - Zt. Since M divides t we have pimi 0 O (mod t) Pimi = 0 (mod t) = pimi Q 0 (mod M) Z pi 1 (mod t) L Z pi - 1 (mod M) so IP1IM''*-*.n IM are the digit weights for the system N -ZM. so the theorem is proved. Let ml, m2,.., mn be the moduli of a residue system N having a range M = < ml, m2,..., mn > and let Pi P2, *.., pn be one of the I mi d = l M sets of acceptable weights. As explained in Chapter IV, the system N can be given a quotient structure a/S, where S is the row space of the diagonal matrix.

-69m2 ".....' If m', m2, 0.., m' are the smallest integers satisfying m!pi 0 (mod M), then S' is the row space of the matrix m2 piJ n which contains Sm Further, if m', *.., mt are all pairwise relatively prime, then In m = M and S' will be identical to the kernel of cp where cp: t -ZM such that cp(ei) = Pi for i 1, 2, e.., n. Then the residue system N' with moduli ml, m2,..., m and weights Pl, P2,...' n having a range M, is nonredundant. The redundant system N can be considered an extension or coded form of N' and the factors i in that case will be called the coding factors. These factors can be used for error checking purposes as will be described later in the next chapter. Also, simplification of any residue number in N can be done by means of the transformations based on S'.

-70However, the condition that there exist a set of weights P l P22., p of N for which the corresponding ml, m2,..., m are all pairwise relatively prime is yet to be established. This can be done by choosing a set ml, m,..., ml satisfying (6.5). 1 2, n ml = ml < ml, m2, *.,m _l,mj > m'= - for j = 2,..., n j j-1 n m i=l (6.5) This way we can obtain m{, mI,., mI that are pairwise relatively prime and n iT ml = < min m2,.* mn > i=l The residue system N' with moduli m{, m,..., m1 having a range equal to I m! = M, will have weights p.,. p that satisfy m! p! 0 (mod M) 1 1 Z p' -1 (mod M) Since m' divides mi, miPi O (mod M), and therefore P1 P2,~, p1 is an acceptable set of weights of N. This Pi' P2'''" Pn establishes the desired condition. Since the ordering of the moduli is arbitrary there can be more than one such set of moduli ml, m1,..., m1 and also of the corresponding weights. Table III shows that the residue system with moduli 6, 10 and 21, has four

-71such sets of weights, leading to ml, m?, m~ that are relatively prime, Irmi 6 x 10 x 21 d = i -— xlx- = 6 M = 210 for that system. The six sets of weights and the corresponding values of ml, m2, ml are listed in the table below. TABLE III DIGIT WEIGHTS AND CORRESPONDING VALUES OF ml, ml, mj Pl P2 P3 m1 m2 m 1 0 21 190 1 10 21 2 35 126 50 6 5 21 3 175 126 120 6 5 7 4 70 21 120 3 10 7 5 105 126 190 2 5 21 6 140 21 50 3 10 21 If m' is the smallest positive integer such that miPi = 0 i 1 1M then the residue system with moduli ml, ml, ml can also have weights Pi, P2, p and represent ZM. Such a system also has diagonal carry matrix S. m' 0 0 0 m' 0 0 0 ml L L~~~5

-72In particular, if mI, m2, mt are pairwise relatively prime, then S is identical to K of the system. Otherwise, we will have K that is not diagonal but is triangular. For the second set of weights from the table ml = 6, m = 5, ml = 21, and the carry matrix S is given as 6 0 0 S = 5 0 and det. S = 360 0 0 21 The null space K has a matrix 60. 2 0 -7 K = I0 5 = 0 5 and det. K = 210 -2 0 7 0 0 21 K is not diagonal but triangular, and the system has carries between the digits which are very much undesirable. This is the case also with the sixth set of weights which have m = 3, m2 = 10 and ml = 21, But in the case of the weight sets 1, 3, 4 and 5 (from the table) ml, m', and mt are pairwise relatively prime and there are no carries at all. Hence, a non-redundant residue system with 6, 5, 7 as moduli having respective weights 175, 126, 120 can be represented by the redundant system with moduli 6, 10 and 21 with the same weights.

-73This is why the selection of the set of weights is important from the arithmetic point of view and also decides the type of redundancyo If the range M is a proper divisor of < ml, m2, **. m > the situation is not very much different. It can be shown by similar reasoning that there exists a set of weights pi, p2, ***' Pn for the system which have corresponding integers 1' 2,,'.., n satisfying (i) i - 0 (mod M) 1 (ii) 2ilmi _r for i = 1, 2,... n n (iii) n i = M. i=l

VII, ERROR CHECKING IN RESIDUE ARITHMETIC 7.1 Introduction Residue number systems, their properties(l,3,10) and computational methods have been investigated by several researchers.(5,10,11) Some of the persistent problems in residue systems such as magnitude and sign determination, overflow detection and division methods have been studied by them. The reliability aspect of residue arithmetic, and error checking in residue number systems using pairwise relatively prime moduli are discussed by Garner.(7) Some of the coding techniques(8,9,13) of error checking in conventional number systems can be applied with advantage to residue systems, Different methods of residue coding, error checking and their relative advantages are discussed in this chapter, 7.2 Residue Representation Error checking can be based on the notion of weights* of the coding elements and the distance between two code elements. The representation of the residues will be an important consideration in defining the weight of a code element, If each modulus is considered a single digit, (irrespective of the type of representation of the residues), then the weight of a code element is equal to the number of non-zero residues, In particular, if a residue system in which (1, 1, 4,., 1) represents the integer 1, the weight of (1, 1,.., 1) is equal to n and so also the distance between * The weight of a residue number referred here in this chapter is related to the concept of Hamming distance and so must be distinguished from the digit weight used before, -74

-75any two adjacent numbers. The distance in this case, between two code elements is the weight of the arithmetic difference between them. This coincides with Hamming distance since there are no carries between the modulio On the other hand, if the residues are binary coded, it is possible to look at each of the residues, and weight can be attached to them separately. The weight of any particular residue is equal to the number of l's in it. The distance between any two residues (of modulus mi ) will then be considered as the weight of their difference. In residue systems, even though there are no carries between moduli, there is difficulty in obtaining the least positive residue (with respect to mi ) anytime the arithmetic result exceeds mi - 1 It will be shown later if the modulus is 2s - 1 for any positive integer s, binary coding of the residues will be advantageous. 703 Pairwise Relatively Prime Moduli Consider a residue system N with moduli ml, m2,..., mn+k (relatively prime, pairwise) representing integers modulo n M = TI mi (7.1) i=l Let n+k M' = I mi (7.2) i=l The k moduli mn+l,.o o mn+k are used for redundancy. And we shall consider the error checking possibilities of this redundant system with M' elements representing ZM, Let us examine this as a system

-76representing ZM,, non-redundantly and pick the subset representing {0, 1, o0., M-l} of ZM, as the correct elements of the system and the rest erroneous elements. Then if the system has a minimum weight t+l (or t error detecting capabilities), any element of weight less than t must have a magnitude greater than M Also let P1, P2.,-Pnk be the weights of each of the modulio That is (0,., 1, O, O.., 0) represents Pi. Such that (i-th place) PiCZM,, for i=l, 2,.,., n+k. For a non-redundant system, we have that M' p = k for all i=l, 2, o n+k where ki is any integer such that (ki, mi) = lo If x = (xl, x2, o.o, xn+k)EN has a weight equal to t, then exactly t of the x's are nonzero. The magnitude of x can then be written as t IXIM, =J s8j Pj M' 1 <j _< mj - 1 where pI, pI,.., pt are any combination of t weights out of n+k weights Pl, p2, P 02, Pn+k' Then the condition IXIM, -> M is sufficient for t error detection, or t error correction, Theorem 13.* A residue system with n+k moduli ml, m2, o'o, mn+k (all pairwise relatively prime) representing integers modulo * For the case k=l, 2, the theorem has been proved by H, Lo Garner, in some of his unpublished work,

-77n M = II mi i=l has a minimum distance k+l if and only if mn+j > mi for j=l, 2,..., d and i=l, 2, *.., n. (703) Proof: If ml, m2,..., mn+k satisfy (7.3), then any element with weight t 1 < t < k has magnitude X t XIM, = 7J? Pj M. M IS=1, J | t =l M j M' where 1 < 5j < mj - 1 and mls, m, m are any t moduli out of the n+k _C M' for C XIM' t t mj 1 < C < I m! - j=l - - i=l - t - t I mjt Mn+j j=l j=l since mn+j > mi for all i=l, 2,..., n Also M' M' — Mt > M- = M since k > t. t k Ji i mn+j j1=l j =1

-78Thus, any element of weight t, 1 < t < k has magnitude greater than M and so is not in the code. Thus every non-zero code element has weight greater than k, Conversely, if every non-zero code element has weight greater than k, then t 1 n mj IMt > M for all 1 <t < k j=l 3 C M' M >M where 1 < C < m! -1 k - - j=l n m! j=l Therefore M' MT -- > M = r -M - k k n m! n m.m j=l J j=l n+J This implies k k n mj < _ mn+j j=l j=l This is satisfied for all t < k and any combination ml m,.. mt only if mn+j > m for j=l, 2,... k i=l, 2, Y... n Thus, the theorem is proved. If the magnitude of any arithmetic result is checked and is found to be greater than M-l then the arithmetic operation is in error. Error correction is based on the principle of table look up or by trial

-79and error check by procedure. Either of them is inconvenient as they involve repeated magnitude determination which is not simple in residue systems. Thus, the excess moduli coding is good at best for single error detection, Single error detection can be obtained with one extra modulus mn+1, such that mn+l > mi for i=l, 2.o n 7,4 Moduli that are not Pairwise Relatively Prime Error checking in residue systems with relatively non-prime moduli is based on the following Theorem 14. If ml, m2,..., mn are moduli of a residue system representing ZM where M = < mi m2,..., mn >, (mi, mj) = d for some i, j, iAj and (1, 1..., 1)eN represents lZM. then d divides xi - xj, where Xi and xj are residues with respect to the moduli mi and mj respectively. Proof: It was shown in Chapter VI, that if (11 1,.., 1) is a representation for 1, then any xeZM has a representation (x1, x2,.&.. xn)EN such that X. = lXlmi For ifj Xi = x - kimin -for some integers ki and k. Xj = x - kjmj - Xj = x- kimi - (x - kjmj) = kmji - kimi

-80Since (mi, mj) = d, d divides kjmj - kimi and so also xi - xj. Thus the theorem is proved. The following example illustrates the error detecting properties of a residue system using 2s - 1 type of moduli, which are not pairwise relatively prime, Furthermore, this system uses binary coding of the residues. Example 11 Let N be a residue system with moduli m1 = 63, m2 = 255, m3 = 511, m4 = 1023. The prime factorization of the moduli will yield the following ml = 63 = 3 x 3 x 7 = 26 -1 m2 = 255 = 3 x 5 x 17 = 28 -1 m3 = 511 = 7 x 73 = 29 -1 m4 = 1023 = 3 x 11 x 31 = 210-1l Since the moduli are not pairwise relatively prime, they can represent ZM when M = < ml, m2, m3, m4 > = 63 x 85 x 73 x 341. If (x1, x2, x3, x4)EN, then 7 must divide x1 - x3 and 3 must divide x2- x4. If the error is divisible by these factors then it can not be detected. On the otherhand if the residues are coded in the binary form, a single error in one of the residues causes a change of t(bmi - 2k) where b=o or 1, and k is any non-negative integer such that 2k < mi. Some simpler methods of obtaining residues modulo 3, 7 or 2k -1 (for some integer k ) are covered in the next section, 7.5 Binary Coded Residue Systems Since the residues are coded binary, conventional binary arithmetic units can be used with certain modifications. Whenever the result

-81of an arithmetic operation produces a residue value greater than mi -1, the least positive residue (mod mi) has to be recovered. This can be done by a division of the result by mi and the remainder be taken as the residue. That is a very cumbersome method, On the other hand, residue addition and recovery of the least positive residue can be done by generation of suitable number of end-around carries. The idea of endaround carries is based on the following. If a certain modulus mi is a power of 2, say mi = 2k then arithmetic modulo mi is done by a k bit binary unit with overflows ignored. Otherwise, mi is such that 2k > mi > 2k-l for some positive integer k let 2k - mi be equal to C e Then C < 2k-1, and 2k = C (mod mi). Thus an overflow from the k-th stage9 (equivalent to 2k) can be taken care of by addition of C. If C in its binary form, has only a few 1's then these can be absorbed as end-around carries. The result obtained by this technique is < 2k, and is the correct value if it is < mi, otherwise mi should be subtracted. This method can be employed for multiplication using end-around carries absorption, comparison with mi being left to the end. If mi = 2kl1, there is only one end-around carry. Multiplication by 2 or by any power of 2 is obtained by a suitable number of cyclic left shifts. Also, since mi = 2k-1 is expressed as 11.,.1 in binary, the complement of any residue is obtained by switching zeros into ones and vice versa, If a set of moduli ml, m2,.,,~ mn is chosen, in which mi = 2Si-l, (i=l, 2,,,, n;) then the moduli may not be relatively prime,

-82The example 11 in the previous section uses moduli of the type 2 i-1 and the redundancy factors are 3 and 7. If the residues are binary coded then error detection proceeds as follows, Single errors in binary residue arithmetic would result in an error of +(bmi - 2k) where b = 0 or 1 and k any non-negative integer such that 2k < mi. Since 3 divides mi but does not divide 2k the error is detectable. The same thing can be said about the moduli that have 7 as a common factor. Thus, single errors can be detected by verifying whether 3 divides x2 - X4 and 7 divides xl - x3. To check whether 3 divides any binary number several methods exist. One method is to delete all sets of two adjacent l's or O's and group the rest of the number and do it over again until no two adjacent zeros or ones exist. The residue modulo 3 will be equal to the number of i's if they are in odd places, or will be equal to -(the number of one's) if they are in even places. Another method is to use a modulo three adder-subtractor to add the odd digit l's and subtract the even digit l's. Residue modulo 2k-1 of a binary number n digits long can be obtained by treating the number in groups of K digit long and adding the [k] + 1, k bit numbers with an end-around carry. This is possible because 2k - 1 mod (2k - 1) 2ak 1 mod (2k - 1)

-83Also k adjacent l's or O's forming part of the number can be deleted, the remaining ones joined. An example of a binary number modulo 7 is given below, Example 12 To obtain X = 1010 111 001 011 11 17 Deleting three adjacent l's we have 010 001 011 011. Again deleting the three adjacent zeros formed, we have 011 011 011 Now dividing into three bit numbers, and adding them, we have 011 011 Oil 110 011 1001 An end-around carry has to be generated. Therefore the result is 001 1 010 Therefore, X = 2. A residue system with moduli 3ml, 3m2,,o., 3mn, where ml, m2, o., mn are pairwise relatively prime, permits single error detection in the residues. In fact, simultaneous detection of single errors in t of the moduli is possible where t is any integer such that t < n- Also, the exact moduli in which the errors occurred can be located. If (xl, x2,..., xn) is the arithmetic result from Theorem 7, we have that all the residues |xl3, |x213,.., Ixnl3 should be equal. If these are single errors in any of the residues,

-84they can be detected. If there are t moduli in which single errors have occurred, corresponding to these moduli, the residues modulo 3 would be different. Since some of the moduli of the 2s -1 type have 3 as a factor, this method can be considered advantageous. Redundancy of the system can be expressed as n log2 3 il i Information per bit = n o1g32 n i=l which will be greater than the single error detecting system using relatively prime moduliif any of the moduli is greater than 3n-1 706 An + B Type Coding of Residues Error checking of the residues is possible by coding each of the residues separately. This is based on the principle of An + B type codes.(9) If Ami + 2B = 2Si -1 for any particular modulus mi, and for positive integers A, B and si, then an si bit binary representation of the residues is possible. Since k and its complement mi - k are coded as A k + B and A(mi - k) + B respectively, their sum A k + B + A(mi - k) + B = Ami + 2B = 2si -1, which is expressed as 11...1 in the binary form. Complementation can be done by switching O's and l's. However for B#O, the addition and subtraction of two code elements should be accompanied by proper correction,

-85This is not suitable for multiplication of two residues in the coded form, However, for codes Ami = 2si -1 (that is for B = 0 ) no correction will be necessary for addition or subtraction. If k1 and k2 are two residues coded as A k1 and A k2, their multiplication will have to be IA kl k21Ami This can be obtained by multiplying A kl by k2 or Ak2 by k1 o That is, one of the operands have to be decoded before multiplication. Also, the minimum distance or weight of the code elements depends on the selection of A. For single error detection A can be any odd integer > 3. For single error correction the minimum distance has to be > 3. For each odd integer A there exists integer rmax such that A rmax is of the form 2t 1 for smallest integer t. Then mi < rmax since Ami is required to be of the form 2 i + 1, mi = rmax. Some values of A and mi are given in the table below. si +1 A m. Ami = 2 19 27 29 1 21 3 26 -1 23 89 211 1 29 565 214 1 37 3085 218 + 1 39 105 212 1 91 45 212 1 99 331 215 1 105 39 212 1 If Ami = 2si + 1 type, the arithmetic is not so straightforward as in si 2 - 1 type. An end-around borrow will have to be propagated in s 2 i + 1 type. Also, complementing a code element can be done by switching O's and l's followed by an addition of 2.

-867.7 Suitable Moduli for Residue Computation The single error detecting system using moduli 63, 255, 1023, and 511 has several advantages as shown before. The redundancy per bit in the system is: log2 63 log2[63 x 255 x 1023 x 5113 6+ 8 + 9 + 11= 176 = 17.6 percent, and the information per bit = 1 -.176 _.824 (approximately). An n-single error correcting system using moduli 89, 117, 565, and 331 which are all pairwise relatively prime has a range M = Ilmi of the order of 231. The corresponding coding factors Ai and their products are as below. i Ai mi Aimi 1 23 89 211 - 1 2 35 117 212 1 3 29 565 214 + 1 4 99 331 215 + 1 Any single error in each of the residues of the arithmetic result (xl, x2, x3, x4) can be corrected by obtaining IXiLAi If the result is correct, I'Ai

-87would be all 0 Since any single error causes a change of + 2k k < si for the 2i + 1 type, k < si for the 2 - 1 type of moduli, and their residues modulo Ai are all distinct; the single error can be corrected. This system enables n-single error correction (or a single error correction in each of the n moduli). As expected, the redundancy per bit given by r log2[23 x 35 x 29 x 99] log(211 - 1)(2l2 _ 1)(214 + 1)(25 + 1)] 14.66 1466 = 40o6 per cent 52 x.694 is much larger than 18.2 percent of the single error detecting 2s - 1 type moduli system described before. Further, this system has 2s + 1 type moduli which are not as convenient as 2s - 1 typeo Also, since the coding factors Ai are 23, 35, 29, 99, there is no simpler way of obtaining residues modulo Ai other than by division. These features make the n-single error correcting system less attractive.,

VIII. CONCLUSION 8.1 Review of the Results and Conclusion In the first part we are able to categorize the finite number systems as linear and non-linear and study their advantages and disadvantages. It is shown that the digitwise sum has no meaning in non-linear systems. In particular, the weighted systems, which are in the category of linear homogeneous, obey the digitwise sum rule (2.2) as stated in Chapter II. Very important consideration is given to the relations between the digit weights and carry propagation rules. These have been explained very successfully by means of the quotient module structure that can be given for all weighted systems. This leads to the interesting notion of triangular form of carry matrix for non-redundant systems and the theory of canonical transformations for redundant systems as explained in Chapter V. For the residue number systems, it is shown that the carry matrix is diagonal, and the range M is a divisor of the product of the moduli. This condition limits the choice of redundancy we can use in the residue systems. Also, since there are d sets of acceptable digit weights in a redundant residue system representing ZM where M = < ml, mn,...,mn > and d = i computation can be done using any suitable M set of weights. However, the selection of the set of weights is dependent upon the error checking scheme of the system. This dependency of error checking and the digit weights is explained by means of the example of a residue system with three moduli 6, 10, and 21. -88

-89Using the theory of redundant residue systems, methods of error checking in residue arithmetic are derived. Moduli of the type 2s + 1 (for a positive integer s) and their advantages in residue computation are investigated, The aspect of selecting suitable moduli and the type of redundancy for reliable and logically superior residue arithmetic is one of great importance. Other problems in residue computation are to find improved methods of magnitude comparison, sign detection, and division. There are attempts by some researchers,(1011) to use redundancy to obtain improved sign determination methods. Unless some breakthroughs are obtained in these problems, the residue computer still remains as a special purpose machine. While the abstract mathematical structure described in the earlier parts is expected to enhance the understanding of the general properties of the weighted systems, the investigation presented in the latter parts of this dissertation is expected to help in the logical design of reliable and improved residue arithmetic units.

APPENDIX Theorem 3: The n independent linear congruences expressed below as Cll C12 ~ Cln Xl 0 C21 C22 C2n X2 ~ (mod M) Cnl cn2 C nn 0 have solutions xi = Pi where (PlP2,o.. Pn, M) = 1 if only M divides the determinant of the nxn matrix above. Proof: The congruences can be written as n equations c1l x1 + C12 X2 +. + Cln xn = kl M C22 x1 + C22 X2 + *. + c2n xn = k2 M Cnl X1 + Cn2 X2 + + nn n = kn M Let c11 C12 Cln c21 C22 ~ C2n A = Cnl Cn2 ~ Cnn and a minor Aij of A be the (n-l) by (n-l) determinant obtained by deleting the i-th row and j-th column from A. -90

-91Then kl M All + k2 M 21 +. + kn M Anl x1 = - =M C1 for some integer c1 Similarly, xi = (_l)i-1 kl M li + 2 M A2i + kn M Ani M C. M Ci for some integer ci o Thus, we have xi A = M Ci for i = 1,2,...,n Let (x1x2o..,xn) = k Since (xlx,x2,.,xnM) = 1 (kM) = 1 (x1 A, x2 A,..0 xn A) = k A (M C1, M C2, o.., M Cn) = M C for some integer C Therefore, k A = M C Therefore M divides k A Since (Mk) = 1, M divides A, thus proving the theorem.

BIBLIOGRAPHY 1. Garner, H. L., "The Residue Number System," IRE Trans. on EC, Vol. EC-8, No. 2, June 1959. 2. LeVeque, W,, Theory of Numbers, Vol. 1, Addison Wesley Publishing Co. 1956. 30 Rozenberg, D, P., "Algebraic Properties of Residue Number Systems," IBM 61-907-176. 4. Jacobson, N., Lectures in Abstract Algebra, Vol. 2, Chapter 3, Van Nostrand Co., Inc., 1952. 5. Garner, H. L., et al,, "Residue Number Systems for Computers," ASD Technical Report 61-483, The University of Michigan Technical Note, ORA 04879-6-T, September 1962. 6. Garner, H, L,, "Finite Non-Redundant Number System Weights," Information Systems Laboratory, The University of Michigan Technical Note, ORA 04879-6-T, September 1962. 70 Garner, H. Lo, "Error Checking and the Structure of Binary Addition," Ph.D. Thesis, Chapter V, The University of Michigan, 1958. 8. Diamond, J. M,, "Checking Codes for Digital Computers," Proc. of the IRE, 43, (1955) 457-488. 90 Brown, D. T., "Error Detecting and Correcting Binary Codes for Arithmetic Operations," IRE TRANS. EC-9, (1960) 333-337. 10. Aiken, H., et al, "Modular Number Systems," Harvard University Computational Laboratory, July 1960. 11. "Modular Arithmetic Techniques," Technical Documentary Report No. ASD-TDR-62-686, January 1963, Lockheed Missiles and Space Co., Sunnyvale, California. 12. Arnold, R. F., "Linear Number Systems," The University of Michigan, Technical Note 04879-8-T, October 1962. 13. Peterson, W. W., "Error Correcting Codes," The MIT Press and John Wiley & Sons, Inc., New York, (Jan. 1961) 236-244. -92