THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note COMPUTER NUMBER SYSTEMS: LINEAR AND NON-LINEAR CATEGORIES T. R. No Rao ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR September 1962

SUMMARY This report is intended to answer some fundamental questions such as: what is the structure of a number system in general? and how is this structure modified with linearity and redundancy? Their properties and usefulness with respect to the arithmetic operations have been derived. The discussion includes some non-linear types of number systems to enable the reader to understand the advantages of linear systems over others. iii

INTRODUCTION Here we may pose the question: what is a number system? To answer the question, it will be fitting to obtain the necessary and sufficient conditions a system must satisfy, A number system could well be considered as a method of representing and assigning names to the integers. Precisely, it is the structure of the system of integers. When our discussion is limited to computer application, we mean it as the system representation of a finite subset of the integers, namely ZM (integers modulo M, or ZM = (0, 1,...M-1). A NUMBER SYSTEM IN GENERAL A system of representation N will be a number system if and only if (1) N is a cartesian product of n tuples and is denoted as N = D1 x D2 x.-. x Dn where Di = (0, 1,...mi-l) Di is called the ith digit set, and mi the ith modulus. (2) N is closed under addition. x, yeN e== x + yeN (closure law) HOeN 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) a a mapping w: N + ZM w is a function of the n coordinate variables such that w(x + y) - w(x) + w(y) (mod M) for all x, yeN. 1

This function, which we will call hereafter the weight function, is the most significant property of the number system and is responsible largely in determining the arithmetic and carry properties of N. We will observe 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 c w is onto ZM. This is to say that for all aeZM ExeN such that w(x) = a, Also M > ~ mi \ N is incomplete. i=l Definition 2, N is a redundant system q _ Sx,yeN such that x 4 y and w(x) = w(y) The above two definitions can be combined to obtain the lemma: Lemma. A number system is complete and non-redundant w is an isomorphism. Definition 3. N is, said to be a linear system if and only if w is a linear function of n coordinate variables, the coefficients coming from ZM. Using the lemma, we can divide systems into redundant and non-redundant types. Definition3 will enable us to classify the systems into linear and non-linear types. Definition 4. A number system N is weighted < T pieZM for i = 1, 2...n such that for any X = (x,...xn)eN w(x) Z= 1 PiXilM the weight function for weighted systems is a linear homogeneous function. 2

Thus all the weighted systems are linear. However, all linear systems are not weighted. Some examples typifying the above statement are given in the next section. 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 are tables of representation of the code known as excess three representing Zlo(N1 + Zo1), and the four-bit reflected binary code for Zl6(N2 - Z16). It is well known that the excess three code has the advantage over the conventional binary (which is linear homogeneous) system, in that the 9's complement is obtained by interchanging O's and 1's. The advantage of the reflected binary code is that it is an unit distance code and any single error in transfers would cause a change of one in magnitude. However, we will soon find that the weight function of the excess three code is linear and non-homogeneous, and that of the reflected binary code is non-linear. 5

TABLES OF REPRESENTATION Excess Three Code N1 Four-Bit Reflected Binary Code N2 10; 4 X4 3 X2 X1 Z1 X X4 X1 2 0 1 0 1 2 0 0 1 1 3 0 1 o3 0 0 1 0 4 0 1 1 4 0 1 0 05 1 0 0 0 0 1 1 6 1 0 0 1 6 0 1 0 1 7 1 0 1 0 7 0o 0 o 0 8 1 1 8 1 o o0 9 1 1 0 0 9 1 1 0 1 10 1 1 1 1 11. 1 1, 1 0 12 1 0 1 0 15 1 0 1 1 14 1 0 0 1 15 1 0 0 0 -r ~" ~ I- -,,, i4

Ni = D4 x D3 x D2 x D1 for ti= 1,2. Dj = (0, 1) for j = 1, 2, 3, 4. The mappings w of N1 + Zlo N2 + Z16 are defined as shown in the table. Both of these mappings are (1-1) and onto, and hence the addition in N is defined by the following relation: for X, YeN X + Y = w-i [w(X) + w(Y) ] This shows that it is closed under addition and the existence of an identity is trivially simple. Therefore, these two codes come under the class of general number systems. We can easily find that the weight function for the excess three code is such that for X = (Xl1 X2, x3, X4) w(X) = 23X1 + 22x2 + 2x3 + X4 - 3. the coefficients 23, 22, 2, 1, M - 3eZM and w is a non-homogeneous linear function on the variables X4,...,X1 However, in the case of the reflected binary code it is not so straightforward to obtain. The suggested procedure is as follows: w(O, O, 0, 0) = 0 w(O, O, 0, 1) = 1 = p w(0, 0, 1, 0) = 3 = P w(O, 1, O, 0) = 7 = P3 w(l, 0, 0, 0) = 15 = p4 5

