T HE U NIVE R S I T Y OF MICHIGAN COLIEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note FINITE, NON-REDUNDANT NUMBER SYSTEM WEIGHTS...... Harvey:. Garner-.~ ~ -i4 ~ *~ -'.'.'. -'.. ~-; UNITED $TATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF'33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE3 OHIO administered through: OFFEIC OF ADMINISTB AT ON ANN. ABOR My 1962

1O586240 o^ P. 6 ^

FINITE, NON-REDUNDANT NUMBER SYSTEM WEIGHTS In this paper the necessary and sufficient conditions for a finite number system to be non-redundant, complete and weighted are given in terms of permissible digit weights. The arithmetic of any given number system follows directly if the digit weights are given. Definition. A finite, weighted, non-redundant number system N is defined as a finite set of n-tuples of the form (xl,,..,xn) isomorphic to the finite group GM. The elements of the GM are the integers from zero to M-l, The mapping between GM and N is defined by the congruence relationship n Z xiPi = g mod M (1) i=l where geGM, (xli,..,xn)eN; XieGmi, i = 1,..,n; The elements of Gmi are the integers O, l,...,mi-l. M is called the modulus of the number system; Pi is the weight of the ith digit; xi is the ith digit symbol; and mi is called the digit modulus or digit base. If ml = m2 =... = mn the number system is termed a consistently based number system. Otherwise, the number system is termed non-consistently based or a mixed base number system. Definition. In a redundant weighted number system there must exist at least one case where two or more elements of N are related by Eq. (1) to a single'1

element of GM. (Redundancy may be introduced by the choice of digit weights n or by choosing M < j mi). i=l Definition. A number system is incomplete if there exists at least one element of GM not related by Eq. (1) to an element of N. n A number system is always redundant if M < 7j mi and is always incomn iplete if M >7j mi. In the remaining discussion we shall be concerned only i=l n with the case where M = mi and the question of redundancy will depend i=l upon the choice of digit weights. Definition, A set of numbers is called a complete residue system modulo m a. If i f j, ai a aj mod m. b, If a is any integer there is an index i with 1 < i < m for which a = ai mod m. By this definition GM is a complete residue system modulo M and xi is a complete residue system modulo mi. n Lemma 1, If M = mi then a number system is redundant if, and only if, i=l it is incomplete. Lemma 2. If the weight Pi is such that (pi,M) = di, then pi = kidi where (kiM, -) = 1 and the mi elements of GM related to xipi by Eq. (1) are intedi gers of the form IxikidilM. 2

Proof: Setting all x's except xi to zero in Eq. (1) yields xipi = g mod M. If (pi,M) = di then difg. Hence g = kidi = p for xi = 1 and (ki, -) = 1 otherwise (piM) ~ di di For any xieGni xikidi = xiPi g mod M so g IxikidilM M Lemma 5. If di = (Pi,M) = and (ki, a-) = (ki,mi) = 1 then the set of elements generated by Ixiki ~-I as xi assumes all possible values of Gii is an additive subgroup of GM of order mi. Furthermore, there exists a one-to-one mapping between the elements Ixiki 7IM and the elements of Gmi. M Proof: If xiki s = g mod M then xiki g' mod mi and g' = Ixikilmi g' is a complete residue system modulo mi because (kimi) = 1 and xieG.. G Hence if (plM) = then the elements of GM associated ~~xi"~Cmi ecmi with xipi are M M2M Omi, -'' (mi-l) m These elements form an additive subgroup of order mi..")~'~

