Computer Organization (17834) - Module: IV Santhosh Kumar D K Module IV ARITHMETIC NUMBERS, ARITHMETIC OPERATIONS AND CHARACTERS NUMBER REPRESENTATION > Numbers can be represented in 3 formats: 1. Sign and magnitude 2. I's complement 3. 2's complement In all three formats, MSB=0 for +ve numbers & MSB=1 for -ve numbers. > In the sign-and-magnitude system, negative value is obtained by changing the MSB from 0 to 1 of the corresponding positive value. For example, +5 is represented by 101 & -5 is represented by 1101. In I's complement representation, negative values are obtained by complementing each bit of the corresponding positive number. For example, -3 is obtained by complementing each bit in 0011 to yield 1100. (In other words, the operation of forming the 1's complement of a given number is equivalent to subtracting that number from 2"-1), In the 2's complement system, forming the 2's complement of a number is done by subtracting that number from 2", > (In other words, the 2's complement of a number is obtained by adding 1 to the I's complement of that number). > The 2's complement system yields the most efficient way to carry out addition and subtraction operations. v v v B Values represented Sign ang sbybyby magnitude 'scomplement 2's complement oii +7 +7 +7 o110 +6 +6 +6 olor +5 +5 +5 0100 +4 +4 +4 ool 43 +3 43 0010 +2 +2 +2 oot +1 +1 +1 0000 +0 +0 +0 1000 -0 7 : 1oo1 -1 -6 -1 1010 2 es) -6 loll -3 -4 -5 1100 -4 -3 BY 1101 -5 aa 3 1110 -6 1 4 mit 7 -0 “1 Figure 2.1. Binary, signedinteger representations. Dept. of CSE, Canara Engineering College Page 100Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K ADDITION OF POSITIVE NUMBERS > Consider adding two 1-bit numbers. > The sum of 1 & I requires the 2-bit vector 10 to represent the value 2. We say that sum is 0 and the carry-out is ADDITION & SUBTRACTION OF SIGNED NUMBERS > Following are the two rules for addition and subtraction of n-bit signed numbers using the 2's complement representation system. Figure 22 Addition of Lit numbers 1. To add two numbers, add their n-bits and ignore the carry-out signal from the MSB position. The sum will be algebraically correct value as long as the answer is in the range -2"' through +2°'-1 (Figure 2.4). 2. To subtract two numbers X and Y( that is to perform X-Y),take the 2's complement of Y and then add it to X as in rule 1.Result will be algebraically correct, if it lies in the range (2"') to +(2"'-1). v When the result of an arithmetic operation is outside the representable-range, an arithmetic overflow is said to occur. > To represent a signed in 2's complement form using a larger number of bits, repeat the sign bit as many times as needed to the left. This operation is called sign extension. Dept. of CSE, Canara Engineering College Page 101Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K > In 1's complement representation, the result obtained after an addition operation is not always correct. The carry-out(c,) cannot be ignored. If ¢,=0, the result obtained is correct. Ifex=1, then a | must be added to the result to make it correct. OVERFLOW IN INTEGER ARITHMETIC > When the result of an arithmetic operation is outside the representable-range, an arithmetic overflow is said to occur. > For example, when using 4-bit signed numbers, if we try to add the numbers +7 and +4, the output sum $ is 1011, which is the code for -5, an incorrect result, An overflow occurs in following 2 cases 1, Overflow can occur only when adding two numbers that have the same sign, 2. The carry-out signal from the sign-bit position is not a sufficient indicator of overflow when adding signed numbers. A cascaded connection of n full-adder blocks can be used to add 2-bit numbers. Since carries must propagate (or ripple) through cascade, the configuration is called an n-bit ripple carry adder.(Fig 9.2). ADDITION/SUBTRACTION LOGIC UNIT The n-bit adder can be used to add 2's complement numbers X and Y (Figure 9.3). Overflow can only occur when the signs of the 2 operands are the same. In order to perform the subtraction operation X-Y on 2's complement numbers X and Y; we form the 2's complement of Y and add it to X. Addition or subtraction operation is done based on value applied to the Add/Sub input controb-line vvv v Dept. of CSE, Canara Engineering College Page 102Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K > Control-line=0 for addition, applying the Y vector unchanged to one of the adder inputs. > Control-line=1 for subtraction, the Y vector is 2's complemented. DESIGN OF FAST ADDERS Drawback of ripple carry adder: If the adder is used to implement the addition/subtraction, all sum bits are available in 2n gate delays. ‘Two approaches can be used to reduce delay in adders: 1. Use the fastest possible electronic-technology in implementing the ripple-carry design 2. Use an augmented logic-gate network structure CARRY-LOOKAHEAD ADDITIONS > The logic expression for sisum) and ci.,(carry-out) of stage i are SAAC (1) vebmicrtyics Cis > Factoring (2) into Cig =KVA(KAYIC Dept. of CSE, Canara Engineering College Page 103Computer Organization (17834) - Module: IV Santhosh Kumar D K » this can be written as. c41=Gt PC, where G=xiyi and Py=xi+yi ‘The expressions G, and P; are called generate and propagate functions (Figure 9.4). > IfGi=/, then c;.)=J, independent of the input carry c;. This occurs when both x; and yj are 1. Propagate function means that an input-carry will produce an output-carry when either x=1 or > All G, and P, functions can be formed independently and in parallel in one logic-gate delay. > Expanding ¢; terms of i-1 subscripted variables and substituting into the ¢js1 expression, we obtain C1 =GAPGi1+PPiiGi2.«...+P/GotPiPis «-. Poco > Conclusion: Delay through the adder is 3 gate delays for all carry-bits & 4 gate delays for all sum-bits. Consider the design of a 4-bit adder. The carries can be implemented as €1=Go+Poco 2=G)4P/Got PiPoco 2+ P2Gi+P2P Go+PP Poco 5=Gs+ PG PsP 2G + PsP2PGy+P PrP Poe > The carries are implemented in the block labeled carry-lookahead logic. An adder implemented in this form is called a carry-lookahead adder. Limitation: If we try to extend the carry-lookahead adder for longer operands, we run v v (@) 4-8 adder Figure 9.40 A 4:bit cory lookahead adder Dept. of CSE, Canara Engineering College Page 104Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K HIGHER-LEVEL GENERATE & PROPAGATE FUNCTIONS > > v v 16-bit adder can be built from four 4-bit adder blocks (Figure 9.5). These blocks provide new output functions defined as G, and Py, where k=0 for the first 4-bit block, k=1 for the second 4-bit block and so on. In the first block, Po=PsP2P Po & Go=G3+P3G2+P3PyG)+P3P2P Go The first-level G, and P, functions determine whether bit stage i generates or propagates a carry, and the second level G, and P, functions determine whether block k generates or propagates a carry. Carry ei is formed by one of the carry-lookahead circuits as €16=G3+P3G2+P3P2G 4 PsP2P Got PP2P Pico Conclusion: All carries are available 5 gate delays after X, Y and cy are applied as inputs. Figure 9.5 4 16-bit cory-lockahead adder butt fram 4-bit adders (see Figure 9.46). MULTIPLICATION OF POSITIVE NUMBERS Bit-level multiplier ab . =D-= Multiplication of two 4-bit words eao|c| ac t by be Ab Ab aby by yb; yb, ab; aby abe iby ibe abn Agby_Azbdy yds yds Pr Ps Ps Ps Ps BO Dept. of CSE, Canara Engineering College Page 105Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K ARRAY MULTIPLICATION © The main component in each cell is Full Adder (FA). © The AND gate in each cell determines whether a multiplicand bit m,, is added to the incoming partial-product bit, based on the value of the multiplier bit q: (Figure 9.6). 2.02 (23) Mutipticand Mt x tott GD Matspeso (a) Manual muttiptication algorthm Mutuipticand Rit of oupoing partial product IPPC + 1D (©) Array implementation Figure 9.6 Array muluplicotion of unsigned binary operands SEQUENTIAL CIRCUIT BINARY MULTIPLIER > Registers A and Q combined hold PP(partial product) while the multiplier bit qi generates the signal Add / Noadd. > The carry-out from the adder is stored in flip-flop C (Figure 9.7). > Procedure for multiplication: 1. Multiplier is loaded into register Q, Multiplicand is loaded into register M and C & Aare cleared to 0. 2. If qo=1, add M to A and store sum in A. Then C, A and Q are shifted right one bit-position. If qo=0, no addition performed and C, A & Q are shifted right one bit-position. 3. After n cycles, the high-order half of the product is held in register A and the low-order half is held in register Q. Dept. of CSE, Canara Engineering College Page 106Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K ee StF setae ° toon SS ° o10e0° seer aaa = boeeer ret Sg yee ° 10800 aves ma _ pe Figure 9.7 Sequential arcutt binary multplier SIGNED OPERAND MULTIPLICATION BOOTH ALGORITHM > This algorithm Y generates a 2n-bit product Y Treats both positive & negative 2's-complement n-bit operands uniformly (Figure 9.9-9.12). Attractive feature: This algorithm achieves some efficiency in the number of addition required when the multiplier has a few large blocks of Is. This algorithm suggests that we can reduce the number of operations required for multiplication by representing multiplier as a difference between 2 numbers. For e.g. multiplier (Q) 14(0011110) can be represented as 010000 (16) > Therefore, product P=M*Q can be computed by adding 2* times the M to the 2's complement of 2! times the M v v v Dept. of CSE, Canara Engineering College Page 107Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K Algorithm: ‘Step1: Find the 2’s compliment of of —ve number Step2: Find the new Q by applying booth recoding technique (use Figure 9.12). Step3: Multiply M with new Q for summands of 2n-bits, where after n-bit the n+1 bit onwards bits til 2n-bit are called sign extension bit, which will have the value of sign bit of the partial product. +1*M means M as it is and -1*M means 2's compliment of M Step4:The final product should be in 2n-bits more that bits can be ignored. Rema ee es © O+teieiet 0 0000000 ororirod orortrod = oo es o1oerto4. ° o ooo 0 oo o ooo oo 0 2 ©1018 on o+1 0 0 1o SCS CURB Se Uw eS oo . : PRLE SER SL ee 1 ooooo ecg egeaeae0e0e0 —— Seecesenn ve oo 00000000 tenis ta es ooo 0000 0 oo 0 o roo o Figure 9.9 Normal and Booth multiplication scheenes. O+1 -1+t 0-1 O41 © O-141-141 O-1 © O orron Gis orton x1 1010 (6 => O-1s1-10 _—_ 0000000000 ritiroort oooor1t0)l 1110001 oooooo TItorrooro 7 Figure 9.11 Boot multiplication with a negative multiplier. Dept. of CSE, Canara Engineering College Page 108Computer Organization (17834) - Modul Santhosh Kumar D K Mater | Version of muitipticand selected by bit Biti Biti—1 : © OxM. a * +teM i -1xM oa oxM Booth multiplier recoding table. o1reroreororororos Worst-case “anpincr > muluphcr ° ooo oo Good mutupher © 0 oO 0 oo Figure 9.13 © Booth recoded multipliers, FAST MULTIPLICATION BIT-PAIR RECODING OF MULTIPLIERS > This method Y Derived from the booth algorithm so it also called as modified booth algorithm. Y reduces the number of summands by a factor of 2 > Group the Booth-recoded multiplier bits in pairs. (Figure 9.14 & 9.15) > The pair (+1 -1) is equivalent to the pair (0 +1). G1 © 1 © B= u oo a, © (a) Example of bit-pair recoding derived from Booth recoding > Algorithm: > Step: Find the 2°s compliment of of -ve number > Step2: Find the new Q by applying bit-pair recoding technique. Implied Oto right of LSB Dept. of CSE, Canara Engineering College Page 109Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K > Step3: Multiply M with new Q for summands of 2n-bits, and each summands will be having 2-bit diffrence, sign extension bits are treated as like booth algorithm. +2*M means 2M and -2*M means 2's compliment of 2M > Step4:The final product should be in 2n-bits more that bits can be ignored. Figure 0.15 9 Muinphcaton requiring only n/2 summands CARRY-SAVE ADDITION OF SUMMANDS > Consider the array for 4*4 multiplications. (Figure 9.16 9.17 & 9.18) > Instead of letting the carries ripple along the rows, they can be "saved" and introduced into the next row, at the correct weighted positions, Py Me Ps % Ps ry Po (2) Ripple-carry array Dept. of CSE, Canara Engineering College Page 110Computer Organization (17¢S34) - Modul Santhosh Kumar D K Figure 9.16 Rapple-cory and cary-sove arrays for a4 x 4 multplier s 1 at i «= ° (6a ees eae ess Pretuct Figure 9.17 A rattplicanon excmple vad to tkmtrate cory-sewe orkdiion cs shown Figure 9.18 The multpicoton example from Figure 9.17 performed using carry-sewe Dept. of CSE, Canara Engineering College Page 111Computer Organization (17¢S34) - Modul Santhosh Kumar D K + i? 4 BOD Leen 1 deve 2eRA z , Level SERA a oo Fina adaison Figure 9.19 | Schemanc representation of fe carry-sawe Gaiton operations in Figure 218. INTEGER DIVISION > An n-bit positive-divisor is loaded into register M. Y An n-bit positive-dividend is loaded into register Q at the start of the operation. Register A is set to 0 (Figure 9.23). > After division operation, the n-bit quotient is in register Q, and the remainder is in register A 2 10101 13 Tze 1101 Troamoo10— 26 riot 1% 70000 Figure 9.23 Circutt arrangement for binary division, Dept. of CSE, Canara Engineering College Page 112Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K RESTORING DIVISION + Procedure: Do the following m times 1) Shift A and Q left one binary position (Figure 9.24). 2) Subtract M from A, and place the answer back in A. 3) If the sign of A is 1, set qo to 0 and add M back to A (restore A), otherwise if the sign of A is 0, set qo to 1 and no restoring done. 10 1) 1000 Initially 90000 1000 eae a i sin 90001 00 of] ee Fins cycle | ‘Second cycle ‘Third cycle | vo NON-RESTORING DIVISION * Procedure: Step 1: Do the following n times i) 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 M1to A (Figure 9.25). ii) Now, if the sign of A is 0, set qo to 1; otherwise set qo to 0. Step 2: If the sign of A is 1, add M to A (restore). Dept. of CSE, Canara Engineering College Page 113Computer Organization (17¢S34) - Modul Santhosh Kumar D K Initially 0 0 0 0 0 1000 gooo11 Suit oaooo1 ooo) Fantogcis Subract 10101 01 Set ¢q @ 110 oo of) Shift r11itooe o of) Add g9oo11 Second cycle Set gy @: 2s oom Shift r11ii1o6é o [o)fo)-) Add 9oo11 Third cycie Set do @e ool ° wag Shift oooi10 Hono Subeact 10101 01 Fourth cycle Set go @: rad fal(o Gt) ——- Quotient Add prddid ooo1t1 Resore remainder aooo10 —~~_~ Remainder Figure 9.25 = A non-restoring division example. FLOATING-POINT NUMBERS & OPERATIONS, IEEE STANDARD FOR FLOATING POINT NUMBERS > Single precision representation occupies a single 32-bit word. Y The scale factor has a range of 2° to 2*'”” (which is approximately equal to 10), > ‘The 32 bit word is divided into 3 fields: sign(1 bit), exponent(8 bits) and mantissa(23 bits). > Signed exponent=E Y Unsigned exponent E'=E+127. Thus, B’ is in the range O The last 23 bits represent the mantissa. Since binary normalization is used, the MSB of the mantissa is always equal to 1. (M represents fractional-part). > The 23-bit mantissa provides a precision equivalent to about 7 decimal-digits (Figure 6.25). Dept. of CSE, Canara Engineering College Page 114Computer Organization (17834) - Module: IV Santhosh Kumar D K > Double precision representation occupies a single 64-bit word. And E’ is in the range 1 The 53-bit mantissa provides a precision equivalent to about 16 decimal-digits. sabe SSS Sign of ‘hit cena 23 ie =. sae eine ometion _— excess-127 gaits — ‘Value represented = £1.M <2" 177 (4) Single precision [Jecroreoofoorsre SSCS Value represented = 001010 ...0x2-*7 (b) Example of a single-precision number (64 big | sic. Se 11-bit excess 1023 sie ‘exponent Value represented = $1.88 2-102 (©) Double precision Figure 9.26 IEEE stondord floating point formats. ‘excess: 127 exponent —— (There is no implicit 1 tothe left of the binary point.) Value represented = +0,0010110... x2” (@) Unnormalized value Value represented = +1.0110...2° (0) Normalized version: Figure 9.27 Floating-point normalization In IEEE single-precision format. Dept. of CSE, Canara Engineering College Page 115,Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K ARITHMETIC OPERATIONS ON FLOATING-POINT NUMBERS, Multiply Rule 1, Add the exponents & subtract 127. 2. Multiply the mantissas & determine sign of the result. 3. Normalize the resulting value if necessary. vide Rule 1. Subtract the exponents & add 127 2. Divide the mantissas & determine sign of the result. 3. Normalize the resulting value if necessary. Add/Subtract Rule 1. Choose the number with the smaller exponent & shift its mantissa right a number of steps equal to the difference in exponents (n). Set exponent of the result equal to larger exponent. Perform addition/subtraction on the mantissas & determine sign of the result. Normalize the resulting value if necessary. AYN Guard bits and Truncation > While adding two floating point numbers with 24-bit mantissas, we shift the mantissa of the number with the smaller exponent to the right until the (wo exponents are equalized. > This implies that mantissa bits may be lost during the right shift (that is, bits of precision may be shifted out of the mantissa being shifted), > To prevent this, floating point operations are implemented by keeping guard bits, that is, extra bits of precision at the least significant end of the mantissa. > The arithmetic on the mantissas is performed with these extra bits of precision. > Afier an arithmetic operation, the guarded mantissas are: ¥ Normalized (if necessary) Y Converted back by a process alled truncation/rounding to a 24-bit mant Truncation 1. Straight choppin; ‘The guard bits (excess bits of precision) are dropped. 2. Von Neumann roundi Y Ifthe guard bits are all 0, they are dropped. Y However, if any bit of the guard bit is a 1, then the LSB of the retained bit is setto 1 3. Rounding: Y If there is a 1 in the MSB of the guard bit then a | is added to the LSB of the retained bits. Y Rounding is evidently the most accurate truncation method. However, Y Rounding requires an addit n operation. Dept. of CSE, Canara Engineering College Page 116Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K Y Rounding may require a renormalization, if the addition operation de- normalizes the truncated number. ¥ TEEE uses the rounding method, IMPLEMENTING FLOATING-POINT OPERATIONS, > First compare exponents to determine how far to shift the mantissa of the number with the smaller exponent. > The shift-count value n ¥ Is determined by 8 bit subtractor & ¥ Is sent to SHIFTER unit. Step 1: sign is sent to SWAP network (Figure 9.28). If sign=0, then Ex>Ex and mantissas My & Mp are sent straight through SWAP network. If sign=l, then E,EB or EB if EASEB Step 2: Step 3: CONTROL logic ¥ Determines whether mantissas are to be added or subtracted. ¥ Determines sign of the result Step 4: result of step 3 is normalized. The number of leading zeros in M determines number of bit shifts(X) to be applied to M. Dept. of CSE, Canara Engineering College Page 117Computer Organization (17834) - Modul Santhosh Kumar D K Dept. of CSE, Canara Engineering College Page 118Computer Organization (17¢S34) - Module: IV Santhosh Kumar D K Question Bank 1, Perform the following operations on the 5-bit signed numbers using 2s complement representation system, Further indicate whether overflow has occurred. 1) (10)4(-13), ii) (-10)-(14) , itt) (47)-(-15), iv) (48)+(410), ¥) (3) +8), vi) (10) - (47) 2. Multiply i) (+14) and (-6), ii) (-12) and (-11), iii) 14 and (-8), iv) 1100 and 1001, vy) 10111 and 1000, vi) 1111 and 1110, vii) 1011 and 1100, viii) 1111 and 1011, 3. ix) 25 and 31, x) 17 and 15 using Booth’s algorithm and Bit pair recoding technique and also write the algorithm, 4, Write the steps and perform the division i) 8 by 3 (8/3), ii) 12/4, iii) 1101/101, iv) 1111/110, v) 1110/10 using restoring division method and non-restoring division method. Given A = 10101 and B= 00100 perform A/B using non-restoring division algorithm. Design a logic circuit to perform addition/subtraction of two ‘n’ bit numbers X and Y. Design a 4 bit carry lookahead logic & explain how itis faster than 4 bit ripple adder. Explain normalization, excess exponent and special values with respective IEEE floating point representation. 9, Explain different arithmetic operation on floating point number. 10, Multiply i) 15 and 9, ii) 14 and 6, iii) 1100 and 1001, iv) 10111 and 1000, vy) LLL and 1110, vi) 1011 and 1100, vii) 1111 and 1011, viii) 25 and 31, ix) 17 and 15, x) 12 and 6 using sequential multiplication techniqueand also write the algorithm. 11, Explain with a neat diagram implementation of floating point addition and subtraction unit. ena Reference: 1. Carl Hamacher, Zvonko Vranesic, Safwat Zaky: Computer Organization, 5th Edition, Tata McGraw Hill,2002, For Softcopy of the notes and other study materials visit: https://sites.google.com/view/dksbin/subjects/computer-organization Dept. of CSE, Canara Engineering College Page 119