Slide 1Half Adder (1-bit)Slide 3Full AdderSlide 5Slide 6Slide 74-bit Ripple Adder using Full AdderFull Adder Propagation DelaySlide 10Issue of 4-bit Ripple AdderIssue of Ripple AdderCarry Generate & Propagate4-bit Carry-Lookahead Adder (CLA)Inefficient Implementation of Carry Lookahead LogicImplementation of Carry Lookahead LogicCascading CLASubtractor DesignOverflow/Underflow for Signed ArithmeticOverflow/Underflow DetectionSlide 21Slide 22Overflow/Underflow ExampleParity CircuitsEven Parity GenerationEven Parity DetectionParity Detection ExampleSlide 28ECE2030 Introduction to Computer EngineeringLecture 12: Building Blocks for Combinational Logic (3) Adders/Subtractors, Parity CheckersProf. Hsien-Hsin Sean LeeProf. Hsien-Hsin Sean LeeSchool of Electrical and Computer EngineeringSchool of Electrical and Computer EngineeringGeorgia TechGeorgia TechHalf Adder (1-bit)A B S(um)C(arry)0 0 0 00 1 1 01 0 1 01 1 0 1HalfAdderA BSCHalf Adder (1-bit)A B S(um)C(arry)0 0 0 00 1 1 01 0 1 01 1 0 1AB CBABABASABSumCarryFull AdderCin A B S(um)Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1FullAdderA BSCoutCarry In(Cin)Full AdderCin A B S(um)Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 100 01 11 1000 1 0 111 0 1 0 CinABBACinB)(ACin)BACin()BABA(CinAB)BACin(BACinCinABBACinBACinS00 01 11 1000 0 1 010 1 1 1 CinABABCinACinBCout 00 01 11 1000 0 1 010 1 1 1 CinABB)Cin(AAB)BABACin(ABCout OrFull AdderBACinS ABCinCoutSH.A.H.A.B)Cin(AABCout Full AdderCoutSHalfAdderSCABHalfAdderSCABBACinBACinS B)Cin(AABCout 4-bit Ripple Adder using Full AdderFullAdderA BCinCoutSS0A0 B0FullAdderA BCinCoutSS1A1 B1FullAdderA BCinCoutSS2A2 B2FullAdderA BCinCoutSS3A3 B3CarryABSCHalf AdderABCinCoutSH.A. H.A.Full AdderFull Adder Propagation DelayS0A0 B0CarryCin11stst Stage Critical Path Stage Critical Path = 3 gate delays= 3 gate delays= D= DXORXOR+D+DANDAND+D+DORORFull Adder Propagation DelayS0A0 B0CinS1A1 B122ndnd Stage Critical Path Stage Critical Path = 2 gate delays= 2 gate delays= D= DANDAND+D+DOR OR (Since 1(Since 1stst Critical path Critical path> D> DXORXOR))11stst Stage Critical Path Stage Critical Path = 3 gate delays= 3 gate delays= D= DXORXOR+D+DANDAND+D+DORORIssue of 4-bit Ripple Adder Critical Path = DCritical Path = DXORXOR+4*(D+4*(DANDAND+D+DOROR) for 4-bit ripple adder ) for 4-bit ripple adder (9 gate (9 gate levels)levels)For an For an NN-bit ripple adder-bit ripple adderCritical Path Delay Critical Path Delay ~ 2(N-1)+3 = (2N+1) Gate delays~ 2(N-1)+3 = (2N+1) Gate delaysS0A0 B0CinS1A1 B1S2A2 B2S3A3 B3CarryIssue of Ripple Adder•Carry propagationCarry propagation is the main issue in an N-bit ripple adder•A faster adder needs to address the serial propagation of the carry bit•Let’s re-examine the equation for full addersCarry GenerateGenerate & PropagatePropagate)B(ACBACiiiii1i)(propagate BAp(generate) BAgiiiiiiiii1iCpgC 00123012312323333340012012122222300101111120001CppppgpppgppgpgCpgCCpppgppgpgCpgCCppgpgCpgCCpgCNote that all the carry’s are Note that all the carry’s are only dependent on input A and only dependent on input A and B and CB and C4-bit Carry-Lookahead Adder (CLA)Carry Lookahead LogicCarry Lookahead Logicg1g1p1p1A1 B1S1S1C1C1g2g2p2p2A2 B2S2S2C2C2g3g3p3p3A3 B3S3S3C3C3g0g0p0p0A0 B0S0S0C0C0C4C4)(propagate BAp(generate) BAgiiiiiiiiiiBACS InefficientInefficient Implementation of Carry Lookahead LogicA0 B0S0S0A1 B1S1S1C0C0A2 B2S2S2A3 B3S3S3C1C1C2C2C3C3C4C4g0g0p0p0g1g1p1p1g2g2p2p2g3g3p3p300123012312323333340012012122222300101111120001CppppgpppgppgpgCpgCCpppgppgpgCpgCCppgpgCpgCCpgCReuse some gate output results Reuse some gate output results Little ImprovementLittle ImprovementCarry Delay is 4*DCarry Delay is 4*DANDAND + 2*D + 2*DOROR for Carry C for Carry C44Implementation of Carry Lookahead LogicC4C4A0 B0S0S0A1 B1S1S1C0C0A2 B2S2S2A3 B3S3S300123012312323333340012012122222300101111120001CppppgpppgppgpgCpgCCpppgppgpgCpgCCppgpgCpgCCpgCCarry Lookahead LogicCarry Lookahead LogicOnly 3 Gate Delay for each Carry COnly 3 Gate Delay for each Carry Cii= = DDANDAND + 2*D + 2*DOROR C3C3g3g3p3p3g0g0p0p0C2C2g2g2p2p2C1C1g1g1p1p14 Gate Delay for each Sum S4 Gate Delay for each Sum Sii= = DDANDAND + 2*D + 2*DOROR + D+ DXORXORCascading CLA•Similar to ripple adder, but different latencyCLAA BCinCoutSS[3:0]A[3:0] B[3:0]CLAA BCinCoutSS[7:4]A[7:4] B[7:4]4 444 4 4CLAA BCinCoutSS[11:8]A[11:8]B[11:8]444CLAA BCinCoutSS[15:12]A[15:12]B[15:12]444Delay of each stageis 3 gate levels instead of 9 of ripple addersSubtractor Design•A – B = A + (-B)–Take 2’s complement of B –Perform addition of A and 2’s complement of BFullAdderA BCinCoutSS0A0FullAdderA BCinCoutSS1A1FullAdderA BCinCoutSS2A2FullAdderA BCinCoutSS3A3B0B1B2B3CSubtractOverflow/Underflow for Signed Arithmetic01001000 (+72)00111001 (+57)-------------------- (+129)What is largest positive number represented by 8-bit? 8-bit Signed number addition10000001 (-127)11111010 ( -6)-------------------- (-133)8-bit Signed number additionWhat is smallest negative number represented by 8-bit?Overflow/Underflow DetectionCn-1An-1Bn-1Sn-1CnOF0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1•Examine the MSB bit• Bottom line:–P: positive; N: negative– N + N = N – P + P = P–P+N or N+P always fall into the range •E.g. -128+P cannot be smaller than -128 or bigger than 127• Problem lies in– N+N = P– P+P = NDiscardedOverflow/Underflow DetectionCn-1An-1Bn-1Sn-1CnOF0 0 0 0 0 00 0 1 1 0 00 1 0 1 0 00 1 1 0 1 11 0 0 1 0 11 0 1 0 1 01 1 0 0 1 01 1 1 1 1 0BACABCOF Discardedn1nCCOFor Overflow/Underflow DetectionFullAdderA BCinCoutSS0A0 B0FullAdderA BCinCoutSS1A1 B1FullAdderA BCinCoutSS2A2 B2FullAdderA BCinCoutSS3A3 B3CarryOverflow/Underflown-bit Adder/Subtractorn-bit Adder/SubtractorOverflow/UnderflowCnCn-1Overflow/Underflow Example01001000 (+72)00111001 (+57)-------------------- (+129)8-bit Signed number addition10000001 (-127)11111010 ( -6)-------------------- (-133)8-bit Signed number additionCn-1 = Cn =Cn-1 = Cn =Parity Circuits•To detect single bit error during
View Full Document
Unlocking...