40 60 80 100 120406080mm8. Design of AddersJ. A. AbrahamDepartment of Electrical and Computer EngineeringThe University of Texas at AustinEE 382M-ICS – VLSI ISpring 2012February 4, 2012ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 1 / 3340 60 80 100 120406080mmSingle-Bit AdditionHalf AdderS = A ⊕ BCout= A · BA B CoutS0 0 0 00 1 0 11 0 0 11 1 1 0Full AdderS = A ⊕ B ⊕ CCout= MAJ(A, B, C)A B C CoutS0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 1 / 3340 60 80 100 120406080mmFull Adder Design IBrute force implementation from equationsS = A ⊕ B ⊕ CCout= MAJ(A, B, C)ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 2 / 3340 60 80 100 120406080mmFull Adder Design IIFactor S in terms of CoutS = A · B · C + (A + B + C) · CoutCritical path is usually C to Coutin ripple adderECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 3 / 3340 60 80 100 120406080mmLayout of Full AdderClever layout circumvents usual line of diffusionUse wide transistors on critical pathEliminate output invertersECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 4 / 3340 60 80 100 120406080mmFull Adder Design IIIComplementary Pass Transistor Logic (CPL)Slightly faster, but more areaECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 5 / 3340 60 80 100 120406080mmRipple Carry AdderSimplest design: cascade full addersCritical path goes from Cinto CoutDesign full adder to have fast carry (small delay for carrysignal)ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 6 / 3340 60 80 100 120406080mmDeal with Inversions to Speed Up Carry PathCritical path passes through majority gateBuilt from minority + inverterEliminate inverter and use inverting full adderECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 7 / 3340 60 80 100 120406080mmCarry Propagate AddersN-bit adder called CPAEach sum bit depends on all previous carriesHow do we compute all these carries quickly?ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 8 / 3340 60 80 100 120406080mmCarry Propagate, Generate, Kill (P, G, K)For a full adder, define what happens to carriesGenerate: Cout= 1, independent of CG = A · BPropagate: Cout= CP = A ⊕ BKill: Cout= 0, independent of CK = A · BGenerate and Propagate for groups spanning i:jGi:j= Gi:k+ Pi:k· Gk−1:jPi:j= Pi:k· Pk−1:jBase CaseGi:i≡ Gi= Ai· Bi, G0:0= G0= CinPi:i≡ Pi= Ai⊕ Bi, P0:0= P0= 0Sum: Si= Pi⊕ Gi−1:0ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 9 / 3340 60 80 100 120406080mmCarry Propagate, Generate, Kill (P, G, K)For a full adder, define what happens to carriesGenerate: Cout= 1, independent of CG = A · BPropagate: Cout= CP = A ⊕ BKill: Cout= 0, independent of CK = A · BGenerate and Propagate for groups spanning i:jGi:j= Gi:k+ Pi:k· Gk−1:jPi:j= Pi:k· Pk−1:jBase CaseGi:i≡ Gi= Ai· Bi, G0:0= G0= CinPi:i≡ Pi= Ai⊕ Bi, P0:0= P0= 0Sum: Si= Pi⊕ Gi−1:0ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 10 / 3340 60 80 100 120406080mmPG LogicECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 11 / 3340 60 80 100 120406080mmRipple Carry Adder Revisited in the PG FrameworkGi:0= Gi+ Pi· Gi−1:0ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 12 / 3340 60 80 100 120406080mmRipple Carry PG Diagramtripple= tpg+ (N − 1)tAO+ txorECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 13 / 3340 60 80 100 120406080mmPG Diagram NotationECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 14 / 3340 60 80 100 120406080mmCarry-Skip AdderCarry-ripple is slow through all N stagesCarry-skip allows carry to skip over groups of n bitsDecision based on n-bit propagate signalECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 15 / 3340 60 80 100 120406080mmCarry-Skip PG DiagramFor k n-bit groups (N = nk)tskip= tpg+ [2(n − 1) + (k − 1)] tAO+ txorECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 16 / 3340 60 80 100 120406080mmVariable Group SizeDelay grows as O(√N)ECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 17 / 3340 60 80 100 120406080mmCarry-Lookahead Adder (CLA)Carry-lookahead adder computes Gi:0for many bits in parallelUses higher-valency cells with more than two inputsECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 18 / 3340 60 80 100 120406080mmCLA PG DiagramHigher Valency CellsECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 19 / 3340 60 80 100 120406080mmCarry-Select AdderTrick for critical paths dependent on late input XPrecompute two possible outputs for X = 0, 1Select proper output when X arrivesCarry-select adder precomputes n-bit sums for both possiblecarries into n-bit groupECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 20 / 3340 60 80 100 120406080mmCarry-Increment AdderFactor initial PG andfinal XOR out ofcarry-selecttincrement= tpg+[(n − 1) + (k − 1)] tAO+txorVariable Group SizeBuffer non-criticalsignals to reducebranching effortECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 21 / 3340 60 80 100 120406080mmTree AddersTree structures can be used to speed up computationsLook at computing the XOR of 8 bits using 2-input XOR-gatesIf lookahead is good for adders, lookahead across lookahead!Recursive lookahead gives O(log N) delayMany variations on tree addersECE Department, University of Texas at Austin Lecture 8. Design of Adders J. A. Abraham, February 4, 2012 22 / 3340 60