L8/9: Arithmetic Structures Number 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 DiagramSlide Number 28SimulationBaugh Wooley FormulationTwos Complement MultiplicationSummaryL8/9: 6.111 Spring 2008 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 Min¾Lecture Notes prepared by Professor Anantha ChadrakasanL8/9: 6.111 Spring 2008 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 2008 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 2008 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 1 01 0 1 1 1If carry in to sign equals carry out then can ignore carry out, otherwise have overflowL8/9: 6.111 Spring 2008 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 2008 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 2008 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 2008 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 2008 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 2008 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= P0 P1 P2 P3Co,3Key Idea: if (P0 P1 P2 P3 ) then Co,3 = Ci,0L8/9: 6.111 Spring 2008 11Introductory Digital Systems Laboratory1616--bit Carry Bypass Adderbit Carry Bypass AdderFAP,GCi,0Co,0FAP,GFAP,GFAP,G01BP= P0 P1 P2 P3Co,1Co,2FAP,GCo,4FAP,GFAP,GFAP,G01BP= P4 P5 P6 P7Co,5Co,6Co,7FAP,GCo,8FAP,GFAP,GFAP,G01BP= P8 P9 P10 P11Co,9Co,10FAP,GCo,11Co,12FAP,GFAP,GFAP,G01BP= P12 P13 P14 P15Co,13Co,14Co,15Assume the following for delay each gate:P, G from A, B: 1 delay unitP, G, Ci to Co or 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 2008 12Introductory Digital Systems LaboratoryCritical Path AnalysisCritical Path AnalysisFAP,GCi,0Co,0FAP,GFAP,GFAP,G01BP= P0 P1 P2 P3Co,1Co,2FAP,GCo,4FAP,GFAP,GFAP,G01BP2= P4 P5 P6 P7Co,5Co,6Co,7FAP,GCo,8FAP,GFAP,GFAP,G01BP3= P8 P9 P10 P11Co,9Co,10FAP,GCo,11Co,12FAP,GFAP,GFAP,G01BP4= P12 P13 P14 P15Co,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 2008 13Introductory Digital Systems LaboratoryCarry Carry LookaheadLookahead AdderAdderRe-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:
View Full Document
Unlocking...