Theorem I. Sufficient conditions for the weights of a non-redundant weighted number system are: (plM) = M /_ M ( M - M q'- 1 q qm (nmn) = The ordering ml,... mn is arbitrary. Proof: If (pM) =- then it follows from Lemma 3 that the elements m1 of GM generated by xpl1, xleGml, form a complete subgroup of GM of order mi. This subgroup is designated Hm1 and consists of elements M M M M 0, -,..,(m-1) -. Now (p2, -) = so the elements generated by x2 satisfy the equationm2 by x20p satisfy the equation M M x p z mod 2 2 mlm2 ml where. z = O,,...m2 - 1. The elements it GM represented by X1P1 + x2p2

are all elements divisible by Mo In other words, xip1+x2p2.m lm2l generates the subgroup of GM of order mlm2" Thus x1P'+Xa2p+x3p3 "is seen to generate the subgroup of GM of' order m1m2ms consisting of all elements of GM divisible''3by M.o Since there is a mlm2m3 finite number of digits, the process will terminate and xzpz+... +xnpn will generate the subgroup of GM of order ml,. mn = M which is GMo M a) Lemma 4'If (pi,M) = di where"di >- and (ki, = 1 then the set of elements generated by Ixikidil as xi assumes all values of Gmi is subgroup M of G M'o order"~ of GM of order o There does not exist a one-to-one mapping between the elements IxikidilM and the elements of Gii because two or more elements of Cmi are associated with the same element IxikidilMo Proof: Given xikidi - gmod M and (piM) = (kdi,M) = di then xik g' mod di or xiklM = g where XieGmi -'1 and (ki, -) - 1 M M If di < m then - < mi di and g; has only M different values: g = 0, 1, 2,. - lo edid 2i -d Hence" g = -d0, di, d,.:M-di ~,:M, M' which is an additive subgroup of G of order.Since -< mi di di there is not [o:~to-one mapping between the elements txikp IM. and Gmi.5

Theorem II. If there exists some (pi,M) = di where di > ~ then the number system is redundant, Proof: This theorem follows directly from Lemma 4 and the definition of a redundant number system. If (Pi,M) = di di > Mi then two different values of xieQmi correspond to the same element of GM and the number system is redundant, M M Lemma 5. If (pi,M) = di where di < M XiEGmi and (ki, i) = 1, then the set of elements generated by fxikidilM as xi assumes all values of Gmi is not ~a complete subgroup of GM but is a particular set of mi elements selected from the subgroup of GM of order A. M Proof: If di < m thenm then mi then i < the Ixikidi =i g M defines a set of mi elements because xieGmi and (ki, 7) = 1. The set of elements IxikiM is a particular subset of mi eledi ments from _ e The set of elements Ixikidi M = g is a particular subset of mi elements selected from the subgroup of GM of order > mi because g'd = g. di Lemma 6. Let S1 be the incomplete subgroup generated by IxikidilM where (p.,M) = di, xiEGmi di = T < M and (k,ai) = 1. The complete subgroup H (Pi'M) = ~xl"Gm'di' x icmi group is of order ai while S1, the incomplete subgroup, is of order mi. There exists a set of eleme'n s, which is to be used to complete the subgroup H by the following operation:

hcH h = lI+ VIM UES1 veS2 H can be completed non-redundantly if, and only if, (ai,mi) = mi and the only element common to S1 and S2 is zero. Proof: If S2 contains an element other than zero which is common to S1 there would exist a redundant representation for that element. Every element of S2 which combines with an element of S1 to give an element of H combines with every element of S1 to yield mi elements of H. If q distinct elements of S2 are used, then qmi elements of H are generated. If the subgroup is to be generated complete and non-redundant, then qmi = ai and (mi,ai) = mi. Lemma 7.* The necessary and sufficient condition for the solvability of the general equation n Z xiPi - C mod M i=l xleGM i =:,...,n is that (Pl, p. PnM)lC M M Theorem III. If for all i, di < - where p = kidi and (ki, -) = 1..m.i di then the number system is incomplete and hence redundant. *This is a standard theorem of number theory. See page 33 Le Veque, Topics in Number Theory, Addison Wesley, 1956. -7

