L8/9: 6.111 Spring 2005 1Introductory Digital Systems LaboratoryL8/9: Arithmetic Structures L8/9: Arithmetic Structures Acknowledgements:R. Katz, G. Borriello, “Contemporary Logic Design” (second edition), Prentice-Hall/Pearson Education, 2005. J. Rabaey, A. Chandrakasan, B. Nikolic, “Digital Integrated Circuits: A Design Perspective” Prentice Hall, 2003.Kevin Atkinson, Alice Wang, Rex MinL8/9: 6.111 Spring 2005 2Introductory Digital Systems Laboratory Three common schemes: sign-magnitude, ones complement, twos complement Sign-magnitude: MSB = 0 for positive, 1 for negativeRange: -(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 NExample: 0111 = 7, 1000 = -7Range: -(2N-1– 1) to +(2N-1–1)Two representations for zero: 0000… & 1111…Subtraction implemented as addition and negationNumber Systems BasicsNumber Systems BasicsHow to represent negative numbers?_L8/9: 6.111 Spring 2005 3Introductory Digital Systems LaboratoryTwos Complement RepresentationTwos 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[Katz05]L8/9: 6.111 Spring 2005 4Introductory Digital Systems LaboratoryOverflow ConditionsOverflow ConditionsAdd two positive numbers to get a negative number or two negative numbers to get a positive number5 + 3 = -8!-7 - 2 = +7!0000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-10000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-153-80 1 1 10 1 0 10 0 1 10 1 0 0 0-7-27100 01 0 0 11 1 0 01 0 1 1 1If carry in to sign equals carry out then can ignore carry out, otherwise have overflowL8/9: 6.111 Spring 2005 5Introductory Digital Systems LaboratoryBinary Full AdderBinary Full AdderFull AdderABCoSCiS = A ⊕ B ⊕ Ci= ABCi+ ABCi+ ABCi+ ABCiCo= AB + Ci(A+B)A 0 0 0 0 1 1 1 1B 0 0 1 1 0 0 1 1CI 0 1 0 1 0 1 0 1S 0 1 1 0 1 0 0 1CO 0 0 0 1 0 1 1 1A BCI0100 01 11 1001101001A BCI0100 01 11 1000010111SCOL8/9: 6.111 Spring 2005 6Introductory Digital Systems LaboratoryRipple Carry Adder StructureRipple Carry Adder StructureFull AdderA0B0S0Ci,0Full AdderA1B1S1Full AdderA2B2S2Full AdderA3B3S3Co,3Co,2Co,1Co,0Worst case propagation delay linear with the number of bitstadder= (N-1)tcarry+ tsumL8/9: 6.111 Spring 2005 7Introductory Digital Systems LaboratoryExtension to SubtractionExtension to Subtraction¾Under twos complement, subtracting B is the same as adding the bitwise complement of B then adding 1Add 1 for subtraction using carry inCombination addition/subtraction system:mux selects B for addition, B for subtraction_Overflow occurs if carry in to sign bit differs from final carry outoverflowFAAdd/SubtractB3B3A3FAB2B2A2FAB1B1A1FAB0B0A0Co,2Co,1Co,0S3S2S1S00 10 10 10 1Co,3L8/9: 6.111 Spring 2005 8Introductory Digital Systems LaboratoryComparator (one approach)Comparator (one approach)A < B = N A = B = ZA ≤ B = Z + N true if negative resulttrue if zero resultNZFA1B3B3A3FAB2B2A2FAB1B1A1FAB0B0A0Co,2Co,1Co,0S3S2S1S00 10 10 10 1Co,3L8/9: 6.111 Spring 2005 9Introductory Digital Systems LaboratoryAlternate Adder Logic FormulationAlternate Adder Logic FormulationFull AdderABSCoCinGenerate (G) = ABPropagate (P) = A ⊕BHow to Speed up the Critical (Carry) Path?(How to Build a Fast Adder?) Note: can also use P = A + B for CoL8/9: 6.111 Spring 2005 10Introductory Digital Systems LaboratoryCarry Bypass AdderCarry 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,0L8/9: 6.111 Spring 2005 11Introductory Digital Systems Laboratory1616--bit Carry Bypass Adderbit 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?L8/9: 6.111 Spring 2005 12Introductory Digital Systems LaboratoryCritical Path AnalysisCritical 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 PathsL8/9: 6.111 Spring 2005 13Introductory Digital Systems LaboratoryCarry Carry LookaheadLookaheadAdderAdderRe-express the carry logic as follows:C1 = G0 + P0 C0C2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0 Each of the carry equations can be implemented in a two-level logic networkVariables are the adder inputs and carry in to stage 0Ripple effect has been eliminated!…L8/9: 6.111 Spring 2005 14Introductory Digital Systems LaboratoryCarry Carry LookaheadLookaheadLogicLogicPiCiSiBiAiGiC0C0C0C0P0P0P0P0G0G0G0G0C1P1P1P1P1P1P1G1G1G1C2P2P2P2P2P2P2G2G2C3P3P3P3P3G3C4Adder with propagate and generate outputsLater stages have increasingly complex logicL8/9: 6.111 Spring 2005 15Introductory Digital Systems LaboratoryBlock Generate and PropagateBlock Generate and PropagateGi:jand Pi:jdenote the Generate and Propagate functions, respectively, for a group of bitsfrom positions i to j. We call them Block Generate and Block Propagate. Gi:jequals 1 if the group generates a carry independent of the incoming carry. Pi:jequals 1 if an incoming carry propagates through the entire group. For example, G3:2is equal to 1 if a carry is generated at bit position 3, or if a carry out is generated at bit position 2 and propagates through position 3. G3:2= G3+ P3G2. P3:2is true if an
View Full Document
Unlocking...