L8/9: Arithmetic StructuresNumber Systems BasicsTwos Complement RepresentationOverflow ConditionsBinary Full AdderRipple Carry Adder StructureExtension to SubtractionComparator (one approach)Alternate Adder Logic FormulationCarry Bypass Adder16-bit Carry Bypass AdderCritical Path AnalysisCarry Lookahead AdderCarry Lookahead LogicBlock Generate and PropagateMore Definitions…Logarithmic Look-Ahead Adder16-bit Kogge-Stone Tree AdderAdder PerformanceAddition of M, N-bit Numbers74181 TTL 4-bit ALU (TI)74181 Addition (Active Low)7418216-bit Carry Lookahead SchematicBinary MultiplicationA Serial (Magnitude) MultiplierTiming DiagramSimulationBaugh Wooley FormulationTwos Complement MultiplicationSummaryL8/9: 6.111 Spring 2007 1Introductory Digital Systems LaboratoryL8/9: Arithmetic Structures L8/9: Arithmetic Structures Lecture Material Adapted From:¾ R. Katz, G. Borriello, “Contemporary Logic Design” (second edition), Copyright 2005 Prentice-Hall/Pearson Education. ¾ J. Rabaey, A. Chandrakasan, B. Nikolic, “Digital Integrated Circuits: A Design Perspective” Copyright 2003 Prentice Hall/Pearson Education.¾Special thanks to Kevin Atkinson, Alice Wang, Rex MinL8/9: 6.111 Spring 2007 2Introductory Digital Systems LaboratoryNumber Systems BasicsNumber Systems BasicsHow to represent negative numbers? 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 negation_L8/9: 6.111 Spring 2007 3Introductory Digital Systems LaboratoryTwos Complement RepresentationTwos Complement RepresentationTwos complement = bitwise complement + 10111 → 1000 + 1 = 1001 = -71001 → 0110 + 1 = 0111 = 7 Asymmetric range: -2N-1to +2N-1-1 Only one representation for zero Simple addition and subtraction Most common representation010000110111010011011000111001101110011100001111114+ 37-4+ (-3)-7-4+ 3-14-31[Katz05]L8/9: 6.111 Spring 2007 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 2007 5Introductory Digital Systems LaboratoryBinary Full AdderBinary Full AdderFull AdderABCoSS = A ⊕ B ⊕ Ci= ABCi+ ABCi+ ABCi+ ABCiCo= AB + Ci(A+B)CiA 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 2007 6Introductory Digital Systems LaboratoryRipple Carry Adder StructureRipple Carry Adder StructureFull AdderA0B0S0Full AdderA1B1S1Full AdderA2B2S2Full AdderA3B3S3Co,2Co,3Co,1Ci,0Co,0Worst case propagation delay linear with the number of bitstadder= (N-1)tcarry+ tsumL8/9: 6.111 Spring 2007 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 1Combination addition/subtraction system:mux selects B for addition, B for subtraction_overflowAdd 1 for subtraction using carry inFAAdd/SubtractB3B3A3FAB2B2A2FAB1B1A1FAB0B0A0Co,2S1S00 10 10 10 1Co,1Co,0Co,3S2S3Overflow occurs if carry in to sign bit differs from final carry outL8/9: 6.111 Spring 2007 8Introductory Digital Systems LaboratoryComparator (one approach)Comparator (one approach)A < B = N A = B = ZA ≤ B = Z + N true if negative resulttrue if zero resultNZFAB3B3A3FAB2B2A2FAB1B1A1FAB0B0A00 10 10 10 11Co,1Co,0Co,2S3S2S1S0Co,3L8/9: 6.111 Spring 2007 9Introductory Digital Systems LaboratoryAlternate Adder Logic FormulationAlternate Adder Logic FormulationFull AdderABSGenerate (G) = ABPropagate (P) = A ⊕BCinCoHow 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 2007 10Introductory Digital Systems LaboratoryCarry Bypass AdderCarry Bypass AdderA0B0FAP,GCi,0P0G0Co,0FAP,GP1G1A1B1Co,1FAP,GP2G2A2B2A3B3Co,2FAP,GP3G3Can compute P, G in parallel for all bitsCo,3FAP,GCi,0P0G0Co,0FAP,GP1G1Co,1FAP,GP2G2Co,2FAP,GP3G301BP= P0P1P2P3Co,3Key Idea: if (P0P1P2P3) then Co,3= Ci,0L8/9: 6.111 Spring 2007 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,3Co,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 unitWhat is the worst case propagation delay for the 16-bit adder?L8/9: 6.111 Spring 2007 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,3Co,15For 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 2007 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 2007 14Introductory Digital Systems LaboratoryCarry Carry LookaheadLookaheadLogicLogicPiCiBiAiAdder with
View Full Document
Unlocking...