THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note LINEAR NUMBER SYSTEMS Richard F. Arnold ORA Project 04879-8-T under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 335(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR October 1962

TABLE OF CONTENTS Page SUMMARY v 1. INTRODUCTION 1 2. ALGEBRAIC PRELIMINARIES 1 3. NUMERICAL SYSTEMS 2 4. CONCLUSION 19 5. ACKNOWLEDGMENT 20 APPENDIX. Le VEQUE'S THEOREM 21 iii

SUMMARY This paper presents a treatment of linear, computer number systems using the theory of finitely generated modules over the integers. The theory succeeds in characterizing certain properties of number systems relating to the. structure of addition and carry propagation. There is some discussion of redundant number systems and their possible importance in computational speed. An appendix contains Le Veque's proof of the key theorem necessary to obtain necessary and sufficient conditions for non-redundant, linear number systems. v

1. INTRODUCTION This paper presents the basic development of a theory of linear number systems based on the theory of modules over a principal ideal domain. A sufficient amount of background information is given together with examples of codes covered in this class. Moreover, some considerations are briefly discussed which relate this theory to practical computer design. 2. ALGEBRAIC PRELIMINARIES It is assumed that the reader is familiar with the concepts of group, ring, field and vector space. Definition: Let R be a commutative ring with identity, and M an abelean group. M is said to have the structure of a finitely generated R-module if there is given a map R x M + M called scalar multiplication satisfying the following axioms: (1) (a + b)x = ax + bx x e M ab c R (2) a(x + y) = ax + ay x,y M a e R (3) ab(x) = a(bx) x E M abb e R (4) lx = x x M 1 R (5) There exists a finite set of elements (xl... xk) xi E M such that for k each y e M, there exist scalars (al... ak) and Z aixi = y. Such i=l a set is called a set of generators of M. The notion of an R-module is a generalization of that of vector space. The 1

generalization takes two directions: (a) The "scalars" of a module need only be a ring whereas a vector space is always defined over a field. (b) A module may not have a basis. That is to say it may not satisfy the following strengthened form of axiom 5, which holds for vector spaces. (5F) There exists a finite set of elements (xi... xk) x. e M such that for each y e M there exist unique scalars (ql... qk) and k Z aixi = y. Such a set is called a basis of M. i=l The difference between a set of generators and a basis is that given the latter, each element of the module is expressable in only one way as a linear combination of basis elements. An R-module having a basis is said to be free. A map 0 from an R-module M to an R-module N is called a homomorphism if: (1) (x + y) = + (x) + (y) x,y e M (2) a/(x) = Z(ax) x e M a e R Much of one's intuition about vector space homomorphisms carries over to modules, however one must be careful to note which theorems assume the existence of a basis. The interested reader should study Vol. II of Jacobson's "Linear Algebra." 3. NUMBER SYSTEMS In this section, we develop the notion of a non-redundant linear number system characterized by the internal structure of the system and an interpretation function which is compatible with this structure. From this definition it will be shown that a non-redundant number system can be given the structure 2

of a module in a very natural way. Definition: A finite set X of m elements is called a digit iff,there is a distinguished element called zero, and a partially defined function s:X:-+ X called "successor" satisfying the axioms. (1) The domain of definition of s has cardinality (m-l) (2) For n > 0, s (x) X x x X (3) s(x) = s(y) - x = y We write the elements of X as (0, 1, 2,..., (m-l) and define an internal addition and subtraction wherever it is compatible with the successor function. (1) x+0 = 0+x =x x e X (2) If x + y and s(x + y) are defined xy e X then x + s(y) = s(x) + y = s(x + y) (3) If x + y = z then z.- y = x x,y,z e X Notice that addition of two elements: whose "sum" in the ordinary sense exceeds (m-l) is not defined. Let Y = X1 x X2.x... Xk be the cartesian product of k digits. Y has k cardinality M = | | mi (the mi are not necessarily the same). A partial i=l addition on Y is inherited from the partial addition in the digits. (x... xk) + (Y1... Y) = (x1 +.i, ^. Xk + Yk) for (x... xk), (y1... Yk) ~ Y if xi + Yi is defined for all i. Y is called a non-redundant linear number system if a function i:Y- Z/M from Y into the ring of.integers modulo- M which is 1-1, onto and is compatii 3

ble with the partial addition in Y. ((y + z) = $(y) + ((z) y,z c Y if y + z is defined. Notice that z is determined if its value is given for each of the elements ei = (0, 0,..., li, O, 0). The numbers $(ei) in Z/M are called weights. The fact that / is 1 —1 onto allows the addition in Y to be extended to arbitrary pairs of elements of Y so that / becomes an isomorphism. Y now has the structure of an abelean group. It becomes a Z/M - module by using the ring multiplication in the obvious way. ay = -(a/(y)) a e Z/M y c Y Consider the free Z/M - module F on R generators (tl... tk). This is just the set of all linear forms in the ti with coefficients from Z/M. With respect to iti} as a basis, the elements of F may be taken as k-tuples of elements of Z/M. The set (ei) ei = (0, O,.i, O... 0) e Y may be taken as a set of generators for Y. A homomorphism *':F + Y is defined from the free module F to the number system Y by mapping ti into el. Since (ti) is a basis for F, it may be mapped arbitrarily into any Z/M - module. and such a mapping determines the homomorphism. ((Z i ti) = Zoi ei 4 is onto because (ei) is a set of generators. Let HCF be the kernel of t- i.*e, H = fh: h e F and t(h) = 0)

so F/H ~ Y H is a submodule of F, and it can be shown (Jacobson Vol. II, pp. 77-78) that if F is free, so is H. The construction given above is usually made for the purpose of showing that every finitely generated module is isomorphic to the quotient of two free modules. Our purpose is quite different. It will be shown that the above characterization yields interesting information about the structure of addition in Y when "digit overflow" occurs. It will be convenient to represent the free submodule H as a matrix. The generators of H appear as rows in this matrix [hij]. Although H is unique, a set of generators for H is usually not. The biig advantage of writing H as a matrix is that it enables us to concisely express the manner in which all sets of generators of a particular H may be obtained. We denote by GI the set of invertible I by I matrices with elements from R. If [hij] is a matrix of generators for H, then we can show that y[hij] is also when ye G~. Let some aeF be in H. Then we know that since [hij] is a set of generators, there exists a set of coefficients (ai) such that (ai... c) hll... hik = (al... ak) = a hi1.** h~k The set of coefficients with respect to the new set of generators y[hij] will then be a(y ). y must exist since y was required to be invertible and 5

(O(y-")y [hij] = a[hij] = a Examples (A) Let Y be the consistently based radix 7 system of three digits. This system represents the integers modulo 73 = 343. Y = X x X x X, each X having modulus 7, and ~ is defined by giving its values on (ei} (eO) 1 1 1 (el=) =7 ei = (0.. i... 0) (e2) 49 where thO symbols on the right side of the equations represent elements in 2343. F is the free Z343 module on three generators with (343)3 elements. If the generators of Y are ordered. from the right to left in the conventional manner, then a set of generators for H is given by: 0.1 36 which could al- 1 -7 336 0 so be written -7 0 Another basis is obtained by taking I1-7 1 -6 -7 y = so y [hij] =j 0 021 -70 2 -14 0 What is F/H? The elements of F/H are cosets of elements of F, two elements'of F being in the same coset if they differ by an element in H. FOr example~ (35 2, 1), (1, 15. 8) and (6, 28, 15) all are mapped by 4 into the code element (3, 2, 1) which is, in turn, mapped by <- into 6

3. 72 + 2 ~ 7 + 1 = 162 of Z343 (B) Let Y be the 3-digit residue number system having moduli 2,3 and 5. Let $(eI) = 15 ((e2) = 10 ~(e3) = 6 F is the free Z30 module on 3 generators andabasis for H is 2535 [ 5 I The interesting properties of the residue number system follow from the property that H has a set of generators: 2 0 03 0 Lo 0 54 The intimate connections between F. H and a number system Y should now be clear. Given any number system Y, used to represent the elements of a ring,. computation in that number system is accomplished by passing first to F, doing the computation and returning to Y. In order to characterize this proces:s more exactly, it is necessary to introduce the notion of an equivalence map. Definition: Let (S,-) be a system consisting of a set S and an equivalence 7

relation "," on S. Let p:;-4 S be a function from S into S. p is called an equivalence map if p(s) ~s s C S The equivalence relation in mind is that induced by the coset decomposition of F by f. We shall define s t d4 *(s) = lr(t) It is now clear that the equivalence maps on F must map each element into an element differing from it by an element of H. Let us define the set C:C:F Zc tieC 0 < i < mi. The elements of C are a full set of representatives for F/H. C "looks" like Y, however it is important to keep them distinct because addition is defined differently in the two sets. Let two maps X and f|C be defined in the obvious way: \:Y C %(ZCiei) = Z iti 4iC:C + Y' lC(ZQti) = ZQiei The computation of the sum of two numbers in Y may now be described as follows. 1. Given xyeY, they are interpreted as elements in F. i.e., we take X(x) and X(y). 2. X(x) and X(y) are added in F. Because F is free, this may be done digitwise k(x):+? ~?(y) ~ 3. A sequence of equivalence maps Ipl, p2... pn is applied to 8

(\(x). W(y)). i.e./ w(tax^ R^ - < - I^Y) ^ The sequence of pi's are subject to the following restriction. Let C+C = (f:fcF and ci, c2fC f = ci + c2) Then PnPn _... pl(C+C)C.C. This insures that the image of any sum obtained after applying the e' j's will be in C. 4. PnPn-l *' P1( x) + K(y)) is interpreted back in Y. i.e., we take *lc [PnPn -'. P (x(x) + x(y))] What is the significance of this four-step process? Steps 1 and 4 are formal only, having been introduced to keep the mathematics straight. What has really happened is that additions in Y may be replaced by the two Steps 2 and 53 Step 2 is addition in the free module and therefore the sum in any position is a function only-of-the values of the summands in those two positions. The equivalence map of Step 3 may again be decomposed into component maps which are easily computed, Referring back to Example A, the equivalence maps used are easily identified. and'in this case it is conventional to call them carry propagations. pi[(l,Ca2,Ca3))] = (ai,Ca2,a3) if 0 < a3 < 7 = (aiCa2,as3) + (0, 1, -7) otherwise P2[(ca1,oU2,a3)] = (oa1',2,Ca3) if 0 < a2 < 7 = (CalC2,as) + (1, -7, O) otherwise p [(ol,o;2,z3) ] = (1,)a2,a3) if 0 < O3 < 7 = (a,a ) + (-7, 0, 0) otherwise 9

It is clear that P3P2P1 applied to the sum in F of any two canonical representatives will again yield a canonical representative. For Example B, the equivalence maps used were P [(a1,2,03)] = (a1,2,a3) if 0 < a3 < 5 = (aac2,a ) + (0, 0, -5) otherwise p2[(alICs,)] = (Ca1,2,C3) if 0 < a2 3 = (a1,a2,a3) + (0, -3, 0) otherwise P3[ C1aa2.PU3)] = (c1,a2,C3) if 0 < ca < 2 = (a1Ca2,a3) + (-2, 0 O) otherwise Enlarging on a comment made earlierW we assert that every equivalence map on F may be described in the following way. 1. F is partitioned into classes (FijF2...- Fn]. 2. There are designated a set of elements of H (hl... hn}. 3. p(f) f + h * feFi'The equivalence maps described in the examples were expressed as the composition of equivalence maps where the partitions on F were into two classes. Notice that in both cases the:-class determination for each component equivalence map was determined by examining only one digit. Such a map will be called an elementary equivalence map. We shall show next that, in "general, " the canonical map always decomposes into exactly k elementary maps. This is done by showing that the matrix [h.i] may always be put in the form 10

-mi C12... 0 -2.. C2k o O-mk It then follows that the maps (Pi (a... i... ak) = (a... ai C' akM) (h h) are duch that pk k... P satisfies the requirement of reducing all elements of F to canonical form. To show that such a triangular form is possible requires the use of a somewhat difficult theorem about non-redundant number systems. The theorem is stated here and proved in the appendix. Theorem: If Y is a non-redundant linear system, representing Z/M, then there exists a digit Xi such that M| mi(ei) ~ It can then be shown that the set of elements (miti) in F are a triangular set of generators with respect to some ordering of the digits. Proof: The conclusion follows from an induction argument on the number of digits. It is obviously true for K = 1. For aribtrary k, by the previous theorem it is known that for some i, MI mi-(ei) or equivalently, mi~(ei) = 0 mod M. It follows that (0, 0... Om0, m) sEHif:the diitslare reordered(-so that the digit satisfy11

ing.the theorem is last. Dividing the congruence by mi, we get s(ek) - 0 mod M/mi. Therefore any two elements of Y differing only in position k are congruent modulo M/mi. From this it follows that the elements of the form (yl... Yk-' O) must map 1-1 into ZM/mk when ( is composed with the obvious map from ZM into ZM/mk. Using the induction hypothesis on this reduced code, the elements (miti] 1 < i < (k-l) form a triangular set of generators of H(k-l) mi C12 Ci3s. Ci-k-i 0) m2 0... 0... mk.iJ Each row is congruent to 0 modulo M/mk and thus congruent to a multiple of M/mk modulo M. However, all multiples of M/mk may be written as multiples of tk so by tang appropriate multiples f tk and subtracting them from the rows of the H(k_), a matrix of elements in Hk is formed. ml C1i2. CLkl - X11k Q m2 C2,k-l - X2,k 0... 0Xk_, k This matrix is now augmented by appending (0,... 0, mk). The resulting matrix may be shown to generate H by noting that the 12

equivalence map mentioned at the beginning of this section reduces any element in F to one in C and uses only multiples of'the. rows ofJthe matrix. We have constructed a free module F, a kernel H, and a canonical set of representatives C for a non-redundant linear number system Y. In order to achieve more generality, a definition of a (possibly redundant) linear number system is given entirely in terms of F, H, and C. Definition: Let F be a free module on k generators, and H a submodule such that F/H is finite. Let CCF be such that its intersection with each equivalence class of F/H is non-empty. Let p be an equivalence map with respect to F/H such that p(C+C)CC. Then C is called a linear number system. Notice that this definition is given entirely without reference to a map from C onto ZM for some M. The non-redundant number systems as defined previously certainly qualify. That this is a non-trivial generalization can be seen from the following wellknown example. (C) "One's Compliment" System Let F be the free Z - module on five generators and H the submodule generated by the following elements. hi -2 0 0 0 1 h2 1 -2 0 0 0 hs 0 1 -2 0 0 h4 O O 1 -2 0 hs 0 O 0 1 -2 15

C is the set of those elements of the form Ziei 0 <I i < 2. Let Pi(al.. i'..5) = (ca.. * i. 5) if 0 di < 2 ( = (C1.. Ci a... C5) + hi otherwise Then P (PlPPsP4Ps): The "squaring" is necessary because of the "end around carry." It is well known that this number system represents Z33. Although C has 32 elements in it, F/H has only 31. It is the structure of F/H that determines which ZM may be represented. To characterize the structure of F/H it is necessary to introduce more module theory. Rather tnan repeat this development the reader is referred to Chapter 3 of Jacobson. The result of interest is: Theorem: If R is a principal ideal domain- any finitely generated R module is a direct sum of cylic. modules. The method of computing the orders of the various cyclic submodules follows from the canonical form construction for matrices with elements from a principal ideal domain. By elementary row and column operations) one reduces the matrix of generators of H to canonical form. This canonical form does not give an alternative set of generators for H since the elementary transformations may change the basis of Fe It does preserve the abstract structure of F/H. The lower right-hand diagonal element gives the order of the largest cyclic submodule and therefore the maximum value of M such that a homomorphism from C onto ZM exists. This process is partially carried out 14

for the above example. -2 0 0 0 1 1 -6 0 0 1 1 -2 0 0 0 1 -2 0 0 0 o 1 -2- 0 0 ( 0 1 -2 0 0 O O 1 -2 0 O 1 -2 0 o o 0 1 -2 0 0 1 -2 by adding, three times the second row to the first row, 1-6 0 0 11 0 0 O 0 0 0 4 0 0 -1 0 4 0 0 -1 0 1 -2 0 0 C) O 1 -2 0 0 0 0 1 -2 0 0 1 -2 0 0 0 0 1-2 0 0 0 1 -2 by another row and then a column operation. 10000 o o 1 0000 10000o o o 0160-1 o1ooo o0oo O 1 6 0-1 0O 1 0 0 0 O 1 0 0 0 0 1-2 0 o L o 1-8 o 1 0) 1 0 0 O 0 1-2 0 O 0 1-2 0 0 0 1 0 0 0 0 1 -2 0 0 0 1-2 0 0 O0 031 It is always possible to represent the ring of integers modulo as a divisor of the order of the maximal cyclic submodule. The notion of equivalence of matrices used above is not appropriate if 15

we are interested in obtaining a "good" set of generators of H. By, "good," we mean a set which lends itself to the construction of easily computed equivalence maps. The appropriate reduced [.set] of:elementary operations is all the row operations plus column permutations since the ordering of the digits is arbitrary. A trivial example of a code whose structure is not cyclic is obtained by letting F have two generators and H = 0 3 H is already in canonical form and F/H is the direct sum of two cyclic modules of order three. Whenever H is of the form: H t l c s partitioning F/H into F1/H. F2/H2, the largest cyclic submodule will have order less than or equal to the least common multiple of the orders of F/HIA and F2/H2. The equality will hold when F1/Hj and F2/H2 are themselves cyclic. For a non-redundant system, it must be that the orders of F1/Hz and F2/H2 are relatively prime. Repeated application of the above, in the non-redundant case using only prime moduli, yields the following form: 16

l 1 0 0 ml 1 m2 1 m2 0 12 0 m2 1 m2 m. 1 0 ) 0 m This is as "sparse" a matrix as possible for any given set of moduli. Conventional consistently weighted codes and residue codes are special cases where j = 1 and ij = 1- respectively, Before continuing this discussion, another example of a redundant code is given to demonstrate the reduction of the free addition portion of computation at the expense of increased complexity of the canonical transformation. (D) Let F be the free Z - module on eight generators and H, the subgroup. spanned by -2 0 0 0 0 0 0 1 1 -n o O o o o o 0 0 0 0 0 0 - 0 0 0 0 0 0 0 1 -2 0 0 0 1 0 0 0 1 17

Notice that H is simply the submodule similar to that of example C with an additional generator, the last row. The addition of this row results in the order of F/H being 17 instead of 255. Let the canonical set be (c07... ao) 0 < ai < 2, i.e., of order 255. The following feature of C may be observed. Every coset of F/H has a representative in C which has at most two ai whose value is one. If $:F/H + Z17 is given by (a7... ao) = ( Qi2 ) mod 17, then a set of representatives with this property is 0 (O 0 0 0 0 0 0 0) 9 (1 0 0 0 0 0 0 o) 1 (O o o o o o o 0) 10 (O O O O 1 o 1 0) 2 (O O O O O O 1 0) 11 (1 0 0 0 0 0 1 0) 3 (o o o 1 0 1 o o) 12 (O 1 0 1 O O O 0) 4 (o o o o o 1 o o) 13 (o 1 o o o o o 0) 5 ( 0 0 0 0 1 0 1) 14 (o 1 o o o o o 1) 6 (o o 1 o 1 o o o) 15 (0 0 1 O o o o 0) 7 (1 0 1 o o o o o) 16 (o o o 1 o o o o) 8 (o o o o 1 o o 0) Notice also that no representative in this set has adjacent "ones." Let this special subset of C be designated C*. For the sum of two elements x, y f C* it is clear that the part of the equivalence map ordinarily corresponding to carry propagations is quite simple, since carries can propagate, at most,one stage. On the other hand,unless the image of C*+C* under p is again in C*, this property will not be preserved. In other words, the canonical set of interest is really C*, but we may choose to represent it as elements of C. For this particular example, the equivalence map necessary to insure p(C*+C*)CC* appears to be not terribly complicated, but sufficiently more so than ordinary carry propagation-type maps to make the code impractical. 18

4. CONCLUSION In evaluating a code, one must consider how easy the.other arithmetic operations are to do. To a great extent, the difficulty of doing integer multiplication follows in a monotonic manner that of doing additions. This results from the fact that the codes are linear and one generally does multiplication by employing the distributive law and summing a set of products. Division is somewhat more complicated and is best considered in the context of magnitude control. The main calculations of interest to computer users are after all, not in any ring ZM, but in a field, usually either the real or complex numbers. The area of numerical analysis has dealt extensively with this question of approximating a field. Unfortunately, it has primarily studied the effect on accuracy of algorithm variation somewhat independently of the number system being used. This has been possible because of the ease in handling scaling problems in consistently based systems. The fundamental nature of the scaling problem is best seen in the context of fractional multiplications Multiplication of fractions where the fractions are represented by integers usually must involve a division. For example, in a binary machine one has xl = n ~ 2 X2 = n2 2 -12 - 36 then xIx2 = n1n2 * 2, but this must be expressed as n3 2 so nLn2 must be divided by 2. In a binary machine this is accomplished by simply truncating the double length result in the middle and retaining the top half. The ability to divide by an arbitrary power of 2 by truncation is crucial, 19

and is not shared by all other linear number systems. Sign determination is seen to be a special case, where the divisor is M/2, so that the quotient is 0 or 1 depending on whether the given number is in the bottom or top half of the set of numbers. In our efforts to understand the nature of the residue number system, ways were found to reduce considerably the necessary number of sign determinations. All the techniques developed involved the necessity for Euclidean division by some large constant. Although any large constant would do, it is a property of the residue number system that division by any number other than the moduli is difficult and must be realized by successive divisions with moduli. Although by no means so difficult as to make the residue number system impractical, the operation of division by a large constant dominates design considerations for residue number arithmetic units, much as multiplication has dominated the design of conventional arithmetic units. It is the above considerations that limit the utility of the characterization of linear number systems given in this paper. Previous work on this problem has been largely confined to the sign detection problem. The central difficulty has been the inability to discover abstract mathematical structures which adequately incorporate the physical operations involved in Euclidean division. The extent to which the module characterization may be useful is still unknown. 5. ACKNOWLEDGMENT The development of this work rests substantially on the earlier work of Prof. H. L. Garner and D. P. Rozenburg. I also wish to thank T.R.N. Rao, Michael Harrison, and Henry Glover for many useful discussions in this area. 20

APPENDIX Le VEQUE'S THEOREM Le Vequets theorem was used to show the existence of a triangular form for non-redundant linear number systems. Theorem: Let X be a non-redundant linear number system and.:X * Z/M defined as before. Then there exists a 1 < j'< n such that mj,(ej ) = 0 mod M. Proof: Let X be mapped into the unit circle of the complex plane as follows:,Ej-wj)2ti/M X: (xi... xn):+ e (xi... xn) eX / n > Notice that it is not necessary to take zXjWj modulo M since the kernel i=l of X(Im (1)) contains (M). Now the sum of the M Mth roots of unity is always 0 since if P is a primative Mth root, M-1 M z pj = P- = j=O -1 So O = Z (4 J xeX t= Z wjxj2~i/M = E l e x~X j Since there is a product term for all combinations of values of x's, the above expression may be factored, i.e.., J Wjxj2li/M 0 = Z e j xj=O 21

Therefore, since we have a product of factors equal to zero. it must be that one of the factors is zero. For some j', we have m,t-l 0 = Z eWjxjt.2ti/M xj =0 m 1 (ewj,2i/M Xj - Z)(e xj,=0 Again using the identity an 1 n a - -1 i ~a -l i=O we have 0 = (eWj,2~i/M)mj' 1 1 = (eWj 2ti/M)mj, ewj mj,2i/M hence M|wjmj, or mj,w., 0 mod M 22

UNIVERSITY OF MICHIGAN 3 90II1 111111115 02493 8899 3 9015 02493 8899