6.111 Lecture 12Arithmetic Circuits1. Binary Representation of NumbersNegative Numbers: Twos ComplementTwos Complement: Examples & Properties2. Binary Addition & SubtractionSubtraction: A-B = A + (-B)Condition Codes3. Speed: tPD of Ripple-carry AdderFaster carry logic4. Carry Bypass Adder16-bit Carry Bypass AdderCritical Path AnalysisCarry Bypass vs Ripple Carry5. Carry Lookahead Adder (CLA)Carry Lookahead CircuitsThe 74182 Carry Lookahead UnitBlock Generate and Propagate8-bit CLA (P/G generation)8-bit CLA (carry generation)8-bit CLA (complete)Summary6.111 Fall 2005 Lecture 12, Slide 16.111 Lecture 12Today: Arithmetic: Addition & Subtraction1.Binary representation2.Addition and subtraction3.Speed: Ripple-Carry4.Carry-bypass adder5.Carry-lookahead adderAcknowledgements:• R. Katz, “Contemporary Logic Design”, Addison Wesley Publishing Company, Reading, MA, 1993. (Chapter 5)• J. Rabaey, A. Chandrakasan, B. Nikolic, “Digital Integrated Circuits: A Design Perspective” Prentice Hall, 2003.• Kevin Atkinson, Alice Wang, Rex Min6.111 Fall 2005 Lecture 12, Slide 2Arithmetic Circuits01011+0010110000Didn’t I learn howto do addition inthe second grade?MIT courses aren’twhat they used tobe...6.111 Fall 2005 Lecture 12, Slide 31. Binary Representation of NumbersHow to represent negative numbers?• Three common schemes: – sign-magnitude, ones complement, twos complement• Sign-magnitude: MSB = 0 for positive, 1 for negative– Range: -(2N-1 –1) to +(2N-1–1)– Two representations for zero: 0000… & 1000…– Simple multiplication but complicated addition/subtraction_• Ones complement: if N is positive then its negative is N– Example: 0111 = 7, 1000 = -7– Range: -(2N-1– 1) to +(2N-1–1)– Two representations for zero: 0000… & 1111…– Subtraction is addition followed by ones complement6.111 Fall 2005 Lecture 12, Slide 4Negative Numbers: Twos ComplementTwos complement = bitwise complement + 10111 → 1000 + 1 = 1001 = -71001 → 0110 + 1 = 0111 = +7 Asymmetric range Only one representation for zero Simple addition and subtraction Most common representation20212223…2N-2-2N-1……N bits“sign bit” “decimal” pointRange: – 2N-1to 2N-1–16.111 Fall 2005 Lecture 12, Slide 5Twos Complement: Examples & Properties• 4-bit examples:-4+ (-3)-71100110111001-4+ 3-11100001111110100001101114+ 37410100110110001-3•8-bit twos complement example:11010110 = –27+ 26+ 24+ 22+ 21= – 128 + 64 + 16 + 4 + 2 = – 42•With twos complement representation for signed integers, the same binary addition procedure works for adding both signed and unsigned numbers.•By moving the implicit location of “decimal” point, we can represent fractions too:1101.0110 = –23+ 22+ 20+ 2-2+ 2-3= – 8 + 4 + 1 + 0.25 + 0.125 = – 2.25[ Katz’93, chapter 5 ]6.111 Fall 2005 Lecture 12, Slide 62. Binary Addition & SubtractionAddition:Here’s an example of binary addition as one might do it by “hand”:1101+ 0101100101011Adding two N-bit numbers produces an (N+1)-bit resultWe’ve already built the circuit that implements one column:So we can quickly build a circuit two add two 4-bit numbers…“Ripple-carry adder”Carries from previous column6.111 Fall 2005 Lecture 12, Slide 7Subtraction: A-B = A + (-B)Using 2’s complement representation: –B = ~B + 1~ = bit-wise complementSo let’s build an arithmetic unit that does both addition and subtraction. Operation selected by control input:But what about the “+1”?6.111 Fall 2005 Lecture 12, Slide 8Condition CodesBesides the sum, one often wants four other bits of information from an arithmetic unit:To compare A and B,perform A–B and usecondition codes:Signed comparison:LT N⊕VLE Z+(N⊕V)EQ ZNE ~ZGE ~(N⊕V)GT ~(Z+(N⊕V))Unsigned comparison:LTU CLEU C+ZGEU ~CGTU ~(C+Z)To compare A and B,perform A–B and usecondition codes:Signed comparison:LT N⊕VLE Z+(N⊕V)EQ ZNE ~ZGE ~(N⊕V)GT ~(Z+(N⊕V))Unsigned comparison:LTU CLEU C+ZGEU ~CGTU ~(C+Z)Z (zero): result is = 0 big NOR gateN (negative): result is < 0 SN-1C (carry): indicates an add in the most significant position produced a carry, e.g., 1111 + 0001 from last FA11−⊕−=NCINNCOUTVV (overflow): indicates that the answer has too many bits to be represented correctly by the result width, e.g., 0111 + 0111111111−−−+−−−=NSNBNANSNBNAV6.111 Fall 2005 Lecture 12, Slide 93. Speed: tPDof Ripple-carry AdderWorse-case path: carry propagation from LSB to MSB, e.g., when adding 11…111 to 00…001.CI to CO CIN-1to SN-1Θ(N) is read “order N” : means that the latency of our adder grows at worst in proportion to the number of bits in the operands.tPD= (N-1)*(tPD,OR+tPD,AND) + tPD,XOR ≈ Θ(N)6.111 Fall 2005 Lecture 12, Slide 10Faster carry logicLet’s see if we can improve the speed by rewriting the equations for COUT:COUT= AB + ACIN+ BCIN= AB + (A + B)CIN= G + P CINwhere G = AB and P = A + Bgenerate propagateActually, P is usuallydefined as P = A⊕Bwhich won’t changeCOUTbut will allow usto express S as asimple function :S = P ⊕CINActually, P is usuallydefined as P = A⊕Bwhich won’t changeCOUTbut will allow usto express S as asimple function :S = P ⊕CIN6.111 Fall 2005 Lecture 12, Slide 114. Carry Bypass AdderFAP,GCi,0A0B0P0G0Co,0FAP,GA1B1P1G1Co,1FAP,GA2B2P2G2Co,2FAP,GA3B3Can compute P, G in parallel for all bitsP3G3Co,3FAP,GCi,0P0G0Co,0FAP,GP1G1Co,1FAP,GP2G2Co,2FAP,GP3G301BP= P0P1P2P3Co,3Key Idea: if (P0P1P2P3) then Co,3= Ci,06.111 Fall 2005 Lecture 12, Slide 1216-bit Carry Bypass AdderFACi,0Co,0FA FAFA01Co,1Co,2FACo,4FA FAFA 01Co,5Co,6Co,3P,GP,G P,GP,GBP= P0P1P2P3P,GP,G P,GP,GBP= P4P5P6P7Co,7FACo,8FA FAFA 01Co,9Co,10FACo,11Co,12FA FAFA01Co,13Co,14P,GP,G P,GP,GBP= P8P9P10P11BP= P12P13P14P15P,GP,G P,GP,GCo,15What is the worst case propagation delay for the 16-bit adder? Assume the following for delay each gate:P, G from A, B: 1 delay unitP, G, Cito Coor Sum for a FA: 1 delay unit2:1 mux delay: 1 delay unit6.111 Fall 2005 Lecture 12, Slide 13Critical Path AnalysisFAP,GCi,0Co,0FAP,GFAP,GFAP,G01BP= P0P1P2P3Co,1Co,2FACo,4FA FAFA 01Co,5Co,6Co,7FACo,8FA FAFA 01Co,9Co,10FACo,11Co,12FA FAFA01Co,13Co,14Co,3BP2= P4P5P6P7BP3= P8P9P10P11BP4= P12P13P14P15P,G P,GP,GP,GP,G P,GP,GP,GP,G P,GP,GP,GCo,15For the second stage, is the critical path:BP2 = 0BP2 = 0 or BP2 = 1BP2 = 1 ? Message: Timing Analysis is Very Tricky –Must Carefully Consider Data Dependencies For False Paths6.111 Fall 2005 Lecture 12,
View Full Document