ASD TECHNICAL REPORT 61-483 RESIDUE NUMBER SYSTEMS FOR COMPUTERS H. L. earner R. F. Arnold B. C. Benson C. G. Brockus R. J. Gonzalez D. P. Rozenberg The University of Michigan Octo-ber 1961 Electronic Technology Laboratory Contract No. AF 33(616)-7340 Project No. 7062, Task No. 706205 AERONAUTICAL SYSTEMS DIVISION AIR FORCE SYSTEMS COMMAND UNITED STATES AIR FORCE WRIGHT-PATTERSON AIR FORCE BASE, OHIO

Ci (

FOREWORD This report represents the results of research performed by the group at The University of Michigan under the direction of Professor H. Lo Garner. Concurrently, research on the same subject was being conducted at Harvard University under the direction of Professor Howard Aiken, and at the Lockheed Missile System Division under the direction of Dr. Richard Tanaka. There was a considerable exchange of information among the above groups during the course of the research effort. The efforts attained exhibit little overlap, rather they are complementary. A portion of this report was extracted from the doctoral dissertation of D. P. Rozenberg. His work was supported by this contract, and led to the Ph.D. ASD TR 61-483 iii

ABSTRACT The purpose of the research performed under this contract was to investigate the feasibility of residue number systems in their applications to digital computers. The problems of such an application are the ones of magnitude determination, sign determination, overflow, scaling, and division. These problems are not independent, but are found to be quite interrelated. A theoretical treatment of residue number systems is given which lays the foundation for a unified study of the complete problem. Treatments of an organizational nature are given which deal with multiplication, division, and scaling. The matter of correlating the theoretical and organizational studies to physical realizations involving networks is treated also. The question of whether the residue number system can be successfully applied to general purpose computers is still an open one. Their application to special purpose machines is considered both feasible and practical. ASD TR 61-483 v

TABLE OF CONTENTS Page LIST OF TABLES xi LIST OF FIGURES xiii LIST OF SYMBOLS xv CHAPTER I. INTRODUCTION 1 1.1 Introduction to the Problem 1 1.2 The Residue Number System 4 1.3 Theorems on the Basic Properties of Residue Number System 7 II. THE R SPACE 13 2.1 Basic Properties of the R Space 13 2.2 Linear Transformation and Matrix Multiplication in the R Space 24 III. CARRY FUNCTIONS IN RESIDUE NUMBER SYSTEM AND RELATED NUMBER SYSTEMS 33 3.1 The Carry Algorithm 33 3.2 The Borrow Algorithm and Complementation 37 303 Change of Basis 40 3.4 Multiplication 43 IV. THE MIXED BASE _NUMBER SYSTEM 53 4,1 The Mixed Base Number System 53 4.2 Overflow 57 4.3 Division in the Mixed Base System 60 4.4 Digit Fill-in 62 V. OTHER NUMBER SYSTEMS RELATED TO THE RESIDUE NUJMBER SYSTEMS 63 5.1 Partitioning Properties 63 5.2 Number Systems Allowing Sign Detection with Fewer than n-Carries 70 5.3 Generalization of Sign Detection for the Residue Number System 72 ASD TR 61-438 vii

TABLE OF CONTElNTS (lor i.r' ed) Page V:I oDIGIT I EODIS.iN.E PEA.? 77 6o, Codes E.ased up&on tL he Group St-ructure of the Eikt ipl.ic at ine Subogroup 77 6o2 Codes Based on Mudltipica'tion' as a Linear Transfo rmat ion 8 VII o DIVISION 87 7.1 Introduc tin 87 7 2 An. Approxi-mate Divisor. Meth;od 88 70 A Newton-Raphson Method 93 7o 4 Initial Approx:irmations 94 VIIIo TEE MULTIPELICA7I VTI COVERFLO.W PROBLEM 99 8.o1 tro.dut.....on 99 8.2 Application of ihe oSquare-Root Criterioen 102 8,3 Considerations of the Dout.e-ength System 104 8,4 mil tiplication 1.05 8, -5 Numher Format- and' Magr nitude C.omnparison 1.1 806 r7The Fo-ur Cases of Addition I 2 a. ",-( o: ~ion,3 1O2 8o7 Division 114 8o8 Carry Co^rpietion Sensirng 1.18 8 9 Postponed Scaling a-nd Special Parpose Machines 120 8, 0i A. Matrix -_n!ve rsio n ornp;L " r 122 8 1.1. A Method -recision C o par.ison 127 IX, I. LEVENAT' ). SIG N F DEEREMlAN!. IvETHODS 131 9 I- r l; roduc ti on 131 902 Residue 4to Mixed Bases Con.version Using Current Sterin Circuitry 1.33 903 uLmoiber of El:.ementrs i.n a Conversion Network 141 9,4 Selection of oduli, for Maximumm Economy 148 90o5 The. App.lication of Binary Coding to Conversion Procedures Usin::g Stored Tabies 149 9,6 General Stri.ucure of the Network 151 9,7 Determination of the lumber of Elements of the Network 152 9,8 The Necessary Number of Binary Bits 160 9~9 Systematic Procedure for the Development of the Network and for the Determination of the Number of Element s 162 ASD TR 61-458 viii

TABLE OF CONTENTS (Concluded) Page APPENDIX Io THEOREMS ON THE GENERATION OF SEQUENCES OF RELATIVELY PRIME NUMBERS 165 IIo A MIXED BASE AND MODULAR COMPARISON 169 IIIo SIGN DETERMINATION BY A IWO-DIGIT REDUCTION PROCESS 177 IVo COMMENTS ON PARITY CHECKING IN IHE RNS 187 REFERENCES 191 ASD TR 61-438 ix

LIST OF TABLES Table Page 1. Encoding of the Multiplicative Subgroup 79 2. Factorization Procedure 80 3. The Code M = 17, n = 8 84 4. Table of the Function F(mi) 143 5. Procedure for the Calculation of the Total Number of Elements 143 6. Number of Elements in the Conversion Network for Different Sets of Moduli 145 7. Number of Elements for Networks of the Type (1+M) 157 8. Maximum Carry and Carry Propagation Length 158 ASD TR 61-438 xi

LIST OF FIGURES Figure Page 1l An adder for the M = 17, n = 8 code. 84 2. Multiplication in the floating point RNS. 109 3. Step 3 of the magnitude comparison. 112 4. Addition in the floating point RNS. 113 5. Division in the floating point RNSo 115 6. Carry completion. 119 7. Block diagram of a computer. 124 8. Blcok diagram for scaling operation. 128 9. Switching network for residue to mixed basis conversion network (1st part). 136 10. Switching network for residue to mixed basis conversion network (2nd part). 137 11. Simplified schematic of the complete residue to mixed basis conversion network. 139 12. Block diagram of the conversion network from the residue system to mixed basis. 140 13. Variation of the number of elements in the conversion network. 146 14. Switching network for sign determination for a residue system with 3 moduli. 153 15. Block diagram of sign determination network for a system with 4 moduli. 154 16. Carry matrix for three addends and corresponding network. 156 17. Carry matrix for four addends and corresponding network. 156 ASD TR 61-438 xiii

LIST OF FIGURES (Concluded) Figure Page 18. General structure of the carry determining network for the first column of K binary bits. 157 19. Carry determining network for the (2 to 3) case. 159 20. Carry determining network for the (3 to 4) case. 159 21. Determination of the number of elements in the carry network. 163 ASD TR 61-438 xiv

LIST OF SYMBOLS [x] The integer part of x (*) (Ix The fractional part of x (*) (ab) = c The greatest common divisor of a and b is c (*) Ix m The residue of x with respect to m a b; (a/b) a divides b; (a does not divide b) a - b mod m a is congruent to b modulo m a - b a is isomorphic to b a " b a is on the order of b (is approximately equal to b) x* x7 The modular complement of x G: R - Sm G is a linear transformation from Rn into Sm a -> a' a corresponds to a' Two levels of switching elements Switching element {-^ I- Delay element -( - Binary Encoder Modulo five operation (*)The brackets are also used at times to indicate association. The square bracket is used also to indicate a matrix. The particular meaning should be clear from context. ASD TR 61-483 xv

CHAPTER I ITTRODUCTI ON 1.1 INTRODUCTION TO THE PSROBLEM The aspects of the residue class of the number system which makes this class of number systems suitable for high-speed computation has been long known to mathematicians. The first consideration of the residue class of numbers for a computer system is due to Valach. This initial work was soon followed by a 2 3 paper by Svoboda, and later a paper by Valsch and Svoboda. Svoboda must be given credit for the most fundamental and comprehensive study of the application of residue class to practical computing machines. In his paper, "Rational Number Systems of Residue Classes," he considers both fractional and integer number systems' The residue number system is most naturally interpreted as an integer system, though the fractional interpretation allows greater flexibility with respect to the problem of scaling. The paper by Garner considers only the integer interpretation of the residue nmber system and suggests a unified approach to the problem of sign detection. The first part of this research report is a continuation of the study of the vector-space approach to the sign detection problem. Carry propagation accounts for the major portion of execution timre in a conventional arithmetic system. The residue number system, based on the algebra Manuscript released by the University of Michigan, October 1961, for publication as an ASD Technical Report. ASD TR 61-483 1

of residue classes, permits addition and multiplication to be performed without the existence of carries. The main advantage to be gained from the residue number system follows from the fact that it should be possible to execute multiplication as rapidly as addition. The usefulness of the residue number system for general purpose computation is still an open question. However, there exist many favorable applications of a special nature. Cheney5 has designed a digital correlator based on the residue number system and has estimated that a correlator of similar accuracy, based on the binary system, would have been 10 to 100 times slower, depending on whether the organization were parallel or serial. The residue number system has several characteristics which have prevented the adoption of this system for general purpose computation. The problems of sign detection, the detection and handling of additive and multiplicative overflow, and division are of extreme practical importance. In this report the algebraic and numeric properties of the residue number system are investigated in order to determine algorithmic solutions for the above problems. Considerable attention has been given to the nature of possible algorithmic solutions. This is, in many cases, more important than the actual algorithms. In the remainder of this chapter, the residue number system is shown to be a ring. Various well-known ring theorems are interpreted in terms of the residue number system to provide fundamental information concerning the problems of sign detection, the representation of negative numbers, and division. Other theorems provided in this section relate to the construction of residue number systems. ASD TR 61-483 2

In Chapter II, the basic algebraic structure required for the investigation of the residue number system and other number systems is developed. In Chapter III the carry structure of the class of non-r edundant lnumber systems is determined. It is shorm that the residue nrumber system is a member of the class of carry-type ntumber systems' focr Thich the carries are congruent to zero modulo base of the number system. In Chapter IV, the characteristics of the mixedbase number system are determinedO In Chapter V, particular attention is given to the problem of sign detecticno It is shown that the only non-redundant number system with simple sign detection characteristics is the mixed-base number systemr Trhis fact is used to establish a general definition for the sign detection process. In Chapter VI the problem of multiplication for a residue number system is studied. iT particular, two different multiplication schemes are presented. The first is based on the decomposition cf the ring structure. This obtains a simple multiplication algorithm at the expense of complicating the addition algorithm. The second approach uses redundancy to speed the multiplication process and. is termed A-codingo Both of the techniques offer advantage over conventional residue coding when the moduli are large. In Chapter VII, division for a residue number system is considered. Two division schemes are presented. One is based on a Newton-Raphson iterative procedure, while the other depends on approximation to the integral part of the quotient. In Chapter VIII specific attention is given to the problem of multiplicative overflow. Various schemes are considered and a special purpose application of the residue number system is given. In Chapter IX the problem of sign detection is considered in terms of physical realizationo ASD TR 61-483 3

1.2 THE RESIDUE NUMBER SYSTEM As a preliminary step in the introduction of the residue -:umber system9 the ring iM of integers modulo M will be discussed.6 The elements of the ring are the integers 0, 1i 2, 0. M-l. Ring addition and ring multiplication of two elements of IM are performed by reducing the conventional sum and product modulo M. That is, the sum or product is divided by M and the remainder is retained as the result~ Thus, for example, the ring I6 cQnsists of the integers 0, 1, 2, 3, 4, 5o Dividing the ordinary sum of 4 and. 5 by 6, one obtains 3 for the remainder. Therefore, in Te, 4+5 = 3. Similarly 2+4 = 0, 2-2: h, and 4.2 = 2. The proof that iM is actually a ring follows from the fact that in the division of an integer by M, the remainder is unique. The complete proof may be found in the literature. The order of IM is M. Consider the ring I of integers and the ring IM of integers modulo M. An arbitrary element m of I determines a unique element m of IM; namely, the remainder upon division by M. If one denotes the correspondence of m to m by m -~, m, it is clear that if mi - n, m 2 mf- m2, then m+m2 ~ mi+m2 - m +ma2 and mm m2>ml1m2 = m1ms2 Therefore, the correspondence between I and IM is a homomorphism. Fixed point digital computers do not operate upon the ring, I, of integers but rather on the ring I-. If one thinks of the radix point as being on the right, then the largest number which can be represented is M-lo That the homomorphism is a many-to-one mapping is painfully apparent when overflow occurs arnd. the most significant digit(s) are lost. Fortunately, one can detect such an overflow by sensing the carry from the most significant digit position. The ASD TR 61-483 4

ring IM possesses an additive inverse of every element. If m is an element of IM, M-m is the additive inverse Thus we map the integers less than M/2 onto the elements of iM less than M/29 and the negatives greater than -M/2 onto the remaining elements of IMo Thus the sign is readily determined and thereby magnitude comparisons can be performedo Since one can perform overflow detection, sign determination, and magnitude comparisons, division is possible. Let SI and S2 be two rings and consider the ordered pairs of symbols (s5n,2) where sieSL and s2eS2. If one defines addition and multiplication to be (sls2) + (tlt2) = (s1 + tl,s2 + t2) and (sls2)(t,t2) = (sltl,s2t2) this set of ordered pairs becomes the ring S termed the direct sum of S1 and S2 and denoted S1 6 S2. In the above definition the operations si+ti and siti are the ring operations of Si. An especially important theorem is the following: 6 Theorem I. If a ring S has positive characteristic n = nl n2 where nl and n2 are greater than 1 and relatively prime, then S is isomorphic (-) to S1 0 S2 where Si is a ring of characteristic ni(i = 1,2). This theorem states, for instance, that 16 is isomorphic to the direct sum I2 e I3 with the following mapping: C -- (0,O0) 3 ~-> (lo0) 1 <-> (1,1) 4 -> (O,1) 2 <-i (0,2) 5 -> (1,2) Theorem I may be extended as follows: Theorem II. If the ring IM has positive characteristic M = mlm2...mn ASD TR 61-483 5

where the mi are integers greater than 1 and pairwise prime, then IM -rt ImD2 i~ I. ( m Proof: If n = 2, the result follows from Theorem I. Assume the result for n = k and consider M = mlm2...mkmk+l. M may be rewritten M = m1m2...mk, where m = mkmk+l. Thus we have IM iml I m2 mk but by Theorem I, mI mk Imk+l Therefore, IM = Iml M2 I —. 3 Imk+l.Thereby, the conclusion is proved. Theorem II completely defines the residue number system. Elements of IM are mapped into n-tuples of the direct sum (elements of the residue number system) according to the following scheme: x 4> (x mod ml,x mod mi2,...,x mod mn). (1-1) If x (-> (xl,x2,... Xn), then x + y -> (xi + y1mod m...,xn + ynmod mn) and x ~ y - l (xlylmod ml,...,Xnynmod mn). It is clear from both the example following Theorem I and Expression (1-1) that the components of the residue representations have no positional significance. ASD TR 61-483 6

Con sider the fo1lrlow ex ampies of aflitions in the ring I210 with m1 - 2 ms = r39. a 5 ^ rl 7m ~ \a) 209 -+ (i,2,,69 (b) 209 -4 (1,924,6) 21 — 7 (C, I) 10t (020,4,6) (c) 210^ <~ (1,0,0,0) 2 c-> (1,2j,69 ) 120 - ( 09o )1 ) 162 7- (1,22,26) 015 — 2 ( 1,0,0,) 185 ee (0,1l0,0) In example (a), the sum prod.ces an overflow and each component ring indicates an overfloTo The s-um in (b) overflows but only one component overflows. In (c), overflow occurs but the component subrings do not indicate overflow No overflowT accompanies the addiition in (d), howeTve r overflow is present in each component. These exaimples indicate that overflow in the component subrings is unrelated to overflow,of.o Similar statements may be made concerning multiplicative overflowo 1o3 THEOREGMS ON THIE BAi3tC PROPEiRTS ES OF RESi LTJE UMER SYSTEMS The'eorem T1. T.he- peTriod o(f a residue class,number system is equal to the least common mulltiple (cm) of the aseso Proof. Given bases mi ooogmno Assume mi jmj, ijthe then the digits associated with modulus mirnj have a period equal to mj. Thus, min has no effect on the period and may be dropped from further consideration. The process may be continued for remaining bases until for all pairs milmj, ifj. The period is n given by the product M =k i mn.. The product is the lcm of the original bases since, by the f'undamental theorem of arithmetic, the product of the bases is ASD TR 61-483 7

P P1i P Pi P2 p P2P.f..lPm the lcm of P, denote by <P>, is <p> = p max p max.p P max, Obviously, <P> = M. Corollary: The maximum length period is obtained when the bases are relatively prime by pairs. i.e., (mimj) = 1. Theorem IV. The replacement of all residue digits, ri, associated with base mi by the modulo mi productl ri mm where c a 0 and a < mi, yields a number system with period M', where M (C,mii) Proof: 1. N - aimod mi 2. oc - = aimod mi'N Ca i [ mi 3 (,mi) = (ami) mod (cmi ) mi M 4. M' = ml.. on = 1 (Ogmi) (Oami) Theorem V. The successor of X an element of a residue number system R may be defined as X' X+ X R X c R e R The period of R is given by M M' = (M, ) ASD TR 61-483 8

Proof For the standard residue number system X' = X+ 1 Multiplication by 5 yields XI = X+5 Hence, the change of successor is equivalent to multiplication of each element of the residue code by the residue representation for 5. This situation is covered by Theorem IV. It is necessary to verify that (M,&) = (ml Qal).o. (mnvOQn) where 5 is represented in residue code by al,..,an. But this is obvious since (M,5) = (m1,5)... (mn,5) - (mei,) o (mnon) (ala2,b) = (alb)(a2,b) _ (al,a2) = 1 Theorem VI. Isomorphic mapping between the ring of integers IM and the residue number system consisting of Im,..Imn exists for any successor value n 5,(5M) = 1 if the operation is addition. If the operation is multiplication, the isomorphic mapping exists only if 5 = 1o Proof: sa + b = (a + b) but (5a) x (5b) i 5(ab) except when 52= - mod M, 5 -= 1 since (5,M) = 1. Corollary: Isomorphic mapping is obtainable between IM and Im,...,I if each multiplication is followed by a corrective multiplication by S. The results of Theorem VI, and the corollary indicate that the integer interpretation is the natural interpretation for the residue number system. ASD TR 61-483 9

Any other interpretation will require multiplicative correction to preserve the interpretation. Theorem VII. Consider the residue digits ri and r. associated with bases mi and mj; then the operation ri-rj m partitions the set of mimj residue digits into j subsets. Each subset has i elements. The subsets are ordered modulo mi. Proof: 1. N - rimod mi N - rjmod mj 2. N = ri+miti N = rj+mjtj 3. ri-rj = mjtj-miti 4. ri-rj = mjtjmod mi (ri-rj)/mj - tjmod mi Note: If N < m.mj then t. < m and I(r.-r)/m = t 3 31i j j3mk Example: ml = 2,m3 = 7 rl r2 -rl-r21l Ir2rll m2 41 r2-rl m21m 0 0 0 0 0 1 1 0 0 0 0 2 0 2 1 1 3 0 2 1 0 4 0 4 2 1 5 0 4 2 0 6 0 6 3 1 0 1 6 3 o 1 1 1 4 1 2 1 1 4 0 3 1 3 5 1 4 1 3 5 0 5 1 6 1 6 1 5 6 ASD TR 61-483 10

Theorem VIII. Consider the ring R. For every a and. b elements of R a*b* = ab a*b = (ab)* where a* is the additive inverse of a definad as a*+a = 0. Every element of a ring has a unique additive inverse. This is usually given as one of the postulates of a ring. This postulate and Theorem VIII taken together indicate two possible correspondences between the elements of the ring, the inverse elements of the ring and the positive and negative signs. The usual convention specifies that an element interpreted as an additive inverse of a represents -a. Thus the additive inverse provides a code for distinguishing positive and negative numbers. The code is valid for'both addition and multiplication but is useful only when the ring is partitioned into elements always interpreted as magnitudes and elements always interpreted a.s inverses, and a simple means exists for determining the correct partition for a given element. Theorem IX. For every a and b; b / 0, elements of a ring there exist x and y such that a = bx + y However x and y are not unique. Theorem X. For every a and b; b b 0 there exist a unique x and y such that a = bx+ y if y < b. y < b may be interpreted in terms of the successor concept. Let y = a Znd b Then y < b if lrj Ilm m is the cardinality of the ring. Theorem IX and Theorem X provide some insight into the nature of the division algorithms associated with any finite number system. The residue number ASD TR 61-483 11

system is included in the class of finite number systems. Observe that a - y mod b and if y < b then alb = y Furthe rmore a-balb A T-b 1alb = a = x ASD TR 61-483 12

CHAPTER II THE R SPACE There are many aspects of the residue number system which suggest the appropriateness and usefulness of the vector space model. This approach is pursued in this chapter. It will be shown that strictly speaking the residue number system is not a vector space. However, a development including much of the conventional vector space concept is a useful tool for the investigation of the residue and related number systems. The appropriate axiomatic system has been called the R space. The basic properties of the R space are developed in the chapter and are applied in the next three chapters to the basic problems of the residue number system. We have found no property of the residue number system which cannot be validated using either the R space approach or the number theoretic approach. However, depending on the nature of the problem, usually one approach is more suggestive 2.1 BASIC PROPERTIES OF THE R SPACE Let any two residue representations be x = (XigX2,...nxn) Y = (Y1,Y2,i ~,Yn) then x+y = [xl+yl(ml),...,xn+y(mn)] where the mj are pairwise relatively prime. The component xi is said to be associated with the base modulus mi. The residue numnber system representations from an additive Abelian group which is denoted by R. From S, a ring with identity, we select the integers and define multiASD TR 61-483 13

plication by a scalar to be ax = [axi(ml),...,axn(mn)] With these definitions it is seen that a. axcRn, b. a(x+y) = ax + ay for a(x+y) = (a[(xl+yl)(m) ](ml),..,a [(Xn+Y n)(m) ](mn)) = ([(axL)(ml) + (ayl)(ml)](ml),..., [(axn)(mn) + (ayn)(mn)](mn)] = ax + ay c. (a+b)x = ax + bx since (a+b)x = [(a+b)xl(ml),...,(a+b)xn(mn)] = [(aXl)(ml) + bl(ml)](ml),..., [(axn)(mn) + bxn(mn)](mn)) d. (ab)x = a(bx) for (ab)x = [(abxl)(ml),...,(abxn)(mn)] = a[bxl(ml),..,bxn(mn)] = a(bx), and e. All elements of Rn are uniquely expressible as linear forms aleL +... + anen by means of a fixed basis elements with O 0 ai < mi where ej has one for its jth component and zero for the other components. The five properties which must be satisfied for Rn to be a n-dimensional vector ASD TR 61-483 14

space a, b, c9 d above, and e v All elements of Rn are uniquely expressible as linear forms alul + o.o + asun by~ means of a f ixed "basis eiemen ts" ui o Un and ai S. This property is not satisfied9. and thus RP is not a, true vecto. spa.e. Tie: pseudo-vector space R-1 will be callecl the R-space and all vector spa-ce terms which follow will have an interpretation in. the R-space whnich is analogous to the vector space definitionso Consider the set of vectors <ai~. o,> wi-th each ai having n components. Form a squlare array of the components by placing the com-ponrent's of a. in the ith rowo If this array can be made triangular (specifically a lo'ner triang-ular array) by reordering rows and coui-mans the set <Cai o O:> is termed, sem - triangular and the reordered set termed triangular. Theorem XIa If the set {l, ^o OOa ) is triangular and the elementr s on the principal diagonal are relatively prime to the associated base moduli., then any linear form aL a + a22, - -. + a-,C w.here the ai are integers can be uniquely expressed as n L ciai where 0 < ci < mio i =l Proof~ kncn Knn anmod mn where kij is the jth component of ai * Thus cn - an mod mll since mn is relatively prime to k,, and 0 c, < mn is uniquely determined. *a - b mod m (a is congruent to b modulo m) if and only if mj a-b (m divides a-b or a - b + kmn). ASD TR 61-463 15

Assume the conclusion true for cj for j = m, m + l,...,n and also that these cj have been determined and consider the congruence km-l,m-lCm-l + km,m-lCm +. - + kn, m-ln kmil,m-laml + kmmlam +... + kn,m-lanmd m_1By adding to both sides of the above congruence the additive inverse of (kmm-lCm +. + kn m_lCn)mod mm_l, this congruence takes on the form kml,mlCm_l = A mod mm-l_ Since (km-_l,m-lmml) = 1, Cm-1 is uniquely determined mod mm-l and 0 < Cml < mm-l Theorem XI is of key importance for it allows us to abandon the ring S and to concentrate our attention on linear forms of triangular sets of vectors; n namely, Z ciQi where < i, ~'.,~^n> is triangular and 0 ci < mi. Except i=l where indicated, the following discussion will be limited to sets of triangular vectors and linear combinations with restricted scalars. Definition: The vectors c,...,cn of a triangular array are linearly independent if and only if c la +... + Cnn = 0 where 0 < cj < mj implies cl = c2 =... = cn = O. Otherwise the vectors l,...,n are termed linearly dependent. Theorem XII. The triangular set of vectors < a1oy2,...o, n > is linearly independent if and only if each element on the principal diagonal is relatively prime to the associated base modulus. *The greatest common divisor (d) of a and b is written (a,b) = d. ASD TR 61-483 16

Proof Consider the ecuation cO1 + cCo + c. o f2-i) Equation (2-2) is eouivale-nt+ to e follwing smultaieous linear cotngrue -,ckc c+ k._ c = 0 rmo d m for iL = __, i + t hi o rkn _. _ O S. l ~ For knrCi C 0 mo. mr to,;-ield r-.te u:rique sclu, ltc c-, 0, it is sufficient that (knnpmn) - Assume (k:,rm) I and. c = 0 for i 2; + 1, + 2,.,. The th congrue<nce tbecomes?kc - 0 m0od nm arnd. c = 0 is'te unique solutio. This prov-es the suffiiciency,of thee h.ypowti esiso Assume r to be the least nd.ex for which (. rl) lo Let c- C for i > r. The above congruence.s become k:cr ~ - 0 0n m.d (2-2) r kiici + L kji 0 mod. mi for i r-lr-2.oo l Ji i+l Congruence (2-2) -aay'be sol-ve, Vwith c^ 0C Since (k i) = or i =r-1 r-2..o.,I, the remaining congruerces assunmt me e form, The ondition (i ) < ganee the existence of a solution The condit-ion (kilsrn ) - cr i' <r gJL.ara..!te. e existenlce o f a s,-Iultion for each congruenceo This completes the proofo Definition: A set of vectors {az ~o0o._o.} 2ris said to span PR if and. only if there exists a set of coefficients ci in the range 0 ci < mi satisfying the equation ASD TR 61-ot83 1 7

n Z ciai = ri i=l where ri is any residue number. Theorem XIII. For a triangular set of vectors < CGl,..,a > to span Rn it is necessary and sufficient that each element on the principal diagonal be relatively prime to the associated base modulus. Proof: The existence of solutions ci to the following congruences will be shown knnCn anmod mn (2-3) n and kiici + j1 kjicj - aimod mi for all ai in the range 0 ai < mi. The necessary and sufficient condition for the existence of a solution to (2-3) is (knn,mn) lan Since an (an integer) will range 0 ~ an < mn, it is necessary and sufficient for (knn,mn) = 1. Assume that solutions ci exist for i > Q. These solutions are substituted into the ~th congruence yielding an expression of the form k1gcA + D ammod mi or k~c~ -- a, + E mod mi Again (a2 + E) mod mE will include all integers in the range 0 through mi-l. Thus to guarantee solution it is necessary and sufficient that (k~,m)) = 1. The proof is complete. Corollary: The triangular set of vectors <l,... > is a spanning set of Rn if and only if it is an independent set. Definition: A basis of an R-space is a linearly independent set of vectors ASD TR 61-483 18

which generate the R-spaceo Theorem XIII may be rephrased in more conventional terms as follows: Theorem XIV. For a triangular set of vectors <al,...,> to be a basis of R it is necessary and sufficient that each element on the principal diagonal of the array be relatively prime to the associated modulus. Theorem XV: If l,....,a forms a basis for Rn, then every vector eRn has a unique expression C = Xlal + X22 + + Xnn, 0 < Xi < mi. Proof: It will be shown that the congruences which must be satisfied for the above expression to hold will provide Xj which are unique modulo mj. Let = (blb2,.,bn). The first congruence is xnknn -n bnmod mn. Since knn and mn are relatively prime, xn is uniquely specified modulo mn. Assume Xm+lxm+2),.. xn have been uniquely determined. Then to be considered is the congruence kmmXm + km+l,mXm+l +... + kn,mXn bmmod mm. Add to each side the additive inverse modulo mm of (km+l,mxm+l +.. + kn,mxn) to obtain km,mXm - B mod mn. Since (kmn,mm) = l,xm is uniquely determined modulo mm. Theorem XV states that every residue number has unique coordinates relative to a given basis. Thus every basis serves to define a number system related to the residue number system. It is now shown that triangularity is a necessary as well as a sufficient condition for a nonredundant number system. ASD TR 61-483 19

