an NOTE || captor Eve arithmetic = CHAPTER 5 a In this chapter, we present the logic circuits used to implement arithmetic operations. ee re time needed to perform various arithmetic — operations affects the processor's performance SS Multiply and divide operation requires more =? fomplex circuitry than addition and subtraction. pe RTE We present some of the techniques used in modern computers to perform arithmetic a NY _prations at high speed. Design fast adder using n-6it ripple carry adder, (WASAT[S for 7 marks) Draw and explain n-bit ripple carry look ofa adler (§-18 for 7 marks) Explain design of cascade of n bit addres, (6-19 for? marks) Draw and explain binary adftion and subtraction logic circuit, (W219 for 7 marks) SS eg. Addition and Subtraction of Signed Numbers Figure 5.1 shows the logic truth table for the ee eee sum and carry-out functions for adding ——— TO equally weighted bits Xj and Yj in two OO numbers X and Y. The figure 5.1 also shows logic expressions for these functions, along with an example of | addition of the 4-bit unsigned numbers 7 and 6. Note that each stage of the addition process must accommodate a carry-in bit. We use Cj Computer Architecture & Organization zz HH] Computer Architecture & Organization Wiser 51Ari _ Chapter Five in to the it tthe carry-in to the it sta, Be chapter Five ithmetic rf to represeas the carry-oUt from the” "hi, is s 1} stage: li ota eam ERE peace +s ot, = eed edie. SR win 245 Se BOCs, Lege treaaet Figure 5.1 Logic Specifications for a Stage of Binary Addition «© The logic expression for Sj can implemented with a 3-input XOR gate, used in Figure 5.2 (a) as part of the logic required for single stage of binary addition. ” SD- :Djp- Ao Gut ebadier «i mesic |, (6) Logie for a Single Stage Computer Architecture & Organization veya ieee (b) An n-bit Ripple-Carry Adder fet Iact fey teas tate Aalto 1 Hel ie ve ts oa - | adder 1 adder (©) Cascade of k n-bit Adders Figure 5.2 Logic for Addition of Binary Vectors * The carry-out function, C (j+1),_ is implemented with a two-level AND-OR logic circuit. A convenient symbol for the complete circuit for a single stage of addition, called a full adder (FA), is also shown in the figure. * A cascaded connection of n full adder blocks, as shown in 2 (b), can be used to add two n-bit numbers. Since the carries must propagate, or ripple, through this cascade, the configuration is called an n-bit ripple-carry adder. «The carry-in, Co, into the least-significant-bit (LSB) position provides a convenient means of adding 1 to a number. For instance, forming Computer Architecture & Organization \QV/¢. 5-3Met ng] signals are aS Useful to form an ting k adders add co nndling input numbers that a ‘as shown in Figure 5.2 (c), kn bits Jong, Finary addition-subtraction Togas (WAS, S-16/17 for 6 marks) 5.1.1 Addition and Subtraction Logic Unit it in Figure 5.2 (b) can be u: . -bit adder in Figure 5. cl ad "ye-complement numbers X and y, where the Xn-1 and Yn-l bits are the. sign bits. : verflow can only occur when the signs of the pees are the same. In this case, overflow obviously occurs if the sign of the tesult is different. Therefore, a circuit to detect. overflow can be added to the n-bit adder by implementing the logic expression. Kae Spt t In order to perform the subtraction operation X-Y on 2's-complement numbers X and Y, we Overflow = YotSna form the 2's-complement of ¥ and add it toX. © The logic circuit network shown in Figure 5.3 can be used to perform either addition or subtraction based on the value applied to the Add/Sub input control line. * This line is set to 0 for addition, applying the Y vector unchanged to one of the adder inputs | along with a carry-in signal, Co of 0. angers Ee ea a chapter Five Arithmetic wa Figure 5.3 Binary Addition-Subtraction Logic Networks When the Add/Sub control line is set to 1, the ¥ vector is I's-complemented (that is, bit complemented) by the XOR gates and Co is set to 1 to complete the 2's-complementation of Y. 5.2 Design of Fast Adders Need: * If an m-bit ripple-carry adder is used in the addition /subtraction unit of Figure 5.3, it may have too much delay in developing its outputs, So through S,.1 and Ca. * Whether or not the delay incurred is acceptable can be decided only in the context of the speed of other processor components and the data transfer times of registers and cache memories, * The delay through a network of logic gates depends on the integrated circuit electronic technology used in fabricating the network Computer Architecture & Organization Qren 55coe eS ee ‘and on the mumber of gates in the pay ey | Paths, FS " inputs to outputs. © The delay through any combination, network constructed from gates in q al logy technology is determined by adding Seu number of logic-gate delays along the by the signal propagation path through the ney W8ty two approaches can be taken to reduce qo, or] adders. clay © The first approach is to use the ¢ possible electronic technology in impleme the ripple-carry logic design or variations * The second approach is to use an atten it logic gate network structure that ig 4ut than that shown in Figure 5.2 (b). large, ‘Draw and explain 4 bit carry look-ahead adder, ; (W15/16/19, 5-16 for 6/4/7 marks) H Draw and explain 4-bit ripple carry adder. | (S-19 for 7 marks) 5.2.1 Carry-Look Ahead Addition A fast adder circuit must speed up the generation of the carry signals. The logic expressions for §) (sum) and C(i+1) (carry-out) of stage I (see Figure 5.1) are: si=x@yi@ci and Cie = Xi + ici + Vici Factor the second equation into cist = ays + (1 + Yio: we can write cin = Gi + Pics Computer Architecture & Organization Yao. 54 apter Fiv Ari etic where iyi and P, The expressions Gi and Pi are called the generate and propagate functions for stage i. If the generate function for stage i is equal to 1, then C(i+l) = 1, independent of the input carry, Ci. ‘This occurs when both Xi and Yi are 1. The propagate function means that an input carry will produce an output carry when either Xi is lor Yiis 1. « All Gi and Pi functions can be formed independently and in parallel in une logic-gate delay after the X and Y vectors are applied to the inputs of an n-bit adder. Each bit stage contains an AND gate to form Gi, an OR gate to form Pi, and a three-input XOR gate to form Si. + A simpler circuit can be derived by observing that an adequate propagate function can be realized as Pi = Xi ® Yi, which differs from Pi = Xi + Yi only when Xi = Yi= 1. Beall a Pesca (@) Bit-Stage Cell Computer Architecture & Organization Ww- (b) 4-Bit Adder Figure 5.4 A-Bit Carry-Look Ahead Addep But, in this case Gi = 1, so it does not m, whether Pi is 0 or 1. Then, using a cascades two 2-input XOR gates to realize the 3-ing XOR function, the basic cell B in Figure 5.44 can be used in each bit stage. Expanding Ci in terms of i-l subscriptey variables and substituting into the Cu expression, we obtain, cist = Gi + PiGia + Pi Pit cit Continuing this type of expansion, the find expression for any carry variable is, cis = Gi + PiGi-r + Py Piet Gio +... + Pi Pa + PiGo + PiPia ... Poco Let us consider the design of a 4-bit adder ‘The carries can be implemented as, c1 = Go + Poco C2 = Gi + PiGo + PiPoco 3 = G2 + P2Gi + P2PiGo + P2PiPoco += Gs + PsG2 + PsP2G1 + PaP2P;Go + PsP2PiPo0e Computer Architecture & Organization Wf. ea Computer Architecture & Organization apter Five Arithmetic The complete 4-bit adder is shown in Figure 5.4 (b). The carries are implemented in the block labeled carry-look ahead logic. An adder implemented in this form is called a carry-look ahead adder. + Delay through the adder is 3 gate delays for all carry bits and 4 gate delays for all sum bits. In comparison, note that a 4-bit ripple- carry adder requires 7 gate delays for S3 and 8 gate delays for C4. Figure 5.5 shows a 16-bit adder built from four 4-bit adder blocks. These blocks provide new output functions defined as Gk’ and Pk’ where k = 0 for the first 4-bit block, as shown in Figure 6.4b, k = 1 for the second 4-bit block, and so on. In the first block, Po = PP2P\Po Gh =G, +P,G, +P,P,G, +P,P,P,G, fun ign ous gue emt at Figure 5.5 16-Bit Carry-Look Ahead Adder Built From 4-Bit Adders 59Chapter Five « In words, Mp eatin ctions det i d eenartes or propagates @ Can» and nate eeeond-level Gk’ and pk’ functions deze th whether block I generates OF Propagaytty = delay in produci ‘ consider the delay in producing oy, fa the 16-bit carty-look ahead adden Py Bopy in developing te CArTICS Prodycey Cee earry-look ahead circuits is two by delays more than the delay needed to ga, Ba the Gk’ and pk’ functions. bp i delays and ‘The latter require two gate onal delay, respectively, after the generation of ¢ see bs Therefore, all carries produced by yf! carry-look ahead circuits are available § delays after X, Y, and Co are applied inputs. Explain array multiplication of positive bing operands. (018 for ma Explain sequential circuit binary multiplier with example (W-18, 5-19 for 7 mark) 5.3 Multiplication of Positive Numbers «© The usual algorithm for multiplying integers by hand is illustrated in Figure 5.6 (a) for the binary system. This algorithm applies to unsigned numbers and positive signed numbers. that the fi whether bit i ie The product of two n-digit numbers can be accommodated in 2n digits, so the product 0 two 4-bit numbers in this example fits into Computer Architecture & Organization WYguasz- 54 apter Five Arithmetic pits. In the binary system, multiplication of the multiplicand by one bit of the multiplier is easy. if the multiplier bit is 1, the multiplicand is entered in the appropriate position to be added to the partial product. If the multiplier bit is 0, then Os are entered, as in the third row of the example. 1 Manian 1G sagter , T 0° ino Tooortit Ces Prot? (a) Manual Multiplication Algorithm atin eT e pio iO mio “nt ‘caryia cgi wi ree PU (b) Array Implementation Figure 5.6 Array Multiplication of Positive Binary Operands Computer Architecture & Organization WY/ff.sm:, 5-12rithm, hapter Five e lication of positive operands Cay Binary multi i combinati be implemented i Oy, aS showy dimensional logic array, own Figure 5.6 (b)- ce omponent_in each cell is f ‘The AND gate in each yhether @ mauliplicand bit mj the incoming parti I-product bj ae on the value of the multiplier bit, gj," i = i <= 3, add; w i, where 0 <= i < 3, adds 4, Bat tiplicand (appropriately shifted) to e incoming partial product, PPi, to generate outgoing partial product, PP (i+ 1), if qi = 1, If qi = 0, PPi is passed vertically downy, unchanged. PPO is all 0's, and PP4 is i, Yesired product. The multiplicand is shifteg left one position per row by the diagonal signa path. The main c adder FA. determines W! Register A (italy 0) Mahila NE (a) Register Configuration Computer Architecture & Organization Computer Architecture & Organization chapter Five Arithmetic SE28 POEL Sah feos ay POEL OE OT poe a ay a a ee ns PoRSES EEE MB} mee fete th (b) Multiplication example Figure 5.7 Sequential Circuit Binary Multiplier The block diagram in figure 5.7(a) shows the hardware. arrangement for sequential multiplication. . This circuit performs multiplication by using a single n-bit adder n timers to implement the spatial. addition performed by the n rows of ripple-carry adders of figure 5.6(b). Registers A and Q combined hold PPi, while multiplicand, M, to PPi to generate PP{i + 1). The product is computed in n cycles. The partial product grows in length by one bit per cycle from the initial vector, PPO, of n Os in register A. The carry-out from the adder is stored in filp-flop C, shown at the left end of register A. At the start, the multiplier is loaded into register Q, the multiplicand into register M, Whe 5-13Chapter fl are cleared to and C a and Q are shified righ cach YY now for growth of the position © he multiplicand into regis prot Aare cleared to 0. pe end of e200 E16 CA, ang Q at d 4 right one bit position to alloy, Cees of the partial product as the my ly Be snifted out of register Q. The mulpigg is aee of figure 8.8 (8) is ghatly ne 5.7 (p) a8 it would be Performed jy a a ware arrangement. Ta sgned operation multiplication > Ser agin with xampl “y Boot (W-18, 5-19 for? ma 5,4 Signed Operand Multiplication i ultiplication of now discuss ml ay veelenent signed operands, generating «| double-length product. The general strategy; still to accumulate partial products by a, versions of the multiplicand as selected by ty multiplier bits. | First, consider the case of a positive multpl negative multiplicand. When we addi sogate ‘multplcand to a partial produc, must extend the sign-bit value of th multiplicand to the left as far as the produ will extend. | In Figure 5.8, for example, the S-bit signel operand, -13, is the multiplicand, and it multiplied by + 11, the multiplier, to get ty 10-bit product, -143, | Computer Architecture & Organization Yfistte FH | 1 (0) Figure 5.8 Sign Extension of Negative Multiplicand Figure 5.9 Normal and Booth iiultiplication Schemes + The sign extension of the» multiplicand is shown in blue. Thus, the hardware’ discussed earlier can be used for negative multiplicands if it provides for sign extension of the partial products, For a negative multiplier, a straightforward solution is to form the 2's-complement of both the “multiplier and the multiplicand and Proceed as in the case of a positive muliiplier. Computer Architecture & Organization Wee 515© This Me does Ot, CHANBE he ya both opera the product. sh technique the Sie ually well for pot Negative vote ‘multipliers, called the Boalt si air. 3 Fa algontim for mliplcatiog (8-16, W-17 for 7/6 mg A pes the Boot ant examp™ 541 Booth’s Algorithm eis pomertalogorithma FOF Signed mpg * qultiplication. . tes 2n bit product and operate, 1 erosive ‘as well as negative nun uniformly. structure shown hardware c roars 0 fa) can be usfd to perform operation 's required by the Booth’s algorithn, | J} Hoe mana ” ot, ia possible because complementat, iv h re Lo Firtey | “rity balds ill zeros Holds Master ‘Aa ata wil double ength 4 aniceential Figure 5.10 (a): Hardware structure implement) Booth's algorithm il Computer Architecture & Organization AYf.s==- ici SE coi Ilustration with Examples: cxamples show how to apply the steps of the Booth’s algorithm. Computer Architecture & Organization \Y/f « The @ ight (ASR) operation i shown below: Keep the MSB as it is and shift the bits including MSB. » The Booth's algorithm Figure 5.10 (b) below- Figure 5.10 (b): Booth's Algorithm for Twos Complement Multiplication The following 5-17Ait a the multiplication of the Example: 2 Coneide er Ca tipliation of > sitive Mm oe ‘at n= 4. The steps needed 9 and assuming low. tabulated be a jution:- Data ‘ nitialization: oe m=oll) Q= 0011 A= 0000 Count = 4 M-=A+2’scomplement of M Ys capri of M= 1000 os complement of M= 1001 |_ on —500 0011 0 gy fang 10011 oa Initial + A-M@A+ H+} 1001 1061 1001 1° 3 as chapter Five Arithmetic problem 5.1: ‘Laplain how Booth’s alorithm t suitable for signed number multiplication in comparison of conventional shift and add method. Multiply the following pair of signed 2's complement numbers: A= 110011 multiplicand, & = 101100 multipher. Draw and explain logic diagram. (S-15/16, W-19 for 7/13 marks) ‘Explain Booth’s algorithm for multiplication A = 110011 multipficand and B = 101100 multiplier. Solution:-Data Initialization: Multiplicand = M = 110011 Multiplier = Q = 101100 1’s complement of M = 001100 2’s complement of M = 001101 Computer Architecture & Organization Wy 4 ASR & 7 1100 A-M~=A+ 2's complement of M = 001101 4 count oot 11 3 ‘ASR & 1110 Count = 6 and A = 000000 4Count Condition A Q Q: | Count } Sayyi Initial 000000 101100] 0 6 AtM SI ASR& o101 1010 0 1 pee is Count 000000 | 010110] o 5 $count 001 ASR & ar 4 +count_| 000000 |oo1011} 0 | 4 +Count 0001 0101, 0 A-M +001101 J OS oan poeta tcount_| 000110 | 1001 oi} a + (210 | fase . J le count 000011 [o1o010] » 2] Computer Architect: ture & Organization Ofc. 519{condition initial 000000 | 110110 | 0 6 ASR & Ycount | 000000 | o11011|/ 0 | 5 a-M |¥101001 ASR & 101001 {count } 110100 | 101101 | 1 | 4 ASR & problem 5.2: : . Jeount_{| 111010 | 010110} 1 3...] eaph folowing pais of 2's compliment mumigy| farm [+O10111 in the Booth algorithm —_ ASR & 010001 08 seatutilcand)| Buin) Yeount | oo1000 | 101011] 0 | 2 ono11 110110 A-M | +101001 110011 101100 asr& | 110001 ‘ 710101 __| 011011 4 Count ditooo | isororj | 2 x dill ooi111 ASR & dcount | w1t100 | ortoro} 1 | o | Solution: 1 4) A= 010111 multiplicand, B= 110110 multiple, Data Initialization: Multiplicand = M = 010111 Multiplier = Q = 110110 <. Vs complement of M = 101000 2's complement of M = 101001 | < A=M=A+2's complement of M =A + 10100] J. Count = 6 and A = 000000 Computer Architecture & Organization We dl ve & 2's complement = (230)i0 i Z ii) A= 110011 multiplicand, B= 101100 multiplier, Data Initiali Multiplicand = M = 110011 Multiplier = Q = 101100 +. 1's complement of M = 001100 tion: “. 2's complement of M= 001101 *, A~M= A+ 2's complement of M = A + 001101 . Count = 6 and A = 000000 4 ‘Computer Architecture & Organization YG 5:21100101 010010 ii) A= 110101 multiplicand, B= 011011 multiplier. Initialization: aren =M= 110101, Multiplier = Q = 011011 :. V's complement of M = 001010 :. 2’s complement of M = 001011 :. A-M=A+2’s complement of M = A+ 001011 :. Count = 6 and A = 000000 : oe the Computer Architecture & Organization Yee chapter fue = Arithmetic Condition | A Q [as | count initial 000000 | 011011 | 0 | 6 | a-M +001011 [* =| ASR & 001013 tcount_ | 000101] 101101 | 1] 5 ASR & 7 Leount_ | 000010 | 110110] 1 | 4 AtM +11010 ASR & 110111 deount | 111011} 111031} 0 | 3 A-M +001011 a ASR & 000110 toount_ | 000011 J o11101/ 1] 2 ASR & teount_ | 900011 | 011101 | 1 1 aeM /+110101 ASR & 110110 teount | 111011 | 010111] 0 | oo -ve & 2's complement = (297)10 i.e, -297 aa element = (297 iv) A= 001111 muitiplicand, B = 001111 multiplier. Data Initialization: Multiplicand = M = 001111, Multiplier = Q = 001111 +: 1’s complement of M = 110000 “+ 2's complement of M = 110001 | A~M=A + 2’s complement of M= A + 110001 “+ Count = 6 and A = 000000 Computer Architecture & Organization Wim. 5-23Chapter ee fooiiit | apter Five Arithmetic __1’s complement of M = 000110 ie | 110 e 3g | rot “_ g's complement of M = 000111 ‘count = |. A~M= A+ 2's complement of M =A + 000111 R & 010011 2 = . [ee | 211004 | count = 6 and A = 000000 ASR & | 1110 | 00100! Conaition A Q@ |: ] count aL | tranat 000000 | 000111 | 0] 6 ASR & | 000100 +o00111 yitiit a-M aanaere 1 jen poo see, | s00012 | 10011} 1 | ie 001110 | count 4 ASR & 000111 | 000010 & 4 Count ASR count | 000001 | 110001 | 1 4 ool = 1 100 ASR & tcount | 000000 | 111000 | 1 3 & P| faem [*1i1001 | ASR & 111001 i toount | 111100. 111100] 0 | 2 Problem 8.3: : ‘ 4 | ! in Booths Algorithm Multiply following pais|| {As & 2H pais compliment numbers using the Booth algortin [$count | 221110 | o1rm20/ o | 21 | FT otuiicond) — (Mulipher) rake 111001 001111 [4count | 122111 | oo1111,/ 0 | oO 5 x Solution: | complement = (49)10 ie, -49 A= 111001 multiplicand, oe B= 001111 multiplier. Problem 5.4: Data Initialization: ‘Explain how Booth’s algorithm , multiply the = following pair of signed 2's complement number: Multiplicand =4.5,114001 A=1001i multiplexed B= 01011 Multiplier = Q = 000111 Draw and explain logic diagram. (S-17 for 13 makes) Solution: Sol Problem 5.2. Computer Architecture & Organization We su aes Computer Architecture & Organiz 5-25 eeAth chapter Five os a of Booths Algorithm in the number of aq the inefficiency gf the bit pattern in Q becg en algorita it of 0 (1) followed by a 1(9); tuation can be improved if an rather th 10) we shoud pe gsc ONE wv 7 a G wT Teen am OTT oI oe ‘OI A= AAT a Pap 4 toot shit rot im = Sa v an em 7 ee sepa eon Se trio _ 101010 + BTA ae wn gt answer: 0001 1011 010% (which is 437) 5.5 Fast Multiplication We now descri the multiplication oper + The first technique maximum num! the multiplicand) that must be a for n-bit operands. ation. « The second technique reduces fhe needed to add the summands. computer Architecture & Organization \WYfs=~ cks of the Booth’s algorig = ‘this last SiN pits are inspected at a tine be two techniques for speeding y guarantees that 4 ber of summarids (versions ded is af i hy Ty 4 ter Five 5.5.1 Bit Pair Recoding of Multiplier pit pair recoding is used to s A ata d multiplication process in Booth’s algorithra the . It is also called as modified Booth’s algorithm. , In this, Booth’s recoded multiplier bi eae multiplier bits are Arithms ach pair is represented by i i , 5 2 ed by its equivalent single bit raultiplicr reducing tota multiplier bits to half. Sole mad Figure 5.12 (2) shows an example of bit-pai recoding of the multiplier in Figure Sil,and ee ee ee u Oer-141 O-1 Or! 0 O-te1-141 0-1 0 0 Figure 6.11 Booth Recoding of a Multiplier and Booth Multiplication with a Negative Multiplier Figure 5.12 (b) shows a table ‘pli ¢ (b) of the mui selection decisions for all possibilities. one Screg Nps ogee \ u 2 ot Ho : ygede. ( : a of bit-pair recoding derived from Booth recoding puter Architecture & Organization WY fier. 5-27ind selection decisions (b) Table of multiplica Figure 5.12 Multiplier bit-pair recoding ad explain 4-bit ripple carry adder. Dewan (WASLsE, SAL for may The 4.Bit Ripple-Carry Adder Schematic . 3 4-bit ripple- + Using full-adder create @ U-Dit rpple- can} adder (schematic only) with pipelined inp and outputs. The ripple-carry architectur | shown in figure 5.13- Ar B Ar Bi Ay By ie Peete a ef Fut ull be ‘Adder | © | Adder:| © | Aaden| EP ad S: Si Figure 5.13 4-bit ripple carry adder * It is possible to create a logical circuit Us multiple full adders to add N-bit num! Each full adder inputs cin, which is the C4) Computer Architecture & Organization Ys H ter Five Arithmetic of the previous adder. This kind of adder is a ripple carry ‘adder, since each carry bit “ripples” to the next full adder. « Note that the first full adder may be replaced by a half adder. + The layout of a ripple carry adder is simple, which allows for fast design time; however, the ripple carry adder is relatively slow, since cach full adder must wait for the carry bit to be calculated from the previous full adder. » The gate delay can easily be calculated by inspection of the full adder circuit. Each full addér requires three levels of logic. In a 32-bit [ripple carry] adder, there are 32 full adders, so the critical path (worst case) delay is 3 (from input to carry in first adder) + 31 * 2 (for carry propagation in later adders) = 65 gate delays, . * We need to determine the clock frequency required by the adder, as well as the dynamic and static power. ‘List out the steps for Booth's algorithm for restoring and non-restoring with example each. G-18 for 14 marks) 3.6 Integer Division * Figure 5.14 shows examples of decimal and binary division of the same numbers. © The decimal division is self-explainable. * In binary division only possibilities for the quotient bits are 0 and 1. Computer Architecture & Organization Wax. 5-290101, 1101 J100010010~ NOL 10000 Hor mo, ow 1 Figure 5.14 Long-Hand Division Example, sreuit that implements division 4 Tea ghes method operates as follows: yy It po respec subtraction. If the remainder is zero or positive, a quot pit of 1 is determined, the remainder extended by another bit of the divideng, th divisor is repositioned, and anoyje subtraction is performed. On the other hand, if the remainder j| negative, a quotient bit of O is determined, ty dividend is restored by adding back th divisor, and the divisor is repositioned {| another subtraction. sitions the divisor appropriately |. t to the dividend and Pert a th the help of circuit, explain Restoring divin (W216 for 7 mare) circuitry. thi! Figure 5.15 shows a implements restoring division, * An n-bit positive divisor is loaded into regist¢) M and an n-bit positive dividend is loaded int Computer Architecture & Organization Yi 4 logic eo spapter Five Arithmetic register Q at the start of the operation. Initially register A is set to 0. . After the division is complete, the n-bit quotient is in register Q and the remainder is in register A. The required subtractions are facilitated by using _2's-complement arithmetic. ‘The extra bit position at the left end of both A and M accommodates the sign bit during subtractions. ‘The following algorithm performs division- 1. Shift A and Q left one binary position. 2. Subtract M from A, and place the answer back inA. 3. If the sign of A is 1, set q0 to 0 and add M back to A (that is, restore A); otherwise, set q0 tol. Figure 5.16 shows a 4-bit example as it would be processed by the circuit in Figure 5.15. restoring Figure 5.15 Circuit Arrangements for Binary Division Computer Architecture & Organization WY. =. 5-31Explain suitable exon 2 Non-Restoring Division ! -division algorithm ¢, gy avoiding the need for resto unsuccessful subtraction ie, nop eger the sequence of Operations tt naner the subtraction operation jn x 5.6. : he restoring afer an result. COM takes place afte preceding algorithm : vrais positive, we shift eft and sutra that is, we perform 2A - M. \ | If Ais negative, we restore it by performin eat ‘hen we shift it left and subtract jy Me ers equivalent to performing 2A+M, ropriately set to O or 1 after the ‘The op bit is app current operation has been performed, Figure 5.16 A Restoring Di | ee Computer Architecture & Organization \Yffusc- 5 ter Five ithmetic fe can summarize this in the following algorithm for non-restoring division: step 1: Do the following n times: 1, If the sign of A is 0, shift A and Q left one bit position and subtract M from A; otherwise, shift A and Q left and add M to A. Now, if the sign of A is 0, set q0 to 1; otherwise, set q0 to O. step 2: If the sign of A is 1 and add M toA. hniily 00000 1000 coor sult oooor ooo Svirct DTN O01 Fimt eyele S24 Orie ooe sin 11100 oof) Af 00011 Seto riti 00f@ sn oritio of aa 00011 Sta Oooo!) cM Om a 00010 GMO Subnet 11101 wri oe I = Quatiet ag niid : beet | a coord mei eee Renae Figure 5.17 A Non-Restoring-Division Example Computer Architecture & Organization We. 5-33Step 2 i Chapter Five 7 i A —_ led to leave is nee the chapter Five rithmetic ter Five ______Aritimet der in A at the end of the n Grete positive remain leg o 9 0 0 0 yo 0 © No restore operations are needeg |” $80 0 t oo 0 Finer exactly one Add or Subtract operation is requ’ tt oe i aoe @ per cycle, Figure 5.17 shows how the qiyigi 01111111 (1's complement) + 1 10000000 (2's complement)—+ -128 © = 00000000 (2’s compliment) Qi. 5-513. . 1g = 00010010 (Binary equivalent) > 11101101 (1’s complement) 1 1101110 (2's complement) “18 1 Problem 5.7: A module 10 adder is needed for adding BCD dye ‘Modulo 10 adding of two BCD digits, A= Araagig, ‘and B = BsB:B:Bo, can be achieved as: Add A 0g (incr aduion), The, ifthe result isan ilegat eg that is greater than or equal to 1010, add 610. (Ignoy, overflow from this addition) i) When is the output carry equal to 1? 8) Show that this algoritim gives correct result for g)A=0101 and B =0110 6)A = 0011 and B = 0109 i) Design a BOD digit adder using a 4-bit binary R adder and external logic gates as needed. The inputs are A = AAAJo, B = ByBrBiBo and carry-in. The output are the sum digit SsS0SiSo and the carry-out, ‘A cascade of such blocks can form a ripple-carry BCD B adder. Solution: : (i) The output carry is 1 when A + B >. This is the condition that requires the further addition 6.0. (ii) a) Give A = 0101 and B = 0110 Computer Architecture & Organization WYf,cox. 55 Mi ae i 701110 (2's compliment) ’ 5 £0110 +8 1011 >10% 11 +0110, 0001 Output carry = 1 piven A= 0011 and B = 0:00 0011 3 +0100 2) O11 <100 7 iii) SHS Figure 5.23 BCD digit adder using a 4-bit binary adder Computer Architecture & Organization YY. 5.53ter FiVé iimethion uy spose acthmetie chi ig manual method, perfo fem 5.8 : the 5-bit ya™ prob problem Band A+ Bon it ung, te ao - operations 4% B AT a B= 00101, Weng | qcapipfrentiate between ripple carry adder and cary Took, numbers A=} ea ead adder in detail ‘The Solution, inculding g,,; al solution: 7 Mt) oration: nt ares equivalel ed B = 00101 Ripple Carry Adder | Look Ahead Carry Adder | A= 10101 ia this wader cary pes In this case input bits are | ugh ‘n’ stay Upple | examined simultaneously yaxB 010) 5 ner from LSB toMSB. | and carry bite art gencrewed Be simultaneously for all xacio10l X21 stages, 105 The oped is affected by| Speed is independent of 00108 The number of full adder | number of stages required. ~ro rot stages used. aoia ea Oats jg Function at each | Logic function for each full ooo ooo fall-adder stage is same. | adder stage is different and ooro 100 its complexity increases 0, oer ONO Oye; & gradually, oo 0 oo eT ness Tinus designing this type of | Circuit design is complex a3 0° circuit is quite simple. compared to ripple adder. 2)A+B jon delay time is | Propagation delay time is ! 100 4 pear reduced and limited. 5V21 |For Logical Diagram Refer | For Logical Diagram Refer oororoia 30 Figure Figure 54. 00001 1 Computer. ‘Architecture & Organization ct. 5-55 Computer Architecture & Organization YY/ficz- 4 c Ww