3.Computer Arithmetic

&CHAPTER 4Computer ArithmeticThis chapter is dedicated to a discussion on computer arithmetic. Our goal is tointroduce the reader to the fundamental issues related to the arithmetic operationsand circuits used to support computation in computers. Our coverage starts withan introduction to number systems. In particular, we introduce issues such asnumber representations and base conversion. This is followed by a discussion oninteger arithmetic. In this regard, we introduce a number of algorithms togetherwith hardware schemes that are used in performing integer addition, subtraction,multiplication, and division. We end this chapter with a discussion on floating-point arithmetic. In particular, we introduce issues such as floating-point represen-tation, floating-point operations, and floating-point hardware schemes. The IEEEfloating-point standard is the last topic discussed in the chapter.4.1. NUMBER SYSTEMSA number system uses a specific radix (base). Radices that are power of 2 are widelyused in digital systems. These radices include binary (base 2), quaternary (base 4),octagonal (base 8), and hexagonal (base 16). The base 2 binary system is dominant incomputer systems.An unsigned integer number A can be represented using n digits in base b:A ¼ (anÀ1anÀ2 . . . a2a1a0)b. In this representation (called positional representation)each digit ai is given by 0 ai (b À 1). Using positional representation, the dec-Pimal value of the unsigned integer number A is given by A ¼nÀ1i¼0 ai  bi. Con-sider, for example, the positional representation of the decimal number A ¼ 106.Using 8 digits in base 2, A is represented as A ¼ 0  27 þ 1  26 þ 1  25þ0  24 þ 1  23 þ 0  22 þ 1  21 þ 0  20.Using n digits, the largest value for an unsigned number A is given byAmax ¼ bn À 1. For example, the largest unsigned number that can be obtainedusing 4 digits in base 2 is 24 À 1 ¼ 15. In this case, decimal numbers rangingfrom 0 to 15 (corresponding to binary 0000 to 1111) can be represented. Similarly,the largest unsigned number that can be obtained using 4 digits in base 4 isFundamentals of Computer Organization and Architecture, by M. Abd-El-Barr and H. El-RewiniISBN 0-471-46741-3Copyright # 2005 John Wiley & Sons, Inc.5960COMPUTER ARITHMETIC44 À 1 ¼ 255. In this case, decimal numbers ranging from 0 to 255 (correspondingto 0000 to 3333) can be represented.Consider the use of n digits to represent a real number X in radix b such that themost significant k digits represent the integral part while the least significant m digitsrepresents the fraction part. The value of X is given byXkÀ1X ¼xi  bi ¼ xkÀ1bkÀ1 þ xkÀ2bkÀ2 þ Á Á Á þ x1b1i¼Àmþ x0b0 þ xÀ1bÀ1 þ Á Á Á þ xÀmbÀmConsider, for example, the representation of the real number X ¼ 25.375. Thisnumber can be represented in binary using k ¼ 5 and m ¼ 3 as follows.X4X ¼xi  bi ¼ x4  24 þ x3  23 þ x2  22 þ x1  21i¼À3þ x0  20 þ xÀ1  2À1 þ xÀ2  2À2 þ xÀ32À3with x4 ¼ 1, x3 ¼ 1, x2 ¼ 0, x1 ¼ 0, x0 ¼ 1, xÀ1 ¼ 0, xÀ2 ¼ 1, and xÀ3 ¼ 1.It is often necessary to convert the representation of a number from a given baseto another, for example, from base 2 to base 10. This can be achieved using a numberof methods (algorithms). An important tool in some of these algorithms is the div-ision algorithm. The basis of the division algorithm is that of representing an integera in terms of another integer c using a base b. The basic relation used isa ¼ c  q þ r, where q is the quotient and r is the remainder, 0 r b À 1 andq ¼ ba=cc. Radix conversion is discussed below.4.1.1. Radix Conversion AlgorithmA radix conversion algorithm is used to convert a number representation in a givenradix, r1, into another representation in a different radix, r2. Consider the conversionof the integral part of a number X, Xint. The integral part Xint can be expressed asÈÉXint ¼ ½Á Á Á (xkÀ1r2 þ xkÀ2)r2 þ Á Á Á þ x2)r2 þ x1Š r2 þ x0:Dividing Xint by r2 will result in a quotient Xq ¼ {½Á Á Á (xkÀ1r2 þ xkÀ2)r2 þ Á Á Á þx2)r2 þ x1Š} and a remainder Xrem ¼ x0. Repeating the division process on the quo-tient and retaining the remainders as the required digits until a zero quotient isobtained will result in the required representation of Xint in the new radix r2.Using a similar argument, it is possible to show that a repeated multiplication ofthe fractional part of X (Xf) by r2 retaining the obtained integers as the requireddigits, will result in the required representation of the fractional part in the newradix, r2. It should, however, be noted that unlike the integral part conversion, the4.1. NUMBER SYSTEMS61fractional part conversion may not terminate after a finite number of repeated mul-tiplications. Therefore, the process may have to be terminated after a number ofsteps, thus leading to some acceptable approximation.Example Consider the conversion of the decimal number 67.575 into binary.Here r ¼¼¼¼110, r22, Xint67, and Xf0.575. For the integral part Xint, a repeateddivision by 2 will result in the following quotients and remainders:Quotient331684210Remainder1100001Therefore the integral part in radix r ¼¼22 is Xint(1000011). A similar method canbe used to obtain the fractional part (through repeated multiplication):Fractional part0.1500.3000.6000.2000.4000.8000.6000.200. . .Carry over bit10010011. . .The fractional part is X ¼f(.10010011. . .). Therefore, the resultant representationof the number 67.575 in binary is given by (1000011.10010011. . .).4.1.2. Negative Integer RepresentationThere exist a number of methods for representation of negative integers. Theseinclude the sign-magnitude, radix complement, and diminished radix complement.These are briefly explained below.4.1.3. Sign-MagnitudeAccording to this representation, the most significant bit (of the n bits used torepresent the number) is used to represent the sign of the number such that a “1”in the most significant bit position indicates a negative number while a “0” in themost significant bit position indicates a positive number. The remaining (n À 1)bits are used to represent the magnitude of the number. For example, the negativenumber (218) is represented using 6 bits, base 2 in the sign-magnitude format, asfollows (110010), while a (þ18) is represented as (010010). Although simple, thesign-magnitude representation is complicated when performing arithmetic opera-tions. In particular, the sign bit has to be dealt with separately from the magnitudebits. Consider, for example, the addition of the two numbers þ18 (010010) and 219(110011) using the sign-magnitude representation. Since the two numbers carrydifferent signs, then the result should carry the sign of the larger number inmagnitude, in this case the (219). The remaining 5-bit numbers are subtracted(10011 2 10010) to produce (00001), that is, (21).62COMPUTER ARITHMETIC4.1.4. Radix ComplementAccording to this system, a positive number is represented the same way as in thesign-magnitude. However, a negative number is represented using the b’s comp-lement (for base b numbers). Consider, for example, the representation of thenumber (219) using 2’s complement. In this case, the number 19 is first representedas (010011). Then each digit is complemented, hence the name radix complement toproduce (101100). Finally a “1” is added at the least significant bit position to resultin (101101). Now, consider the 2’s complement representation of the number (þ18).Since the number is positive, then it is represented as (010010), the same as inthe sign-magnitude case. Now, consider the addition of these two numbers. In thiscase, we add the corresponding bits without giving special treatment to the signbit. The results of adding the two numbers produces (111111). This is the 2’s comp-lement representation of a (21), as expected. The main advantage of the 2’s comp-lement representation is that no special treatment is needed for the sign of thenumbers. Another characteristic of the 2’s complement is the fact that a carrycoming out of the most significant bit while performing arithmetic operations isignored without affecting the correctness of the result. Consider, for example,adding 219 (101101) and þ26 (011010). The result will be (1)(000111), whichis correct (þ7) if the carry bit is ignored.4.1.5. Diminished Radix ComplementThis representation is similar to the radix complement except for the fact that no “1”is added to the least significant bit after complementing the digits of the number, asis done in the radix complement. According to this number system representation, a(219) is represented as (101100), while a (þ18) is represented as (010010). If weadd these two numbers we obtain (111110), the 1’s complement of a (21). Themain disadvantage of the diminished radix representation is the need for a correctionfactor whenever a carry is obtained from the most significant bit while performingarithmetic operations. Consider, for example, adding 23 (111100) to þ18 (010010)TABLE 4.1The 2’s and the 1’s ComplementRepresentation of an 8-Bit NumberNumberRepresentationExample2’s Complementx ¼ 000 (00000000)0 , x , 256x77 (01001101)2128 x , 0256 2 jxj256 (11001000)1’s Complementx ¼ 00 or 255(11111111)0 , x , 256x77 (01001101)2127 x , 0255 2 jxj256 (11000111)4.2. INTEGER ARITHMETIC63to obtain (1)(001110). If the carry bit is added to the least significant bit of the result,we obtain (001111), that is, (þ15), which is a correct result.Table 4.1 shows a comparison between the 2’s complement and the 1’s comp-lement in the representation of an 8-bit number, x.4.2. INTEGER ARITHMETICIn this section, we introduce a number of techniques used to perform integer arith-metic using the radix complement representation of numbers. Our discussion willfocus on the base “2” binary representation.4.2.1. Two’s Complement (2’s) RepresentationIn order to represent a number in 2’s complement, we perform the following two steps.1. Perform the Boolean complement of each bit (including the sign bit);2. Add 1 to the least significant bit (treating the number as an unsigned binaryinteger), that is, ÀA ¼ A þ 1Example Consider the representation of (222) using 2’s complement.22 ¼ 00010110+11101001 (1’s complement)þ111101010 ( À 22)4.2.2. Two’s Complement ArithmeticAddition Addition of two n-bit numbers in 2’s complement can be performedusing an n-bit adder. Any carry-out bit can be ignored without affecting the correct-ness of the results, as long as the results of the addition is in the rangeÀ2nÀ1 to þ 2nÀ1 À 1.Example Consider the addition of the two 2’s complement numbers (27) and(þ4). This addition can be carried out as (27) þ (þ4) ¼ 23, that is, 1001 þ(0100) ¼ 1101, a (23) in 2’s complement.The condition that the result should be in the range À2nÀ1 to þ 2nÀ1 À 1 isimportant because a result outside this range will lead to an overflow and hence awrong result. In simple terms, an overflow will occur if the result produced by a64COMPUTER ARITHMETICgiven operation is outside the range of the representable numbers. Consider the fol-lowing two examples.Example Consider adding the two 2’s complement numbers (þ7) and (þ6). Theaddition can be done as (þ7) þ (þ6) ¼ þ13, that is, 0111 þ (0110) ¼ 1101, awrong result. This is because the result exceeds the largest value (þ7).Example Consider adding the two 2’s complement numbers (27) and (24). Theaddition can be done as (27) þ (24) ¼ 211, that is, 1001 þ (1100) ¼ 0101, awrong result. This is because the result is less than the smallest value (28).Notice that the original numbers are negative while the result is positive.From these two examples, we can make the following observation: when twonumbers (both positive or both negative) are added, then overflow can be detectedif and only if the result has an opposite sign to the added numbers.Subtraction In 2’s complement, subtraction can be performed in the same wayaddition is performed. For example, to perform B À A ¼ B þ A þ 1, that is, sub-tracting A from B is the same as addition to the complement of A to B.Example Consider the subtraction 2 2 7 ¼ 25. This can be performed as2 þ 7¯ þ 1 ¼ 0010 þ 1000 þ 0001 ¼ 1011 (25).It should be noted that our earlier observation about the occurrence of overflow inthe context of addition applies in the case of subtraction as well. This is because sub-traction is after all addition to the complement. Consider the following illustrativeexample.Example Consider the subtraction 7 2 (27) ¼ 14. This can be performed as7 þ 7¯ þ 1 ¼ 0111 þ 1000 þ 0001 ¼ (1) 0000, a wrong answer (result . 7).Hardware Structures for Addition and Subtraction of SignedNumbers The addition of two n-bit numbers A and B requires a basic hardwarecircuit that accepts three inputs, that is, ai, bi, and ciÀ1. These three bits representrespectively the two current bits of the numbers A and B (at position i) and thecarry bit from the previous bit position (at position i 2 1). The circuit should pro-duce two outputs, that is, si and ci representing respectively the sum and thecarry, according to the following truth-table.ai00001111bi00110011ci2101010101si01101001ci000101114.2. INTEGER ARITHMETIC65The output logic functions are given by si ¼ ai È bi È ciÀ1 and ci ¼ aibi þaiciÀ1 þ biciÀ1. The circuit used to implement these two functions is called afull-adder (FA) and is shown in Figure 4.1.Addition of two n-bit numbers A and B can be carried out using n consecutiveFAs in an arrangement known as a carry-ripple through adder (CRT), see Figure 4.2.The n-bit CRT adder shown in Figure 4.2 can be used to add 2’s complementnumbers A and B in which the bnÀ1 and anÀ1 represent the sign bits. The same cir-cuit can be used to perform subtraction using the relation B À A ¼ B þ A þ 1.Figure 4.3 shows the structure of a binary addition/subtraction logic network.In this figure, the two inputs A and B represent the arguments to be added/sub-tracted. The control input determines whether an add or a subtract operation is to beperformed such that if the control input is 0 then an add operation is performed whileif the control input is 1 then a subtract operation is performed. A simple circuit thatcan implement the Add/Sub block in Figure 4.3 is shown in Figure 4.4 for the caseof 4-bit inputs.One of the main drawbacks of the CRT circuit is the expected long delay betweenthe time the inputs are presented to the circuit until the final output is obtained. Thisis because of the dependence of each stage on the carry output produced by the pre-vious stage. This chain of dependence makes the CRT adder’s delay O(n), where n isthe number of stages in the adder. In order to speed up the addition process, it isnecessary to introduce addition circuits in which the chain of dependence amongthe adder stages must be broken. A number of fast addition circuits exist in the lit-erature. Among these the carry-look-ahead (CLA) adder is well known. The CLAadder is introduced below.Consider the CRT adder circuit. The two logic functions realized are si ¼ai È bi È ciÀ1 and ci ¼ aibi þ aiciÀ1 þ biciÀ1. These two functions can be rewrittenin terms of two new subfunctions, the carry generate, Gi ¼ aibi and the carry pro-pagate, Pi ¼ ai È bi. Using these two new subfunctions, we can rewrite the logicequation for the carry output of any stage as ci ¼ Gi þ PiciÀ1. Now, we can writeFigure 4.1The full-adder (FA) circuit66COMPUTER ARITHMETICFigure 4.2n-Bit carry-ripple through (CRT) adderthe series of carry outputs from the different stages as follows.c0 ¼ G0 þ P0cÀ1c1 ¼ G1 þ P1c0 ¼ G1 þ P1(G0 þ P0cÀ1) ¼ G1 þ G0P1 þ P0P1cÀ1c2 ¼ G2 þ P2c1 ¼ G2 þ P2(G1 þ G0P1 þ P0P1cÀ1)¼ G2 þ G0P1P2 þ G1P2 þ P0P1P2cÀ1c3 ¼ G3 þ P3c2 ¼ G3 þ P3(G2 þ G1P2 þ G0P1P2 þ P0P1P2cÀ1)¼ G3 þ G2P3 þ G1P2P3 þ G0P1P2P3 þ P0P1P2P3cÀ1...The sequence of carry outputs shows total independence among the different car-ries (broken carry chain). Figure 4.5 shows the overall architecture of a 4-bit CLAadder. There are basically three blocks in a CLA. The first one is used to generate theGis and the Pis, while the second is used to create all the carry output. The thirdblock is used to generate all the sum outputs. Regardless of the number of bits inthe CLA, the delay through the first block is equivalent to a one gate delay, thedelay through the second block is equivalent to a two gate delay and the delaythrough the third block is equivalent to a one gate delay. In Figure 4.5, we showthe generation of some carry and sum outputs. The reader is encouraged to completethe design (see the Chapter Exercises).BAAdd/SubControl = 0/1CFigure 4.3Addition/subtraction logic network4.2. INTEGER ARITHMETIC67Input Argument AControl = 0/1Figure 4.4The Add/Sub circuitb3 a3b2 a2b1 a1b0 a0PP3G32G2P1GP10G0c- 1AND-ORAND-OR circuit forcircuit forrealizing c3realizing c2c3c2c1c0P3P2P1P0s3s2s1s0Figure 4.5A 4-bit CLA adder structure68COMPUTER ARITHMETICMultiplication In discussing multiplication, we shall assume that the two inputarguments are the multiplier Q given by Q ¼ qnÀ1qnÀ2 Á Á Á q1q0 and the multiplicandM given by M ¼ mnÀ1mmÀ2 Á Á Á m1m0. A number of methods exist for performingmultiplication. Some of these methods are discussed below.The Paper and Pencil Method (for Unsigned Numbers) This is the simplestmethod for performing multiplication of two unsigned numbers. The method is illus-trated through the example shown below.Example Consider the multiplication of the two unsigned numbers 14 and 10.The process is shown below using the binary representation of the two numbers.1110 (14) Multiplicand( M)1010 (10) Multiplier(Q)0000(Partial Product)1110(Partial Product)0000(Partial Product)1110(Partial Product)¼¼¼¼¼¼10001100 (140) Final Product(P)The above multiplication can be performed using an array of cells each consistingof an FA and an AND. Each cell computes a given partial product. Figure 4.6 showsthe basic cell and an example array for a 4Â4 multiplier array.What characterizes this method is the need for adding n partial products regard-less of the values of the multiplier bits. It should be noted that if a given bit of themultiplier is 0, then there should be no need for computing the corresponding partialproduct. The following method makes use of this observation.The Add-Shift Method In this case, multiplication is performed as a series of (n)conditional addition and shift operations such that if the given bit of the multiplier is0 then only a shift operation is performed, while if the given bit of the multiplier is 1then addition of the partial products and a shift operation are performed. The follow-ing example illustrates this method.Example Consider multiplication of the two unsigned numbers 11 and 13. Theprocess is shown below in a tabular form. In this process, A is a 4-bit register andis initialized to 0s and C is the carry bit from the most significant bit position.The process is repeated n ¼ 4 times (the number of bits in the multiplier Q). Ifthe bit of the multiplier is “1”, then A A þ M and the concatenation of AQ isshifted one bit position to the right. If, on the other hand, the bit is “0”, then onlya shift operation is performed on AQ. The structure required to perform such an