for an n-bit code w(O, O, 0,... 00) = 2i - 1 =i ith place. Next we denote the weight function for the n-bit reflected binary code as fn. Taking note of the alternate negation in the weights of the digits in the positions where l's are present, we can write as below: In the case of a 1-bit code fl = w(X1) = p lX = X1 And for a 2-bit code f2 = w(X2, X1) = X2p2 + Xlp1 - 2X2Xlp1 = X2p2 + (1 - 2X2)fl For a 3-bit code f3 = (X3, X2, Xl) = X3p3 + X2P2 + X1P1 - 2X3X2p2 - 2X2X, 1 - 2X3X1,p + 4x3X2Xp1 = X3p3 + (1 - 2X3) [X2p2 + (1 - 2X2)Xlp, ] = X3p3 + (1 - 2X3)f2 By induction or otherwise, we can obtain for f4 = w(X4... X1) = X4p4 + (1 - 2X4)f3 6

and fn = w(Xn.. X1) = XnPn + (1 - 2Xn)fn.= XnPn + (1 - 2Xn)Xn_lPn1 + (1 - 2Xn)Xn_2Pn_2 + e e e e + (1 - 2Xn)(1 - 2Xn.l)... (1 - 2X2)Xl1p which is clearly a non-linear function of order n. In a non-redundant system (w is a (1-1) mapping), the addition in N is defined by w. This is because that for X, YeN w(X + Y) = [w(X) + w(Y)]M (X + Y) = w-{[w(X) + w(Y) ]M and w-1 is (1-1) and, as ZM is an additive abelian group, so is N. More important is the property of all linear homogeneous systems that for all X,YEN w(X + Y) = w(xl + Y1, x2 + y2... Xn + Y) (*) This is trivial if xi + Yi < mi for all i = 1,... n. In which case X + Y = (xl + Yl, x2 + Y2,... xn + yn)cN. But in cases where for any i xi + Yi > mi, then (xl + yl,..., Xn + yn)4N. However, (*) still holds. w(X) = [xlpl + X2p2 +... + XnPn]M w(Y) = [Y1iP + Y2P2 +... + YnPn]M w(X + Y) = (X) + ) = [(x + yl)p +... + (xn + Yn)Pn]n = w(x1 + Y1,..., Xi + Yi',.., Xn + Yn). 7

In an excess three code which is non-homogeneous X = (x4, x3, x2, x1), Y = (Y4, Y3, Y2, Yl), XYeN1 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) + (xl + Y1) - 3 - 3 = w(x4 + Y4, X3 + y3, x2 + Y2, xl + Y1) - 3 Thus w(X + Y) 7 w(x4 + Y4, X3 + Y3, X2 + Y2, Xi + Y1) In the reflected two-bit binary code (N2 - Z4) X = (x2, x1) Y = (Y2, yx) X,YeN2 w(X) = 3X2 + Xi - 2x2X1 w(Y) = 3Y2 + Y1 - 2Y2Y1 w(X + Y) = w(X), w(Y) = 3(x2 + Y2) + (xi + Y1) - 2(x2x1 + Y2Y1) w(x2 + Y2, X1 + Y1) This only proves that digit-wise addition is possible only in linear homogeneous systems. CONCLUSION In linear homogeneous systems, we know that digit-wise addition can be carried out. Then if there is any overflow of the digit, we know the result is not in our number system. Therefore, it is necessary to transform the 8

result back into the system. In conventional arithmetic this is done by carry generation and then carry assimilation. To understand the complete algebraic structure of this process of addition, it is necessary to introduce the theory of modules and other notions of abstract algebra. Using the theory of modules it is proved that any linear number system can be given the structure of a difference module of the type M/S; where M is a Zm - module and S is a submodule of M. A set of generators of the submodule S placed in a matrix form will be called the carry matrix, and readily gives the carry propagation structure of the number system. For a full discussion on this topic, the interested reader may refer to the technical report on "Linear Number Systems" by R. F. Arnold, soon to be published by the Information Systems Laboratory, The University of Michigan. 9

UNIVR OF MIC AN 3 9015 03695 5972