計(jì)算機(jī)組成與結(jié)構(gòu)體系英文課件：Chapter9 – Arithmetic

1、Computer Organization & Architecture Chapter 9 ArithmeticContent of this lecturen1.4 Integer Representationn9.1 Addition and Subtraction of Signed Numbersn9.2 Design of Fast Addersn9.3 Multiplication of Unsigned Numbersn9.4 Multiplication of Signed Numbersn9.6 Integer Divisionn9.7 Floating-point Num

2、bers and Operationn9.10 Solved ProblemsnSummaryInteger Representation (1)nUnsigned RepresentationImplies that the representation does not have a separate bit to represent the sign bit of the number.Note that numbers can be either positive or negative in some unsigned representation.nUnsigned Integer

3、Unsigned Non-Negative RepresentationUnsigned Twos Complement RepresentationInteger Representation (2)nUnsigned Non-Negative RepresentationTreats every number as either zero or a positive value. This representation can only represent non-negative numbers.A n-bit number can have a value ranging from 0

4、 to 2n-1.Example: An 8-bit word could be used to represent the numbers from 0 to 255n10000000 = 128n11111111 = 255Integer Representation (3)nUnsigned Twos Complement RepresentationThis representation can represent both positive and negative numbers. A positive number (or zero) is represented exactly

5、 the same as in non-negative representation. A negative number is represented as the bitwise complement of its absolute value +1.Integer Representation (4)nUnsigned Twos Complement Representation (ctd.)Bitwise Complement (Ones Complement)nTake the Boolean complement of each bit of the number. That i

6、s , set each 1 to 0 and each 0 to 1.Example 5 10n5 10= 0101 2nBitwise complement of 0101 is 1010n1010 + 1 = 1011 Integer Representation (5)nUnsigned Twos Complement Representation (ctd.)Positive numbers (and zero) have a 0 as the leading bit and negative numbers have a 1 as the most significant bitA

7、 n-bit number can have a value ranging from -2n 1 to 2n 1 1.Integer Representation (6)nSigned IntegerSign and Magnitude RepresentationSigned Twos Complement RepresentationSigned Ones Complement RepresentationnSign and Magnitude RepresentationRulenThe sign part is a 1-bit value that is 0 for positive

8、 numbers, and 1 for negative numbers.nThe magnitude part is an n-bit value that holds the absolute value of the number in the same format of unsigned non-negative numbers.Integer Representation (7)nSign and Magnitude Representation (ctd.)B = bnb1b0nbn = 0, B is a positive number.nbn= 1, B is a negat

9、ive number.Examplen+18 10 = 00010010n18 10 = 10010010n+ 0 10 = 00000000n 0 10 = 10000000bnb1b0SignMagnitudeInteger Representation (8)nSigned and Magnitude Representation (ctd.)In general, if an (n+1)-bit sequence of binary digits bnbn-1b1b0 is interpreted as an signed integer B, its value isn(2n1) V

10、 (B) 2n1V (B) =if bn = 1if bn = 0iniib102iniib102Integer Representation (9)nSign and Magnitude Representation (ctd.)DrawbacksnAddition and subtraction require a consideration of both the signs of the numbers and their relative magnitudes to carry out the required operation.nThere are two representat

11、ions of 0 . 0 = 000000000 = 10000000Integer Representation (10)nSigned Twos Complement Representation RulenThe sign part is a 1-bit value that is 0 for positive numbers, and 1 for negative numbers. nThe magnitude part is an n-bit value that is equivalent to a unsigned twos complement number. Example

12、n+18 = 00010010n18 = 11101110n+ 0 = 00000000n0 = 00000000Integer Representation (11)nSigned Twos Complement Representation (ctd.) The general case B= bnbn-1b1b0n2n V (B) 2n1V (B) =iniinnbb1022iniib102iniinnbb1022=B 0B 0(for both positive and negative numbers)Integer Representation (12)nSigned Ones C

