6.111 Fall 2004 Lectures 9/10, Slide 1Arithmetic Circuits01011+0010110000Didn’t I learn howto do addition inthe second grade?MIT courses aren’twhat they used tobe...Acknowledgements:• 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 2004 Lectures 9/10, Slide 2• 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 implemented as addition followed by ones complementNumber Systems BasicsHow to represent negative numbers?_6.111 Fall 2004 Lectures 9/10, Slide 32’s Complement20212223…2N-2-2N-1……N bits8-bit 2’s complement example:11010110 = –27+ 26+ 24+ 22+ 21= – 128 + 64 + 16 + 4 + 2 = – 42If we use a two’s-complement representation for signed integers, the same binary addition procedure will work 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“sign bit” “decimal” pointRange: – 2N-1to 2N-1–16.111 Fall 2004 Lectures 9/10, Slide 4Twos Complement Representation Asymmetric range: -2N-1to +2N-1-1 Only one representation for zero Simple addition and subtraction Most common representationTwos complement = bitwise complement + 10111 → 1000 + 1 = 1001 = -71001 → 0110 + 1 = 0111 = 74+ 37010000110111-4+ (-3)-711001101110014-310100110110001-4+ 3-1110000111111[Katz93, chapter 5]6.111 Fall 2004 Lectures 9/10, Slide 5Binary AdditionHere’s an example of binary addition as one might do it by “hand”:1101+ 0101100101011Carries from previous columnAdding 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…6.111 Fall 2004 Lectures 9/10, Slide 6Subtraction: 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 2004 Lectures 9/10, Slide 7Condition 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)111111 −−−+−−−=NSNBNANSNBNAV11−⊕−=NCINNCOUTVV (overflow): indicates that the answer has too many bits to be represented correctly by the result width, e.g., “(2N-1 - 1)+ (2N-1-1)”Z (zero): result is = 0 big NOR gateN (negative): result is < 0 SN-1C (carry): indicates that add in the most significant position produced a carry, e.g.,“1 + (-1)”from last FA6.111 Fall 2004 Lectures 9/10, Slide 8tPDof Ripple-carry AdderWorse-case path: carry propagation from LSB to MSB, e.g., when adding 11…111 to 00…001.tPD= (N-1)*(tPD,OR+ tPD,AND) + tPD,XOR≈ Θ(N)CI to COCIN-1to SN-1Θ(N) is read “order N” and tells us that the latency of our adder grows proportional to the number of bits in the operands.6.111 Fall 2004 Lectures 9/10, Slide 9Faster 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 propagateFor adding two N-bit numbers:CN= GN-1+ PN-1CN-1= GN-1+ PN-1 GN-2+ PN-1 PN-2CN-2= GN-1+ PN-1 GN-2+ PN-1 PN-2GN-3 + … + PN-1 ...P0CINActually, P is usuallydefined as P = A⊕Bwhich won’t changeCOUTbut will allow usto express S as asimple function ofP and CIN: S = P ⊕CINActually, P is usuallydefined as P = A⊕Bwhich won’t changeCOUTbut will allow usto express S as asimple function ofP and CIN: S = P ⊕CINCNin only 3 (!) gate delays:1 for P/G generation, 1 for ANDs, 1 for final OR6.111 Fall 2004 Lectures 9/10, Slide 10Carry Bypass AdderFAP,GCi,0P0G0A0B0Co,0FAP,GP1G1A1B1Co,1FAP,GP2G2A2B2Co,2FAP,GP3G3A3B3Co,3Can compute P, G in parallel for all bitsFAP,GCi,0P0G0Co,0FAP,GP1G1Co,1FAP,GP2G2Co,2FAP,GP3G301BP= P0P1P2P3Co,3Key Idea: if (P0P1P2P3) then Co,3= Ci,06.111 Fall 2004 Lectures 9/10, Slide 1116-bit Carry Bypass AdderFAP,GCi,0Co,0FAP,GFAP,GFAP,G01BP= P0P1P2P3Co,1Co,2FAP,GCo,4FAP,GFAP,GFAP,G01BP= P4P5P6P7Co,5Co,6Co,7FAP,GCo,8FAP,GFAP,GFAP,G01BP= P8P9P10P11Co,9Co,10FAP,GCo,11Co,12FAP,GFAP,GFAP,G01BP= P12P13P14P15Co,13Co,14Co,15Assume 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 unitCo,3What is the worst case propagation delay for the 16-bit adder?6.111 Fall 2004 Lectures 9/10, Slide 12Critical Path AnalysisFAP,GCi,0Co,0FAP,GFAP,GFAP,G01BP= P0P1P2P3Co,1Co,2FAP,GCo,4FAP,GFAP,GFAP,G01BP2= P4P5P6P7Co,5Co,6Co,7FAP,GCo,8FAP,GFAP,GFAP,G01BP3= P8P9P10P11Co,9Co,10FAP,GCo,11Co,12FAP,GFAP,GFAP,G01BP4= P12P13P14P15Co,13Co,14Co,15Co,3For the second stage, is the critical path:BP2 = 0 or BP2 = 1? Message: Timing Analysis is Very Tricky –Must Carefully Consider Data Dependencies For False Paths6.111 Fall 2004 Lectures 9/10, Slide 13Carry-lookahead Adders (CLA)We can choose the maximum fan-in we want for our logic gates and then build a hierarchical carry chain using these equations:CJ+1= GIJ+ PIJCIGIK = GJ+1,K+ PJ+1,K GIJPIK= PIJ PJ+1,K where I < J and J+1 < K“generate a carry from bits I thruK if it is generated in the high-order(J+1,K) part of the block or if it isgenerated in the low-order (I,J) partof the block and then propagatedthru the high part”Hierarchical building blockP/G generation1stlevel oflookahead6.111 Fall 2004 Lectures 9/10, Slide 148-bit CLA (P/G generation)From Hennessy & Patterson, Appendix A Log2(N)6.111 Fall
View Full Document
Unlocking...