Iowa State University Capstones, Theses and Retrospective Theses and Dissertations Dissertations 1969 Residue number system in computer arithmetic Jesus Ocampo Tuazon Iowa State University Follow this and additional works at:https://lib.dr.iastate.edu/rtd Part of theElectrical and Electronics Commons Recommended Citation Tuazon, Jesus Ocampo, "Residue number system in computer arithmetic " (1969).Retrospective Theses and Dissertations. 3794. https://lib.dr.iastate.edu/rtd/3794 This Dissertation is brought to you for free and open access by the Iowa State University Capstones, Theses and Dissertations at Iowa State University Digital Repository. It has been accepted for inclusion in Retrospective Theses and Dissertations by an authorized administrator of Iowa State University Digital Repository. For more information, please [email protected]. This dissertation has been microfilmed exactly as received 70-7754 TUAZON, Jesus Ocampo, 1940- RESIDUE NUMBER SYSTEM IN COMPUTER ARITHMETIC. Iowa State University, Ph.D., 1969 Engineering, electrical University Microfilms, Inc., Ann Arbor, Michigan I^SÎDUE î'iJKiER LYoTEM IN COI-îi^UlîlR ARTTHMETIC by Jesus Ocampo Tuaaon A Dissertation Submitted to the Graduate Faculty in Partial Fulfillrent of The Requirement,s Cor the De.-T^oo of •J(^CT^;R OF niTLOSOMIY i'p.jnr .Ouiijoct: I'lcctrical I nfitiror i vpcl: AT Signature was redacted for privacy. ar^e of Major Work Signature was redacted for privacy. Iifc ..'aidn rvj'ff •lor- l1 'i=!!:;rii-t;-iT;;:cnntt -"i,.T Signature was redacted for privacy. 1; 01 i.C.-iii îo-.ja State University Of Science an'l Techno] Ames, lovra 1969 PLEASE NOTE; Not original copy. Several pages have indistinct print. Filmed as received. UNIVERSITY MICROFILMS ii TABLE OF CONTENTS Page I. INTRODUCTION 1 A, Review of literature 1 B, Statement of the Problem 7 C, Comrliter System C^^anization 8 IT. RÎ'^STDIï. NIMBF'.R SYSTEM 11 A, Description of Residue Nimber System and Notation iised 11 B. Residue Arithmetic for Special l'!od"uli 13 C, Residue-Coded Number l5 D. Input and Output Conversion 17 L. Siçmed-Nunber System 29 F. Magnitude Comparison 30 0, Overflow Detection 31 H, Multiplicative Overflov: 36 1. Fractional Multiplication and Fractional Representation 3? J. 'j^A'i.tîion and Scali.np; l-O K. Division Algorithms 1;3 L, Flnafi.Tip-Pniiit Arithrietic Ii7 II. Multiple Precision ).;? II}. IN COMPUTERS g2 A. Conventional Arithmetic Processor Usin^ Residue îir.nbet- System ^2 iii Page 3. Arithmetic Processor in Residue Mode with Magnetic Core Matrix 55 0. Performance Analysis 62a r;. CONCLUSIONS 66 V. Bri!LIf>;RAliiY 68 VI. ACKI-.'ajLlLDOW-Tl'OTS 71. VII. Al-reKiiTX 72 1 I. D-jTRODL'CTION A. Review of Literature Some redundant ni-mber systems, such as the residue number system, have intorestinR and potentially useful characteristics in the arithmetic opera­ tions of multiplication, addition and subtraction. In a conventionally vrciphted runber system, the n-th dip;it in the sum is derendent. i-.yor. the n-th dipits of the tiojo operands and the carry from the lesner r i ;-;yt Ticnnt difit". Tn th(! residue numier system, the n-th dipit of t}:e sum is fir-rendeni. only ur''>n trie n-th diyits of the oncrands. I!o cnrries w neede:] t,': proT;a: ntc ?- lorif- the syrtnm. Pronapation of carries are also not needed for the orcra- tion of multiplication and subtraction, 'iith those properties, ndTiition, î.rjltiylication and subtraction in the residue number syrtein is significantly faster than the same operations in conventionally weighted number r;ysteiTis, In the last few years, a significant amount of work [(lfi)-(28)l has been devoted to improving the speed of arithmetic operations in computers. '•\lthour/i present machines have some spectacular speed (e.n-, 1 microsecond) for ar: add cycle, there are problems which are cotnrute boimd rather thar Lnrut/'')utput hound, Such problems are in correlation analysis, partial riif- I'c.'rential ccuations, numerical analysis and matrix oyiernt.ionL; to name a Lew. TJiere arc also computer systems where the arithmetic j;need in almost di^^ctly related to the performance of the whole system, such as in the cases of rock- et-borne or min^ile-borne on-line control comruters. :'ome of the ways to speed up the operations of an arithmetic processor are: (a) V^y tbe use of hiph-speed circuit elements, and (b) by the use of 2 carry-look-ahead or conditional-sum adder. It ir.\ist be noted that the carry propaf'ation tine in a parallel adder usually has a decisive influence upon the time of execution of arithmetic operations. This has been a subject of intensive investigations [(l8)-(2l)]« In the conditional-sum method (19), the partial sum and carry are re­ corded in two separate registers. The carry register is shifted to the left, and the ones in the carr;/" register are reset to zero whenever they are aliened with a zero in the partial-sum register, and the act of resetting the ones to zero in the carry register forces a onei n the corresponding position in the partial-sum register. The process is continued until all the ones in the carry register are eliminated. In a cirry-look-ahead (20), the register is segmented into blocks of k- bit long. In each block, the k bits of the sum and the carry to the next block are computed simultaneously. The carry is propagated from block to block instead of bit by bit. Due to complexity of the circuitry and limita­ tion of fan-in and fan-out in a gate, k is usually no more than 5 bits, 5 bits is also the average carry propagation length of a 32-bit adder (21). The skip-carry technique (20) is useful in multiplication where there are a string of ones and zeros in the mi&tiplier. A string of m zeros will imply that the multiplicand is shifted m positions. A string of ones be­ tween positions k and k+m is replaced by 2^. Consequently, m addi­ tions and shifts are replaced by a shift and a subtraction. Lehman (l8) extended this basic recoding technique and demonstrated that isolated zeros could be treated as a part of a longer string of bits. An isolated "one" calls for an addition of the multiplicand while an isolated zero 3 c.-îlls for a nv;htracxiori, (20.; presented a skir.-patii distribution c'jrs:'stir.-- oi" a division cl' the adder into k-position p;ro\;ps, and î^ajerski (21) presented a method to determine the optiimim oistrib^tion of carr?/ okir) :'r, ar: adinr. This ncthod could increase the speed of the 'iri' hnctn c unit a).r/;t 5 tj'nos over the conventionally striictured ones, wh.m irmloineni.ed wi th tho 5:anc class of lopic. A third v:ay to increase the speed of arithrnetic operations is to com­ pletely elj.ir.inate the carrry pr^^ap^tion problem. This is one of t.lic in­ herent properties of the residije nijnber syrtem. I'.arner (10) in\'estirated 1 r o ..Kc of residue number cy.-'tem in computers. Althoujrh 'n 1.3 main r^al was -Î.U •'.re r/'di;lar corir-G to detect anij correct errors, he also pointed out the pr I'o-rti's f''." i.l'.o residue numbers. The prcpertii-vs he descri bed were not. new !:i.t ; .";ve been known for cert eric s aniî could be found in '•t,.andard 1.exi-i;ooks or: V.-.ooi-y oj" i-j rr.hers (12). He, however, vrent fi:rthar ir; shewing hOi-; •:ne r rh ' -..UH; t;:;S res'duc represent-ati on in the arii i,: n-oti c processor. A- v,ho Svob.oda (30) was invest-i r;r iP--; apoJ 1 cnti or; o!" re- rifiual :i::jcbers in rnathc;r-i£ti.oal machines, de described an alr'or for rfn:l- it.rim t 1 r -1 yi n.:'- rridi !ir n^irbers in rr-si di-al classf's . lie also rxtended this to '"I'.'ifd. ; o; ::"i Corin, v-hich is his nain coid.ri tn; id.e n. hf rover- i.t.i: rion:n tj vc; ,n'c;iS oL" numi er soi.:. ,r:^ /' ^ i s' -, ] -n O' 1.o-.-i I-.a -..I.; <i< iecti cr and maruitndn cc-rp-iriscn. lie .'sV n :' • ! ::si, «>• •; 'y ! ; Ml ; 1,0 'Iff id;- .'-l' r ; I : x'l ill p''';cti cal c i roi: i try . dlor-us (' ! J.I'd dasaki (2'') 'no<i if icrd thr- residi;o C'jfie by nclud i n^ a rr;;if:ni iude hxiex A(y) which is carried oi;t dirt, eddy from tho Criim.-sc; icer'iain- der Tiujoreiu. The niaprdLude index will si}vpli fy nnrrd i.udc coinpari son and u sign detection, but it introduces a problem in multiplication, and conver­ sion is more difficult than before. Cheney (6) and Guffin (13) used the residue nrimher nymtem for spfxial arplicntions. Cheney applied it to correlation problems nnfl Ouffin used it to nolvo lin(-;ir sirrajltaneous eouations by an iterative method. Tt must bp noted that these special problems require a lot of multiplication and addition operations with very few division operations. Other applications that one may add to this list are the matrix operations such as multi­ plication and inversion which are common operations in solving partial liiiTorential equations. Neither author proposed any new solution to the inlierent problems of modular arithmetic. They avoided division in modular T'ifxlc, an", to assure that there is no overflow, they comruted t-'-fore hand T"a%irn'm rnr.'-e they woi;]d onc"urn,f,T ir t' cir cof::.ui.al.i on, and ucalcd appropriately. Cheney (6) used analog-modular and modular-.tnalo;,; conver­ sion. Thic may slim-.j.ify anri speed up the conversion operation, !".nv;evor, at t'r.e cost o;' accuracy. At any rate, he obtained an accuracy of 1 part in 100. Gu 'Tin in turn used the mijced-radix code to convert a modular number back to binary form. This is the same technique n- oposed by Garner. A few autliors f(ll:), (l?), i2h), (32) and (33)1, in the field of Infor­ mation Theory, have looked at the residue number syrtem from a different point of vnov;. They h-ive used it for detecting and correcting errors, \nd aro rnorc intt;ri';r,ted in the; reduniîant residue nmnber syst.em. A reciimdnnt i;\;riitpc:r .••.y;item is a residue-coded numbe r systi:m with the; moduli not i-<-lativ( iy :Thuc with each other. in order to increase th». reliability of tlie arithmetic and data trans-