13、omplement Representation RulenThe sign part is a 1-bit value that is 0 for positive numbers, and 1 for negative numbers. nThe magnitude part is an n-bit value that complementing each bit of the absolute of the integer. Examplen+18 = 00010010n18 = 11101101n+ 0 = 00000000n0 = 111111110000 0001+1+(2n-1

14、(2n-1)1110000 0001+1+(2n-1(2n-1)10000000001+1+(2n-1)011-1111-(2n-1)1001-2n100sign and magnitude signed ones complement signed twos complement Integer Representation (13)nConclusionsIn all three systems, the leftmost bit is 0 for positive numbers and 1 for negative numbers

15、.Positive values have identical representations in all systems, but negative values have different representations. The 2s-complement of a number is obtained by adding 1 to the 1s-complement of that number. The Sign and Magnitude system is the simplest representation, but it is also the most awkward

16、 for addition and subtraction operations.The 2s-complement system is the most efficient method for performing addition and subtraction operations.Integer Representation (14)nConverting between Different Bit LengthsSign and Magnitude NumbersnMove the sign bit to the new left-most position and fill in

17、 with zeros.nExample18 = 00010010 ( 8 bits)18 = 0000000000010010 (16 bits)18 = 10010010 ( 8 bits)18 = 1000000000010010 (16 bits)Integer Representation (15)nConverting between Different Bit Lengths (ctd.)Signed Twos Complement NumbersnExample18 = 00010010 ( 8 bits)18 = 0000000000010010 (16 bits)18 =

18、11101110 ( 8 bits)32568 = 1000000001101110 (16 bits)nSign ExtensionMove the sign bit to the new left-most position and fill in with copies of the sign bit. For positive numbers, fill in with zeros, and for negative numbers, fill in with ones.Integer Representation (16)nConverting between Different B

19、it Lengths (ctd.)Example18 = 11101110 ( 8 bits)18 = 1111111111101110 (16 bits)Addition and Subtraction of Signed Numbers (1)nAddition of 1-bit Positive Numbers 0+ 0 0 1+ 0 1 0+ 1 1 1+ 1 1 0Carry-outAddition and Subtraction of Signed Numbers (2)nAddition of n-bit Signed NumbersRule1 (In Signed Twos C

20、omplement Form)nTo add two numbers, add their n-bit representations, treating the sign bit as the most significant bit (MSB), ignoring the carry-out signal from the MSB position.nThe sum will be algebraically correct value in the twos-complement representation as long as the answer is in the range 2

21、n 1 through +2n 11.Addition and Subtraction of Signed Numbers (3)nAddition of n-bit Signed Numbers (ctd.)ExamplenTextbook P14(a)-(d) n(+5) + (+4)n(-6) + (-7) 0 1 0 1+0 1 0 0 1 0 0 1 1 0 0 1+1 0 1 01 0 0 1 1overflowoverflowAddition and Subtraction of Signed Numbers (4)nAddition of n-bit Signed Number

22、s (ctd.)Arithmetic OverflownThe result of an arithmetic operation is outside the representable range.nIf two numbers are added, and they have the same sign, then overflow occurs if and only if the result has the opposite sign to both summands.nThe carry-out signal from the sign-bit position is not a

23、 sufficient indicator of overflow when adding signed numbers. Overflow can occur whether or not there is a carry-out.Addition and Subtraction of Signed Numbers (5)nSubtraction of n-bit Signed NumbersRule2 (In Signed Twos Complement Form)nTo subtract two numbers X and Y, that is, to perform XY, form

24、the 2s-complement of Y and then add it to X, as in rule1. nThe result will be the algebraically correct value in the twos-complement representation system if the answer is in the range 2n-1 through +2n 11.nEssence of Rule2 XY= X + (Y)Addition and Subtraction of Signed Numbers (6)nSubtraction of n-bi

25、t Signed Numbers (ctd.)Twos Complement Operation (Negation)nTake the boolean complement of each bit of the integer (including the sign bit). That is ,set each 1 to 0 and each 0 to 1.nTreating the result as an unsigned binary integer, add 1.ExamplenTextbook P14 (e)-(j)Addition and Subtraction of Sign

26、ed Numbers (7)nSubtraction of n-bit Signed Numbers (ctd.)Example (ctd.)nM = 7, S = -7 , M S = ?M = 7 = 0111S = -7 = 1001- S = 0111 0 1 1 1+0 1 1 1 1 1 1 0overflowAddition and Subtraction of Signed Numbers (8)nSubtraction of n-bit Signed Numbers (ctd.)ConclusionsnThe examples in Figure 1.6 (P14) show

27、 that two, n-bit, signed numbers can be added using n-bit binary addition, treating the sign bit the same as the other bit.nIn other words, a logic circuit that is designed to add unsigned binary numbers can also be used to add signed numbers in 2s-complement.Addition and Subtraction of Signed Numbe

28、rs (9)n1-bit Full AdderExample: X= 7, Y=6, X+Y = ? X+ Y 7+ 6 0 1 1 1+ 0 0 1 1 1 1 0 0 0 1 1 0 1 Z = 13 =Addition and Subtraction of Signed Numbers (10)n1-bit Full AdderFull AddernA full adder circuit takes three bits of input, and produces a two-bit output consisting of a sum and a carry out.Full Ad

29、der(FA)xiyicisixiyicici+1sici+1Addition and Subtraction of Signed Numbers (11)n1-bit Full Adder (ctd.)Logic Truth Tablexiyicisici+10000000110010100110110010101011100111111Addition and Subtraction of Signed Numbers (12)n1-bit Full Adder (ctd.)Logic Expressionsis=iiicyx+iiicyx+iiicyxiiicyx+=iiicyx1ic=

30、iicy+iicx+iiyxxcyiiisiciyixiciyixici1+Addition and Subtraction of Signed Numbers (13)nn-bit Ripple-Carry Adder FA FA FA c1 c0 cn-1 cn y0 x0 x1 y1 yn-1 xn-1 s1 sn-1 Least significant bit (LSB) position Most significant bit (MSB) position s0 Addition and Subtraction of Signed Numbers (14)nn-bit Ripple

31、-Carry Adder (ctd.)Overflow Detectxn-1yn-1sn-1Overflow00000011010001101000101011011110Addition and Subtraction of Signed Numbers (15)nn-bit Ripple-Carry Adder (ctd.)Overflow Detect (ctd.)nOverflow =nOr overflow = nGate DelaysEvery gate takes some small fraction of a second between the time inputs ar

32、e presented and the time the correct answer appears on the outputs. This little fraction of a second is called a gate delay.111nnnsyx+111nnnsyx1nnccAddition and Subtraction of Signed Numbers (16)nGate Delays (ctd.)There are actually detailed ways of calculating gate delays that can get quite complic

33、ated, but for this class, lets just assume that theres some small constant delay thats the same for all gates.We can use a timing diagram to show gate delays graphically.xx10gate delaysAddition and Subtraction of Signed Numbers (17)nDelays in the Ripple Carry AdderThe delay through a network of logi

34、c gates depends on the integrated circuit electronic technology used in fabricating the network and on the number of gates in the paths from inputs to outputs.The delay through any combinational logic network constructed from gates in a particular technology is determined by adding up the number of

35、logic-gate delays along the longest signal propagation path through the network.In the case of the n-bit ripple-carry adder, the longest path is from inputs x0,y0 and c0 at the LSB position to outputs cn and sn-1 at the MSB position.Addition and Subtraction of Signed Numbers (18)nDelays in the Rippl

36、e Carry Adder (ctd.)Assume that the gate delay of an AND gate or an OR gate or a XOR gate is T.Full adder(FA)ciyixici1+si(a) Logic for a single stageciyixiciyixixiciyisici1+ci+12TsiTAddition and Subtraction of Signed Numbers (19)nDelays in the Ripple Carry Adder (ctd.) FA FA FA c1 c0 cn-1 cn y0 x0 x

37、1 y1 yn-1 xn-1 s1 sn-1 Least significant bit (LSB) position Most significant bit (MSB) position s0 cn-1 2(n-1)Tsn-1 2(n-1)T+T=(2n-1)Tcn 2(n-1)T+2T=(2n)TAddition and Subtraction of Signed Numbers (20)nHierarchical Adder Design kn-bit addern-bit addercnc0ckny0 x0 xnynykn-1xkn-1s0sn-1skn-1s(k-1)nn-bit

38、addern-bit addersns2n-1x2n-1xn-1y2n-1yn-1Addition and Subtraction of Signed Numbers (21)nAddition/Subtraction Logic UnitControl=0 c0=0Perform additionControl=1 c0=1Perform subtractionAA 0AA 1Addition and Subtraction of Signed Numbers (22)nAddition/Subtraction Logic Unit (ctd.)An XOR gate can be adde

39、d to detect the overflow.All sum bits are available in 2n gate delays, including the delay through the XOR gate on the Y input.Design of Fast Adders (1)nDrawback of n-bit ripple-carry adderIt may have too much delay in developing its outputs, s0 through sn-1 and cn.nsn-1 (2n-1)T ncn (2n)TSolutionsnU

40、se the fastest possible electronic technology in implementing the ripple-carry logic design or variations of it.nUse an augmented logic gate network structureDesign of Fast Adders (2)nCarry-Lookahead Additionis=iiicyx1ic=iicy+iicx+iiyx=iiyx+iiicyx)(iiiyxG iiiyxP(generate function for stage i)(propag

41、ate function for stage i)1ic=iiicPG Design of Fast Adders (3)nCarry-Lookahead Addition (ctd.)iiiyxPiiiyxPxiyixi+yixi yi00000111101111101ic=iiicPG iicP1=11ix1iyifandDesign of Fast Adders (4)nCarry-Lookahead Addition (ctd.)A simpler circuit of bit stageDesign of Fast Adders (5)nCarry-Lookahead Additio

42、n (ctd.)(111iiiiicPGPG111iiiiiicPPGPG001011211.cPPPGPPPGPPGPGiiiiiiiiiiis=iiicyx1ic=iiicPG Design of Fast Adders (6)nCarry-Lookahead Addition (ctd.)Delays of n-bit CLAnAll carries can be obtained 3 gate delays after the input signal X, Y and c0 are applied.nAll sum bits are available 4 gate delays a

43、fter the input signal X, Y and c0 are applied.CLA SummarynProvide supplemental logic circuits that form a carry signal into each adder stageTo accelerate the propagation of carriesCarry propagation becomes concurrent instead of sequentialDesign of Fast Adders (7)n4-bit Carry-Lookahead Adder1c=000cPG

44、 2c=001011cPPGPG3c=0012012122cPPPGPPGPG4c=001230123123233cPPPPGPPPGPPGPGis=iiicyx3 , 2 , 1 , 0i B cell Carry-lookahead Logic B cell B cell B cell c0 c1 c2 c3 c4 x3 y3 x2 y2 x1 y1x0 y0 s3 s2 s1 s0 G3 P3 G2 P2 G1 P1 P0 G0 P0I G0I 4-bit carry-lookahead adderDesign of Fast Adders (8)Design of Fast Adder

45、s (9)n4-bit Carry-Lookahead Adder (ctd.)Delay Comparisonn4-bit CLA 3T 4Tn4-bit ripple carry adder 8T 7T1c2c3c4c1s2s3s4c3sDesign of Fast Adders (10)nExtension to Longer AddersThe 4-bit ripple-carry adder design cannot be directly extended to longer operand sizes. B cell Carry-lookahead Logic B cell B

46、 cell c0 c1 cn-1 cn xn-1 yn-1 x1 y1x0 y0 sn-1 s1 s0 Gn-1 Pn-1 G1 P1 P0 G0 P0I G0I Design of Fast Adders (11)nExtension to Longer Adders(ctd.)Fan-In ConstraintsnFan-InThe number of inputs to a logic gate is called its fan-in.nFan-OutThe number of gate inputs that the output of a logic gate drives is

47、called its fan-out.nPractical circuits do not allow large fan-in and fan-out because they both have an adverse effect on the propagation delay and hence the speed of the circuit.nExample: Fan-In of the last AND gate is i + 2001011211.cPPPGPPPGPPGPGiiiiiiiiii1icDesign of Fast Adders (12)nExtension to

48、 Longer Adders(ctd.)Build 32-bit Adders with 4-bit Adders nCascade of 8 4-bit Carry-Lookahead Addersc32c04-bit adderc4y0 x0 x4y4y31x31s0s3s31s284-bit adder4-bit adders4s7x7x3y7y3y28x28c28Design of Fast Adders (13)nExtension to Longer Adders(ctd.)Build 32-bit Adders with 4-bit Adders (ctd.)nCascade o

49、f 8 4-bit Carry-Lookahead Adders (ctd.)Calculate the delays in generating sum bits s28 , s29 , s30 s31, and c32 in the high-order 4-bit adder.3T4c8c3T+2T=5T12c5T+2T29c(62)T+3T=15T28c30c31c32c15T+2T=17T28s29s30s31s17T+T=18TMultiplication of Unsigned Numbers (1)nManual Multiplication Algorithm (unsign

50、ed & positive signed)Example: M= 1101, Q= 1011, calculate P= MQ 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 Multiplicand Multiplier Product Partial ProductsMultiplication of Unsigned Numbers (2)nManual Multiplication Algorithm (unsigned & positive signed) (ctd.)Multiplication of

51、the multiplicand by one bit of the multipliernIf 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 0s are entered.NotenThe multiplication product of two n-bit binary integers results in a product of u

52、p to 2n bits in length.Multiplication of Unsigned Numbers (3)nArray MultiplierM = m3m2m1m0 Q = q3q2q1q0 P = MQ = p7p6p5p4p3p2p1p0 m3 m2 m1 m0 q3 q2 q1 q0 m3q0 m2q0 m1q0 m0q0 m3q1 m2q1 m1q1 m0q1m3q2 m2q2 m1q2 m0q2m3q3 m2q3 m1q3 m0q3p0p1p2p3p4p5p6p7 0 0 0 0 m3 m2 m1 m0 Multiplicand Partial product PP0

53、 q0 0 p0 q1 0 q2 p1 q3 p2 0 0 p3 p4 p5 p6 p7 PP1 PP3 PP2 Multiplier PP4 = p7p6p0=Product FA Carry-in Carry-out Bit of incoming partial product (PPi) mj Bit of outgoing partial product PP(i+1) qi Multiplication of Unsigned Numbers (4)nArray Multiplier (ctd.)Q: When calculating P = M Q (M and Q are al

54、l n bit unsigned binary numbers) , how many FAs and AND gates do we need (using n n array multiplier)?A: FAs : n(n-1) AND gates : n2n= 32, 992 FAs, 1024 AND gatesn= 64, 4032 FAs, 4096 AND gatesMultiplication of Unsigned Numbers (5)nSequential Circuit Multiplier C an-1 a0 qn-1 q0 n-bit adderr mn-1 m0

55、 MUX Control Sequencer Shift right Multiplier Q Multiplicand M Register A(initially 0) Add/Noadd control 0 0 StartC, A=0M=MultiplicandQ=MultiplierCount=nShift C, A, QCount= Count 1Q0=1?C, A= A+MCount=0?EndYesYesNoNo1 1 0 1 1 0 1 1 0 0 0 0 0 M C 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 0

56、 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 A Q 0 1 0 0 0 1 1 1 1 First CycleSecond CycleThird CycleFourth CycleInitial ConfigurationExample:M= 1101, Q= 1011, calculate P= MQAddShiftAddShiftNo addShiftAddShiftMultiplication of Signed Numbers (1)nHow do we handle signed num

57、bers ?Convert to unsigned, multiply, then convert back to signednWorks but is slow and a bit cumbersomeDirectly handle the multiplication with the signed numbersnBooth algorithm recodes the bits to allow for such a computation.nWorks with 2s complement numbers directlySigned-Operand Multiplication (

58、2)nIf the multiplier is negative, how should we do multiplication straightly?Straightforward multiplication will not work in the case of a positive multiplier and a negative multiplicand.nExample: M = 1001, Q = 0011, calculate P = MQP = 00011011If M, Q, and P are unsigned non-negative numbers, then:

59、 M = 9, Q = 3, P=27If M, Q, and P are signed 2s complement numbers, then: M = -7, Q = 3, P = 27Signed-Operand Multiplication (3)nIf the multiplier is negative, how should we do multiplication straightly? (ctd.)Case 1: a positive multiplier and a negative multiplicand (ctd.)nExample: M = 1001, Q =001

60、1, calculate P = MQ 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 = - 21Signed-Operand Multiplication (4)nIf the multiplier is negative, how should we do multiplication straightly? (ctd.)Case 2: a negative multiplier and a negative multiplicand nExample: M = 110