Theorem XVI. If the set of residue numbers, <Kc)2,...n>, spans Rn n (i.e., rcR n (aia) aixi = r) then the set is triangular. i i Proof: If (ala2,..,a n) E 0 alc1 + a2Co +... + anCn (bjb2,. o,bn) < bill + b202 +... + bnOn From the properties of Rr it follows that aiji + biai = (ai + bi)0i then (aicj + a2%c +... + anc) + (blCX +... + bn%) = (al + bl)aO1 + (a2 + b2)c% +... + (an + bn)cn = A dall + d2c2 +... + dna+n = S Consider the form di = miqi + ri in which miqi is an integer; then n miqi Z eijOj and n n n S = riai + ZE qjejiai i-l " iJJi=l j=l n i n ) -=! (r + q.e a i=l\i j=lge ij The above expression yields the residue number which is cqngruent to the sum S modulo M; It is not, however, the required expression for the sum. The desired sum has restricted coefficients, O0< ai < mi. So consider the above expression to be 1 1 1 1 U S = d.^ l + dd2oQ + -.. + 2. d n 2 This sum is manipulated to yield S, and the process is continued until k+l k S = S. It will be shown that the existence of this sum is equivalent to ASD TR 61-483 20

triangularity. The next step of the proof will be to show that no carry cycles can exist. Assume that carry cycles of length k, when k n, exist. That is ek,k-l 0 ek-l,k2 # 0 ii,k 7 0 and ejk = 0 for j > k Consider the element (xi,x2...,xkO,0,0,0), where xi < mi-l. Since Rn is an additive Abelian group, the additive inverse of the above element exists. Assume it to be (Yl,Y2,2-,Yn) Further it is known that the sum (X1,X2,...,Xk,...,0,0,0) + (Yly2,. -,Yn) = (0,0,...,0) No carries can enter this initially from outside the group of k under consideration. Case I. k = 1: here, eii f 0; eji = 0, j > k. A. xi + i must produce a carry into the first position, thus the first component of the sum is non-zero. B. If the sum, reduced modulo m, plus the carry is mi, there must be a carry in the first position and the result is non-zero. Case II. The general case. A. It will be necessary to have a. Yk = xk to get a zero in the kth position. This will produce a ASD TR 61-483 21

carry to (k-l)th position. b. If jth position produces a carry, the (j-l)st will also produce a carry, for the (j-l)st unreduced sum is non-zero and will have to be made congruent to zero by the addition of an appropriate yj -l It can be seen that there will be at least one full cycle of carries. B. Assume we have had I full cycles of carries. a. The sum of carries plus the previously reduced sum is in the kth position. This is non-zero. If this sum is < mk the desired contradiction has been obtained. That is, the existence of the additive inverse has been contradicted. A carry must propagate from k to k-l, otherwise the inverse does not exist. b. Again it may be argued that, if the jth position produces a carry, the (j-l)st position must also produce a carry. Therefore, there are I + 1 carry cycles and the carry process does not converge; the proper sum is not obtained. This is the desired contradiction which proves that it is not possible for carry cycles to exist. From the fact that carry cycles of length 1 cannot exist it can be seen that the principal diagonal of the carry matrix consists of zero elements only. Since there can be no carry cycles of length 2,eij 0 =~ eji = 0. The next step in the proof of the theorem is to show that the number system must have a carry matrix which is a lower triangular array with zero elements on the principal diagonal. 1. Initial Step. There must be at least one column which is composed ASD TR 61-483 22

entirely of zeroso If this were not the case, there would be carries into every position; and thus carry cycles 2. General Stepo A.ss-le there is one column with at most k-l non-zero elements for k = 1,2,.o o, o There is a columrn with at most ~-1 non-zero elements. The array may be rearra:nged by placing the column, with k non-zero elements in the old array, into the kth column of the new array for k = 1, ~+1,..,n. The rows are interchanged in a similar manner, giving 0 x C I 0',. x x 0 ~an~ let e Consider a non-zero elerment ei,1 above the principnl diagonal in the (Q-l)st column. Since eij / 0 implies eji = 0; row i may be interchanged with row Q-1, and columr. i with col'urmn 1- w-hile retaining e-i, ~1 = 0 and ei e-i = 0. Thus all non-szero elements are placed below the principal diagonal. To complete the proof it is onl'y necessary to note that since the base moduli are pairwise relatively prime, multiplying a vector by the ith baSe ASD TR 61-483 23

