Arithmetic Building Blocks Chapter 11 RabaeyAnnouncementsA Generic Digital ProcessorBit-Sliced DesignFull AdderThe Binary AdderThe Ripple-Carry AdderComplimentary Static CMOS Full AdderA Closer LookInversion PropertyMinimize Critical Path by Reducing Inverting StagesApplying Inversion PropertyExpress Sum and Carry as Function of P, G, DA Better Structure: the Mirror AdderThe Mirror Adder IThe Mirror Adder IIAdder ArchitecturesCarry-Bypass AdderCarry-Bypass Adder (cont.)Carry Ripple vs. Carry BypassCarry-Select AdderCarry Select Adder: Critical Path Linear Carry Select Carry-Select Adder ObservationsSquare Root Carry Select Adder Delays: Comparison Carry Look Ahead: Basic Idea Look-Ahead: TopologyBinary MultiplicationBinary MultiplicationThe Array MultiplierThe MxN Array Multiplier: Critical PathAdder Cells in Array MultiplierMultiplier FloorplanArray Multiplier ReflectionsCarry Save MultiplierThe Tree MultiplierTree MultiplierTree MultiplierTree MultiplierTree MultiplierTree MultiplierWallace-Tree MultiplierMultipliers: SummaryTree MultiplierAnnouncementsDigital Integrated Circuits © Prentice Hall 1995ArithmeticArithmetic Building BlocksChapter 11 RabaeyDigital Integrated Circuits © Prentice Hall 1995ArithmeticA Generic Digital ProcessorMEMORYDATAPATHCONTROLINPUT-OUTPUTDigital Integrated Circuits © Prentice Hall 1995ArithmeticBuilding Blocks for Digital ArchitecturesDatapath (Arithmetic Unit)-Bit-sliced datapath(adder, multiplier, shifter, comparator, etc.)Memory- RAM, ROM, Buffers, Shift registersControl- Finite state machine (PLA, random logic.)- CountersInterconnect-Switches-Arbiters-BusDigital Integrated Circuits © Prentice Hall 1995ArithmeticBit-Sliced DesignBit 3Bit 2Bit 1Bit 0RegisterAdderShifterMultiplexerControlData-InData-OutTile identical processing elementsBit SliceDigital Integrated Circuits © Prentice Hall 1995ArithmeticFull AdderABCoutSumCinFulladderDigital Integrated Circuits © Prentice Hall 1995ArithmeticThe Binary AdderSABCi⊕⊕=A=BCiABCiABCiABCi+++CoAB BCiACi++=ABCoutSumCinFulladderDigital Integrated Circuits © Prentice Hall 1995ArithmeticThe Ripple-Carry AdderA0B0S0Co,0Ci,0A1B1S1Co,1A2B2S2Co,2A3B3S3Co,3(= Ci,1)FAFAFAFAWorst case delay linear with the number of bitstadderN1–()tcarrytsum+≈td = O(N)Goal: Make the fastest possible carry path circuitDigital Integrated Circuits © Prentice Hall 1995ArithmeticComplimentary Static CMOS Full AdderVDDVDDVDDVDDABCiSCoXBACiABBACiABCiCiBACiABBA28 TransistorsDigital Integrated Circuits © Prentice Hall 1995ArithmeticA Closer Lookz Drawbacks» Tall PMOS Stack– Slows down circuit» Coload is 2 diffusion and 6 gate capacitances» Ci goes through the extra output inverter to Co– Could optimize with next stage» Sum generation has extra inverter on output– Not the critical pathz Positive» Ci closest to output nodeVDDVDDVDDVDDABCiSCoXBACiABBACiABCiCiBACiABBA28 TransistorsDigital Integrated Circuits © Prentice Hall 1995ArithmeticInversion PropertyABSCoCiFAABSCoCiFADigital Integrated Circuits © Prentice Hall 1995ArithmeticMinimize Critical Path by Reducing Inverting StagesA0B0S0Co,0Ci,0A1B1S1Co,1A2B2S2Co,2Co,3FA’ FA’ FA’ FA’A3B3S3Odd CellEven CellExploit Inversion PropertyNote: need 2 different types of cellsDigital Integrated Circuits © Prentice Hall 1995ArithmeticApplying Inversion PropertyVDDVDDVDDVDDABCiSCoXBACiABBACiABCiCiBACiABBA28 TransistorsCoVDDVDDVDDVDDABCiSCoXBACiABBACiABCiCiBACiABBACoTo CiWith the next stage, invert A and B. You will get as outputs S and C…so take away inverters on these outputs.Invert A and B inputsDigital Integrated Circuits © Prentice Hall 1995ArithmeticExpress Sum and Carry as Function of P, G, DDefine 3 new variable which ONLY depend on A, BGenerate (G) = ABPropagate (P) = A ⊕ BDelete = A BCan also derive expressions for S and Co based on D and PC0= 0 if D = 1C0= 1 if G = 1C0= Ciif P = 1Digital Integrated Circuits © Prentice Hall 1995ArithmeticA Better Structure: the Mirror AdderVDDCiABBABAABKillGenerate"1"-Propagate"0"-PropagateVDDCiABCiCiBACiABBAVDDSCo24 transistorsDeleteDigital Integrated Circuits © Prentice Hall 1995ArithmeticThe Mirror Adder I•The NMOS and PMOS chains are completely symmetrical. This guarantees identical rising and falling transitions if the NMOS and PMOS devices are properly sized. A maximum of two series transistors can be observed in the carry-generation circuitry.•When laying out the cell, the most critical issue is the minimization of the capacitance at node Co. The reduction of the diffusion capacitances is particularly important. •The capacitance at node Cois composed of four diffusion capacitances, two internal gate capacitances, and six gate capacitances in the connecting adder cell .Digital Integrated Circuits © Prentice Hall 1995ArithmeticThe Mirror Adder II•The transistors connected to Ciare placed closest to the output.• Fastest for late arriving inputs, Citends to arrive late•Only the transistors in the carry stage have to be optimized for optimal speed. All transistors in the sum stage can be minimal size.Digital Integrated Circuits © Prentice Hall 1995ArithmeticAdder Architectures•In addition to optimizing each full adder cell and exploiting inversion property, we can also reorganize the add computation to speed things up •Basic idea is to overlap propagating the carry with computing the Propagate and Generate functions•Discuss three basic architectures• Carry-Bypass• Carry-Select• Carry-LookaheadDigital Integrated Circuits © Prentice Hall 1995ArithmeticCarry-Bypass AdderFA FA FA FAP0G1P0G1P2G2P3G3Co,3Co,2Co,1Co,0Ci,0FA FA FA FAP0G1P0G1P2G2P3G3Co,2Co,1Co,0Ci,0Co,3MultiplexerBP=PoP1P2P3Idea: If (P0 and P1 and P2 and P3 = 1)then Co3 = C0, else “kill” or “generate”.Digital Integrated Circuits © Prentice Hall 1995ArithmeticCarry-Bypass Adder (cont.)SetupCarryPropagationSumSetupCarryPropagationSumSetupCarryPropagationSumSetupCarryPropagationSumBit 0-3 Bit 4-7 Bit 8-11Bit 12-15Ci,0Note that this is done at the expense of a MUX in the carry delay path !!Digital Integrated Circuits © Prentice Hall 1995ArithmeticCarry Ripple vs. Carry BypassNtpripple adderbypass adder4..8Essentially greater than 4 bits is needed to overcome the overhead of the MUXDigital Integrated Circuits © Prentice Hall 1995ArithmeticCarry-Select AdderSetup"0" Carry Propagation"1" Carry PropagationMultiplexerSum GenerationCo,k-1Co,k+3"0""1"P,GCarry VectorEvaluate possibilities for both Ci = 1 and Ci = 0 and then select when