EECS 150 - Components and Design Techniques for Digital Systems Lec 17 – Addition, Subtraction, and Negative NumbersOverviewComputer Number SystemsUnsigned Numbers - AdditionBinary Addition: Half AdderFull-AdderRipple CarryFull Adder from Half Adders (little aside)Delay in the Ripple Carry AdderRipple Carry TimingRecall: Virtex-E CLBAdders (cont.)Carry Select AdderExtended Carry Select AdderCarry Select Adder PerformanceAnnouncementsWhat really happens with the carriesCarry Look Ahead LogicAll Carries in ParallelCLA ImplementationHow do we extend this to larger adders?Cascaded Carry LookaheadTrade-offs in combinational logic designSo what about subtraction?Finite representation?Number SystemsSign and MagnitudeOnes Complement (algebraically)Ones Complement on the number wheelTwos Complement number wheelTwos Complement (algebraically)How is addition performed in each number system?Sign Magnitude AdditionOnes complement additionWhen carry occursWhy does end-around carry work?Twos Complement AdditionSlide 382s Comp: ignore the carry out2s Complement Overflow2s comp. Overflow Detection2s Complement Adder/SubtractorSummaryEECS 150 - Components and Design Techniques for Digital Systems Lec 17 – Addition, Subtraction, and Negative Numbers David CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp://www-inst.eecs.berkeley.edu/~cs150Overview•Binary Addition Full Adder Revisited•Ripple Carry•Carry-select adder•Carry lookahead adder•Binary Number Representation Sign & Magnitude, Ones Complement, Twos ComplementComputer Number Systems•We all take positional notation for granted–Dk-1 Dk-2 …D0 represents Dk-1Bk-1 + Dk-2Bk-2 + …+ D0 B0 where B { 0, …, B-1 }–Example: 200410, 11012 = 1310 = 0D16 •We all understand how to compare, add, subtract these numbers–Add each position, write down the position bit and possibly carry to the next position•Computers represent finite number systems•How do they efficiently compare, add, sub?–How do we reduce it to networks of gates and FFs?•Where does it break down?–Manipulation of finite representations doesn’t behave like same operation on conceptual numbersUnsigned Numbers - Addition0000011100111011111111101101110010101001100001100101010000100001+0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+Example: 3 + 2 = 5Unsigned binary additionIs just addition, base 2Add the bits in each position and carry 0 0 1 1+ 0 0 1 0 0 1 0 11How do we build a combinational logic circuit to perform addition?=> Start with a truth table and go from thereBinary Addition: Half AdderAi 0 0 1 1Bi 0 1 0 1Sum 0 1 1 0Carry 0 0 0 1AiBi0 1010 11 0Sum = Ai Bi + Ai Bi= Ai + BiAiBi0 1010 010Carry = Ai BiHalf-adder SchematicCarry Sum A i B i But each bit position may have a carry in…Full-AdderA 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 1000010111SCOS = CI xor A xor BCO = B CI + A CI + A B = CI (A + B) + A BNow we can connect them up to do multiple bits… 0 0 1 1+ 0 0 1 0 0 1 0 11ABSCinCoRipple Carry+A3 B3S3+A2 B2S2+A1 B1S1+A0 B0S0C1C2C3Full Adder from Half Adders (little aside)Alternative Implementation: 5 GatesA B + CI (A xor B) = A B + B CI + A CIStandard Approach: 6 GatesAAABBBCICISCOHalf AdderABHalf AdderA + BCIA + B + CIS SCOCOCI (A + B)A BSCODelay in the Ripple Carry AdderCritical delay: the propagation of carry from low to high order stagesAABBCICO@0@0@0@0@N@1@1@N+1@N+2latearrivingsignaltwo gate delaysto compute CO4 stageadderfinal sum andcarryA 0 B 0 C 0 S 0 @2 A 1 B 1 C 1 @2 S 1 @3 A 2 B 2 C 2 @4 S 2 @5 A 3 B 3 C 3 @6 S 3 @7 C 4 @8 0 1 2 3Ripple Carry TimingCritical delay: the propagation of carry from low to high order stages1111 + 0001worst caseadditionT0: Inputs to the adder are validT2: Stage 0 carry out (C1)T4: Stage 1 carry out (C2)T6: Stage 2 carry out (C3)T8: Stage 3 carry out (C4)2 delays to compute sumbut last carry not ready until 6 delays laterT0 T2 T4 T6 T8S0, C1 Valid S1, C2 Valid S2, C3 Valid S3, C4 ValidRecall: Virtex-E CLBCLB = 4 logic cells (LC) in two slicesLC: 4-input function generator, carry logic, storage ele’t80 x 120 CLB array on 2000E16x1 synchronous RAMFF or latchAdders (cont.)Ripple AdderRipple adder is inherently slow because, in generals7 must wait for c7 which must wait for c6 …T n, Cost nHow do we make it faster, perhaps with more cost?F Ac 0a 0b 0s 0c 1c 2c 3c 4c 5c 6c 7s 7 s 6Or use a MUX !!!Classic approach: Carry Look-AheadCarry Select AdderT = Tripple_adder / 2 + TMUXCOST = 1.5 * COSTripple_adder+ (n+1) * COSTMUX01c8FA0a4a5a6a7b7 b6 b5 b4c0a0b0s0a1a2a3b3 b2 b1s1s2s3FA1a4a5a6a7b7 b6 b5 b41 0 1 01 0 1 0s4s5s6s7Extended Carry Select Adder•What is the optimal # of blocks and # of bits/block?–If # blocks too large delay dominated by total mux delay–If # blocks too small delay dominated by adder delay per block101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r4 - b i t A d d e ra 3 - a 0b 3 - b 0c i nc o u ta 1 1 - a 8b 1 1 - b 8a 1 5 - a 1 2b 1 5 - b 1 2 b 7 - b 4 a 7 - a 4bits N of stages NT sqrt(N),Cost 2*ripple + muxesCarry Select Adder Performance•Compare to ripple adder delay:Ttotal = 2 sqrt(N) TFA – TFA, assuming TFA = TMUXFor ripple adder Ttotal = N TFA“cross-over” at N=3, Carry select faster for any value of N>3.•Is sqrt(N) really the optimum?–From right to left increase size of each block to better match delays–Ex: 64-bit adder, use block sizes [12 11 10 9 8 7 7]•How about recursively defined carry select?101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r101 0 1 0 1 0 1 04 - b i t A d d e r 4 - b i tA d d e r4 - b i t A d d e ra 3 - a 0b 3 - b 0c i nc o u ta 1 1 - a 8b 1 1 - b 8a 1 5 - a 1 2b 1 5 - b 1 2 b 7 - b 4 a 7 - a 4Announcements•Reading Katz 5.6 and Appendix A (on line)•Midterm regrades in writing by Friday–the box by 2:10 Friday (along with homework)•If your partner drops, talk to your TA–Reduced project or “re-pair” within section•If you and your partner are having problems, talk to your TA•Don’t think of end of one-week grace period as “due date” for the lab.•Next midterm 11/9What really happens with the carriesF Ac 0a 0b 0s 0c 1c 2c 3c 4c 5c
View Full Document
Unlocking...