Proof: Let di = (p,M) = <M and (kia) = 1. It follows from Lemma 5 that IX1P1lM generates ml elements of Hal (Hal is the subgroup of GM of order al). Specifically, the elements are: OMk... (ml - 1) Mkli a M, al M Mkl mlM JL z mod. M So a, al xlkl z' mod ml. Lemma 6 shows that (ml,a1) = mi. We are given that (kl,al) = 1. So al = qlml and (kl,qlml) = 1. It follows that (kl,ml) = 1. Therefore, z' = O, 1,..., ml-l. The elements needed to complete Hal are a, ml al a1'''l a1 The necessary and sufficient condition for the completion of the subgroup is the existence of a- n-tuples of the form (0, x2,...,xn) satisfying the following congruence: n Z xii - y mM mod M i=2 (2) al 1 y= O,1,... 8..

A similar condition exists for elements which are not members of the subgroup Hal n Z xiP y mod i=2 a y = 0, 1,..., M al The proof of the theorem presented here demonstrates that the subgroup Hal can never be represented by the number system if for all, (i, M M mi mi Some, but not all, of the xi, i = 2,...,n, which make up the n-tuples satisfying Eq. (2) may have the value zero for all values of y. To account for this the variable ii is introduced. If xi = 0 for all values of y then gi = 0, otherwise ni = 1. It follows from Lemma 7 that the necessary condition for the solution of Eq. (2) is (n2P2,..,nPn, M) I Y a for all y = 0, 1,... a - 1. ml mi Thus (n2P2,.-, nnM) = l 5ai and Eq. (2) may be divided by Ml to yield 5al n i XiPi Mml = 5y mod m~ 9

But every Pi = ki M-so ai n Division by 5 yields n Z x.ik. - ymod a (6) i=2 1 aim ml O 1 al 1 y =0 1,..., mi Equation (6) shows that aim1 must divide kia1 if ri = 1 since xiGmi..... i:....... - -.. Suppose that there is only one i = 1. If mi > -l then the number sysmi tem is redundant. If mi < -1 then the number system is incomplete. If. a, = miml then aiml 4kial since (aiki) = 1 and mi < ai. Thus the number a! = mira then aimi Jki~al since (aiki) =l and mi < ai. Thus the number system is not complete if only one qi = 1. If more than one 1i = 1 then Eq. (6) must be reduced. A given weight in Eq. (6) for which 1i = 1 generates Gal an incomplete subgroup of -. The complete subgroup is of order ai while ml the incomplete subgroup is of order mi. Except for the reduction of the order of the group this is the same condition considered at the start of the proof of this theorem. Thus the repetition of the process of removing the partially generated subgroup and stating the conditions necessary to complete the subgroup will lead eventually to a condition involving only one digit ai-r ai-r of the form xiki - v mod. This cannot be satisfied. aimi-r mi.r Theorem IV. The cobit'fons for weights given in Theorem I are necessary as well as sufficient..10'

Proof: By Theorem III, not all Pi can be such that (pi,M) < mi By Theorem II, no pi can be such that (pi,M) > _. Therefore mi there exists at least one Pi such that (Pi,M) =. Since order mi is of no consequence let i = 1. Then (pl,M) M and xlp, genml erates the subgroup of G of order mi. The remaining n-l digits must satisfy n z - M. xPi.. z mod M i =2 x mi z = 0 1,.... - mi Repetition of the above argument yields ( MAM M P2, 2 ^nml) - mlm2 Repetition of the argument until termination provides all of the conditions stated in Theorem I. Theorem V. Given a non-redundant and complete weighted number system. The multiplication of weight pq by a constant k' yields a non-redundant complete number system if and only if (k4,mq) = 1. Theorem VI. The number of distinct weights which may be assigned to the qth weight of a non-redundant, complete number system is q-l *(mq) X mii=l t(x) is Euler's I function which is equal to the number of integers less than x and relatively prime to x.'9(x) = x J (1 — ). (The notation Ti indipix pIx cates a product over all distinct primes which divide x.) l

Example: (10) = 10(1 - )(- ) = 4. For further details see Le Veque, pages 27-30. n Proof: If kq = 1 then p =. - mi i=q+l i=l n All multiples of ( mi for which (kq,mq) = 1 may be used as i=q+l ni the qth digit weight. Multiples of mi greater than or equal i=q+l to M are congruent modulo M to a multiple less than M and must not n be counted. The total number of multiples of mi less than q T i=q+l M ^ M is equal to = mi. The fraction of these multiples. mi i=l i=l i=q+l for which (kq,mq) = 1 is Thus there are ^ ^ mq m- il mi = V(mq) q-i qs i=m i=l distinct weights for the qth weight. Corollary: The number of distinct weighi7d, non-redundant, n digit, number systems for a given ordering of the digit moduli is equal to fn ( q-l 7'In) 7 mq) q=l i=l Corollary: The number of distinct weighted, consistently based, non-redundant, n(n-1) n digit, number systems for base m is mXl(m) where x = 2 Theorem VII. Every non-redundant complete number system with relatively prime moduli can be represented by a lower triangular matrix [W] where wij = IPilmj' (We shall consider the base moduli symbols mi,...,mn as variables. The set of base moduli ul,....n are constants. There are n: different ways of assign12

ing the base moduli constants to the base variables. There is a lower triangular W matrix for at least one of these assignments.) Proof: klM klM k1M ml ml ml ml mn. k2M Ik2M.. 2M W = mlm2 ml mlmM2i m2 M2 mn knM knM. knM mi~~.mn ml ml..mn n2 ml mn mn where (ki,mi) = 1 i= l,...,n W is a lower triangular matrix because: 1. No diagonal element is equal to zero. The qth diagonal element has the form kqM m...mq = m.q.n q ikqmq+l..' mn m 0 because (kq,mq) = and all base moduli are relatively prime by pairs. 2. In any row every element to the right of the diagonal element is equal to zero. Elements to the right of the diagonal in the qth row have the form k^QM = i^ n j.~~ ~-~ = kqimq+l... mn ml.. mq mq+k q+t. where t = 1,...,~qkqmq+l. i. mn + = 0 for all t = l,...,n-q. 13 +

Theorem VIII. The elements below the diagonal in the W matrix are not necessarily zero. wij, i > j assumes mj different values depending on the choice of ki. Proof: Elements to the left of the diagonal in the qth row have the form k M ml...mq mt kqmq+l mn mq t - Wq,q-t where t = l,...,q-1. The only restriction on kq is (kq,mq) = 1. The moduli are relatively prime so kq can be equal to any moduli except mq. kq = mq-t for any t = 1,...,q-1 yields wqqt = 0. If kq / mq-t then wqQb / 0 Furthermore Ikqmq+l-. mnlmq t is a complete residue system modulo mq.t so wij, i > j may assume mj different values. Theorem IX. The diagonal element wqq assumes only ~(mq) different values such that (wqq,mq) = 1. Proof: Theorem VI shows that the number of distinct weights assignable to the qth weight is given by q-l (mq) 7C mi i=l From TheoremVIII we know.that the nondiagonal elements to the left q-l. of the diagonal in the q row have 7T< mi different combinations. ".'" i=l since each wij may assume mj different values and i = 1,...q-l. Hence 4(mq) different values may be assigned to the diagonal element.

Assume that (wqq,mq) = d 1. Then d mq+l...mn since wqq = Ikqmq+l..mnlmq and (kq,mq) = 1. But d mq+l...mn because mq is relatively prime to all the other moduli. Hence there is a contradiction and the assumption that(wqq,mq) /1 is not valid. Lemma 7. Repeated permutation of selected pairs of rows followed by the permutation of the same pair of columns will transform a lower triangular W matrice in the S matrix. The S matrix is associated with a standard ordering of the base moduli constants l-i,..,pon Let ri be the digit weight associated with pi, then sij - Iri. Irl 1 r, I. Irll-n ~rli' r Ij2... 1r21p Pr2l.... * - Theorem X. In the S matrix symmetric elements cannot both be non-zero. This and the condition (wqq,mq) = l for the diagonal elements is necessary and sufficient for the construction of an S matrix associated with a finite, non-redundant, weighted number system for relatively prime base moduli.'15

Proof.: Consider the symmetric elements of the W matrix wij, and ji where j < i. Since w j = 0 it follows that wij = wJi only if Wji = O. A permutation of the ith and jth rows followed by a permutation of the ith and'jth columns simply interchanges wij and wji. A permutation of the ith and kth rows followed by. a permutation of the ith and kth columns does not destroy the -relationship between wij and wji since wij replaces Wkj and wj replaces Wjk. Thus the permutation operations do not change the relationship between symmetric elements in the matrix. Every W matrix, and hence every S matrix, has at least (n-1) zero elements. In n(n-l) every n x n matrix, there are 2 symmetric elements. The specification of the diagonal elements and the n() symmetric elements- subject to the condition wij or wi = 0 and wij / wj except when wij = wji = 0 define a non-redundant, finite, weighted number system for relatively prime moduli. That every such number system is so specified follows from the fact that the n! possible W matrices specify every possible non-redundant, finite, weighted number system at. least once. Theorem XI. For a given set of relatively.prime moduli pl..-,n there exists n- n-l n Q =7 (7k) T 7C (i+ +j - 1.) k=l i=l j=i+l 16

distinct weighted, non-redundant, number systems. (Each number system is distinct in the sense that the set of weights rl,...rn is different for each number system.) Examples: 1i = 2, =2 = 3, Q 8 M1 = 2, 12 = 3, Y3 = 5, Q = 1344. Proof: Consider the S matrix: Each diagonal element skk can be as~ —" - ~n signed *(mj) different values. There are therefore { I(mk) difk=l ferent combinations of diagonal elements. The number of different values which can be assigned to the symmetric pair sij, sji is n(n-1) ti+Uj-l. The number of values that may be assigned to the ( 2 pairs of symmetric elements of the S matrix is obtained from enumeration of the elements in each column below the diagonal. Each element in the ith column is associated with pi. Each element below the diagonal has a corresponding symmetric element in the ith row. The modulus corresponding to this element depends on the position and is designated p.j where i < j < n. Hence there are n-l n 9T X (pi + mj - 1) i=l j=i+l different combinations of element values for the non-diagonal elements. The total number of different combinations of element values for the matrix S is n n-l n j'l i=l j=i+l 17

Corollary: If all moduli are prime then n-1 n Q = 7 7- (pi + j- 1) where % = 0. i=O j=i+l 18

LIST OF SYMBOLS GM the group of M integers 0, 1,...,M-1 Gmi the group of mi integers O, 1,...mi-l a subgroup of GM of order mi Xi.Gmi xi an element of Gm. (PiM) the greatest common divisor of pi and M IXlmi is the least positive residue of X modulo mi. This can be defined in terms of the greatest integer part. The symbol for the geatest integer part of X + mi is [-. Then XiXmi X -.mi[n ] a lb a divides b a/jb a does not divide b.(x) Euler's V function 19.