modulus can create a zero only in the ith position. Thus a carry matrix with all non-zero elements below the principal diagonal implies that the set < l, * 2.ooOn > is triangular. 2.2 LINEAR TRANSFORMATIONS AND MATRIX MULTIPLICATION IN THE R SPACE Definition: A linear transformation G: Rn - Sm of an R-space Rn into an Rspace Sm is a transformation which satisfies ( + n)G = CG + G (cj)G = c(aG) Theorem XVII. If Oll,..,cn is any basis of R and.,i.. are any vectors in Sm, then there is one and only one linear transformation G:RnSm with aoG = 71 cnG = n This transformation is defined by (x1la +... + xnG = x X272 ++ + Xnyn Proof: Let A = (a,.. ~ be a basis for Rn and B = (1 m,.,im) be a basis for Sm. then liG y- 7 onG = 72 UOnG - Yn. whe re yi = ails +... almm ASD TR 61-483 24

for i = l,..o,n. If [ = (Xi,oo.xn)AsR then = xjaz + o. + XnQn, from which results oG = xl(aiG) + x2(%0G) +. + xn(anG). By substituting for (aiG), one obtains x= x(a113 + - + almsm) + x2(a2131 +... + a2mPm) + xn(anii + * + anm.m)y and by rearranging terms, CG = (xlaii + x2a21 +... + Xnanl)3 + (xla12 + x2a22 +..+ + xnan2)2 + (xialm + x2a2m +..o + Xnanm)mBy Theorem XI the image ~G can be uniquely expressed m. di P where 0 < di < mi and, therefore, GeSm and the transformation G is a linear transformation Rn+sm. ASD TR 61-483 25

Let = (Y1,. * yn)A then = Ylal +... + YnanThus ~G = yl(alG) +.. + Yn(anG) = y +Yl +... YnYn + n = (X1 + yl)C1l +.o. + (xn + Yn)Cn (5 + n)G = (x + yl)aG +... + (xn + yn)OnG =(xl + yl) 71 +... + (Xn + Yn)7n = XlYl +... + x7n + YlY1 +. + YnYn and c( = cxll +...+ cx*nn (c )G = (cxl)clG +... + (cXn)(CYnG) = cx7Yi +. + Xn7n = c(G). Thus the transformation is linear. It is to be noted that it is not necessary that the set (71,...,Yn] be a triangular set. Since every vector in Rn can be expressed uniquely as xlal +.. + xnn for 0 xi < mi, the transformation is single valued and, therefore, no other transformation from R into S yields BiG. The proof is complete. Let A = (c.,...,cn) be a basis for Rn and B = ([,... - m} be a basis for Sm. We then have the equations CSlG = all-1 +..e + a26 ASD TR 61-583 26

O2G = a21zl +.*. + a2mPm OnG = ani +i +.o + anmrn The form of these equations suggests writing the square matrix alla12 *2 aim a2i1 a~2m a = ani ao mi If Rn, Sn, and Tn are three n-dirmensional R-spaces, G is a transformation n n of R into S, and H is a linear transformation of Sn into T. The product of the transfornations is defined a((GHf) = (-G) Theorem XVIII. If the product of two transformations is defined, then it is a linear transformation. Proof: Let G and H be linear transformations whose product exists, let c be a scalar, and let 0,, cU be vectors in the domain of G. Then we have (c, + 2 )(GH) = [(x, + cx)G]H = [(c1G) + (ac(G)JH - (o1G)H + (o2G)H and (cOCX)(GH) = [(caO)G]H [C (c i \; )] I -:: (:K-ii) ].H ASD TR 61-483 27

Muultiplication of linear transformations has been dBefined and. will now be used as a guide to defining multiplication of matrices. To this end let Rn, Sn and Tn be three R-spaces of dimension n with respective bases A - u i,. ) B = (3i ^~~1n) and C C = {71^.o7)}. Relative to these bases G has the matrix a and H has the matrix 3. Consider the matrix P = |iPij I| of the product transformation J = GH relative to the bases for Rn and Sn. A development of the rows of P will be given in terms of aij and bij clG all:L +. o + aln3n OcG = a21Ii + o + a2nn nG = a= nl + + ann nr and 5mH = bY17, +..+ bln7n H = b21171 +... + b2Y n PnH = bn1l + o o + bnn7n Thus (caG)H = all-(1H) + al2(S)2H) +... + a(in(H) = all(b171 + bl72i +. o + b n7n) + al2(b21T7 + b2272 + -.. + ban7n) + a n(b7, +b bm7 +.. + bnn^ n). ASD TR 61-483 28

Therefore n n (%7GHT) = alkbkl, aikb.,, L akbk i. k/^1 k=l k=1 Similarly /n n (CY2GH) a b a b a b (CocE) -- C a2kbik 1 a2k k2'' 2kbkni) k~ ~k=-l k=1 / Thus /n n n (UnGH) a a (cinG:) = Zn abklZ=bl;ankbk2p. n Jbkfk k=l- /l k The above equations are preliminary results in the determination of the rows of P. Each of the linear forms indicated above must be expressed as linear forms with restricted coefficientso The linear form with restricted coefficients corresponding to (oiGH) constitutes the ith row of P. The justification for restricting the discussion to the multiplication of matrices which correspond to linear transformations from n-dimensional R-spaces into n-dimensional R-spaces is the projected application of such multiplication. The principal application will be in the change of basis operation (conversion from one number system into another). In this application the linear transformation is an automorphism from Rn onto Rrn In the interest of completeness, the result for the most general case will be given. Let RX, SW, and Tz be three R-spaces with respective bases A =_ (0 - o,.ox} E - O B i~ * 3 W } and C - 7,* o- z) The linear transformations G and H are defined by w i^G = E aiv (i = 1,2,..,x), v=i ASD TR 61-483 29

and z ikH= Ebiuyu(i =,2,...,w). u=l Therefore, /w w w z (CiGH) = Z.airv)H = Zaiv(SvH) Zaiv Zbvuu v =l v/= v=l l z w w w w Z aivbvuu = aikbkl aikbk2.. 7 aikbkz u=l v=l k=l k=l k=l The above linear form when expressed with restricted coefficients constitutes the ith row of the product matrix. If A = |laijII, B = llbijll, and C = llcij U are n x n matrices relative to the natural basis, the product (AB)C is developed in the following manner: AB = E = Ileij 1 relative to the natural basis and the ith row of E is obtained from the linear form /n n n (7 aikbkl, Zk aikZbk,* klaikbkn\k=l k=l k=l Since this linear form is to be reduced relative to the natural basis, the ith row of E is aikbk )(ml) (aikbk2 (m2). * aikbkn(mn)I The product (AB)C = F = Ilfijil is similarly developed and the ith row of F is n n N L. eaikck (ml1)..., Zeikckn (mn =-1 1 / - J K zairbb (mkicki'>(m1)... <[k~l [rairbrk) (mk) Ck& (mn) ( 2-4h) Consideration of the product BC gives rise to the following linear form with ASD TR 61-483 30

restricted coefficients. n k(lbikcki (ml), ~ ~, bikCkn) (m \k=l / \^k=l / Also A(BC) = D = Ildij{l where the ith row of D is n n n n ai rkk (,, air b rkCk (m) airkkn mn) (2-5) \r=l k=l r=l k=l As shown by equation (2-4) and (2-5), multiplication of matrices associated with the residue system is not associative, for the ranges of the components in (2-4) and (2-5) differ. ASD TR 61-483 31

CHAPTER III CABRY FJUNCTIONS TN RESIDUE NUMBER SYSTEM AND RELATED NUMBER SYSTEMS 3.1 THE CARRY ALGORITHI In the second chapter many of the results depended upon the existence of a linear form with restricted coefficients which was equivalent to a given linear expression. This chapter will discuss an algorithm (the Carry Algorithm) for finding the linear form with restricted coefficients when any linear combination of the basis vectors (con...C On is given. The algorithm involves the notion of carries from some components of the representations into other components of the representationo If the linear form to be reduced is all + a2l2 +.o + ancn, one proceeds by expressing anta as bllt + b20. + o b + bni where 0< bi < mi and making the substitution to obtain (a+bl)<l +.. + bnOn. The process is then repeated focusing attention on (bn l+an )l )l_1 and continued until one has the desired result. Dividing aj by m., one obtains a. = mjq + r, 0 r < mj. Any multiple of mjCj will yield a vector in the subspace (xl,X2,oo., xjl,.o,). Since'he set of vectors (ai) is a basis, the set ([l,...,cj) is a basis of the mentioned subspace by Theorem XII. Thus the term mjq will not affect the multiplier of Oj in the reduced expression; that coefficient must be r. The product mjaj can be expressed as a linear combination of al through aj_l and qrr,.ja is merely q times each term of that combination. The linear combination for (qmj)caj is added to the original linear combination and ajcOj is replaced by ASD TR 61-483 33

rCj. Thus one applies the above procedure to first an, then to the new coefficient of cn!1, and so on until the desired result if obtained. The Carry Algorithmn may be stated as follows: 1. Express mjaj as a linear combination of l,. *e,%aj-l denoted b.j a + bj2 2 +... + b.. j-aj for j = 2,3,.o,n. Beginning with j = n and a' = an. 2 Divide aj by mj and obtain aJ = qjmj + rj with 0 rj < mj. 3. Replace a j with r ja and a! with (a!+qibji) for i = 1,2,...,j-l. 1 1 13 4. Repeat steps 2 and 3 substituting j-l for j. Stop after executing steps 2 and 3 with j = 1. Theorem XIX. The linear form produced by the application of the Carry Algorithm expresses the same residue number as the original linear combination. Proof: The proof will be the demonstration that the coefficients of the resulting linear form satisfy the congruences indicated in the proof of' Theorem XI. Consider cn - an mod mn with 0 < cn < mn. By the uniqueness of division rn is the residue of an modulo mn and rn = cn. Assume that rj = cj for j = m,m+l,...,n. The congruence which then must be satisfied is km-l,m-lCml + km,m-lCm +... + kn,m-lcn -= kmlm.laml + km,m.lam +. + kn,m-l a mod mml (31) The quantity aj which enters the division in step 2 of the Carry Algorithm is ASD TR 61-483 34

a. = a. +qnb + b + +.+ +..+q 1 j j n nj qnl- n-lj "J+l j+ l, j thus an = an a 1 = an1 + qnbnnan-2 = n-2 + qnn,n-2 + qn-lb n-ln-l, n-2 I-l am-i 1 + nml + + mbmm-l In expressing pjaj = bJ1EK + b j22 +.o + bjjl-j-l, one solved the congruences kj_-ljlbjjl - mjkj j_lmd mj_ kj-2,jbj, 2 + kj_1j-2btjj -1 mjkj _j2mod mj-2 km-l,m-lbj,m1 + km-2,m-lbj,m-2 +' + kj-l,m-lb,n-1 mjkj,m_lmod mml kllbjl + k21bj2 +... + kjl-,l j 1 mjkjmod i. Using the induction assumption, relation (3-1) can be written km-l,m-lcm-l + kmm-lrm + kn,m-ln = km_-lm-lm-l + km,m_lam + e.. + kn,m_lanmod m_-l which can be manipulated to yield km-lm-lm-l + kmm_lrm +. + knl,mlrn_l (3-2) km-lm-lam-l + km,m-lam +... + kn,ml(an - rn) mod mm-lo Since an = an,an - rn = qnmn, (3-2) becomes ASD TR 61-483 35

km-l,mr-lCm-l + km-lm,.rr + k^ n-l,m-lrn-l - lm-ll-(aml + qnbn,m-l) + k,m-l(am + qrbnm) +..o + krl,i^-l(an-1 + qnb in-l)mod mm_ (3) upon the substitution qn(kml,mlbnm-l + m,mlbnm +.. + kn-l,m-l n,bn-1) qnmknknm- (mod mmr1)~ Once again we transpose (add the inverse) kn-lmlrn-l and recognize that an-l + nbnnl - rn1 = an_ - rn-l = qn-lmn-l Making the following substitution~ qn- l(ml,m-lb n- lm-1 + &m,m-lbn-l,m +.. + kn-l,m-lbn-l,n-2 - qn-lmnlknl -l lmod mm-1.l we obtain km_-lmCml + kmm-lrm +.. + kn-2,mlrn_2 km 1 ml(am_1 + qnbnm + q1n bn lm-l) = lnm-l(m-l ) ^n,m-l Yn-ln-l,m-l) + k rim-(am + qb + nln, m + n-ln-,m) + *. + kn-2,m-l(an-2 + nn,n- + n-lbn-l,n-2)mod mm-l. Again we identify the last quantity in parenthesis as a_2, transpose and substitute. By repeating these manipulations, one finally obtains kmlm-lCm-l km-l,m-l(m-l + L nbnm-1 + n'm-l )+ mbm,m-l)m~d mm-l or Cml = amlmOd m which yields the desired result cm 1 = rm-1. By showing that rm = cm- we have shown that the linear form produced by the Carry Algorithm is identical to the linear form of the conclusion of Theorem ASD TR 61-483 36

XI. Therefore the proof is completed. Without the Carry Algorithm, one can perform operations such as addition, multiplication, and matrix multiplication by resorting to the defined operations of addition and scalar multiplication of residue numbers. The only alternative is to solve a set of simultaneous linear congruences every time one wishes to express a linear form with restricted coefficients. With the Carry Algorithm, it is necessary to solve only n sets of simultaneous linear congruences, and further those sets of congruences may be solved immediately upon the selection of the base moduli and the basis vectors. Thereafter, any linear form may be reduced to one with restricted coefficients by the application of steps 2, 3, and 4 of the Carry Algorithm. It is thus possible to select a set of basis vectors, perform step 1 of the reduction algorithm (i.e., determine the carry functions), and thereafter perform addition of two vectors by addition of the components followed by the application of the Carry Algorithm. Scalar multiplication is effected by multiplying each component of the vector by the scalar and then applying the Carry Algorithm. The Carry Algorithm will prove significant in the multiplication of representations for it will provide a means of combining partial products. 3.2 THE BORROW ALGORITHM AND COMPLEMENTATION The question arises~ Given two representations X and Y of positive integers, how does one obtain the remainder X - Y? This question will now be considered in some detail. Let X be represented by (xi,X2,o^..,xn)0 and Y by (yl,Y2,..,yn)ao Initially one forms (xl-y1,x2-y2,. o.,Xn-Yn) This last expression denotes ASD TR 61-483 37

(xl-yli)a, + (x2-Y2)a2 +.. +- (xn-yI)%l. Corsider the jth component of an expression to be negative. Since mjj = bj1a + bja2a +.. + bj, j- l one may add to the above ex-pressio zero in the form dj [mj {j - (bj aO + b.,a + bj, jjl)] = 0 where dj is the smallest multiple of mj which is larger than the magnitude of the jth component~ This addition yields (Xi - y1 - dnbnl, x2 -2 - dnbr Xn- -l Y- 2 - dnbn nXn - Yn + dnmn) for j = n, (x - Y dnb - dnl- lbnl,l 2 - Y2 - nb - dlbnl,,'d'Xni - Yn-1 - dnbnl dn lrlxrl - Yn+ dnr1) for j = n-l, and finally (X - Y - db- ddlb _n- -. - d2b21 + dr1m, X2 - Y2 - dnbn - dlbn-l,2 - - d3b32 + d2m2,''Xn-l1 Yn-l - dnbn,d l + dn-lmn-lnXn - Yn + dnran) for j = 1. This final expression will be a linear form with restricted coefficients which is the representation of X - Y if X >Y. If X < Y the above procedure yields a representation of -(Y - X)o Thus complementation quite naturally enters the picture By dividing the range of integers which can be represented by residue numbers into those integers less than M/2 and those integers larger than M/2, one can designate the first group of vectors to be representations of positive integers and the second group, codings for the complements of the elements of the ASD TR 61-483 38

first group. f M is enx^, M/2 is self complement. To find the complement of a given representation Z, one generates the remainder (O-Z) as indicated above. The procedure for periorming subtraction and finding complements indicated above suggests the statement of a Borrow Algorithm as follows: 1. Express mjaj as a linear combination of c29.o., j_ denoted bji l + bj-22 + o* + bj j _lj -1 for j = 2,3,..,n. Beginning with j = n and a! = al. 2. Perform steps 3 and 4 if a. < 0, otherwise skip to step 5. 3. Determine d. such that dj is the smallest multiple of mj which is larger than a Io Add to the liear rm the epression 4. Add to the linear form the expression (-djbj, - djb j2..,. db j~ iT - + admj,0,. 0) 5. Repeat steps 2, 3, and 4 substituting -1 for j. Stop after executing steps 2, 3, and 4 for j - 1L Example: With the basis < (1 00,0), (,2,0,0), (1,1,2,0), (1,1,1,1) > where the moduli are m1 = 2, rr_ = 3, m3 = 5 and rra -', the carry functions are 3o2 = %si, 503 = a2, and 7`4 = a3. An example of subtraction using the Borrow Algorithm directly will be given as well as subtraction by using the complement of the subtrahend. Subtraction using the borrow algorithm1, 2, 2, 1) -> 190 ( 0, 2, 4, 6) > -104 ( 1, 0,-2,-) + (., 0-i, 7) 1, 0,-3, 2) + ( 0,-, 5, 0) ( 11-i. 2, 2) + (-1, 5, 0,^ 0 ) ( 0, 2, 2, 2)) - 86 ASD TR 61-483 39

Complement of (0,2,4,6): (,-24,-6) + ( 0, o,-1, 7) + ( 01, 5, O) ( 0,-3, 0, 1) + (-1,-3, O, 0) (-1, 0, 0, 1) + ( 2, 0, 0, 0) ( 10, 0, 1) Subtraction utilizing the complement: ( 1, 2, 2, 1) — > 190 + ( 1, 0o, 0 1) 4-> -le ( 0, 2, 2, 2) 0- 86 3.3 CHANGE OF BASIS One quite important use of the carry algorithm and matrix multiplication is the change of basis operation. Quite often it is desirable to convert from one number system to another, i.e., express a vector in coordinates relative to a different set of basis vectors. One might wish to make the conversion because different number systems are more advantageous for particular operations than others. More will be said concerning this later. Let a vector X be represented by (xl,x2,...,xn) relative to the basis < al,20...,oG >. It is desired to find coordinates (Yy2, -,Y n), ) relative to the basis < i, 2,.,on >. Each vector C1 of the old basis can be expressed as a linear combination of the vectors of the new basis in the form czi - qail + q1232 +.. + +qin n- (-4) However, since both bases are triangular, qik = 0 for k > i. The vector X with ASD TR 61-483 40

coordinates (xl,x2,...,x ) relative to the basis < Cl.. e',a' > is xi + X2 + x2C + x. + Xnn Substituting from above, one obtains for X xlqll1~ + x2[q21Pi + q2232] +'~- + xn iir.l + - + qnn3n] which can be written (xlq i xq2 + Xq2i + + Xnqni)3i + (X2q22 + o + Xnqn2)P2 + o. + Xnqnnn. (3-) The carry algorithm is then applied to linear form (3-5) and the result is X = YlT1 + Y252 +... + YnLnThe Yi are the coordinates of X relative to the basis < 1,2Sn, —.,nn >If the zero coefficients are retained in expression (3-4), expression (3-5) becomes (Xlqll + X2q2l + * + Xnqnl) 1 + (Xlq12 + X2q22 + —. + xnqn)P2 +... + (xlqin + x2q2n +.. + Xnqnn)n.This expression is an interpretation of (Xlqll + x2q2l +. + Xnqni),(xlql2 + x2q22 +.. + Xnqn2), *-. + (xiqln + -. + Xnqnn) which is the matrix product [XIx2.. ~xnJ] q-.iiq.2 ~. q inl q( 1q22a q2n = [Y1,Y2, ~ Yn qniqn2... qnndenoted X'Q = Y. The above procedure constitutes an effective procedure for executing ASD TR 61-483 41

change of basis. The vectors oi of the new basis can be written as linear combinations of the old vectors, n = PijKj (3-6) j=l Thus for a change of basis from < L., oo > to < Ol,..,0 >, the appropriate matrix product is Y^P = X where P = 1Pij ll Substituting equation (3-6) into equation (3-4) one obtains n n n i = iljlPij + qi2 2P2jj + p j + qinZlPnjaj -=1 l j=jL J== n n n qip I. + = + + E q inPnjj j=l j= l j = n n k=l j One may interchange summations to obtain n n T 7,IikPkSqj ji =- k=lkPk qJ n n n = kB'qikPkjcl + ^qikPk2e2 + ^i+ qikPknOn (3-7) Equation (3-7) written in n-tuple form with restricted coefficients is the ith row of the matrix product QP. Since the ai constitute a basis, the reduced form of equation (3-7) must be 1i = ai. As a consequence, it is seen that Q " P = I. (3-8) By advancing a dual argument, one deduces P - Q = I. (3-9) Equations (3-8) and (3-9) can be used as a check on the determination of the P and Q matrices. These equations are necessary but not sufficient conditions. ASD TR 61-483 42

3.4 MULTIPLICATION To multiply two elements of a number system related to the residue number system, one forms partial products, one for each component of the multiplier, and adds them together producing a linear combination of the basis vectors which is then reduced by means of the Carry Algorithm. The algorithm for determining the form of the partial products will be called the Multiplication Algorithm. The Multiplication Algorithm may be stated as follows: Consider the most general multiplicand (y1,y2,. o-yn) and multiplier (XlX2... o,Xn) lo Write the multiplicand (yiy2,.o.,yn) as the vector sum yll + y2s2 +... + YnanBeginning with j = n 2. Write the partial multiplier (0,...,,xj,0, o.,0) as the vector xjcaj. 3. Multiply, component by component, xj0j ~ Yiai) i = 0,...,n. 4. Express the vector xjoj ~ yiai as the linear combination Ziel +... + Zia,, i = 0,..o,n. 5. Sum the linear forms produced in Step 4 to determine the jth partial sum~ 6. Reduce j by one and repeat Steps 2 through 5. Terminate the procedure after doing the above steps with j = lo Example: Consider the multiplication (Y1,Y2. -.,y4)M ~ (xlx2,.., ^X4)M in the mixed base number system where mi = 2, m2 = 3~ m3 = 5, m4 = 7. Here ASD TR 61-483 43

the basis is < (1,0,0,0), (1,2,0,0), (1,1,2,0), (1,1,1,1) >. The following steps are numbered to correspond to the statement of the Multiplication Algorithm. 1. (Yl,0,0,O) + (Y2.2y2,0,0) + (Y3,y3,2y3,0) + (Y4,Y4,Y4,Y4) 20 (X4 x4,x4,4 ) 3^ (Ylx40,O,0O) (y2x4,2y2,x, O, 0) (y3X4.y3X4,2y x4,0) (74X4.7Y4x4.,Y4X4 Y 4x4 ) 4. (Ylx4,0,0,0) = (y.x4,0,0,0)M (y2x4,2y2x4, 0,0) = (O,y2x40,,o)M (y3x4,y3x4,2y3X4,0) = (0,0,y3x4,0)M (y4x4,y4x4,4,y4.x4,y44 ) = (O,O,,y4x4)M 5. (Y1,Y2,Y3,Y4)M' (00,0,OX4)M = (x4.Y1.x4y2, 4 Y3. X4Y 4)M 2. (X3, x3,2X3 0) 3- (ylX3s0,0,0) = A (y2x3,2y2x3,0,0) = B (Y3x3Y3x3 2 (2y3X 3), 0) C (y4x3,y4x3,2y4x3,0) = D 4. A = (ylx3,.,O,O)M B = (O,y2x3,0,O)M C = (0,0,2y3x3,o)M + (O,x3sy30,,)M since (0,0,2x3y3, )M + (O xsys30,0)M = (2X3y3.2x3y3,4x3y3,0) + (X37y32x3y3,0,0) ASD TR 61-483 44

= (y33,y3x,2 (2y3x3), O) D = (O,o,x3y4,o)M5. (Y1,Y2,Y3,Y4)M (OO,x3s0)M = (y1x3,y2x3 + Y3 + 3X34y + y40)M 2. (x2,2x2,0,0) 3. (x2yl,O,O,O) = A' (x2y2,4x2y2, O O) = BE (X2Y3,2x2y3,O,O) = C' (x2x4,2x2y4,O,0) = D' 4. A' = (y7x2,0,0O,)M B' = 2(0,x2y2,0,O)M + (x2y2,0,0,0)M for (x2y2,4x2y2, 00 )M (x2y2,2x229,OO) + (0,2x2Y2,0,0) (x2y2,2x2y2,O,0) + ( x2y2,2x2y2,O,O ) + (x2y20,0O.0) C' = (O,x2Y3s,0,)M D' = (O,x2y4,0,0)M 5. (Y1,Y2,Y3,Y4)M' (~,x2,o~'o) = (x2yl + x2y2,2x2y2 + x2y2 + x2y4,, 0)M 2. (xl,O,O,O) 3. (xlyl,O,o,O) (XlY20, O,O,) (xiy3, 0,0o) (xiy4,0,0,0) ASD TR 61-483 45

5. (Y123,Y3,Y4)M' (xl,0OO)M = (xlyl 2 + + xly4,0,,0,)M The results of the Multiplication Algorithm in this example are the following for rules for the formation of partial products: (Y1,Y2,Y3,Y4)M' (x,0,,0)M = (xy X2 + + x x + xly4,0, 0,0)M *(Y +2Y32 xy- * y20xti3)xy = (+ x2YY + x24,0,3 0)M (Y Y2,Y3Y4 )M - (OO,3xa,)M - (X3syl3xsy2 + xsy3,2x3ys + X3Y4,0)M (Y1,y2,Ys,7y4)M' (0,0~0x4 )M - (x4yi,x4y2,x4y3,x4y4)M To multiply two mixed base elements (yl2y2,YsY4)M and (xlx29x3sx4)M one proceeds as follows: 1. Form the above partial products. 2. Reduce each partial product by employing the Carry Algorithm. 3. Sum the partial products again employing the Carry Algorithm. As an example, consider the product (1,2,3,4)M. (0,2,4,6)M. The partial products are (1,2,3,4)M ~ (0o00,6)M = (6,12,18,24) = (1,1,1,3)M mod M (i,2,3,4)M ~ (0,0,4,0)M = (4,28,40,0) = (l,l,0,0)M mod M (1,2,3^4)M (0,2,0,0)M = (6,22,0,0) = (1,1,,0,)M mod M. Therefore, (1,2,3,4)M (0o,2,46)M (0,0,1,3)M mod M (0,2,4,6)M (- 104 and (1,2,3,4)M -> 200 104 ~ 200 = 20800 = 10 mod M (0,0,1,5))M (> 10 ASD TR 61-483 46

Let us look again atl the question of associativity of matrix multiplicationo Consider the three matrices A = Ilaij l, B = jbi jl., and C = lci. jlo Let the basis of the vector spaces by U, < c i2,,. Co,n >; V, < P31,2 *o, r >; W. 7>,72.',yn >7 and Z. < 5152.o.5n > TA is a transformation from U + V, TB: V - W9 and TcO W + Z. The ith row of the product A B is (k=1 k=1 k=l kkn n n reduced relative to the basis < y1'y7n >. Designating the reduced form obtained (ei1e i2,...e in), we obtain Define n - Z aikbkn k=l in = mn D naikbkn-l + ingrn- =mnl ~n laikbkn-l + fingn,n-1 mn-l fi,n-1 = m_l lZ aikbki + fg + fin-lg -1 + fi,2g2, ei, - mwhe re *i =.Y + gj2Y +.o. + g.j_1T "mj - gjll j2 j J-1 j -1 ASD TR 61-483 47

The ith row of the product (A-B)C is 1/ "1)n n ( eikCk,, ei ck2 Z ~ e ikCkn ~_-1=I k=l k=l reduced relative to the basis < y 7,. s, nr >. This gives rise to the reduced from (hi1 hii~.. i hin) where hin = ~; kl, eikCkn hin Sin =- r n h Zekckn:L + ~irrnJnl hi,n-1 = ^iLkei nl c Rin'r, " Ri,n-lrn-l,l + o + fi2r2i 1 lm mm j whe re mi. I rj l + +rSimilarly the ith row of the product B$.C is and n n Zebikk n- i + kin nn- kckn k=l k-l k=l Bi n-1 - mn-1 Eeikcki + Binrnj, + Oinnlrn-lll +. i. + 121ir reduced relative to the basis K s..e >. The reduced form is ASD TR 61-483 48

( sin - I mwere - bikCkn kbi tin = n n i k7i ikckn-l + tinrn n-l Si,n-l =. mi Tkbikck n-l + tznrn n-l ti,n-l mL n rn klbikCkn + tinr nl + tin-lrn-ll +'' ~ + ti2r21 L Oil The ith row of A(BC) is n n n lk=laikkl, klani kSk2i,n n, k+ ikSk21 whe re Za ikskn Vin= n n n rn k=l iksk n-l + Uinrn, nVi,n-l = n ASD TR 61-483 49

n hiaikskn- + Uinrn,n-l uin-1 = r/ 1 _______"___________ ____________________________________t Selecting particular comrponents fcr comparison /fn hin m dk ) + La, b +mod. c'9e i nkn+ l mod mir ll - n-l,n N *1 aikbk....i -ingn- n-.-1' i+l + f 1ia2g921 mod ml ci rnm mod mn or hin " a/b, ro da m mod mn + ni ZL f. l g mio-d m~ m c mod nm +Removing one term and changing ndie one finds nr I1 n n-+! M r ~ ^ijg jr^ mod 1Y Crnmod. rn ASD TR 61-483 50

k- aikbkncnnOd mnn k=l n-1 n n + l LE aikbkr + fijgjr 1mod mr' Crnmod mn. r=l k=l j=r Also n/. Vin =,aikSkn, od mn ~L i Sil z bikCknmod mn + ai2 k b2kcknmod M / n +... 2 ain ( bnkCkmod mod mn or n n-1 n Vin = Zairbrncnnmod mn + Z a Zlairbrkcknmod mnv r=l k=l r=l Changing indices for clarity, one obtains n n-1 n Vin = Z aikbknnnmod mIn + Z Z aikbkrCrnmod mn k=l r=l k=l Since the first terms of hin and Vin are the same, it is sufficient to look at n n 1 airbrk + figk mod mk (3-10) r=~ J ~J i and n airbrk mod mn. (3-11) It is seen that the above expressions are not in general equal, for the range of expression (3-10) is the positive integers less than mk whereas the range of (3-11) is the positive integers less than mn. Since the mj are relatively prime, one is led to conclude that the ith row of (AB)C is not equal in general to the corresponding row of A(BC). This was shown independent of the ASD TR 61-483 51

selection of the basis for the various image spaces involved. Therefore, no selection of basis will guarantee associativity of matrix multiplication. ASD TR 61-483 52

CHAPTER IV TilE MIXED BASE JTUMBER SYSTEM 4.1 GENERAL CHARACTERISTICS In order to remove ambigui-ty the elements of a finite number system are partitioned into two classes, those representations defined as positive and those defined as negativeo Normlal convention assigns a magnitude interpretation to positive elements and a complement interpretation to the negative elements. For sign determination and magnitude comparison, it is necessary to identify the classification of each and every element. The structure of the residue number system makes immediate classification difficult. The structure of the mixed base system facilitates immediate classification. In addition, the mixed base system allows one to handle the problems of additive and multiplicative overflow, and divisiono We shall see that the mixed base system extracts payment in the form of carries for these advantages The basis vectors for the mixed base system are generated in the following manne r: 1. Order the primes mz,m2,.., mno 2. Set na equal to the vector consisting of all l's. Beginning with j = n. 3. Obtain.j_- = mjCj 4. Repeat step 3 with j replaced by j-l. Stop after performing 3 with j = 1. ASD TR 61-483 53

Theorem XX. The vectors (OC,..,Cn) produced by the above scheme constitute a basis. in order *to pro-Te the theorem, Le-:ma 1 will be proven. Lemria 1i If (ab) = 1, then (a mccl bb) = 1. Proof: a bg + r, 0 r < b and.. by definition r is the residue of a mod b a m r mod b or a (a mod b) mod b. Since x = y mod z > (x,z) - (yz), (a mod b,b) + (a,b). The conclusion follows. Proof of Theorem XX: Qn is a representation of the integer 1. The vector n ai is the residue representation of A = 7 mi. Each mi for i < is relatively prime to Ai. Thus it is seen that ki = 0 for i > and (k2imi) = 1 for i >~. By Theorem XII the set < al,a2,..,a. > is a basis of Rn. Theorem XXI. An elemert (xlx2. o., Xn) of the mixed base number system is a representation of an integer X in the range C X ( ) if and only if xi = C. Proof: The element X (XsxX2, o,x n) is a coding of the integer xi-+:x -+ + Xs M +. oo + x modulo M. (-1 mi M1m2 m1lm2r3 n Consider the quantity M M M xl + x2 mm2 + x mim +m + X.n (4-2) ASD TR 61-483 54

The largest value expression (4-2) can assume is attained when X = ml - o Upon substitution one obtains (ml 1 + (m - 1) + (m3 - i) M + + m 1) Ml IrI1m2 mim2m3 This is then rewritten as M + (mn - 1) + mn(mnl - 1) + _l) + m 1 1) + o. + m- -2(m2 - 1) + m remembering the scheme for generating the base vectors. All but the following terms add out: -1 + M+ M + M - 1. mi ml This means that expression (4-2) is equivalent to expression (4-1) Consider next the quantity: (m2 - 1) M + ( I + (m - 1) ilmn2 mimmn 3 which is equal to M (mn - 1) + mn(mnl - 1) + rmnm-1(mn-2 - 1) + + (m2 - 1)m The above expression reduces to M -1 + -. ml From this the conclusion is clear. To determine the sign of a mixed base number it is necessary to have a partitioning of elements representing consecutive integers into two classes. The first coordinate gives such a partitioning if mi is even, i.e., ASD TR 61-483 55

xi < m1/2 0 < X < M/2. When applying the Carry Algorit-hm., to the reduction of the expression a1e, + a2+g + + an0n (Cei is a base vector of the mixed base system) one must increase by one aj for every multiple of mj+1 contained in a +. (The notation here is consistent with that contained in the discussion of the Carry Algorithm. ) This indicates that a carry may be propagated from the nth coordinate to the first. Therefore, when adding two elements of the mixed base system, one unit of time is required to produce the unreduced sum, and up to n-l units of time may be required to propagate carries Borrowing is accomplished by reducing a' by 1 and increasing a' by m i Again up to n-l units of time may be required to perform subtraction or complementationo Multiplication of two elements of the mixed base system was discussed and an example given in Chapter III. Theorem XXII. When two mixed base numbers are added, the carries are binary and a position which produces a carry cannot also propagate a carry. Proof: The largest jth component of the unreduced sum occurs when the jth components of the addend and the augend are maximum, i.e., equal to mj-l. The maximum sum will be m -2. J Let j = n. The maximum unreduced nth component will be 2mn-2; therefore, the carry can only be zero or one. Consider j = n-i. The component 2mn-1-2 will produce a carry. If a carry was generated by the nth position mnl-2 + lmn_l; therefore, no carry is both propagated and generated. Assume the results true for j = m. In this case 2m l-2 will generate a ASD TR 61-483 56

carry of one, and 2m _-2 + 1 will also give rise to a carry of oneo 4.2 OVERFLOW A problem of the residue number system, which can be solved with the mixed base system is cverflowo in a mixed base number system where ml = 2, the integers less than M/2 are represented in the system. Therefore, overflow is defined to be the condition where the true arithmetic result is an integer larger than or equal to M/2. First additive overflow will be discussed and then various conditions for the absence of multiplicative overflow will be demonstrated. (Due to sign detection and overflow conditions it will be convenient to assume ml = 2 for the remainder of this chapter. In this chapter all n-tuples will be elements of the mixed base number system. ) Theorem XXllI. If the sum of two positive elements of the mixed base system is (zl,..,zn) additive overflow occurs if and only if zi = 1. Proof: (zlz2,....zn) represents the integer M M Z2 + + zo + o + Zmd M (4-3) Z17 + Z2 m3 and overflow occurs when Z1J + Z2 + * + zn 2 2m2 2 This will clearly be the case if zl = lo The largest value that 22- +. + z can attain has been shown to be 2m2 n 2 - 1. The largest sum possible is 2 - 1 = M-2 < M. Thus expression (4-3) becomes Zl + z.. + Zn and the other conclusion follows. 2 2m2 To insure that multiplicative overflow will not occur, conditions will be ASD TR 61-483 57

given which will insure that no multiplicative overflow will occur as the partial products are formed. It is also necessary that overflow does not occur when the partial products are summed. This will also be treated. Consider (y1,Y2..o,Yn)' (xi,O,...,O). Since (x1,O,...,O) M xl, overflow will occur unless y y= -..o =Yn = 0. Consider next (Y1,Y27,.,'Yn)' (Ox2,O,..,O) and note that (O,x2,O,..,O) M x2m2. Therefore, the condition which is necessary and sufficient for the absence of multiplicative overflow in this partial product is: Y1 = Y = 2Y1 = 0 arnd x2 ~ Yn < m2. M Since (OO,x3,O,o...,O) represents X3 M and (YzY2,-.-Yn) represents Y = Yn + Yn lmn + y m m1 +..+ yM -, a necessary and sufficient condition Y = Yn + Ynlmn + Yn_2mnmn- ml to prevent overflow is X3 Y< (4-4) 2mm3 or X3 Y < m2m3 Thus it is seen that condition (4-4) becomes X3(yn + Yn lmn) < m2m3 (4-5) and Y1 = Y2 =. Yn-2 = 0 Since Yn < mr we may substitute for expression (4-5) x3mn(ynl1 + 1) < m2m3 to obtain a sufficient condition. Consider now the general partial product (Y1,Y2,..,Y n)' (0,...,O,xj,O,..,O). In this case (0,..o,O,xjO,...,O) represents xj m. ASD TR 61-483 2m.. ASD TR 61-483 ^8

To guarantee that no overflow will occur we must satisfy the inequality xjY < m2...mj or x( Yn + Yn -lmn + * + Yn-(j -2)1.' mn-(j ) (4-6) + Yn-j+lmnmn-l mn-j-2 + ~ ~ + Yi ) < m2m3m3 The condition becomes Yn-j+l = Yn-j= yj = 0 and Xj(Yn + Yn-lmn + + Yn-(j-2)mn —mn-(j-3)) < m2m3mj (4-7) This constitutes a necessary and sufficient condition that this partial product does not produce an overflowo Again there are simpler inequalities the validity of which will imply the validity of (4-7). These inequalities are Xj[(Yn-l + l)mn +.. + Yn-(j-cO)mn..mn-(j-3)] < m2m3''m-r Xj[(yn-2 + l)rnmnl + - + Yn-(j-2)mn.mn-i(j-3)] < m2m3.. mj Xj[(Yn-(j-2) + l)mn...mn_(j3)] < Mm32..mj. The sufficiency of the above inequalities stems from Theorem XXIV. Theorem XXIV. If xi < mi, then xl+ + x32m 1 +.mlm2 + x, + _lmlm. omk_2 < mlm2.- omkl.,-lJ" - yLk-2 Proof: The maximum value that xl + x2m1+ x3m2... + X3 _lmlm2.*.mk2 ASD TR 61-483 59

can attain is (ml - 1) + (m - )m + ( m2 - l)mlm + )m..l + (mk-1 - l)mlm2...mk_2 = mlm.. mk-2m - 1 < mrlm2..m- k k-I1 Even when none of the partial products of a multiplication involve multiplicative overflow, overflow may result when the partial products are summed. Such overflow will be avoided only if the first coefficient of the unreduced sum is zero and no carry is propagated into that position. 4.3 DIVISION IN THE MIXED BASE SYSTEM Utilizing the overflow rules given in this chapter, one may now state rules for performing division in the mixed base system. The conditions for the absence of multiplicative overflow and rules for forming partial products provide a means for estimating trial divisors. The subtraction rules then allow one to determine the new dividend. The method will be demonstrated before the formal rules are stated. Example: Divide 95 by 14 using the mixed base system where ml = 2, m2 = 3, ms = 5, and m4 = 7o 95 4 (0,2,3,4) 14 -> (0,0,2,0) Step 1: Determine first divisor,0,0,2,0 j,2,,4 It is seen that it is necessary for a = 0 to avoid overflow. Step 2: Determine second divisor 0,3 0,0,2,0 0,2,3,4 ASD TR 61-483 60

Again to avoid overflow = O0 Step 3: Determine third divisor 0 0 2:~9'n y4,0,y0 00,92,0 0,2,34 From overflow considerations it is seen that y = 1 is satisfactory. 0, 0,1 0 0,2,0 0,3 2 0,2,4,0 it is seen that y = 1 is too large; therefore, 7 = 0. Step 4o Determine fourth divisor 0,0,0) 0,0,2,0 0,2935 4 From reference to overflow rules and multiplication the estimate is ~ = 6. 0,0,0,6 0,0,2,0 /0,2532 4 0,22,2,0 0,0,1,4 The division is completed giving 95 = 6 ~ 14 L l. The procedure for determining the trial divisor is as follows: 1. Consult the conditions for the absence of multiplicative overflow to determine the possible range of trial divisors. 2. Use the rules for forming partial products to determine a trial divisor which will yield the required zero(s) in the most significant place(s) and a non-zero comrponent in the most significant non-zero position (kth) of the dividend. (The kth component must be less than or equal to the kth component of the dividend. ) 3. Subtract the partial product from the dividend and if necessary ASD TR 61-483 61

revise the quotient so that the least possible non-negative result is achieved. 4.4 DIGIT FILL-IN An addition problem which can be solved by using the mixed base system is the problem of digit fill-in. If one is given the coordinates of a vector representing the integer relative to the basis A = (alo i^,.^,oin) and base moduli mlIm2-. o.mrnl the problem is to express the integer s in terms of coordinates relative to the basis {lj2,.). on,3 n+l,', n+m] = B and base moduli m,m2,.,m n'mn+l.o.,m. The m. are pairwise relatively prime. n+m Since one can represent s as a vector relative to the base moduli n ml,m2,...,mr, s is less than 7=1 mi. Therefore, if s is expressed in the mixed base system relative to the moduli m n+l mn+2,..,mn+m,ml,m2,. rmn, the coordinates with weights greater than or equal to 4 mi must be zeros. i=l' The weights of the last n components of the mixed system will be in reverse order, lmn,mnmn_l,n..,mnnlo.. m2. These weights are the same as the weights of the components in the mixed base system relative to the primes ml,m2,...mn Therefore, digit fill-in is accomplished as follows: i. Perform the change of basis operation from the basis A to the mixed base system. 2. Prefix the m zeros to produce the correct representation in the extended mixed base system. 3- Perform the change of basis operation, this time from the extended mixed base system to the basis B. ASD TR 61-483 62

C HAPIR V OTHER NKRV'ER;~.T^.._S RELATED TO THE RESiDUE NUMBER SYSTEM.1 PARTiTITONTING PROPERTI-ES In Chapter IV i't vwas noted that the mixed. base number system. representations corresponding to conseecutive integers are partitioned by the first coordinate. It is this property which permits a rapid solution to the sign detection problem.o A questi;r. arises whether other number systems exist which possess the desirable parzaltitioning while having simpler rules of arithmetic manipulation. to will be shown that the only non-redundant number system to achieve a partiti oning of elemerents representing consecutive integers is the mixed base systemr Lemma 2~ For any integer k within the range 1 < k < p, there exists an integer & such that p < k < 2p wThere & < p and p > 2. Proof: It is evident that k cannot lie in the range.' k< p9 for p > 2, p-2 > 0 2p-< > p 2(p-1) > p; therefore, P <2. p-l ASD TR 61 -483 63

Thus there exists an integer I such that P P < k < P-e with p > I and one concludes p I.k < p. 2p. Theorem XXV. If the base moduli are ordered mlm2,..o mn only the mixed base number system gives a partitioning of the elements into those elements which represent integers'in the range less than (C+l)M but greater than or equal to c M _ where c is the first coordinate of the element. ml Proof: We will consider all number systems which give the desired partitioning and conclude that they are all identical to the mixed base system. Consider the number system based on the vectors < 1,P32...,Pn >. It is assumed that this number system achieves the desired partitioning. Here 31 corresponds to B1;P2 to B2 etc, An element of this number system Y = (Yi,Y2,...,yn) represents the integer. yIBi + Y2B2 +.X. + ynBnmod M. For the set < 31.-. Sn > to be a basis it must be triangular; therefore, one may state Bn kn Bn-l = knlmn n Bj = kj i- mi. n B,= kl i=2 mi whe re J o < kj <X mi ASD TR 61-483 64

Consider yl = c and yi = 0 for i / 1. The expression ylB1 + y2B2 +... nBn M kl = 1. One conrdition which must be satisfied is y1 = 0 -= Y < m. This requiremernt becomes Y2B2 + y3B3 + o + yrBn z rod M ( -) where z < M for all Y27,Ys3. oYn Consider first the case Y' O0 Y3 =.Y = Yn = O We have y2B2 Y2k M If there is an integer Q in the range 0 < K < m2 that M M < k <M (5-2) condition (5-1) is violated. Expression (5-2) may be written m2 < Kk2 < mini (5-3) By Lemma 2, it is seen that for k2 > I, we can find an integer in the range 0 < K < m such that m2 2k2K < 2m2. Since mi >2, inequality (5-3) is satisfied. Therefore, k2 = 1. Assume that we have shown k = 1 for i = 1,2,...,m. Let yi = mi -1 for i = l,2j...,mym+l 0, and Ym+2 = Ym+ = + = 0. Consider (^, )-.> M (m - ) - k) + y + m+lkm+ mim) mzmams m mm m oi ~in.mim2... m m + ml mm or (m2 - l)m3s..mn + (m3 - l)4...mn +.. + (mm - l)mm+l..mn + Ym+lkm+lmm+2. m n which yields ASD TR 61-483 65

(m2m3S..mn) - (mm+1..mn) + Ym+lk m+m+2. m But m= m2m3. mn. mi Thus the sum s is M s m= m +- Ylkm+lmm+2...m mi ml +l m2n +' n If M s <M (5-4) mi condition (5-1) will be compromised. Expression (5-4) becomes mm+l mn < Ym+lkm+lmm+2~. mn < (ml - 1) M m+l mn which upon substitution for M yields mm+l O - mn < Ym+lkm+lmm+2 ~~ mn < [m2... m(ml - 1) + l]mm+l. o mn Removing the common factor in the above expression one obtains mm+l < Ym+lkm+l < [m2-...- (ml - 1) + 1]mm+. (5-5) If mm+l < km+l < (ml-l)m2...mm+l, (5-5) is satisfied by Ym+l = 1. If km+l < mm+l and km+l > 1, Lemma 2 guarantees that there exists a Ym+l such that m+l1 < Ym+lkm+l < 2mm+1 but since 2 < [m2.. mm(mL - 1) + 1]. It is necessary that km+ = 1 or that (ml - l)m2o..nm+l < km+ < mm2.. mm+l. To see that km+l cannot be in the range (mi - l)m2..r m+1 < ki+1 < mlm...mm-, consider Ym+l = 1 and Yi = 0 for i f m + 1. Then ASD TR 61-483 66

s - Bm+lkm+lmm+2. omn and M -_< (ml - l)me...m. +2omn < s < mmmi. ommn+R. om m = M. Again we have satisfied condition (5-4); it is necessary that m+1 = 1 Therefore, the only number system which effects the partition described is that system having ki = I for i = 1.. o,n. This system is the mixed base number system. Theorem XXVI. If the base moduli are ordered ml,9m,..,lmn, there is only one number system with the property that the first coordinate partitions elements which represent consecutive integers into mi classes. That number system is the mixed base number system. Proof: Theorem XXV shows that there exists but one number system which partitions the elements into those elements which represent integers in the range less than (c + 1) M but greater than or equal to cM, where c is the first ml coordinate of the elemento By definition this number system is the mixed base number system. It remains to show that no number system exists which effects the same partitioning for y1 f c. Assume such a number system exists with basis t3,%.o,,.~ An element of the rumber system represents the integer Y13 + y2B2 +.o + YnBrl mod M (5-6) Again we may state Bn - kn BnA1 = kn-lmn ASD TR 61-483 67

n B' = k. C mi i=j+l B! = ki, mi i=2 where 0 < kj < 7mi. The range imposed on kl is 0 < kl < mi. Thus we have B' = kl M/ml and expression (5-6) becomes M y1kl 1 mod M when yl 7 0, Y2... =n = 0 It will now be shown that there exists an integer c in the range 0 c < ml such that c m ylkl M mod M < (c + 1) M (-7) im- - mi mi cannot be satisfied for 0 < kl < ml, 0 < yl < mi, and yl ~ c. Take c = 0. Expression (5-7) becomes 0 < yikiM mod M -. (5-8) 0~ Ylk ml ml (5-8) Condition (5-8) will be satisfied only if Ylkl - 0 mod mi. Since yi t 0, (5-9) requires that k1 = 0. This is the desired contradiction which completes the proof. Corollary 1: If the base moduli are ordered ml = 2, m2, m3,...,mn there is one and only one number system with the property that the first coordinate partitions the elements into two classes, the representations of the integers less than M, and the representations of integers greater than or equal to - ASD TR 61-483 68

Proof: This corollary follows from Theorem X.XVI with mi = 2. One now asks whether a nimber system with, base moduli mTr,m2,. o,mr exists which partitions elements -which represent consecutive integers into mj classes with the first coordinate where j. I? The number of elements having the same jth coordinate in any system having mj as a base prime is first coordinate is n i=2 The number of elements in the two cases differs and the greatest common multiple is oneO Therefore, the answer to the question posed in the preceding paragraph is negative. A similar argument shows that no number system with base moduli m1,m2, ~..,mn where (ml,m) = (nMm) =.. - (mnm) = 1 exists which partitions with the first coordinate elements which represent consecutive integers into two classes, one class the elements of which represent integers less than M/m and the other class representing integers greater than or equal to M/m. The argument follows: Since M is relatively prime to m, m M M, but m/M - & when 0 < & < m. Let m - = dm. If m < ml M, M - T. If m > mi m~i f M - & for cmir < < < ( + l)mi. ASD TR 61-483 69

Suppose kml = Q, then m - & = mlm2,..,mn - mlk but (m,ml) = 1; therefore, m(M-e which is a contradiction. The only related number system which produces a partitioning is the mixed base number system and; therefore, the proof is completed. From the theorems and arguments advanced thus far in this chapter, one concludes that the mixed base number system is the only number system which partitions the elements representing consecutive integers. In particular only the mixed base system with ml even partitions the elements representing consecutive integers into two groups —(l) elements corresponding to positive integers and (2) elements representing complements. Thus if one wishes to use a number system to determine the sign of the residue element, he will find it necessary to use the mixed base system. 5.2 NUMBER SYSTEMS ALLOWING SIGN DETECTION WITH FEWER THAN N-CARRIES It has been suggested that the use of number systems which are neither strictly residue nor strictly mixed base might ease the carry situation in sign determination. Such systems are those in which a certain number of carries are eliminated from the operation of expressing a vector in the mixed base system. As developed in the chapter concerning the Carry Algorithm, a vector X with coordinates (xl,x2,...,xn) relative to the basis < 31,,B n > is expressed with coordinates (Y1,Y2,..,Yn) relative to the mixed base basis < al,..., n > by determining the q = Ilqi jl matrix and following with the matrix multiplication X * Q = Y. The elements of the Q matrix are governed by the equation ASD TR 61-483 70

Pi = ql + *. + qinn for i = 1,2,..,n (-10) The Y so obtained vgl not in general be a li-near form with restricted coefficients Carrys murt tohen'be propagated from each position to the next more significant posit;ion The general co-nversion will require up to n-l carries. To reduce the maximnum possible n if.ber of carries which can occur by say m-l carries, it will be necessary and sufficient to guarantee y < mk for k - n-mr,..n. (5-11) This is in turn equivalent to the condition qik = ik for ik = n-m,...,n. (-12) Condition (5-12) may be expressed as n-m-l = +k + ciki. for k = n-m,. o,n. (5-13) If Ilaijll is the array of the mixed base basis vectors, consider the m x m sub-array in the lower right corner. Equation (5-13) states that this subarray must be preserved in Ijbi(ll, the array of the 3 vectors. The only other requirement is that Ilbij. be triangular. Other considerations which affect the selection of the reraining elements in the 3 array stem from a desire to simplify the carry structure in the P system. Since aiJ - ij for i, j = n-m,.o.,n the carry structure in the last m positions is fixed. Carries from the kth components to the jth components whe re k = n-m,oo.,n j = 1,2,...,n-m-l1 can be prevented by the following constraint ASD TR 61-483 71

bij = 0 for i - n-m,...,n j = 1,2,...,n-m-1. Further carries can be eliminated by making the upper right partition of the array the identity matrix. Since aij = b.i for i, j = n-m,...,n carries from the 2th component to the (e-l)st component will occur for Q = n-m+l,...,n. Therefore, at least m-l carries will occur in the ( system. The total number of carries in the 3 system for a subtraction followed by sign detection is at least as great as for subtraction in the residue number system and conversion to the mixed base system. Such number systems do not appear practical, for nothing is gained in addition and sign detection. In fact, from the Multiplication Algorithm of Chapter III, it is clear that much speed is sacrificed in multiplication. 5.3 GENERALIZATION OF SIGN DETECTION FOR THE RESIDUE NUMBER SYSTEM Let a residue number system be defined as Pn Pn SRN =Y1 +' + Yn m(-14) (mmj) = 1 except for i = j where SRm X XI = x. i mi, i= Pn m - Pn ASD TR 61-483 72

The residue number system is a member of the general class of nonredundant weighted number systems wnich satisfy the following relationship: Sr1 Z P1 +.- + ZnPn (5-15) The necessary and sufficient conditions for the validity of this relationship is the triangularity of the weight matrix (See Theorem XV and XVI). Consider next the special mixed base number system which satisfies the relationship. It has been showa in the previous sections of this chapter that the only non-redundant number systems having simple sign properties is the mixed base system. n p SM - i (5-16) i=O Pi ZO is identified as A(x) and zl is the high order digit of X. Any nonredundant weighted number system S must satisfy the relation S = S. (5-17) where S = zlp, +... + ZnPn' The following relations are also valid if S = SM kS = kkSM [kS] = [kSM] (5-18) IkS} = IkSM) jkSm = lmjI Consider the normalized residue code S =S RN SM (5-19) RN i SM i SPn ] = _Pn2 ASD TR 61-483 73

n yipil i Pi Lj=l m i o Z lP (5-20) It is possible to further reduce the left hand side of the equation when mj IPi. This occurs when i > j. P n YPi i Pi Ey - + = z i (5-21) j'i mj J>imj I=0 P The i-l term associated with equation (5-20) is _i ____ oi -l LSn YjPil 1 Pi-l Z mi-li= ZO Pa (5-22) Both sides of equation (5-21) are multiplied by mi and the resulting equation is subtracted from equation (5-20) to give n YjPi n YPi-l1 E mj^ -M E ~ mj = zi l [i] n (5-23) j =l " J _j=1 Reduction of the left side of equation (5-23) yields n Yj, i n ^ jPi-I YiPi-l + Ei m mj Z = z. (5-24) ^i i-l p>i mJ j-1 mj The identity [f] - mi -- = [] Imi (5-25) may be applied to equation (5-23) to give M=1 2 = i (5-26) = j mi -i 0 [i ] n where mo =oo Equation (5-26) may be reduced to Zyj Pi + Fj yjP7]i J L J>i mj m i ASD TR 61-483 74

ln yjPI YiPi -1 + L i m mi (5-27) The special case 2 mli z2 = z11 ^- + Z12; 0 < Z < 1; 0 < z < 21 may be handled within the framework of the previous formulaso In particular zll = r + + + Yn (5-28) mi ml ml mn and Z - +.. ] 2+y+ (5-29) Lmi mn 2 or in general when 2' mi zm =J ml Z1 = + L Y 2+ + +mn y2 (5-30) Equation (5-29) and (5-30) should be regarded as the fundamental definition of the sign digit- All known methods of sign detection may be interpreted in terms of these equations. ASD TR 61-483 75

CHAPTER VI DIGIT ENCODING iN ARITHPvTIC OPERATIONS This chapter discusses some coding schemes for individual moduli and the resulting facility of arithmetic operations Two types of natural encoding result depending upon how one represents the integers with respect to multiplication. The first approach analyzes the abstract structure of the given prime subring, i.e., residue digito It is recognized that still a further decomposition is possible with respect to multiplication, A representation scheme is suggested by the direct sum decomposition of the component multiplicative subgroups. The second approach treats multiplication as a linear transformation on the additive subringo Such a treatment suggests a weighted code so that 1the fundamental property of multiplication, its distributivity, may be employed. This is the more conventional approach. It will be shown how codes may be constructed for arbitrary moduli by the use of redundancy. Furthermore, the redundancy may itself be used to speed up arithmetic operations, 6,1 CODES BASED UPON THE GROUP STRUCTURE OF THE MULTIPLICATIVE SUBGROUP The fundamental idea of the residue number system is the ring decomposition: RM - Rpla1 Rp a2 e — Rp m m 7p.i = M (PiPJ) = 1 i j ASD TR 61-483 77

where Ri denotes the ring of integers modulo i. If the pi are taken prime, there is no further ring decomposition possible. Nevertheless, the subrings Rp possess multiplicative groups which may be further decomposed. In general, the order of the multiplicative group of Rp a is a group of order ((pi.i) where $ is the Euler function. If p is Pi 1 prime and a = I, then ~(p) = p-l and the multiplicative subgroup includes all but the zero of the subring. Since p-l is not prime, this cyclic group may be represented as the product of its prime power cyclic subgroups. In number theoretic terms we are just saying that multiplication may be done by taking the index function of the additively expressed integers and performing a residue encoding. As an example, take R31o Column I contains the additive code for R31, column II the index or multiplicative representation, and columns II a, b, c the decomposed or residue representation of II. If ai 1 then the multiplicative subgroup will no longer include all but the zero of Rp a, since p, 2p, 3p, etc., will be "divisors of zero." In this case, a larger system may be constructed of which Rp ii is a homomorphic image. A semigroup acting like an exponent of p is adjoined to the multiplicative subgroup representation. This semigroup EF = (0,1,..., l has the operation defined as follows: x - y = max(a; x+y) x,yeEa Every element in %X is represented in the form x = ypi where y is in the multiplicative subgroup and i is in E1. The whole system is then ASD TR 61-483 78

Cq1 @ Cq2 ~ Cqn E Fa fqi = (pai) i=l TABLE 1 ENCODING OF THE MULTIPLICATIVE SUBGROUP I II III I II III a b c a b c C31 C30 C2 C3 C5 C31 C30 C2 C3 C5 0 -- -- -- -- 16 6 0 1 1 1 0 0 0 0 17 7 1 1 2 2 24 0 0 4 18 26 0 2 1 3 1 1 1 1 19 4 0 1 4 4 18 0 0 3 20 8 0 2 3 5 20 0 2 0 21 29 1 2 4 6 25 1 1 0 22 17 1 2 2 7 28 0 1 3 23 27 1 0 2 8 12 0 0 2 24 13 1 1 3 9 2 0 2 2 25 10 0 1 0 10 14 0 2 4 26 5 1 2 0 11 23 1 2 3 27 3 1 0 3 12 19 1 1 4 28 16 0 1 1 13 11 1 2 1 29 91 0 4 14 22 0 1 2 30 15 1 0 0 15 21 1 0 1 As an example take R27 = R3. Column I gives their additive representation, column II the index if it exists or a factorization ypi if i O0. Column III a, b the residue representation of the index and column IV the exponent. Notice that the system contains a certain amount of redundancy. The number six could have just as easily been represented at 11.3 or 20.3. ASD TR 61-483 79

TABLE 2 FACTORIZATION PROCEDURE I II III IV I II III IV a b a b C27 CL8 C9 C2 E3 C27 CL8 C9 C2 E3 or or Factorization Factorization 0 1.33 0 0 3 14 17 8 1 0 1 0 0 0 0 15 5.31 5 1 1 2 11 1 0 0 16 4 4 0 0 3 1.31 0 0 1 17 15 6 1 0 4 2 2 0 0 18 2.32 1 0 2 5 5 5 1 0 19 12 3 0 0 6 2.31 1 0 1 20 7 7 1 0 7 16 7 0 0 21 7.31 7 0 1 8 3 3 1 0 22 14 5 0 0 9 1.32 0 0 2 23 11 2 1 0 10 6 6 0 0 24 8.31 3 1 1 11 13 4 1 0 25 10 1 0 0 12 4.31 2 0 1 26 9 1 0 0 13 8 8 0 0 There appears to be at least two possibilities for application of the multiplication decomposition exhibited above. The most obvious is to use a machine code that is based on this decomposition. The desirability of such a scheme appears questionable except in rather exceptional circumstances. The fundamental question, of course, is how one adds in such a code. If a reasonably fast technique for addition were forthcoming, it might be reasonable to consider using the multiplication code since multiplication in the multiplication code is considerably more easily accomplished than addition in the normal code due to reduction of carry problems. Nevertheless we are not too hopeful since there is no distributive law operatASD TR 61-Lv83 80

ing so that, addition can be done by only multiplication as one can the converse in the normal situation. The other possibility is to somehow use the multiplicative decomposition in the logical design of the multipliers where a more conventional code is used as the basic machine language, This is essentially dependent on conversion from conventional to multIiplication code and reconversiono This problem ressembles the radix based-residue conversion problem except on a much reduced scale and the techniques developed there are applicable. Some techniques which appear quite expensive in time and hardware for the gross conversion problems will be applicable at this level because the order of the subring being decomposed will be of very moderate magnitude. A further distinction is that the completely reduced codes would only have to be added whereas in the ring decomposition one must both add and multiply in the subrings, The use of this code within residue multipliers would be indicated if mappings were used rather than sequential methods, 6.2 CODES BASED ON MULTIPLICATION AS A LINEAR TRANSFORMATION The type of weighted binary code with which this section deals in the following. It consists of a set X= [Xo,. oxn-l], xe{O;l1 of 2n elements. The set is interpreted by a set of weights W = wloo wnj and a modulus M where the wi and M are integers with wi < Mo We further require the following relation on the weights I~W ecW= (2~ mod M)eW ASD TR 61-483 81

This latter property ensures that addition of code elements may be done using ordinary carry procedures. Also we shall consider only the case where M is an odd primeo The work is easily generalized to the case of composite moduli, at the expense of a certain amount of notational inconvenience. A code or a subset of a code is said to be complet if for every positive integer k < M there is at least one xEX such that /n-1 X k L {L xiwi)mod M. It can be noted immediately that if M < 2m the entire code will be complete. We shall be primarily interested in the completeness of certain subsets of codes. If wo = i and wi+ - 2wimod M, then because of the restriction on the weights and modulus, it must be that 2wn_1 1 mod M. Since for each wi, there exists a wj such that wj - 2wi mod M then a permutation xi->xj results in multiplication by 2, Repeated shifts will therefore generate all powers of 2 modulo Mo Thus there is set up a correspondence between certain elements of the code set and a cyclic permutation of the bits of the code. This correspondence is the basis of the ordinary pencil and paper method of doing multiplication as well as conventional machine multiplication with the slight difference that in our case we have a true permutation whereas conventionally one bit is "lost" and a zero introduced. It should be clear at this point that we have described what is sometimes called a reduced radix code. This is the special case obtained when M = 2 -1. We mention another coinmonly known example of this class which is not usually ASD TR 61-483 82

thought of as a weighted code at all. It is the one digit per wire code. In this case n = M-l, and the weight set includes all possible weights, These two well known coding schemes are the extremes of all codes of this class. In the case of the former, there is almost no redundancy (zero has two forms) but the arithmetic must be sequentially, The one digit per wire code on the other hand has extremely high redundancy while permitting simple combinational arithmetic, It is our purpose to investigate those codes lying somewhere inbetween, Consider the code M = 17, n - 8, W = (1,2,4,8,16,15,13,9}. In this case the weights are entirely generated by powers of two. This code may be viewed as using the reduced radix code for 28 = 255 to represent numbers modulo a divisor of 255. Notice, however, that by introducing all this redundancy it is possible to select a complete subset of this code with some very nice properties. The following subset has the useful property that no element has more than two bits which take the value one. This property ressembles the property of the one digit per wire code in that it facilitates arithmetic. It is not quite as easy to do arithmetic in this code, but on the other hand it is much less redundant. Addition may be done quite easily in this code using adders in each position consisting of one two input "and" and one three input "or." At most, 2 levels of logic are required regardless of carries because carries can propagate only one levelo This results from the additional property of the set chosen that no element has two adjacent "oneso" ASD TR 61-483 83

TABLE 3 THE CODE M = 17, n = 8 Wi 1 2 4 8 16 15 13 9 X0 Xl X2 X3 X4 X5 X, X7 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 3 0 0 1 0 1 0 0 0 4 0 O 1 0 0 0 0 0 5 1 0 10 0 0 0 0 6 0 0 0 1 0 1 0 0 7 0 0 0 0 0 1 0 1 8 0 0 0 1 0 0 0 0 9 0 0 0 0 0 0 0 1 10 0 1 0 1 0 0 0 0 11 0 1 0 0 0 0 0 1 12 0 0 0 0 1 0 1 0 13 0 0 0 0 0 0 1 0 14 1 0 0 0 0 0 1 0 15 0 0 0 0 0 1 0 0 16 0 0 0 0 1 0 0 0 YXi Ci Or Si Figure 1. An adder for the M = 17, n = 8 code. ASD TR 61-483 84

Unfortunately the sum produced may no longer be a member of this special subseto It is necessary to retrieve this proper form prior to doing further arithmetic. The nature of the ccomplexity of this problem is not yet known sufficiently to make final judgemento It is known that in special cases, reduction networks may be designed such that the total addition time plus reduction is competitive if not superior to conventional binary addition, Futthermore the complexity of the coding networks seems to increase only linearly with the number of bitso Notice that complementation may" be done either by complementing each bit individually or by a simple permutation since "-1" is included as one of the weights. If a complete set exists having only at most 2"one" bits per digit, multiplication is reduced to a single addition of the two appropriate permutations of the multiplicand0 In the example given above, the weights were generated by successive powers of two, This is not the only manner in which a set of weights meeting the criteria may be generated. The set of powers of two form a multiplicative subgroupo Any coset of this subgroup is also closed under multiplcation by two and therefore may be included in the weight seto Consider 1,2,4,8,16 1. the set of weights 1>6,12,24,17J and M 31. This code has a complete subset having the 2 "one" bit property. The only difficulty here is that there are no permutations corresponding to the coset weights {3,6,12,24,17], and therefore multiplication cannot be carried out by successive shifts and adds, In order for this property to be retained, it is necessary that the cosets p1,2,4,8,16 X themselves form a subgroup under multiplication. Thus the set j3029,27, 23,1J ASD TR 61-483 85

would be a better choice since the cosets are now isomorphic to the 2 element group (1,303. In general, it is easy to determine closed sets of weights of arbitrary order dividing M, using powers of primitive roots as generators. The problem of determing whether a code has a complete "2 one's" subset is more difficult. The coset decomposition of the entire multiplicative group allows a short cut to be usedo If any element of a coset is representable with only 2 one bits, then every other element in the coset also is, since each is only a permutation away. Thus, only the least element in each coset need be examined. Consider as a final example a coding for M = 127. Certainly the weight set must include (1,2,4,16,32,64 } If no additional weights are used, the almost non-redundant reduced radix code of seven bits results by adding the ]1,2,4,8,16,32,64 subgroup generated by 36 126, the 14 element subgroup 126,125,123,119,11 95,63 results. This code has a "3 one's" complete subset but no "2 one's" complete set, If the subgroup of order 3 generated by 342 is used, the resulting 21 weight set does yield a "2 one's" complete subset. In concluding these remarks about redundant weighted codes it should be emphasized again that the recovery of the cannonical form of a number is the big question in the practical utilization of these codes. If moderate success is met here, the way is open to use very large moduli with a resulting saving of scaling and base extension time. ASD TR 61-438 86

CHAPTER VII DIVIS ION 7.1 INTRODUCTION The definition of a division in Euclidean rings suggests that algorithms for performing it will be crucially tied up with magnitude comparison. Given two elements (ab) it is desirable to find a (q,r) such that. a = bq + r and r < b The difficulty of recovering the natural magnitude ordering from the residue representation had initially led us to suppose that division within the system would be very difficult also. Recent workers have recognized essentially three different approaches. a, Devise a really efficient magnitude comparison scheme; more conventional algorithms will then prove feasibleo b. Do division in some other closely related systems such as a mixed base system. c, Find an algorithm which is independent of magnitude tests, This chapter is devoted almost entirely to the approaches of the third type, The brief discussion of the first two approaches is given for purposes of contrast Considerations of the nature of the sign detection problem have been made in other parts of this report. While it is not so fair to say that no improvement can be made in the presently knowri sign determination scheme, it is clear that sign detection will remain essentially as time consuming as ASD TR 61-483 87

division by a divisor of the moduli of the system. Since, the division algorithms used in class C also use these "division by a constant" procedures any improvements in sign determination techniques would yield a corresponding improvement in techniques of type C also. With regard to algorithms of type B, mixed base system division seems to be awkward at beste It certainly is more complex than any binary division even without consideration of translation time. This approach appears to be the least valuable of the three, since it has rather extensive hardware requirements without really being very fast, The magnitude determination free techniques known to us are all iterative in nature and resemble most closely the non-replacement techniques of conventional binary division. With respect to these algorithms, several important questions must be asked. 1. What is the rate of convergence? 2. What are the hardware requirements? 3. Are any initial estimates needed, and if so, how are they determined? 4, What is the stopping procedure? 5. What type of arithmetic systems can this algorithm easily be fit into? 7.2 AN APPROXIMATE DIVISOR METHOD This algorithm utilizes the fact that inverse multiplication corresponds to ring division if the remainder is zero. Let: m M = pi (i=,2,..m) i-=l ASD TR 61-438 88

be the modulus of a residue number system, Let Z be the set of 2m numbers less than M of the form m bi 7Pi bi (0,1}. i=l It is well known that division of any number in. the ring of integers, modulo M by zcZ may be performed in a straightforward way by successively reducing the dividend by an amount necessary to make it exactly divisible by one of the component primes of the diviser, and multiplying by the reciprocal of that prime, In general, the division of x by z will take either 2n or n steps depending on whether one counts substraction and multiplication as 1 or 2 steps, If m primes compose z, then the remainder of the n-m stages are necessary to re-extend the quotient to full length. Using the set Z to approximate y for divisors the following algorithm; may now be employed, To divide x/y; x,yeR; 2y > z > y; zcZ = r J =X - y qi qi-l ri ri -= r - L-i stop when qi = qi- L An error of 1 will occur if every y < ri < z which may be corrected by comparison of ri with y following qi = qj if an exact answer is necessary, It is not necessary that z > y; however, the partial quotients will be of opposite signs on successive iterations if z < yo The rate of convergence depends on z/y. Let y = (l-e)z and x/y = qo ASD TR 61-438 89

The Si are the partial sumands qi-qi _(l-c)x q(l-) r X (l-C)x y = o y x y - Si = = q(l-E) ri = xE y y y = x[E-c(l-C) ] = X Si XC (l)- = q(l-c) i ri = xci - xi(1-) y = x[Ci-(l-e = x x[i-(j-E)EJi] = XE The error after i iterations will be q(l-e)(Ci + i+l..) = qi for q <10 then for qi < 1 ci < 10-a i loge < -a i > a/loge'expressing e as a function of i and a, then e < 10 / The convergence of this algorithm is crucially dependent upon how well the set Z approximates arbitrary divisorso In the partical cases where only a few moduli are used it would appear that this algorithm would not be feasible if a fast division were sought. However, in systems including a large number of different moduli the closeness of approximation is remarkable, The system consisting of the primes less than or equal to 31 was considered in detail. The set Z was tabulated and ordered, A set of twenty-five random divisors in the range 105 to 106 was examined to see how closely they might ASD TR 61-438 90

be approximated. Assunming these nunmbers to be divisors of dividends of the order 101 a quotient of less than 106 will, be produced, The approximating zcZ for each number was determined along with the necessary number of iterationso For all numbers examined the number of iterations was either 3 or 2, As an example consider the computation of 10,00,000,000o/815,392 z = 817,190 = 10,000,000,000 12237 r = 10 - (12,237)(815,392) 817,190 22,048,096 q = 12,237 + 22 048096 12,263 ri - 22,048096 - (26)(815,392) 817,190 847,904 q2 = 12,263 84790 12264 r 847,94 - (1)(815,392) 817,190 q = 12,264 * 32,512 r - 32,512 Note that for this particular divisor, which was chosen at random, the probability of an error of one in the quotient for a random dividend is less than 1%o There are three possible means of terminating this procedure. A fixed number of iterations can be usedo If indeed it were shown that three is the largest ever needed, such procedure would be the best, For a very small divisor however, this may not be sufficient as the approximations are not as good. The test ri+1 = ri does not involve either additional hardware nor significant additional controls, However, given ri +l = ri, one additional unnecessary iteration has already been performed. Nevertheless, the insurance ASD TR 61-438 91

that the error in the quotient is at most one, makes it more desirable than the fixed length procedure, unless the particular arithmetic system used scales a.. nunmbers in!to a range where the approximations are always goodo The third method involves c-omparison of rL with a real divisor and therefore, an additional cycle of n operations following the conditions ri = i+i~ This is the only method for determining an exact quotient0 It appears that this additional test would best be left tc the prograJmner just in case an exact quotient is required, since for most uses the error involved is unimportanto The hardware requirements for this algorithm are moderate in addition. to the residue multipliers and adders which will already be available, A control register of n bits is necessary to indicate the base primes used in the approximate divisor, D.e hardware for producing the approximate divisor is an additional problemo It appears that this may most efficiently be implemented by a'table-look-up procedure, Indexing this table requires the first two or three digits of the mixed base representation of the divisor and requires the equivalent of an additional iteration~ The magnitude of the table required for this system illustrated would be about 2000 eleven bit words, which is not prohibitive, The remaining two algorithms are essentiality unrelated to the residue number systems itself, )but it is of interest to see what difficulties ensue in their realizatio.no Both methods require a fractional multiply operation. It is not yet certain that; alle possible utilizations of residue arithmetic would entail, having a fractional multiply, however, for any conventional numerical analysis it seems likely. Fractional multiplication schemes all inASD TR 61-438 92

volve division by one of the divisors of the moduli. It is fair to compare the number of iterations of the above described algorithm with the number of fractional multiplications of the two algorithms described below. In a system that permits postponement of scaling, i i reasonable to count the number of scalings necessary, rather than the number of multiplications. 703 A NEWTON-RAPHSON METHOD A Newton-Raphson method is derivable from b 0 A b. - x ax a i.e., xi+ = Xi - f(xi)/f'(xi) b b ax0 = Xi - (x _)/( ax 2)^ ~ < 1 ax. i(2 - ) This is useless directly since it involves the calculation of a/b. If b 1 however, then xi+ - xi ~ (2 ax), laxo - I < 1 is quite satisfactory since one may compute I/a and then multiply by b. These procedures converge exponentially since if Xi = (l-c) o x then xi + = (l-~) e x[2 - (a/b)(1-c)x] (l-e2) ~ x ASD TR 61-438 93

so. 1 + 1 il Given an xo suc-h that co < 2' then c < 2 40 which is of'the order requiredo This con:rtrasts favoraily w'ith -the third algorithm. Xi+i = xi ~ I+b-axi) b < for xi = (1-c) ox, x i = x(ti-) [Tl+b-a(l-c))x = x(i-G) ~ ('-Fb) = xyl-e(l-b)-bc2] so'i~l _-(l-b) i~b+b 1 - b +- bec which is very poor if (i-b-) is not very close to 0o It is possibole to scale b by one of the divisors of the modulus of the residue system, howevser this still results in a geomet ric convergence to better than tlhat provided by the approximate divisor method which does not require fractional multiplication,o Te scaling would require hardware similar to the obtaining of,the approximate divisor as in t;:e first method described, 74 INIIAL APPROX7IMA!TO7N..S it is possible to use a uniform xo in the reciprocation formula. For integral a, then a very small x0 will always sati sfy Il-axol < I A decent approximation, however, is clearly necessary since if (!-c) is the requ:ired ASD TR 61-843 94

precision then the number of iteration i must be such that 2i ( C < 2f >(logc)/iOgo i > iog2 loge/logEo 1i -,.1 i > iog2log E - iog21og E which for co close to 1 becomes largeo As an initial approximation, one may use a table-look-up; however, the index to such a table must reflect relative magnitude and therefore, for residue numbers, requires a conversion to mixed base, Still, such an approximation is superior to a linear approximation which would require about the same time but no table. We consider now a system which is mentioned else where in the report which involves the use of a "double length plus" expression of numbers when in the arithmetic unit. The use of this system is convenient in both the initial approximation procedure and in performing the iterations themselves, If the size of the system is such that the double length magnitude M* is of the order IM2 where MvI is the single length magnitude then in approximately the same time, one can compute a quadratic approximation where the coefficient of the second order term is a small integer less than L. This is possible since where the fraction x is represented as [xM], the first coefficient is represented directly [a] while the second and third as bM and cM2, so that ax2 + bx + c is represented before scaling ASD TR 61-438 95

[a][xM]2 + [bM][xM] + [cM2] = [ax2M2 + bx] + [cM2] [(ax +bx)M2] + [cM2] which becomes [(ax2 + bx + c)M2] Overflow will not occur as long as [(a+b) < L], A comparison of approximation techniques is somewhat difficult because of the measure of goodness of fit. Ideally one wishes to minimize the expected number of iterations which is I I c + [- log log - (a)l]da given a uniform distribution of Xo If f(a) is the approximation of 1/a then co = l-af(a) and only a numerical solution appears feasible. A simple least squares measure should, however, give a rough comparison. The best-fitting quadratic using a least squares criterion results from the solution of the system of linear partial differential equations: _ = 0 = _ 1 _a ab bc 1 [ l-x(ax2 + bx + c) ]2dx. These equations easily reduce to three linear equations in the coefficients. The solution yields a nonintegral value for a, however the linearity of the system insures a unique local maximum, and the best integer values for a may be determined by inspecting the two nearest integers. The hardware requirements in addition to those already needed for the fractional multiple are almost negligible= The only additional equipment is ASD TR 61-438 96

that associated with determining the initial approximationo Depending on the type of instructional organization used in the machine, it may be possible to do away with the division instruction per se, altogether. The condition under which this would be possible without loss of speed would essentially involve a streaming mode of operation, similiar to that used in computing the vector dot product Before concluding this chapter, it is important to emphasize again the impossibility of deciding on a'best division algoritbm without considering the system on a whole. In our opinion, the Newton-Raphson Reciprocation procedure is clearly superior to any other known if a fast fractional multiplication has already been purchased. Its exponential rather than geometrical con.vergence plus its lower hardware requirements make it quite satisfactory., The other algorithms might have use in certain limited, special purpose applications where a full fractional multiplication is not desiredo ASD TR 61-438 97

I I I I

CHAPTEFE VII TEE MUL IIT PLI2ATIVE OVERFT LO PROBLEM 8.1 INTRODUCTION The problem of multiplicative over-fl.ow detection is one that is unique to systems in which the multiplication operation is accomplished in one step. In conventional systems, those in which multiplication is performed as a series of additions, the detection of multiplicative overflow can be handled by the detection of additive overflow. One of the main advantages of a Residue Number System (RNS) is its adaptability to a one-step multiplication operation. it follows that one of the more pressing probl ems of a RNS is that of detection of multiplicative overflow. In any finite number system, an obvious way to prevent overflow under multiplication is to require that every number to be processed be less than the square-root of the system's limit, The product of any two such numbers will be less than the limit of the system, and no multiplicative overflow will exist. But this restriction must apply to every step of each calculation, and merely represents the substitution of a scaling problem for the one of overflow detection. A universal problem of finite machines, whether their organization is integer or fractional, is the one of scaling the double-length result of multiplication back into single-length form, This problem has a solution ASD TR 61-438 99

that takes the form of multiplication by a constant. In a RNS of singlelength capacity m, where the residue representations are interpreted as integers, that constant is the inverse of mo In his work on RNS, Svoboda2 suggests handling this scaling problem by employing a double-length multiplier whose capacity is at least as great as the square of the capacity of the single-length system, He then employs a procedure which is essentially division by m (the single-length capacity) to rescale the result of multiplication into suitable form for further calculations. The unfortunate feature of this method is the amount of time required for the digit-fill-in operations (single-to-double-length and vice versa) used to implement the scaling processo Cheney9 has suggested a method which involves scaling by combinations of the individual base primes. The precision achieved by this method is not as good as Svoboda s, but the comparison is somewhat unfair since Cheney does not use the double-length idea. The question of precision will be treated more fully in the last section of this chapter. The individual-base scaling procedure is awkward and cumbersome. As a result it is time-consumingo Even if precision were equal for the two procedures, this one suffers by speed-comparison. Consider now an, extension of Svoboda's concept to include what will be termed multiple-precision. This title may be misleading, as the direct result is a gain in speed while precision is increased non-uniformly. That is, the increase is slight (or non-existent) in some cases, while present to a greater degree in otherso ASD TR 61-438 100

The proposed extension is accomplished by attaching positional significance to each of a group of RNS representations (as in, for example, a decimal number) and allowing the propagation of carries between subgroups of these representations. Such an arrangement, with the operations of truncation and scale-factor multiplication, constitutes a Floating-Point number system. The arithmetic of this system is apparently retarded by the necessity for carries, but carry assimilation is accomplished as a part of the scaling operation. The speed advantage of this system comes from the fact that the subgroups of RNS representations (the coefficients) are small. This permits the standard RNS operations to be accomplished rapidly. The digit-fill-in and scaling operations are performed on the entire number by processing several small parts of its simultaneously. A complete description of these operations is continued in the following sections, The two parts of this chapter which follow are both methods of employing this parallel structure. The system contained in Sections 8.2 through 8.8 is primarily a general purpose structure, while that of the remaining sections of the chapter is intended for special purpose use. That is, the one considers everything that might occur, while the other ignores or minimizes certain problems under the assumption that they will occur infrequently, if at all. The original starting point for the two developments was different. The former is a result of an inquiry into the general problem of multiplicative overflow. The latter came about as a use for the redundancy established by ASD TR 61-438 101

an extra-length representation. There are two main areas of dissimilarity between the two methods. The first is the question of whether the sign of a number should be carried along explicitly in the representation, or be allowed to remain implicit within the representation. The second is a question of the size of the double-length system; whether its capacity should be the square of the capacity of the single-length system, or slightly larger than the square. Rather closely connected to these two areas is the question of when and/or how often the internal scaling procedure must occuro Perhaps each system is superior for its intended use, or even for a series of specified uses. Given a well-specified purpose, the two systems could be carefully compared to determine equality or the superiority of one over the other. 8,2 APPLICATION OF THE SQUARE-ROOT CRITERION This direction of attack upon the overflow problem branches off from the square-root criterion. Consider, for the bases of a RNS, some sequence, 3, of composite numbers 3 = 5ioo^n subject to two restrictions: (ij) = 1, j(8-1) 31 - pf (8-2) ASD TR 61-438 102

The first restriction is equivalent to, and may be replaced by, the following restriction on the set, P, of su-bbaseso (Pi,pj) = 1, i A j (8-3) The set, P, may be thought of as a sequence of prime numbers with no resulting loss of generality, Consider also, in the matter of coding the modular representations of the RNS with respect to the base i3, the use of a two-digit uniformly-based number with base pi. Such a coding does indeed accomplish the representation, although it requires one carry-digit within each composite-base representation, The following formulas serve as a summary of the discussion of this section: N - imod Pi, 0 N < M (8-4) n X = M H i = P2 (8-5) i=l ~i = ailPi + aio (8-6) It follows that the zero power, or units, digit (aio) represents the residue of N with respect to p.i Thus there exists a readily available ndigit number which represents the residue of N with respect to m, where m= vM = (pi (8-7) i=i These n digits are the units digits (aio) of the n representations of N modulo i(i = 1,2,.8,n). ASD TR 61- 43 8 103

8.3 CONSIDERATIONS OF THE DOUBLE-LENGTH SYSTEM If a number, A(O < A < M), is considered to be of the form A = am + a (8-8) it is clear that ao may be found by some reduction process involving the single-length system m: if you will, the "square-root" system m. That is, since Oao<m and the n units-digits of A(aio; i = 1,2,...,n) are available by inspection, the search to find ao may be limited to the m-system. Digitfill-in of ao from the m-system into the M-system acquires the first-power digits of ao, and subtraction of this result from the original representation of A leaves alm as the new representation. Because alm is an integer multiple of m, the units-digits of this representation are all zeros. For this reason, consideration may be limited once more to an m-system representation, in this case involving the first-power digits. Division of this representation by the first-power digits of the representation of m, along with m-system to M-system digit-fill-in, yields a,. The above paragraphs describe a complete reduction of the M-system representation of a number to more conventional form by means of m-system operations. With the background established so far, investigation of some properties of this "square" system may be undertaken. The redundancy established by this particular system, the easy availability of the square-root residue, is gained only at the expense of providing a carry-digit within each composite-moduli group. But this system is useful in the scaling aspect of the problem. The redundancy provides the ASD TR 61-438 104

necessary magnitude information for scaling, which makes division by m a simple operation. 8.4 MULTIPLICATION Consider the multiplication of two numbers A and B (0 < A, B < M) in algebraic form. A = aim + ao, B = blm +bo (8-9) AB = alblm2 + (aobl+albo)m + aobo (8-10) Each of the ordered pairs (aibj) represents a non-overflow situation since, by the nature of the system, every ai, bj < m. The interesting part of this is not in the possibilities for detection of overflow, but in other possibilities suggested by the ordered pairs. These numbers are all readily available in the system, and the products are guaranteed non-overflow. Through some system of manipulations they may be carried along to give a complete description of any number, though it be arbitrarily larger than the finite limit of the sub-system, Such factors as truncation and round-off may be considered if an approximate answer is acceptableo For example, it may be considered necessary to keep only the four most significant coefficients, any remaining terms then being discarded. Now consider a more general multiplication, AB, with A and B not restricted in magnitude as they were previouslyo Let R be defined as the reduction operation of Section 8.3, and understand R1 to be the first (ao) portion of this operation, while R2 shall be the remaining (al) portion. ASD TR 61-438 105

Let r A = 7 aimi (8-11) i=O s B = E bjmi (8-12) j=O r s +i AB = C = Z cdmd (8-13) d=0 where 0 < ai,bj,cd < m. (8-14) The multiplication AB results in several ordered pairs, aibj, and by the restriction of equation (8-14) 0: aibj < M (8-15) so that the operation R, when applied to these products, gives R aibj Cijim + cijo (8-16) in which 0 cjji < m-i; 0 cijo < m. (8-17) Define, for the collected term of multiplication: Ck = z cijt (8-18) i +j +t=k Since the number of terms collected is very small compared to m, 0 < Ck <<m2 (8-19) ASD TR 61-438 106

Now, under a further reduction step: R (8-2O) ck -> ckm + Cko (820) The restrictions upon these coefficients follow from equation (8-19) 0 < cki << m; 0 < Cko < m (8-21) At this point, AB = C may be expressed as follows: r+s C = S (cklm+cko)mk (8-22) k=O Since the largest number expressible in this form is given when A = m -- 1 (8-23) B = m S - 1 (8-24) AB = mr - - ms+1 + 1 (8-25) it follows that C = AB < mr 2 (8-26) and Cr+s+2 = 0 (8-27) Thus, finally, the form of equation (8-13) is obtained r +s +1 C = z cdmd. d=O Since the cd's must satisfy the restriction of equation (8-14), they must result from a process of reduction upon the ckt's and completion of the carry ASD TR 61-438 107

(or scaling) processo An exception is cr+s+l which will never propagate a carry, as a result of equation (8-27) An estimate of truncation error would be in order at this point. Let the decision be made to store only the four most significant coefficients of any number, the highest-order of which is non-zeroo Thus if A = armr + arlmrl + ar_2mr-2 + ar_3mr3 + ar_4mr +... (8-28) bsms + bs2lms-3 s-4 B = bsm + b 1m s-l ~b2ms + bsms-2 + bs-2ms + bs +... (8-29) certainly AB < arbsm (8-30) while the highest-order neglected term is (ar-4bs + arbs-4)m 4 (8-31) Therefore the error is given approximately by arbs 4 + ar-4bs arb m4 (8-32) In the worst case, with ar, bs — 1 and ar-, bs,4'v m, a rough upper bound on the error as obtained from equation (8-32) is 2/m3o While if ar, b ^ m and ar_4, bs_4 - 1, a bound on the error is 2/m5 In any case m need not be too large to result in quite a few significant demical digits with such an arrangemento For example, if the set P of sub-bases is (2, 3, 5, 7), m = 210 and 2/m3 - 2.16 x 10-7 And if P is (3, 5, 7, 11), m = 1155, 2/m3 -v 1.3 x 10-9 This demonstrates the feasibility of a "small" BRNS ASD TR 61-438 108

Figare 2 is a schematic description of multiplication in the proposed, floating-point RNS. The justapositions (aibj) all indicate non-overflow RNS multiplications, the R operations are as defined earlier in this section, and the additions indicated are also non-overflow RNS operations. a3b3 a3b2 a2b3 a3b1 a2b2 alb3 a3b0 a2b1 a1b2 aob3 a2bo albl aob2 R R R 1R j; R R R R IR jR R R C331 C330 C320 c310 c300 C200 C0321 +C230 +C220 +C210 + 110 i 0231 3 1 1 + 130 120 + 020 +C221 +C301 0+30 + 131 +211 +2201 +12 1 + 1 1 _c_031 +C021 C7 06 C5 C4 3 02 R R R R R C7 C60 C50 C40 C30 C20 Vc61 < 2; c51 < 4; c41 < 6; +061 +051 i041 +-31 +021 *** 1C31 < 6; C21 < 2; c7,cio < mj C7 C6 c5 04 03 X R R IR R C7 C60 050 C40 C30 +061 -+51 +041 +031 { cil 1; C7,Cio < mi C7 c6 5 04 C3 R R R C7 C60 C50 C40 C3 (T: Truncate, if C7 0O) c61 +051 +041 07 C60 C50 C4 03 R R ***See Section 808 for ^ ~\ ~ ~~ J^~~~/ >carry-completion c7 C60 C50 C4 C3 sensing. + 61 +051 C7 06 C5 04 03 Figure 2, Multiplication in the floating point BRSo ASD TR 61-438 109

The first level shown is actually the only multiplication involved, the remainder of the operation can be regarded as scaling to get the respective digits back intc the C < mi < m rangeO This scaling can take place quite separately from the multiplicationc leaving the thirteen side-by-side Msystem multip lication units free immediately for a new cperationo The results are no't immediately available for further computation, however, but must first be processed through the reduction "grinder " The red:cti-cn ma -hine will consist of various levels and may operate as a unit- or as several semi-independent stages. Some of the stages may prove useful for operations on, added numbers, etco The "grinder" may also be processing a sequence of numbers at the same time in different stages, with a continuous flow of results from the outputs In Figure 2, A and B are taken to be of the following form: A = mr(a.sm3 + a2m2 + alm + ao) (8-33) B = m (b3m + b2m2 + b1m + bo) (8-34) Manipulation of the "exponent" (m ) is not shown, but understood, At the first level of reduction, thirteen side-by-side R-type units are necessary' These are folloowed by five adders, followed in turn by five Rtype unirtso N'ext come five adders, followed by four R-type units, As was seen in equatiion (8-2'7) further attention to c7 is unnecessary as it cannot overflowo At this level, fs ou ad.es a re necessary and truncation can occur by dropping 030 In the worst case three more levels are necessary, with R folASD TR 6!-438 110

lowed by adder, The number of elements needed would decrease with each stage, It is possible that carry-completion sensing would be both possible and profitable. That subject will be taken up in a later sectiono 8.5 NUMBER FORMAT AND MAGNITUDE COMPARISON A description of number format is now presented in order to lay the groundwork for a discussion of some other operations in the system. The system-description of a number, A, shall consist of a magnitude-plus-sign arrangement. The magnitude is to be represented by four coefficients with positional significance, and an exponent term, S(A) is defined to be the sign of A, and may be represented by one bit. S(A) a3 a2 al ao r (8-35) where 0 a a1 < m, while r = 0 41, ~+2,,.o~q (8-36) Equation (8-35) is then defined to mean A = S(A)(a3m3 + a2m2 + a1m + ao)mr (8-37) The magnitude comparison operation may now be accomplished by a threestep procedure. If A and B are represented as suggested in equations (8-35, 36, 37), then: 1. Inspect the signs; ao If they are different, the positive one is larger. b. If they are the same, proceed to step 2. ASD TR 61-438 111

2, Inspect the exponents; a, If they are different, the more-positive one corresponds to the larger nurmbero b, If they are the same, proceed to step 3o 50 Complement bi(i = 0 1, 2, 3) with respect to M, add A+B = C. Operate on ci with Ri, Ispect c31m a, If c3im n C, B > A> b, If c31m = 0, inspect C3o. 1. If c 30 00 A > Bo 2. If C3 = 0 inspect C21m, The complete operat-ion R is not needed in step 3, because the question of magnitude is determined by whether or not cilm is zero, This information is available at the output of Ri, Figure 3 is a graphical aid for step 3 above, The X under sign and exponent indicates that they are of no interest in this step. S(A) as a2 al ao r S(B) b3 b2 b1 bo r X 0C3 c2 C i Co X,I jRi j1 RI C31mnC30; 212MC20; ClmC10; C01om,00 Figure 3, Step 3 of the magnitude comparison. 806.TIfE FOUR CASE-SS OF ADDITION For the addition of two numbers, there are four cases of interest, Inspection of -the signs and exponents of A and B determines the case in any particular instance, For convenience and simplicity, A is assumed always positive, with more-positive relative exponent if the exponents are different. The four cases are: ASD TR 61-438 112

1. Same exponent, same sign; 2o Same exponent, different signs; 3o Different exponents, same sign; 4, Different exponents, different signs, Addition in case 1 is acom nplished by positional addition of corresponding coefficients. The sign of the result is the same as the signs of the two numbers. The exponent must be determined in the scaling process. Truncation (T), the right-shift of coefficients, and augmentation of the exponent as shown in the final stage of Figure 4, take place only if c31 A O No further carries are possible out of c3 or c2_, but in the worst possible case, three more sequential (R, Add) operations will be necessary to complete the carry process. It can be seen that only one carry (and of unit magnitude) can be transmitted from any position. That is, a position that generates a carry cannot propagate one. Thus, carry-completion sensing is suggested. + a3 a2 a1 ao r + b3 b2 bl bo r + c3 C2 cl Co r R R R m + Cc31 c30+C21 c20-I 11 010+01 Co + C3 C2 C1 C0 c c lr+l T Figure 4. Addition in the floating point RNS, Addition in case 2 is accomplished by, first, step three of the magnitude comparison operation. The next step is complementation of the smaller number, and then positional addition. This is followed by the R1 operation as in Figure 3. Then a check must be made on cii(i = 0,1,2). If cil = 0, the process is complete. if cil ~ 0: ASD TR 61-438 113

1. Add m to ci; 2. Add M-1 to ci+. This reduction process must be carried out three times in the worst possible case. However, a borrow can be propagated through the ith position only if cil = cio = O0 which suggests a possible borrow-completion sensing method. The sign of C is that of the larger number, A or B. The determination of r must, upon borrow completion, be determined by the highest-order non-zero ci, and a shift accomplished to put that ci into the c3 position. Addition in case 3 involves a relative shift to the right, of (r-s) positions, for the smaller number. At most four reduction processes are necessary to complete carry-propagation. Sign is carried along unchanged, while truncation and r-augmentation are accomplished as the last step. Addition in case 4 combines the right-shift of case 3 and the complementation of bi with respect to M as in case 2. Once again, borrow-completion requires at most three reductions (R1). The resulting sign is that of the larger number, while positional-shift and r-determination are accomplished as the final step. 8.7 DIVISION The division procedure in this floating-point system must be some combination of the familiar and the unfamiliar. The familiar portion is due to the similarity of the gross system-structure to the decimal system. The unfamiliar portion is due to the modular arithmetic of the sub-structure, One possible division procedure is graphically displayed in the flowdiagram of Figure 5. Some prior attention must be given to the orerations ASD TR 61-438 114

~ cd=cd+t l A j cdto:~t |~'' ~' "- yes A^ Add cd 1t^ ^^ ^ 118^ <0 -a — aPfa t A Arm ta), r A > B a a ~ a b a b __ Add Cd -^ do0l= C-C do^ ) x=2 ( Rab) cdod 0 l o " I'l (r) cdo dodi OloO.f. ~1^~I " do - "d IOC I'' a cd- * dCheck 1 ~ If: 03/A0; stop r6~~M3(a~~~~~b) I~~c2-0, "Hi~ c-cm, t-t-1, stop Figure 5. DabivisicOn coo; cncmS, ttt-i, stopt (Db ana - Cdo t tQ c, C^; c^ ^2. stop I~ A r_; a. 3 r i~ )! x=2 A-Bcd= r' I~j ^' " (r') i i+- C1 " cd-cdo Q I ______, N~ x o;o.f. *~1 - 1i1. gd * Cdtedo a i Cin R N Figure 5. Division in the floating point RNS.

involved, and the intent of the over-all operation explained, in order that the flow-diagram may be more easily interpreted. Given two numbers, A and B, in the form of equation (8-35), the sign of A/B = C will be determined, as in multiplication: If S(A) = S(B), S(C) = + (8-38) S(A) # S(B), S(C) = - (8-39) While the initial determination of the exponent (t) of C will be accomplished as t = r-s-3 (8-40) and may or may not require modification in the final step of the division procedure. This the number, C, will be represented by S(C). I c j t (8-41) where the box around cd(d = 0, 1, 2, 3), here and in Figure 5, implies that the number is in the storage location reserved for that particular final result For the calculation as shown in the flow-diagram, the signs of the numbers are ignored and the exponents are treated as though they were zero (excepting the final step). In other words, only the stems of the numbers (their coefficients) are treated in the calculation. The operation M3(A,B) is the step-three magnitude comparison operation of Section 8.5. The operation M3(a,b) is a reduced version of the same thing, ASD TR 61-438 116

operating on a pair of single coefficients rather than on two complete numbers, The A = Am operation is a single left-shift of the dividend, while the operation a3 = a3-,ra2a is a sub-system computation to obtain the new coefficient a3o The operation, Add cd to., is understood to leave cd = 0 upon completion, R1(x) is the reduction operation of Section 8,3, but is used only to detect overflow of the m-system in this procedure, The multiplications used in this procedure are not the full-scale multiplications of Section 8,4, The multiplication in the) sequence involves no carries at all and is a single-step operation involving two m-system coefficients, The (D sequence multiplication does involve carries, but it is the multiplication of a number, B, by a single coefficient, cd, and might be thought of as a "scalar multiplication" as opposed to the complete "vector multiplication" described in Section 8.4. The R3(a,b) operation is one for the selection of a reasonable first approximation for the quotient digit. It could be done by a table-look-up procedure; since the m-system may be relatively small, such a table could also be of reasonable sizeo However, it can be done by a simultaneous-reduction process, the reduction being to a non-uniformly-based number system, If a3 is of the form (0 < a3 < m) a3 - 1 UO2 x03 O4 (8-42) corresponding to the definition of equation (8-4), then the process a3 - a4 - o3 P4 - d2 p3____ -- il (8-43) P2 ASD TR 61-438 117

an operation in the m-system, must go to zero at one of the steps. If the pair of coefficients (ai,bj; ai > bj) are reduced simultaneously, when the b-sequence goes to zero the remainder of the a-sequence may be re-expanded into the M-system and used as the desired approximation. If both sequences go to zero at the same time, unity may be taken as the approximation. The ( and () sequences of Figure 5 are used to find and improve a series of quotient-digit approximations. The first approximation in each case is chosen in such a way as to be smaller than (if not equal to) the correct one. The loops increase the approximations by consecutive-integer-multiples until overflow results, thereby bracketing the correct result. Restoration is used, upon overflow, and a new approximation is then found from the remainder term. The remainders are always compared with the divisor for relative magnitude to determine the subsequent operation. When the remainder is smaller, the correct quotient-digit is the current sum in jc. Note that the M3(a,b) operations in the A > B portion of the sequence show only two alternatives, because the third one (a < b) does not exist as a possibility at that point. The convergence of this division scheme is roughly geometric. A NewtonRaphson scheme converges nearly exponentially and would thus be more desirable. This method has been presented in the spirit that these straightforward algorithms serve to demonstrate that the system is feasible with rather simple operations. 8.8 CARRY-COMPLETION SENSING There are several tools that might be of use in the carry-completion probASD TR 61-438 118

lemo For example, borrow-completion, in addition cases 2 and 4, may be sensed by testing every cil and cio after the application of R1 (as in Figure 3). If, for all i; cil, Cio C 0 then no further steps are necessary. Carry completion, in addition cases 1 and 3, is aided by the fact that carries cannot be both generated and propagated by the ith position. Obviously, if cil = 0 or 1 (for all i) the process is completed. Moreover, if any cil = 1 (it cannot be greater) then it need not be checked further. Figure 6 is a chart specifying the situation in detail, following the additional rule that if cil = 0, c(il) B 0 a further step is necessary. If i equals 3 2 1 0 N And ci equals 0 0 0 0 0 Then N corresponds to 0 0 0 1 3 the number of further O0 1 0 2 possible steps. 0 0 1 1 2 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 2 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 Figure 6. Carry completion. The scaling operation after multiplication is not as slow as it looks in Figure 2. It may be seen that carries occur only if m-6 n cio < m (in the worst case) at the starred level. Under the assumption of a uniform distribution of numbers in the range 0 \< cio < m, and taking m to be 1155, this ASD TR 61-438 119

represents less than a 1 percent probability. This may be detected by the criterion that cil = 0 (for all i) represents completion of the scaling process, Moreover, if carries do exist at that level, at the next level Figure 6 is directly applicable to the completion problem, under a change of the subscripts given by i = i+3. 8.9 POSTPONED SCALING AND SPECIAL PURPOSE MACHINES The most striking characteristic of RNS arithmetic is the substitution of the magnitude-control problem for the one of pure integer multiplication. The first approach discussed in this chapter demonstrates how ENS arithmetic may be used to construct a conventionally-organized machine. This means that the machine instruction code employed might be indistinguishable from a conventional machine instruction code. The difficulties in the RNS, however, might well demand a machine organization of a different type. The direction of exploration here is based on the maximum postponement of the time-consuming magnitude-control operation. The primary characteristic of a system using such an organization is an arithmetic unit capable of operating on longer-than-double-length numbers. This feature permits addition and subtraction operations on a set of products before scaling. Postponement of scaling necessitates "remembering," between operations, which numbers have been properly scaled and which have not. The best method of handling this difficulty depends on whether a general-purpose or special-purpose use is intended, General-purpose organization will require special scaling instructions, or perhaps tag bits in the ordinary instructions, indicating whether or not ASD TR 61-438 120

a result is to be scaled. The difficulties for the programmer, in keeping track of magnitudes, should be overcome by the use of compilers. Such compilers initially would need information as to the possible range of all input variables; they would keep track of each variable, inserting scaling instructions where necessary. The postponement of scaling requires an implicit sign scheme, since signdetermination is as difficult, in general, as scaling itself. An ordinary complement-system appears applicable to a multiple-precision RNS, with one slight difficulty. The base-extension procedure must differentiate between negative and positive numbers. The former must then be placed in the upper half of the double-length system. There are certain numerical-analysis procedures which can take quite natural advantage of scaling-postponement. The computation of the dot-product of two vectors is typical of these procedures. This operation occurs in relaxation methods for differential equations, in the formation of a weighted sum of neighbors. This procedure is basic to several matrix inversion algorithms. The design of a special-purpose machine for matrix inversion was considered in some detail during the past year. That portion of this study having to do with organization is included here. The suggested configuration appears to be considerably faster, at no great cost than conventionally-organized machines. The "streaming mode" of operation, with its resulting savings in instruction fetch, is of particular interest, apart from the use of the RNSo In some respects this organization resembles the "Harvest" device of IBM.0 ASD TR 61-438 121

8.10 A MATRIX-INVERSION COMPUTER The matrix-inversion problem involves little input-output data, but a great deal of arithmetic computation. The proposed computer is capable of handling up to 100 by 100 matrices. In any residue machine, the digits of the residue number may be coded in binary form. Only prospective moduli which are equal to (or slightly less than) powers of 2 can be coded efficiently in binary form. If a sufficient number of digits are carried throughout the computation (in this case the equivalent of 16 decimal digits will be carried) to insure the desired accuracy, either the number of residue digits required, or the size of the individual moduli, becomes excessively large. The time required for magnitude and/or sign determination is almost directly proportional to the number of residue digits. A multiple-precision system was selected as the best way to reduce the number of residue digits and to insure an efficiently coded number for storage. Sufficient accuracy can be obtained, using multiple-precision, to carry the equivalent of 16 decimal digits throughout the computation. The basic machine number will consist of four base "b" digits, where "b" is 127 x 128. A scaling factor, a, will also be part of the number. Each base "b" digit will be expressed in a two-digit residue code, the two digits of which are 127 and 128. These residue digits are then binary-coded, using 7 bits for the 127-digit and the same number for the 128-digit. A 64-bit storage word allows an additional 8 bits for exponent. The problem of matrix inversion can be broken down into a series of ASD TR 61-438 122

matrix multiplications. Matrix multiplication can be broken down into a series of "sum of products" operations' n =ij " aikbkj~ f the arithetic unit e r i to compute is "s of products" opIf the arithmetic unit can be organized to compute this "sum of products" operation efficiently, it will be ideally suited for the matrix inversion problemo In a conventional machine, a double-length accumulator is provided to insure that multiplicative overflow does not occur, The accumulator is made somewhat larger than double-length so that it is possible to computse the sum of several products without overflow, To this end each base "b" digit (expressed in a 127, 128 residue code) will be extended to a 127, 128, 63, 61, 59, and 31 code as soon as it is obtained from storage, These numbers are pairwise prime, Furthermore, their product is greater than 400 (127 x 128). The extended-base representation of each base "b" digit will be carried throughout the arithmetic unit, A block diagram of the proposed arithmetic unit is shown in Figure 7. The machine will be basically a two-address machine, The general storage is to be word organized, and divided into X and Y halves. The cycles of the two halves can be interlaced to reduce the time required to obtain both operands The "sum of products" operation will proceed as follows: i1 The two operands X and Y are obtained successively from storage. 2. Each operand passes through the base-extension unit and then to one ASD TR 61-438 123

X Storage Y Storage Base Extension, X2 X3 X4 Oxp Yi Y2 Ya Y1 exp ault. Unit _ Q) zt zt i_ 2l Exponent Coaparison Unit I I C ~ I ControlI 0Q ^'~'^~ ___ Shift Unit Scaling 7unt Zo Zc Zd Zs 2m ZS Zs Z, exp Figure 7. Block diagram of a computer. 124

of the operand registers. 3. When both operands are present in the operand registers, the actual multiplication can begin. The multiplication operation will involve forming several sets of cross products. As each set of cross products is formed, they are added into the Z registers through the shift unit (SU). To multiply two numbers together, it will be necessary to form four sets of four cross products each. It is evident that in the worst case, after one multiplication, some one of the Z registers will contain a number of order 4b2. 4. The SU is controlled by the Exponent-Comparing unit (ECU). The ECU adds the exponents of the X and Y operands and compares the results with the exponent already present in the Z register. a. If the exponent already present in the Z register is greater than or equal to that of the new product, the cross products are added through SU into the appropriate Z registers. b. If the exponent of the new product is greater than that already present in the Z register, the contents of the Z register are shifted right enough positions so that the most-significant digit of the product will add into the Z1 position. 5. This process is continued until a maximum of 100 of these products have been summed. At the end of the "sum of products" operation, each of the Z registers will in general contain a number of order 400 b2 But since the capacity of the register exceeds 400 b2, no overflow will have occurred. Before the result can be stored, it must be scaled so that the number in each of the Z ASD TR 61-438 125

registers is less than b. When this condition is met, the 127, and 128 digits will express the number uniquely and the 63, 61, 59, and 31 digits may be dropped. The scaling operation proceeds as follows: consider the set of digits (Zo, Z1, Z2, Z3, Z4, Z5, Z6, Z7). ZO represents an overflow digit and will be zero at the start of the scaling operation. Each of the Zi digits will be divided by b. The remainder in the nth position will be added to the quotient from the (n-l)th position and the sum placed in the nth register. The resulting number is exactly the same as the original number except that each digit is smaller by a factor of b. The only exception will be the ZO digit which will be larger if there was a quotient in the Z1 position. This process is repeated until all of the quotients are zero, at which point the contents of any digit position will be less than b. Consider the set of digits: Z1 Z2 Z3 -.. Z7 which are of order 400 b2 where b = 127 x 128. If Z1 is replaced by: Ri + i. b Where Ri is the remainder when Zi is divided by b, and Zi-l/b is the integer part of the division Zi-l/b. The procedure for scaling should proceed as follows: 1. Decode each Z digit 2. Divide by 127 3. Divide the quotient of step 2 by 128 4. The quotient from step 3 consists only of the modulo 63, 61, 59, and 31 digits. These are now extended to include modulo 127 and 128 digits. ASD TR 61-438 126

5o The remainder of this division is taken as the number expressed by the 127 and 128 digits before division. This number is extended to include modulo 63, 61, 59 and 31 digitso 6. The quotients and remainders are now added. A block diagram of this operation is shown in Figure 8o A floating-point mode of operation has been implied in the discussion, However, the arithmetic structure as defined will work equally well in a fixed point mode. Floating-point round-off may be accomplished by adding a constant K = 1/2b into position Z5 just prior to the scaling operation. After scaling, if Zo is non-zero, the contents of the Z registers are to be shifted right and the exponent increased by one, The four high-order digits and the exponent are then to be stored. 8.11 A METHOD-PRECISION CGOMPARISON In Cheney's9 procedure, the scaling is accomplished before multiplication. Because of this feature, Cheney's method is the worst in terms of precision. If A is scaled by m1 and B by m2 A = Lklmi + JAKl = a o ml + a (8-44) B = L2jm2 + IB~m = b_ o m2 +bo (8-5) where mi o m2 = m (8-46) then __ -ab1 anbo aob o (847) =, a b (8-47)+ m ml m2 m ASD TR 61-438 127

Inputs From Z - Register Decode 112 112I 128 128 Base Ext. B.E. B.E. r 63,61,59,31 Base Ext. B. E. B.E.I 127, 128 Add Encode O utput Register Figure 8. Block diagram for scaling operation. 128

By scaling before multiplication only a.b1b is kept. Thus the contributions of aobi 1 alb~ o t E abi m to are lost. In Svoboda'ts method, AB = C is completely available in the double-length form. C is then scaled by m, with the result that rq= _ AB] suffers no contribution losses as above. However, it should be observed that the comparison between the two systems does not take into account that the Cheney method employs a single-length operand, while the Svoboda method involves a double-length operand. The precision advantage of the floating-point system over Svoboda's method follows from the degree to which IABIm must be discarded. In the most extreme case, when ~ is on the order of unity, the loss of precision in Svoboda's method can approach m/2, The corresponding worst case in the floating-point system occurs when the most-significant coefficient is on the order of unity, The error is then bounded by 2/m3, as was demonstrated in Section 8,4. Certain assumptions must be made about the capacities of the systems in order to make further comparisons. If one takes the magnitude of Svoboda's single-length capacity to be equal to the mantissa-magnitude (approximately m5 in Section 8.4) of the floating-point system, there exists a common basis for comparison, ASD TR 61-438 129

The precision of Svoboda's method will, at best, be equal to that of the floating-point system. This occurs only when'A = 0 or X m In the ideal case, with K]_ = 0, neither method loses any precision. This case is one of no multiplicative overflow, and represents only 1/m of the total number range. In the larger range, with __ = E(E # O), Svoboda's method loses precision approximately linearly as compared to the floatingpoint system; from equal precision when E ~ m, to the extreme case (m/2 when E A 1) described above. ASD TR 61-438 130

CHAPTER IX IPTLvZEi:i\TA TL>ON OF SIGN DET-ERMINATION TETHODS 9,1 INTRODUCTION The problem of sign determination in a RNS has received a great deal of attention, and five different met-hods have been proposed for the solution of that problem in an efficient manner, Efficiency here means the capability of operating in a very short time, of the order of one or two pulse-times, and the possibility of implementing in practice the conversion network with a reasonable number of switching elements The methods referred to are the following: (1) Implementation of the conversion equations; (2) Change of representation;'1 i Xx (3) Addition of m- 1- quantities;l mi mi mi (4) Method of estimates;12 and (5) Successive reductionol These five methods can be grouped in three categories, according to the means by which the conversion is achieved~ (a) Methods implementing the conversion equations: (1) (2) (b) Methods using stored tatlies: (3) (4) (c) Methods using a reduction procedure (5). If one is interested in extreme economy of equipment, the methods under (a) must be considered, taking into account that any gain in simplicity is ASD TR 61-438 131

paid for by a loss in speed. In general, this method takes (n-l) pulse-times to be completed, where n is the number of moduli used in the system. This type of conversion procedure has been dealt with only as an elegant but impractical solution because it has been considered that for a practical RNS, for example one with a range equal to 230, the number of elements would become impractically large. This statement appears in practically every paper on the subject, and must have been suggested by a wrong association with the idea of a decoding network in the form of a complete tree. This type of network requires 2n1 elements for n variables (levels in this case). In a system with a range of 230, a set of at least 8 prime moduli is needed if small moduli are used, and an examination of the number of binary digits necessary to encode the coefficients of the associated mixed radix representation leads to the conclusion that the decoding tree for performing conversion from the mixed radix to the residue system comprises 29 levels. If this network were a complete tree, the number of elements would be 536,870,911 = 22s91. The networks for obtaining the other residues have a progressivelydiminishing number of elements, but the number of elements in the veryfirst network is enough to discourage any further attempt. It will be shown that the number of elements for such a conversion is actually very small and depends on the encoding used. For a RNS with a range of 230 it is never much greater than 1,000. An implementation of this method, using current steering techniques, is given in Section 9.2, and Section 9.3 deals with the procedure for determining ASD TR 61-438 132

the number of elements of the conversion network for the general case of several moduli and large range. A criterion for the choice of moduli, resulting in an economy in the number of switching elements, is given in Section 9.4o If a very fast conversion procedure is desired, only those methods which are inherently non-sequential should be considered. In this case only those under (b) are capable of being implemented with a reasonable amount of circuitry, Section 9.5 covers the application of fractional-binary-coding, to the necessary tables for further reduction of the number of elements, at the expense of one additional pulse-time, bringing the total time needed for signdetermination to two pulse-times. This procedure, although presented as part of an algorithm using a table of i I-rlm quantities, actually can be applied mi mi mi to any method using a table-look-up operation together with subsequent addition of the quantities thus obtained. Section 9,6 explains the general structure of the network, and Sections 9.7, 9.8 and 9.9 present a systematic procedure for determining the number of required elements without actually drawing thae network, This procedure is based on a general algorithm for developing a carry determining network (for any number of variables) from a smaller network that is easily drawn, 902 RESIDUE TO MIXED BASIS CONVEFSION USING CURRENT STEERING CIRCUITRY The networks used to perform the conversion from residue to mixed basis representation implement the equations of procedure number 1o ASD TR 61-438 133

an = lxIm (9-1) anl = 1 mn mnl I (Xmn-1 an) Imnl m 1 (9-2) "m-n mi^ n-n-l in-l an_2 =. i i - a an-2 m nmn-2'mn-l _n-2 mn-mn_2 _ n I- mnmn2' an-1 mn-2 mn_2 ( In general: 1 1 1 ai l= l mnimi Imn-llmi'mn-21mi Imn-1+1 mi. iXmi - an - Imnmi an-1 - Imn * mn-1mi' n-2 - Imn mn-l'' mn-i+21mi' ai+l mi mi If one considers the case where only three moduli are used, the preceding equations take the form: a3 = xlm (9-4) a2 = M3lM2 IXlm2 - a3 m2 m295) m3 1 Ml1 ^ = ^m3 ~ lm | a3|l - ~3 lmlmi e ~m (9-6) Each of the equations (9-2) and (9-3) is implemented by an independent network, but as an is always equal to IX mn, only n-l networks are required. The inputs to each network are the residues, coded as one number per wire, therefore the number of input lines is equal to the corresponding modulus. ASD TR 61-438 134

As an example, Figures 9 and 10 represent the conversion networks to perform conversion from the system mi: (4'3,5) to the associated mixed basis system. The broken line is the path of information when the number 53 in residue notation (1,2,3) is converted to the mixed basis representation: (3,1,3). The procedure includes the following steps, as indicated on Figures 9 and 10: 1. The input (al) is received on wire number lo 2o The first binary digit of la3m = 131 = 3 = 11 is inspected. 3. The first binary digit of lasm is subtracted. 4. The interchange of wires in this step has no arithmetic meaning. It is only a rearrangement to simplify the drawing. Every wire retains its original weight. 5. The second binary digit of las3m is inspected. In this case ia31lm in binary is 11, and the second digit is also a 1. 6. The second binary digit of las3ml is subtracted. Weight = 2. 7. Multiplication by Il/ms3lm is performed. In this example 1l/ms3lm = I/51 = lo 8. The first binary digit of la2lmi is inspected. 1a2lm1 = 1. First binary digit is 1. 9. The first binary digit of la2lmj is subtracted, with a weight of 1. 10. No operation. ASD TR 61-438 135

Control Signals Inpt: Ix ImxI tep' perion lit bin. digit of lal 31 2 I's &3 3 13 1lt digit of Ia3lm 4 No operation 2nd bin. digit of 1a31 o 0 3 3a -3- 11 3 - 6 2nd digit orf Issl1 12 0 1 3 ^_ __ 1_ 7 x1 1.1I 7 xlIl j3 IM 1 Ist bin. digit of tlale 0 1x i 8 |1B a 1 - 01 9 I1st digit of I&2lm1 10 2nd bin. digit of la21i 0 2d d t3 IO l86214 - 1 = 01 12 I2nd digit of xll2 2 0 11 3 13 x 1*14 I Otput put a 3 Figure 9. Switching network for residue to mixed basis conversion network (1st part). 136

Control Signals Input: x1 1-2 Ste a Operations 1 let bin. digit of las1m2 2 1a3I1 -- 131 o0 25X 3 -lst digit of laSlm200 h I |4 No operation 2nd bin. digit of Ia3lm2 2 =m 131= 00 6 -2nd digit of jas m2EX2 I1 0o 112 7 No operation 81 xmL ill =2 Output: a2 = 1 Figure 10. Switching network for residue to mixed basis conversion network (2nd part). 137

11. The second binary digit of la21 is inspected. 1a2lm = Therefore the second binary digit is 0. 12. The second binary digit, with a weight of 2, is subtracted. 13. Multiplication by l/m21ml is performed: l1/m21ml = 11/31 = 3. 14. The output is al = 3. It is to be noted that the number of levels that are necessary depends on the number of a coefficients to be inspected, which is (n-l) for the first network, and on the number of binary bits needed to represent the a coefficients modulo mi. As ml = 4, the largest magnitude to be dealt with is 3, and therefore only two binary bits are necessary for each coefficient. The complete network to perform conversion in this system is shown in Figure 11, and in more detail in Figure 12 where the I andC] elements and connections indicate auxiliary equipment performing notation changes, encoding or modulo operations not essential to the conversion procedure. The operation is sequential, that is, the coefficient as appears first at the output; after a certain time interval a7 is obtained, and so forth, Therefore the total delay to obtain the complete conversion is the sum of the propagation times through the path shown as a broken line in Figure 12. All the Ixlmi are applied simultaneously as inputs, but they are delayed by the delay elements 3 to allow time for the modulo and conversion operations to take place on Ix ms. After that delay, both signals, that is, the individual Ixlmi and the corresponding setting signal for the switching elements obtained from |x m, ASD TR 61-438 138

1XI.I X.., XIM as as IX~~~~~~~~~~m~m a2 a2 mi I I I ~~~~~~~~~~1 level of' switching elements (a,~'kxi. 5 operation -Q}- Binary encoder 81 ^8 "~ f^ Figure 11. Simplified schematic of the complete residue to mixed basis conversion network.

mi = 3 5 7 11 13 17 23 31 XIml XIm2 XmS XKm4 xIm II XIm8 I C^J I C~l \^/ 2 levels of all a \4 1 I:~~ L' r'm 47 )|2 levels of switching elem I ___ |^J | {|- - Binary encoder 1,~ ~ ~1 13 ^a~~~~ (~ ModrI. 5 operation Figure 12. Block diagram of the conversion network from the residue system to mixed basis.

are applied to the first group of switching levels, indicated in Figure 2 as:. The number inside the indicates the number of levels actually comprising the group. The output of the modulo 23 column is already a7, from which the setting signals for the second group (second row) of switching elements are derived by modulo and conversion operations. Therefore, initially there are no outputs, and the ai coefficients begin to appear successively in decreasing order until they are all available after a time equal to the total propagation time through the chain of elements indicated by the broken line in Figure 12. A slightly simpler network can be obtained by omitting the delay elements # lin Figure 12; but then the output has to be strobed after a time equal to the total delay A, because in this case there are output signals present since the moment the Ixmi input signals are applied, but it is only after a time A that they are all correct. The initial values present at the output depend on the state in which previous operations left the switching elements, and they change successively into the correct value as the signal travels through the broken line diagonal path of Figure 12. 9.3 NUMBER OF ELEMENTS IN A CONVERSION NETWORK When performing conversion from a residue number representation, the number of independent conversion networks is one less than the number of moduli of the system, because the coefficient an in the mixed radix representation in equal to the residue x lm. ASD TR 61-438 141

The number of input lines to the ith network is equal to the corresponding modulus mi. For example, if for a network mi = 3, the number of input lines will be 3, because the input is ai, and this can take any value up to mi-l; therefore the largest possible value is 2, but an additional line is needed for the 0 (zero) signal, which brings the total back to 3. The number of levels is the product of the number of binary digits necessary to represent moduli i the coefficients ai from ai+l to an, times the number of coefficients to be added up, which is equal to (n-i). The itemized calculation for a residue system with 8 moduli is given in Table 8. For the first network, mi = 3, and the number of coefficients to be added is 7: a2 through a8. All these coefficients are taken moduli 3 and therefore are represented in a binary notation by only two digits. The total number of levels needed is therefore: 2x7 = 14 The following general formula can be used to calculate the total number of switching elements of a conversion network for a system of any number of moduli: (n-l) No. of elements = Z (n-i) x mi x F(mi) (9-7) i=l F(mi) is a function giving the number of binary digits necessary to represent a number modulus mi. When operating moduli mi, the largest number that can occur is evidently (mi-l), and for systems with a small number of moduli, F(mi) can be obtained from the following table: ASD TR 61-438 142

TABLE 4 TABLE OF THE FUNCTION F(mi) Any mi up to 2 4 8 16 32 64 128 Largest No. posSo 1 3 7 15 31 63 127 F(mi) 1 2 3 45 6 7 In those cases where the number of moduli is very large, or the calculation is to be included in a program as a subroutine, F(mi) can be obtained from the expression: log (m~+l) F(mi) = integer part of lg + 0o99 (9-8) 0.3010 It is interesting to note that given a residue number system and the associated mixed basis system, the conversion either way takes the same number of switching elements, although the networks are quite different in their circuitry, and in the time required for the conversion. Modular system with moduli: 3, 5, 7,,, 13, 17, 23, 31. TABLE 5 PROCEDURE FOR THE CALCULATION OF THE TOTAL NUMBER OF ELEMENTS 1.2 3.4.. =..3x4 6 7 = 5x6 1 3 7 2 14 3 42 2 6 3 18 5 90 3 7 5 3 15 7 105 4 11 4 4 16 11 176 5 13 3 4 12 13 156 6 17 2 5 10 17 170 7 23 1 5 5 23 115 Total number of elem. = 854 Column 1: network number Column 2: mi Column 3: number of coefficients to be added Column 4: number of binary digits necessary to represent the coefficients moduli mi Column 5: number of levels Column 6: number of input lines Column 7: number of elements ASD TR 61-438 143

The table beginning on page 145 gives the number of elements necessary to implement the conversion network for different sets of moduli, all giving a range equal or greater than a specified value. The results are a direct application of the equation (9-7) and have been calculated for values of M 27 34 27 from 22 through 2. Only the table for 2 is included here, For the calculation of these tables, the first 400 prime numbers, excluding 2, have been considered as numbered from 1 to 400. Therefore, the numbers in columns 1 and 2 identify the first and last moduli of the set by their ordinal position; ioe, 3 indicates the third prime number, that is 7o The tables contain the following information: Column 1: The first modulus. Column 2: The last moduluso Column 3: The number of moduli in the set. Column 4: The actual range obtained, in floating point notation. Column 5: The number of elements in the conversion network. Column 6: The number of elements normalized for a range of 101~. Column 7: The minimum range, in floating point notation, as prescribed in the program. The same type of information is presented in Figure 13, beginning on page 146. Here only the first and last moduli are indicated, together with the number of elements. The length of the lines of 8's in the scale indicated, is proportional to the number of elements. ASD TR 61-438 144

TABLE 6 NUMBER OF ELEMENTS IN THE CONVERSION NETWORK FOR DIFFERENT SETS OF MODULI nrt $IadulMw tat Modulus uv&*r of Bange Number of Rmber of Elements Pri No. Prim o.e. oduli Obtained Elements for a Ranu - 10~O 2 ~ ~) ~ ~~' ~ 9 7 215656239 1114 51(56 134217759 4 10 7 955048459 1524 15957 154217759 6 11 6 247110459 1595 64546 134217759 7 12 6 959971659 1902 51914 134217759 8 13 6 134877760 2310 17126 154217759 9 14 6 275619560 2761 10017 13421'759 %1 15 5 1(2489759 2424 149178 134217759 12 16 5 259105159 2(40 101889 154217759 13 17 585497559 2868 73597 134217759 31 18 5 60065559 15242 1'4217759 15 19 5 907376959 3555 58958 1'L21775, 16 20 5 124978260 3949 31597 1542177517 21 5 17343660 45376 26149 144217759 18 22 5 227696860 4942 21701 134217759 19 23 5 302462760 5208 17218 1',217759 20 24 5 413223560 5488 13280 13521775; 21 23 5 571720060 5880 10284 13421775 9 22 26 5 745406960 (258 8'95 1,421775, 23 27 5 960945460 6664 6934 1'L217759 24 28 5 117688661 7028 5971 1 4217159 26 29.4 135743659 3879 285759 1-421775; 27 30 4 167373059 5474 2075(0 154217759 28 1 4 204914459 3125 152502 134217'59 29 32 4 257552659 5199 2018(1 154217759 30 33 4 316812259 5859 184936 17x217759 31 34 4 371692699 6448 173476 134217759 32 359 4 428439559 6704 15(474 14721477 33 36 4 490985159 6928 141104 1!:-21779 34 37 4 575759259 7248 125885 1'-21'759 39 38 4 645313759 7440 115292 1'21-75 36 39 4 739332659 7386 99900 1,-217759 37 40 4 804900059 7968 94507 1~217759 38 41 4 936017299 8208 87690 13-217759 39 42 4 107093460 8464 79063 114217759 C 43 4 119429460 8720 73013 1i4217759 9 4. 44 4 131439060 8944 68046 154217759 14 45 4 144510260 9248 63995 13421779 43 46 4 159642160 9376 58731 134217759 44 47 4 184456960 9600 52044 154217759 45 48 4 212546760 9936 46747 135217759 46 49 4 244588660 10118 42716 1354217795 47 50 4 270090460 10616 40045 154217759 4 51 4 289468860 10976 37917 134217759 49 52 307321260 11136 36235 134217759 50 53 336845060 11344 33677 134217759 1 54 3 71541260 11600 31221 154217759 52 55 4 408850460 12113 29626 134217759 56 45 16351360 13017 28524 134217'59 57 4 492713760 14094 28604 15217'? 58 1 531056760 1438 27081 17.421.759 56 59 5 67402260 1463 25791 154217759 57 60 4 596931960 14832 2487 14217759 sS 61 4 645390860 1908 2335571 1217759 39 62 4 715288360 15318 21415 151217759 60 63 4 791653160 15678 19804 15-217759 61 64 4 875573360 16236 18543 134217'59 62 65 4 947292060 16704 17633 134217-59 63 66 4 102134761 16884 16531 134217759 64 67 4 110673161 17136 15483 121779 65 68 4 122694961 17550 14303 15421779; 66 69 4 135080461 18126 13418 154217759 67 70 4 144058461 18486 12832 13421759; 68 7. 4 154162661 1882 12268 134217759 69 72 4 162307661 19006 11711 13-21-59 70 73 4 173469061 19296 11123 15221,5 71 74 4 186245561 19656 1093 1; 217799 72 7 4 198696261 20034 10082 1' 217759 73 76 4 210606961 20340 9697 1-h21'759 74 77 4 224157961 20628 9209 1"42177?= 7 ^78 4 237169661 20916 8819 76 79 4 253269661 21278 8393 1P2-'5 77 80 4 27281861 21618 7924 1:21-'5 78 81 4 289293561 21960 7590 1 2 - 79 82 4 310936161 22374 7199. 217159 So 83 4 3291816610 6917 21 84 4 3447894261 23062 6675 1 -21" ^82 854 362917061 23382 6442 5' 83 86 4 37807361 23580 6256 1' 21";9 4 87 4 399028861 2368 981 14217759 85 88 e~ ~4 4 19025563 24156 5764 15-217759 86 89 1* 437943061 24498 5593 1,421-'5 87 90 4 45549461 24804 5445 1-4211" 9 88^~ ^^ll^7896 4 147'7426861 24964 55 12179 69 92 4 904352361 2210 5000 152P7 90 93 4 548522361 25614 4788 154217759 91 94 4 571500661 26118 4570 154217759 92 95 4 60013461 26478 441 151217759 91 97 4 66561)63.^ 271076 407 1321779 93 28 t r18683659 14372 1036313 134217779 ^ ^ ^ 1708579 15650 1061720 1?4217759 ~10541 114217759 988558 15421"779 1]0

Number of elements Scale: 1000 ele/cm Last modulus, prime No. First modulus, prime No. 1114 3 9 lll4 4 10 1524 6 11 1595 7 12 1902 8 13 2310 9 14 2761 - 1 —-lst type 11 15 2424 12 16 2640 13 17 2868 14 18 3156 0\^~~ 1^~15 19 3535.\^0~~~ \16 20 3949,\^0~~~ \ 17 21 4376.0^~~ \ ~18 22 4942. 0~~l\ 19 23 5208.\^0~~~ \20 24 5488 21 25 5880 22 26 6258 23 27 6664 24 28 7028 ^~- 1st type 26 29 3879 27 30 3474 -1 ~ 2nd type 28 31 3125 29 32 5199 30 33 5859 31 34 6448 32 35 6704 33 36 6928 34 37 7248 35 38 7440 36 39 7386 37 40 7968 38 41 8208 39 42 8464 40 43 8720 41 44 8944 42 45 9248 43 46 9376 44 47 9600 45 48 9936 46 49 10448 47 50 10816 1 2 3 4 5 6 7 8 9 10 11 12 Figure 13. Variation of the number of elements in the conversion network. 146

8 6151 1097684 9 62 111536 ~~~6o0~~~~~~~~50 63 15678 2 12111 64 162600 62 65 16704 63 66 1688401 64 67 17109 65 68 17550 66 69 18126 67 70 18486 68 71 108828 69 2 19008 70 73 1929678 71 74 1966 6 62 65 16704 63 76 2016840 74 77 171320628 75 78 20916 76 79 212586 77 0 2161886 78 1 219608828 79 82 19008 0 3 2277096 81 4 196022 82 85 2003382 83 86 2580 84 87 20868 85 88 24156 76 79 24498 87 90 24804 88 91 2498460 89 92 252187 80 93 225614 81 94 20226118 92 95 26478 83 86 2676680 94 87 2710868 85 88 24156 86 89 24498 96 98 148072 88 91 24984 89 92 25218 97 99 15614 91 94 26118 92 95 26478 93 96 26766 94 97 27108 96 98 14372 98 100 15870 1st type 99 101 16290 1011 12 15 4 15 16 17 18 19 20 21 22 3 24 2 2627 Figure 13 (Concluded). 147

9.4 SELECTION OF MODULI FOR MAXIMUM ECONOMY It is evident that some combinations of moduli require a minimum of elements, and that two types of relative minimums can be distinguished: One type is produced when the number of moduli in the set drops by one, because as larger moduli are considered suddenly the range can be obtained with one less modulus, The second type occurs even when the number of moduli remains constant, and is produced when the nth-l modulus takes the largest value not exceeding one of the following magnitudes: 2k-1. That is when the nth-l modulus takes the maximum value less than or equal to: 3, 7, 15, 31,.... This can be explained in the following way: The nth modulus does not influence the number of elements because it gives directly the last coefficient in the mixed radix system. When the nth-l modulus takes for example the value 15, it is possible to encode it using four bits to full capacity. If the modulus were 16, it would be necessary to use 5 bits and therefore five levels of switching elements. The rest of the moduli are also encoded in the same number of bits or in less, because they are all smaller than the nth-i. In the graph for a range of 227, the first type of minimum occurs for the sets having the following first moduli: 6, 11, 26, 96. In those cases, the number of moduli is reduced by one. The second type is evident in the set having prime number 28 as the first modulus. This set is composed of the following primes: 109, 113, 127, and 131. We see that the nth-i modulus is 127, which is the maximum value representable by 7 binary bits, ASD TR 61-438 148

9.5 THE APPLICATION OF BINARY CODING TO CONVERSION PROCEDURES USING STORED TABLES One of the procedures used to obtain the mixed radix coefficients corresponding to a given residue representation consists of the addition of the 1 x corresponding values of the quantities 71 in mixed basis notation. This procedure requires the storage of n tables, n being the number of moduli in the system. Each table contains the values of Ix for all posmi mi mi sible values of 1Ximi, expressed in mixed basis notation. From these tables one obtains the mixed basis coefficients corresponding to each of the residues. They are added in a modular adder, taking into account the carries that may occur. The main disadvantage of this method is that it reintroduces the problem of carries. But when the problem is sign determination rather than change of representation, the method can be modified to perform the determination of sign in only one pulse time, assuming that the corresponding quantities have already been obtained from the tables. This modification is based on the fact that when a number x is represented as: 1 x x = M - Z -j-I mi mi mi where M is the range of the system, the summation takes values less than 1/2 for the first half of the range, and values greater or equal to 1/2 for the second half. Now if the quantities stored in the tables are represented in binary form, it is not necessary to perform the actual addition of all the quantities, but only the determination of the first binary bit after the decASD TR 61-438 149

imal point. If this is a zero, the summation is less than 1/2 no matter what the other bits are. If the first bit is a 1, the sum is always equal to or greater than 1/2o When all the quantities have been obtained from the tables, the carries are determined for all the columns except the first one, and the resulting carry is added to the digits of the first column. For example, if the (2,3,5) modular system is used, the corresponding tables, expressed in binary notation, are as follows:!'l2xl 3 3 1 13 xl 515 5 0 00000 0 O00000 0.00000 1 10000 1.01011 1.00110 2.10101 2.01101 3. 10011 4.11010 For x = 16, residue representation is (0,1,1), and from the tables we obtain: For 0.O 0 0 0 0 For 1.0 1 0 1 1 For.0 0 1 1 0 1 O 0 0 1 As only the first digit after the decimal point is to be inspected, the complete sum is not needed, It suffices to determine the carries up to the first column, and then to add the last carry to the first column. This simplification makes it possible to perform sign determination in a single pulse-time using a current steering network, because the necessary setting signals for all the levels are available at the same time, and there is no carry propagation problem, ASD TR 61-438 150

9.6 GENERAL STRUCTLURE OF mTHE:NEWORK The switching network fur carry deternination is very simnple because it does not have to handle largce numbers since te l largest carry for a sum of N binary numbers is N-i, which happens only after several columns have been added. For the first columns' the network has to handle carries of increasing magnitude. This necessitates an increasing number of wires to represent the carries, but after the maxnimum value of the carry has been reached, the complexity remains stationaryo Thnen the same type of circuitry is repeated for the following columns, Three well defined regions can be distinguished in the network. This begins with a single wire representing the original "zero" carry into the first column from the right. In the first region where the number of values that the carry can assume keeps growing, the individual networks representing the columns are all different, because the possibility of carries of larger magnitude demands more wires for their representation. This region ends with the network corresponding to the columnn where the carry first assumes its maximum value: N-I. The second region is foDrmed by a number of networks' all alike, corresponding to the solhumns up to and including the next to the last, for which the same number of values are possible for the carries' The third region comprises only one network in which the resulting carry from the previous columns is added to the binary digits of the last column0 The result is interpreted as (+) if it is a zero, and as (-) if it is a one. ASD TR 61-438 151

Note that the networks in regions 1 and 2 perform binary carry determination, while the network of region 3 performs binary addition. The configuration of the sign determining network for the example of Section 9.5 is shown in Figure 14. A simplified network for the case where 4 moduli are used is shown in Figure 15. 9 7 DETERMINATION OF THE NUMBER OF ELEMENTS OF THE NETWORK The three sections of the network, as described in 9<6, contain four different types of individual networks: Region 1: The first network is of the type (1-M), indicating that it is of the type having only one input and M outputs. From the second network on, only the type (M-M+W) occurs, indicating a network having more output wires than input ones o Region 2: All networks are of the type (M+M), that is all have equal number of input and output wires, Region 3: The network is always of the type (M+2) Each of these types of networks requires a separate calculation to determine the number of elements necessary for its implementation. Networks of the first type (11+M) are the most difficult to evaluate because they are asymmetric and include many cases of "don't care" conditions, which tend to simplify the network but introduce difficulties for the systematic determination of the number of elements, ASD TR 61-438 152

O carry last bit 1st row 2nd row slt column 3rd row 0 1 Carry from 1st column 3 similar networks o 1 2 bin, addition l / Figure 14. Switching network for sign determination for a residue system with 3 moduli. 153

Carry Wires e of Network Regions 0 1 35 0,1,2 3 34*4 / \ 3 0,1,2,3 I 4 4 444 A \ 01,2,1 4 ~~44with 4 moduli. 4 4 0,1,2,3 4 4+2 3 2 0 1 Figure 15. Block diagram of sign determination network for a system with 4 moduli. 15k

The following is an explanation of a procedure by which the number of elements can be determined for any number of variables (levels) without actually drawing the complete network. Figure 16 shows the carry matrix and the corresponding network for the case n = 3, while Figure 17 shows the case n = 4, It can be seen that the carry matrix for the case of four variables can be thought of as being formed in the following manners 11 1 1 1. 0 0 0 0 0 0 0 l- Carry. Carry.lo'C1 Co matrix n=-2* Ln=2i for n=3 The asterisk (*) in the carry matrix of 2* is just a symbol to indicate that the matrix is derived from the matrix for n = 2 by interchanging l's and O's in the first row. The corresponding diagram in network form, for the previous diagram can be indicated as; ~ {Cox*1&ys1 n=2* n.L2 The procedure can be extended for a larger number of variables, and the general structure of the network for the first column is indicated in Figure 180 ASD TR 61-438 155

n00111 110100 1 0 EE 10 1 0 0 1 1 0 I 0 E = either 0 or 1 Figure 16. Carry matrix for three addends and corresponding network. n= 4 000000 1 111 1 000111 000111 110100 100110 1 0 E E 1 0 E 1 0 1 0 E 100110 110211 Figure 17. Carry matrix for four addends and corresponding network. ASD TR 61-438 156

K-1 K-2 I K-3 (K-3) Branches I s 2 2* Figure 18. General structure of the carry determining network for the first column of K binary bits. The number of elements in this network can be obtained from the following table: TABLE 7 NUMBER OF ELEMENTS FOR NETWORKS OF THE TYPE (l+M) Output wires, No. of levels = Number of M No. of moduli, N elements 2 3 4 3 4 10 4 5 21 5 6 43 6 7 87 7 8 175 8 9 351 ASD TR 61-438 157

For values of N = 6, the following formula can be used: Number of elements = 17 x 2(-5) + 4 x 2(N-6) + (N-i) + 5 x (N-6) (9-9) Second type: Networks of the form (M-M+W) o These networks implement the carry determination procedure from the second column up to and including the column in which the carry assumes its maximum value. The number and type of networks that are needed in each case can be determined from the following table, which gives the maximum carry from every column and at which column the carry stabilizes at its maximum value of N-1. TABLE 8 MAXIMUM CARRY AND CARRY PROPAGATION LENGTH No. of binary bits Max carry from column Max carry at in a column to column column No. 2 1 1 1 1 1 1 1 3 1 2 2 2 2 2 2 4 2 3 3 3 3 3 2 5 2 3 4 4 4 4 3 6 3 4 5 5 5 5 3 7 3 5 6 6 6 3 8 4 6 7 7 7 7 3 9 4 6 7 8 8 8 4 10 5 7 8 9 9 9 4 It must be remembered that the table gives the maximum carry, not the number of wires, which is one greater. Figure 19 shows the corresponding network for the case (2-+3) for 3 levels, Figure 20 shows the network for the case (3+4) for 4 levels. The ASD TR 61-438 158

0 01 2+3 type for levels 00 1 2 Figure 19. Carry determining network for the (2 to 3) case. O0 1 02 0 ~1 2 13 Figure 20. Carry determining network for the (3 to 4) case. ASD TR 61-438 159

preceding table indicates that for 4 levels, that is four binary bits per colu mn, the carry from the first column into the second is a 2. Therefore the network for the second. coiJmmn musst have 3 input wires (for the values 0,1,2) and 4 output wires (for the values C0 1,2,53). Therefore the network of Figure 20 represents +the second network for the case n = 4, Number of elements: The n-urer of eoments ef a network of the type (MI+N+W) for N levels depends only on M a aNrd is calculatfed by means of the following formula: Number of elements: M+(+l) + (M-2) +....+ - (9-10) Third type: Networks of the form: (-MM). For this type of network, the same formula (9-10) applies. Fourth typeF Networks of the form: (M*2)o This network performs binary addition, but no carry read our wires are needed, because only the resulting digit is inspected, The number of elements is determined by applying: Number of elements: M + (iH+l) + (M+2) +.o..+ (M+P-l) (9-11) 9.8 THE N:ECESSARY lTi MER OF BINKARY BITS In order to attain the required discrimination between the positive and negative regions, it is necessary to determine the number of binary bits of the m-alx quantitieso At the samle time, it is convenient to use the minimum D mi43 ASD TF 61-438 160

possible number of bits in order to save space in the tables, and to economize in equipmenrbt The necessary discrimination is 1/M. In the worst case, two representations may differ by only one bit in the last place. The weight of this bit is 1/2, where k is the numfber of bits in use. Therefore k is the number of bits that produces a suitable discrimination, and must satisfy the relation: 2k M. This number of bits insures an adequate discrimination in all cases, but when maximum simplification is desired, it is possible to obtain accurate sign determination even when several of the final bits are dropped. In that case the magnitudes are represented only approximately, but the sign is still correctly determined. The following considerations apply: In a RNS, using 2 as one of the moduli, the representation for the first number of the second half of the range is always: (1; 0; 0;....o0) Therefore, the summation of the quantities from the tables is always equal to 1/2 for this number, no matter how many digits there are in use. If the following numbers are also represented with less than k bits, their magnitude will be represented only as an approximation. But as long as the summation results in values of 1/2 or greater, the sign determination procedure will continue to operate correctly. As an example, let us suppose k is being determined for the system (2; 3; 5), Here M = 30, therefore k must be 5, because 25 = 32 which is greater than 30. ASD TR 61-438 161

But it is possble to use.nly four Mits in the table and still obtain correct s:ign determinat' 5io The foll.owing approximate representations are ia'uiaa...ed using the ta.l. on page 150,'but considering only four bits: AA 5/16 5/16 First half 12 6/i6 < / cf "-,he range 13 6/i6 84 7/16 16- 8/16 Seco rd half 17 8/16 > 1 /2 of,thAe range 18 9/16 19 10/16 20 o1/16 9.9 SYSYTEAT IC PROE4i RE FOR I 5E DEVELOP MENT OF TIE NETWORK AND 1FR THE DETERMINATIEO"N OF IHE tiER OF ELIIO ENT'S The onl.y data availabl are tehe set of moduli in the system. The following steps should be follow^ed, as illustrated in the next exampleo I.: Draw the schematic of thte network, as in Figure 21, with as many \ (indicating individal networks) as thee numnber K of binary bits used in the tables of the ~-~ i quantities~ "ni mi 2, Determine te iequence of maximum carries from Table 8 for the number of moduli used in the systemo 3o Write eor the left- side of the network the sequence of carries and on the right side the samre rzmbers increased by one, indicating the number of wires 4o Identify and separate the three regions in the general network, 50o For the first network, o. tain the nrumber of elements from Table 7, or apply equation (9-9) O ASD TR 6 i-48 162

Number of Network Carries Wires elements Number 0 1 1 43 4 5 1st region 2 62 6 7 3 77 _.. _ _, _ _ - _ _ 7 8 7 1 8 4 84 2nd region (18 levels) 21 84 7 8 22 92 13rd region 0 1 Total number of elements: 1786 Figure 21. Determination of the number of elements in the carry network. 163

6, Calculate the number of elements for the networks in the rest of region I and 2, using equation (9-1C)o 7 Det eriine the number of elements for the network in the 3rd region using equation (9-11) o 8o Add the partial results obtained in steps 5, 6, and 7, The number of terms to be added is equal to the number of individual networks, Example~ Given the system: 2, 3, 5, 7,, 1 11 1 17 23, draw a diagram of the general network and determine the number of elements. The nYumbers on the left side refer to the steps of the preceding procedure, 1i Number of bits in the l- quantities K = 22o 2. Sequence of carries for n = 8: from the Table 7, we obtain: 4, 6, 7, 7, 7, 7 oooo 3o This sequence is written on the left side of the network, and on the right side the same quantities appear increased by one, 4I The three regions are separated by broken lines, 5~ From the Table 7, for M = 5, the number of elements is found to be 435 6, Applying equation (9-10), we obtains For the 2nd net4work: 5+6+7+8+9+10+11.+[12/6] = 62 For the 3rd networks 7+8+9+10+11+12+13+[14/2] = 77 For the 4th u.p to the 21st network: 8+9+10+l+12+1 3+1+4+[15/2] = 84 7o For the 22nd network~ 8+9+10+11+12+13+14+15 = 92~ 8o Adding the partial results of 5, 6, and 7~ 43 + 62 + 77 + (18 x 84) + 92 = 1786 ASD TR 61-438 164

APPENDIX I THEOREMS ON THE GENERATIO:N OF SEQUENCES OF RELATIVELY PRIME NUMBERS Theorem Io Given an ordered monotone sequence of positive and negative integers for which the difference between successive numbers is +~. If there exists one number in the sequence divisible by Pm then the maximum length L or a subsequence of numbers not divisible by Pm is L = (p,) - 1; note (Pm,5) = 1 or P Proof: Given pmlea then the next number divisible by Pm is, 3 = Kipm + aS = K2Pm (kl-k2)Pm + ab = 0 (klk2) -P + a = 0 (k1 (Pm ) (Pm,) Hence a = and there exists m numbers between a and 5, (Pm,6) (Pm, ) Corollary: If one element of an ordered sequence of constant difference 6 is divisible by Pm then the length of the maximum subsequence containing only 2Pm one number divisible by pm is 1: = m) - i. Theorem II. Given a subsequence of length 2pm-1 of the form a-(pm-1),.o.,,... o, +5(pm-l) There is at least one number divisible Pm. Proof: l~aSKpm assumes all values between C and pm-l as k goes from zero to Pm-1. Corollary: If Pm65 in the subsequence of length 2pm-l then two numbers of the subsequence are divisible by Pm. ASD TR 61-438 165

Theorem IIIo A necessary condition for a relatively prime sequence of numbers of length Lm = P = = 1; (pm, ) = 1 is that no number of the sequence (Pm,'6) is divisible by a prime less than Pm' Proof: Assume PnKl pn < pm; then it follows from Theorem I that the length of the subsequence including two numbers divisible by p is Ln= 1. = (Pn,) The length of the subsequence including 3 numbers divisible by Pn is Ln3= 2Pn + 1o Both Ln2 and L3 Lm (Pn, 6) Lemma I: Let P? > Pm divide one number of the subsequence of length L = 2pm-l. pi never divides 3 numbers of the subsequence if (p~;6) = l1 Proof. 2p~ + 1 > 2pm - 1 Lemma 2: Let p > pm divide one number of the subsequence of length L = 2pm-l. The subsequence is partitioned into two parts a-6(pm-l),.o. a and aea-6,... a+6(p-1l), where pm{ca. Neither part has two numbers divisible by pi if (PI,6) = I" Proof: p~8 > (Pm-1)8. Theorem IV. If pI > p divides one number of the subsequence of length L-2pm-1 then the necessary condition for the division of two numbers in the sequence by p is P~- + 2 4 2Pm (Pl5) Nm The sufficient condition is either PA +i < Pm ASD TR 61-438 166

or if (P,5) = 1 then integers k1 and k2 must exist such that lk2 = ipp k2 <p <Pm - kl5,p _ P= llp kL7 P-1 Corollary 1: If p~ > p divides one number of the subsequence of length L-2pm-1 then a sufficient condition that only one number of the subsequence is divisible by pf is ~ 4+ 2 > 2p Corollary 2; A sufficient condition that only one number of the subsequence of length L = 2pm-1 is divisible by pj > pm for the case pQ+2 < 2Pm; (6,p2) = (8;Pm) = 1; is i1 0, 181,o0.I(PQ - Pm)FIp or! - 1(PQ 1)5 1p2,~*D9lp IPm6 lpI Theorem V. The necessary and sufficient conditions for a relatively prime sequence of length L = pm-l cf the form a-6(pm-l),OoO,.,ooa+(pm-1) are lo (p5,6) = I 2. Pm I 3. for all Pi < Pm PiX a and (pi,5) =Pi 4o for all p~ > Pm satisfying p9 + 2 < 2Pm ASD TR 61-438 167

185p = 0, 151 o (P- Pm)51 p or MiP = (P 1)5 p l, Pi Proof: i Ooroll ary, heorem I 2o Corollary, -Theorem II 35 Pi/yx follows from Theorem IIT (Pi,5) = Pi follows from the fact that ISKIp for k = C0, 1, 00, Pm-1 assumes all values of Pi is 6 is not restricted and hence for some k,, cx~kl61 = I o Theorem III states that if one k exists satisfying aL~k6l = 0 than a second k also exists. 40 Corollary 2, Theorem IVo Corollary: A relatively prime sequence meeting the conditions of Theorem V may be modified by the multiplication of one and only one number in the sequence by each of the pi, i < n, without destroying the relatively prime relationship between the numbers in the sequence Example: Pm = 5, a = k5, 5 = 2o3 = 6, 2pm-2 = 8 so p~ = 7 and 1a17 = 0, 6, 5, 1, 2o Thus, suitable a's are 25, 55, 5, 85, 65, and the resulting sequences of relatively prime numbers are: II, 17, 23, 29, 35^ 41, 47, 53, 59 31, 37, 43, 49, 55, 61, 67, 73, 79 -19,,13 - i 53 11 17, 23, 29, etc. A choice of a such that ja17 = 3 or 4 or a such that Pi Ol, i < n results in a sequence of relatively prime numbers shorter than 9, consider cx = 25, -5 i 7, 13, 19, 235 31 37 4 49, 55 ASD TR 61-438 168

FAPENDIX -.I A MIXED BASE AND MODULAR COMPARISON The following theorem specifies the conditions that, must be satisfied for a number S to have identical mixed base and modular representations, Theorem Io Let p!, P2o.o pSP bee the bases of a modular number system of total modulus p =- p1pp3. p aird Lep^ the nmodular representation of a number S be given byo S (aia2a3~ *.a) a9 - S mod pK 0 a ak PK - Let the mixed base representationx of S be given by: S = hbo2, obN where S = b1 PN1 bP2 +.bN N b1p + and PTNK P= PN-.1P- 2' ^ P K+ ~ S has identical mixed base and modular representations if: ak = bk, K 1, 29,.. \T Then S has identical mixed base and modular representations if, and only if, S —-_ —- is an integer P K 1, 2,...- ~ ASD TR 61-438 169

Define the quantity tNK: S s PNK= NK = PK K = 1, 2,...,N-1 Now since aK = bK only when tNK is an integer, the following theorem relates to the number of integer tNK's which appear as S goes through the integers 1, 2,,.,p and K is fixed. Theorem II. As S goes through the integers 1, 2,,,,,p, the number tNK, given by: S PNK tNK - PK assumes the value of all integers l,2,...,(plp2p3...pKl)(pNK- ) at least once and at most twice. Proof: Examine the quantity A = S - For 0 S < PNK, A = S For PK S < 2PNK, A = S-1 and in general aPNK S < (a+l)PNK, = S-a It is easily seen from the above that as S goes through the integers 1, 2,.., bpNK, A goes through the integers i, 2,...,bpNK-b. Therefore, as S goes through the integers 1, 2,...p and since p = (P1p2P3..PK)(PNK) A goes ASD TR 61-438 170

through the integers 9 2o o o P o ~P ) P; o Now N( =./p r henie. it, fol-.ws th.iat as S goes through. the integers C- 9,0p0 tTJ( asstiem: i;nter values at least _PP~PK- K< times PK or tNK assumes every'iteger.i ) ~o oo( poip..)(p-.) at least ornce as S goes throukgh -ihe hintegers i. 20ooo po Now examinre the case of two irtegers S1 and S2 vhere 1, S1 < 32. p to see under -what conditions their respective tNK'S are the sameo Let 1 < SI < S2 ( p where Si and S2 are integers If tK for S1 equals tNK for S2 thetn Si- S2 2 Si~ ~ S2PK PK (2-1) S - = S2 - J Let ~| = and and PNl i = a2 Then S1 = a1PNiK r, 0 < r1 P K - 1 (2-2) S2 = aPNK "r2, O r2 < PN K (2-3) ASD TR 61-438 171

Further more, since S1 < S2, this implies a1 -< a2. Substituting a1 and a2 into equation (2-1) gives S1 - al = S2 - a2 S2 - S = a2 - al (2-4) Using equations(2-2) and (2-3) to develop an expression for S2-S1 gives S2 - Si = (a2-al)pNK + r2 - rl (2-5) Equating equation (2-4) and equation (2-5) a2 - a = (a2-al)PNK + r2 - ri r2-r1 a2 - a1 = 1-PNK Now a2 > al implies a2-al > 0. Furthermore, since a1 and a2 are integers, a2-al is an integer. If all the bases are greater than one, pNK > 1 and 1-pNK < 0. Thus r2-r1 < O. Recalling the restriction on the range of r1 and r2 from equations (2-2) and (2-3) it is seen that in general 1-pNK r2rl pNK-1. In this case r2-r1 must satisfy the additional conditions: (1) r2 - rl < 0 (2) 1 - PNK must divide r2-r1. This leaves only two allowable choices of r2-r1: Case (1) r2- rl = 0 Case (2) r2 - rl = 1 - pNK Case (1): Let r2-r1 = O, then r2 = rl and a2-a1 = = 0 thus for Case 1-PNK (1) r2 = rl and a2 = al. ASD TR 61-438 172

Now since S1 = alPNK + rl ~ > Si = S2 S2 = a2PNK + r2 But S1 = S2 contradicts the original hypothesis that S1 < S2. Therefore, r2 - ri O. Case (2): Let r2 - r = NK then 1-PNK a2 - a1 = r = 1!-PNK By equation (2-4) 2 - S1 = 1 Now if r2 rl = - PNK r - r2 = PNK - Recalling the limits on r1 and r2 it is seen that ri = p -l "r- PNK r2 = 0 Hence, S1 = aPNK +PNK 1 S2 = (al+l)PNK when tNK for S1 equals tNK for S20 ASD TR 61-438 173

It has been established that two integers S1 and S2 will have the same tNK for some 1 ( K < N-1 when S2 is a multiple of PNK and S1 = S2-1. Now assume that there is a third number, S3, which has the same tNK as S1 and S2. Since S is always and integer, it is clear that if such a S3 exists it is either less than S1 or greater than S2. If S3 is less than S1 it can only be S1-l. If S3 = S1-1, then to satisfy the conditions already established S1 must be a multiple of PNK. But S1 (pNK-l)mod PNK which is a contradiction. Furthermore, if S3 > S2, then S3 = S2+1 and S3 must also be a multiple of PNK Now since S2 is a multiple of PNK, S3 = S2+1 can only be a multiple of PNK if PNK = 1. This contradicts the hypothesis that pNK > 1. Hence, no such S3 exists. In summary, it has been shown that as S goes through the integers 1, 2,...,p, tNK assumes integer values at least (P1P2. PK-1)(PNK-1) times and further that no more than two numbers have the same tNK. Hence, the theorem is proved. Define MNK as the number of integer tNK for some fixed K as S goes through the integers 1, 2,..,p. On the basis of the previous theorem we can say that MNK = (P1P2~ PK-I)(PNK ) + mNK where mNK is the number of integer tNK which appear twice as S goes through 1, 2,...,p ASD TR 61-438 174

It has been shown that, tNK wli.l be the same for two numbers if they are successive and if PNK divides the greater oneo Note that tNK in this case is not necessarily an integero As S goes through 1, 2, ooop there will be P/PNK integers which are multiples of pTK. Now examine t wNK when S is some multiple o of PNKo NNK "PPW, 1; ( PNK-1) NK PK PK It is clear that if pK PNK1) all. NK for S = cPK will be integerso Since there are P/PNK = PP2o ~ PK multiples of PNK' MN = PP2~ ~oPK and K (lp O.PKl1) (PNK1) +,pp o p-)1, NK = (PiP2 PKi) (PNK+PK-1), Pklj(PmNKl) For the case pKX(p.-l), tNK will be an integer only for those values of c For he cse K (_P\PN1) - K. ~\K which are divisible by PK and there will be PIP2 ~PK of theseo PK -.K = (P1P2 - PKA-l) PK X (PNK 1)'\NK = (PiP2.PK-9i)NK 1) (P1P2 00PK lK - (pi2o - PKLI) (PNK) PX K(K 1P ) Given some set of bases PP2P3pso.PN, +the set M.N1, M27 M 11N3,~...T can be calculated. The number of identical mixed base and modular representations of integers S such that I < S < p cannot exceed the minimum MNK Example: P1 = 3, P2 = 5, P3 = P4 = 11 P = 11, P = 711 77, 775 = 385 7 Xl l -i M4s = 355o1 = 165 5X77-1i M42 = 3o77 = 231 3 1 385-1= i = 385+3-1 = 387 ASD TR 61-438 175

min MNK = 165. The actual number of identical elements = 27. Although the minimum MNK does provide an upper bound for the maximum number of identical mixed base and modular representations, it is a poor estimate of the actual number. Furthermore, to determine the maximum number of identical elements for all the N: mixed base systems associated with N bases requires (N-l): computations. The MNK function does give some insight into the problem of choosing the bases to achieve the maximum number of identical elements, Comparing the two expressions for MNK seems to indicate that choosing the bases and their order so that pKIPNK-l will lead to the greatest probability of attaining a high degree of correspondance between mixed base and modular representations in a system. ASD TR 61-438 176

APPEN2BIX III SIGN DEPTERNAITION BY A WWO-DIGIT REDCTZICON PROCESS INTRODUCTORY REFARKS This report presexnt-ms a method for determining the magnitude of a number from the decimal system whbich has been transformed into a residue number systemo The residue representation does not pernit a trivial recognition of magnitude, otherwise there wTould be no need of such a method. This method determines which half of the system the number is in, TERMINOLOGY The bases are taken as primes, where p1 is taken to be the number 2 while Pi(i A 1) represents any arbitrary prime.'ihe primes are to be arranged in increasing order, after arbitrary selection, such that PI < P2 <. < Pi < P1i6 < O..'... < Pn (3-1) The letter n will be taken to mean th-e total number of prime bases, and N will mean any number representable in the system. The letter ai shall represent the residue of N with respet to p1i and the range of N to be considered shall be < N < M (3-2) where M = 7Pi i=l ASD TR 61-438 177

In symbolic form, the number shall be represented by Bases: P1P2P3.......... Pn (3-3) N = = a1a2a3.....oooo. a Use will also be made of further terminology. The letter m shall indicate the product of two base primes, and to be orderly let ml = pnPnnm2 = Pn-2Pn-3 o (3-4) mk = P4P3 The case under consideration is seen to be n an even number, with k thus being equal to (n/2)-l. This orderly pairing of primes and assignment of subscripts to the m's is not essential and does not effect the generality of the result, It is merely an aid to simplification of symbolism, The letter bi shall represent the residue of N with respect to mi, and si, ti and dj represent integers. OPERATIONAL REMARKS From the terminology section, ai is the residue of N with respect to pi. This may be written as: N = sipi + a (3-5) and, from the interpretation of bi; N = timi + bi (3-6) ASD TR 61-438 178

By the nature of the residue system, certain operations are easily performedo If the representation has a zero in the ith digit position, division by Pi is simnple and guarantees an integer resulit Thus = - si (3-7) Pi is easily performed, because N-ai does indeed have a zero in the ith positiono Similarly, tlhe operation t= i t~ (3-8) mi is easily performed, since mi is the product of two base primes and N-bi has zero digits corresponding to these primeso However, bi is not as readily available as was aio But bi may be found by equations (3-12) and (3-13)o in the development of these equations, the subscripts on b, t and m have been changed to avoid confusion with p, d and a, Let mo = PifP where 2 i < j n and 0 d j Pi - 1 By the definition of a and b bo - aimod Pi b0 m ajmod pj (3-9) ASD TR 61-438 179

These equations (3-9) may also be interpreted as follows bo = diPi + a bo = djpj aj (3-10) Combining equations (3-10) yields i aj = djPj - diPi which may be also interpreted as ai aj - djpjmod Pi (3-11) and thus the procedure for the determination of bo, from equations (3-10) and (3-11) is: d = ai- (3-12)'' Pj P i o = djpj + a (3-13) ADDITIONAL REMARKS If care is taken in selection of the primes for mi, a savings will resulto For if, in equation (3-12), pj - +1 mod pi the congruence relation is solved merely by subtracting aj from ai in the mod pi portion of the system, a fast and simple step~ In connection with the forthcoming expansion, note that the machine step of equation (3-7) destroys the ith digit position0 If the system is assumed capable of re-expanding si to reclaim the lost digit position, then a reduction to a uniformly-based number system can be made~ The following ASD TR 61-438 180

reduction to a no.nur..iformiy-'based nuniber system does not require such an. as sumpt i on o REDUCT.ION TO NON-UII\TiP3R)LT 23AS5 SYSTEM The nurmber N will r..ow'be d-eve-soped from its residue representation into a non-uniformly-based numbnero, The e starting point is the use of equations (3-6) and (3-8), an.d te fol owing iterative procedure: N _ t,,m, + b1 t1 N bm N = ~,~1 + bitl mi tl - b2 -i2..i im k Ml o -bkl tkl = Iknk bk (1k =4) m'kk Equation (3-14) +t.r.us -hows the final result of the iterative process. By combining thlis equ.ation -i:t can. be seen that k —1. tk =e (3-15) k Rk~. k l N =tk t m tN-bk l-nb~o o. o o o o o + + JT~ mi = Then by solving (3-15) for N, the result is seen to be a non-uniformly-based number k k-i N = tk "- bi + bk7(C i ~...oooo.oo.o bsm2ml + btmi + 13 (3-16) ASD TR 61-438 181

in which 0 O<bi mi - o DEVELOPMENT OF THE FINAL STEP There are exactly (plp2) -1 occurrences of the case bi = mi-l for 0 < N < M, two of which will be helpful in establishing certain limits. The two cases are now to be examined, and they are: (a) N = - 1, and (b) N = M- l In each case, add unity to the representation of (3-16), resulting in: M (a+ )~7mi (5-17) (a) = (1 + t ) m (3-17) i=l (b) M = (l+t ()) 7 mi (3-18) i=l In the equations (3-17) and (3-18) the letters t() and t() refer to speM cific constants, respectively the most significant digit of 7 - 1 and M-l in the non-uniformly-based system. By equations (3-2) and (3-4) k n Trmi = 7 Pi (3-19) i=l i=3 M = Pi i=l ASD TR 61-438 182

And, since Pi = 2 by definition M - 7( = TL(3-20) i=2 By combining equations (3-17-3-20) (a) M: P2- L(t = 2 1) (b) tk = P1P2- l(N - M-1) (3-21) It now follows from equations (3-21) and as a direct result of the carry properties of the non-uniformly-based number system of equation (3-16) that for 0 N < ~, O tk < P2 M<2 N < M, P2 < tk < PP (3-22) Since the orderly use of the primes in the formation of the mi's was not essential to any of the steps involved up to now, as long as each prime is used once and only once in that formation except for p, and one other prime Pr, the equations become in the more general case M 0 N' < 2 0 < tk < Pr 2 ^ < M, Pr < Ntk < PiPr (3-23) The only difference resulting from a given selection of Pr will be in the weights assigned to the digit positions of the non-uniformly-based number system~ Each step of this procedure eliminates two digit positions from further ASD TR 61-438 185

consideration. After k steps, upon the derivation of tk, there are two digits remaining for its representation, a1 and ar. The primes on these letters merely serve to underline the fact that they are not the a, and ar of the number N. A brief study of equations (3-23), bearing in mind the cyclic nature of a residue representation, shows that for f 4. even, a even < tk < Pr; a is odd when ar is odd while Pr < tk < PiPr; al is even when ar is odd odd even And therefore when a + ar - Nomod 2 (3-24) it is seen that when O, O N N< No 1, 2< N<M (3-25) And it is for this reason that pI = 2 was saved for the last (k+l) step, EXAMPLE An example is now given to illustrate pairing the prime bases to satisfy the criteria of the additional remarks section, For the bases (2, 3, 5, 7, 11, 13, 17, 19, 23, 29), pairs ml = 29x7; m2 = 23x11; m3 = 13x3; m4 = 19x5; while P = 2 and pr = P7 = 17. ASD TR 61-438 184

The assignmente of sutsc-ripts to the mns in this examnple is arbtitraryo Each definite assigrn.me:nt leads to a separate number systemo CO,,LLUDING RERkiRKS An. answer to -t his particular magnitude question is guaranteed in K4. steps3, where for n n evern K I = nr odd K = 2 (3-26) In the latter case, the final step becomes merely an inspection of the al digit with th.e conditions of equation (3-25) becoming (0L-r M (9, 2 < N <. If aI = But,'w'hile Ktl.' steps are required in general, the procedure may terminate earlier, depending upon the size of No For when any M i 0i < K) 9 0 N< since ti = G if 0I f N < 3 mj D.=I Now a.tinme estimate for the somp'lete operation gives, for equation (3-8) 1 add time; while for equations (3-12) and (3-13); 2 add times; for a total of 3 add times per ith step 1 i < Ko The final step for n even takes i add time, while for n odd does not, requiare an addition, but an inspection. iThese ASD TR 61-438 185

facts coupled with equations (3-26) give n even: - 1)3 +1 add times n odd: (n) 3 add times (3-27) to guarantee an answer. However, if only one digit is removed at once, by the use of equation (3-7) alone, only two add times per step are required for n-2 steps, and one add time for the final step (n both even and odd) and equations (3-27) become, for this case every n: (n - 1) add times. ASD TR 61-438 186

APPENDIX IV C! MMENIS ON PARITY C HECKITG N THEN RNS A first thought is to apply normal checking procedures to the Residue Number System. Any conventional method may be applied to the transmission of digits from one point to another,o hat is, simple parity, multiple parity, and Hamming checks may be applied by considering the binary coding to be a message, with no consideration given its semantic character, Nothing new or special is added merely because the message is a residue coding. This discussion will be on arithmetic checkingo The problem is essentially to find a function F(a) having the property F(a) + F(b) = F(a + b) The most obvious example of such a function is F(a) = a, This is interpreted as duplication of the addition circuitry, A second and more significant example is F(a) a mod mo If the moduli of the RNS are mi, m2,, omn and m = mj for some j, then this function is not particularly useful. It is a duplication of one of the component sums and suffers from the same type of limitation as the identity functiono Attention will be focused on the case where m ~ mj (for all. j). Here if m mj (for all j), then F(a) is a function of all n components and, therefore, requires a conversion to the mixed base system, The carries involved make this system very unattractive. A "useful" check will either involve a conversion to the mixed base system or will require a separate check on each of the digits. This latter case will be discussed in considerable detailo ASD TR 61-438 187

In Garner'sl4 paper on Generalized Parity Checking, the dimished-base check is discussed, in which: ibj - oimod (b-l) Also the augmented-base check, in which: cibj - cimod (b+l) or a- imod (b+l) Neither of these can be used when bj = mj for then k = 0 and these relations are trivial, However, were the components to be binary-coded, it would be possible to use the augmented-base checko It is more intriging to consider a binary-coded base-3 system of components with the dimished-base check, Moduli up to 81 could then be employed with a maximum of 4 such binary groups, and up to 27 with 3 base-3 digits, Only the least significant bit of each group would be involved in the checkingo Three or four digits could conveniently be handled with "carry-lookahead," if not by purely combinational circuits. Consider the RNS with moduli mlj m2J,2 mnn If ji x - imod mi then x = ai + kmi and x = 0i + (kmi )mi~, where ~ < ji ASD TR 61-438 188

yielding x =- imod mi' Thus, the residue of x mod mi may be obtained from the residue of x mod miJi. From this it follows that such a RNS could be used to obtain the residue of x mod mi as a function of the individual components. This derived residue could be used to implement a che;ck It, will now be shown that the only moduli which would work in the above scheme are those which divide mi If x = aimod m and y - b mod m then x - y - al m bmod m and the retained residue is Fa,1 +b11 L m Now a1 - a2mod m' bl b2mod ml and al + bi = a2 + bt2od m'o The residue of a2gT2mod m' equals the residue of a+blmod m'. The residue produced in the check procedure is ASD TR 61-438 189

ma Choose for consideration an a, and a b1 such that al + b1 = m Such a selection is possible because allb will span the integers I 0 < I < 2(m-1) If m' Im then La - k,+ bi and i a+bi b, = a+ ab However, if m'/ m ml m and al+ b, 0. mL' The hypothesis has been demonstrated. ASD TR 61-438 190

REFERENCES 1. Valach, MN Vznik Kodu A Ciselne Soustavy Zbytkovych Trid, Stroje Na Zpracovani Informaci, Sbornik III; 1955. 2. Svoboda, Ao Rational Number Systems of Residual Classes, Stroje Na Zpracovani Informaci, Sbornik, 1957. 3. Svoboda, A. and Valach, M. Operatorove Obvody. Stroje Na Zpracovani Informaci, Sbornik III, 1955o 4. Garner, Ho Lo "The Residue Number System." IRE Transo PGEC, Volo EC-8, June 1959, Po 140-47, 5. Cheney, Po W. A Digital Correlator Based on the Residue Number System. Technical Document LMSD-702670, Lockheed Aircraft Corporation, Palo Alto, Califo, 1960, 6. McCoy, N, H. Rings and Ideals Buffalo, New York: The Mathematical Association of America, 1948. 7. van der Waerden, B. Lo Modern Algebra, New York: Frederick Ugar Publishing Company, Volo I and II, 1950. 8. Hildebrand, F, Bo Introduction to Numerical Analysis, McGraw-Hill Book Co.; 1956. 9. Cheney, P. Wo Scaling by Deletion of Bases. Modular Arithmetic Note 10, Lockheed Aircraft Corporation, Palo Alto, Calif.; August 1960. 10o Herwitz, P. So and Pomerene, J. Ho The Harvest System, Proc, WJCC, pp. 23-32; May 19600 11. Report BL-25, Harvard University Communications Laboratory. 12. Valach, M. and Svoboda, A. Operational Circuits, Institute of Mathematical Machines; Oct, 1954; p. 330. 13o WADC TR-59-472 Project 7062; July 1959. 14, Garner, Ho L. Generalized Parity Checking. IRE Trans, PGEC, Vol. EC-7, Sept, 1958, pp. 209-13o ASD TR 61-438 191

UNIVERSITY OF MICHIGAN I 1 1 11111111ill il l11111111 3 9015 03127 1979