ECE2030 Introduction to Computer Engineering Lecture 12 Building Blocks for Combinational Logic 3 Adders Subtractors Parity Checkers Prof Hsien Hsin Sean Lee School of Electrical and Computer Engineering Georgia Tech Half Adder 1 bit A B Half Adder S C A B S um C arry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Half Adder 1 bit A B Sum A B S um C arry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Carry S AB A B A B C AB Full Adder A Carry In Cin B Full Adder S Cout Cin A B S um Cout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Full Adder Cin A B S um Cout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 S Cin A B Cin AB CinAB CinA B 0 1 1 0 1 Cin A B AB Cin AB A B 1 0 0 1 0 Cin A B Cin A B Cin A B 1 0 1 0 1 1 1 0 0 1 1 AB 1 1 1 1 Cin Cin AB 00 01 11 10 0 0 1 0 1 1 1 0 1 0 AB 00 01 11 10 0 0 0 1 0 1 0 1 1 1 Cout CinB CinA AB Cin Or 00 01 11 10 0 0 0 1 0 1 0 1 1 1 Cout AB Cin AB A B AB Cin A B Full Adder S Cin A B Cout AB Cin A B A B H A H A S Cin Cout Full Adder S Cin A B Cout AB Cin A B A A S A Half Adder B Cin B S S Half Adder C B C Cout 4 bit Ripple Adder using Full Adder Carry A3 B3 A2 B2 A1 B1 A0 B0 A B A B A B A B Full Cin Adder Cout Full Cin Adder Full Cin Adder Cout Cout Full Cin Adder Cout S S S S S3 S2 S1 S0 A B S S Cout A H A B Cin C Half Adder H A Full Adder Full Adder Propagation Delay A0 B0 Carry Cin S0 1st Stage Critical Path 3 gate delays DXOR DAND DOR Full Adder Propagation Delay A1 B1 A0 B0 Cin S1 S0 2nd Stage Critical Path 1st Stage Critical Path 2 gate delays 3 gate delays DAND DOR DXOR DAND DOR Since 1st Critical path DXOR Issue of 4 bit Ripple Adder A3 B3 A2 B2 A1 B1 A0 B0 Carry Cin S3 S2 S1 S0 Critical Path DXOR 4 DAND DOR for 4 bit ripple adder levels 9 gate For an N bit ripple adder Critical Path Delay 2 N 1 3 2N 1 Gate delays Issue of Ripple Adder Carry 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 adders Carry Generate Propagate Ci 1 A i Bi Ci A i Bi g i A i Bi generate p i A i Bi propagate Ci 1 g i p i Ci C1 g 0 p 0 C0 C 2 g1 p1C1 g1 p1g 0 p1p 0C0 C3 g 2 p 2C 2 g 2 p 2 g1 p 2 p1g 0 p 2 p1p 0C0 C 4 g 3 p 3C3 g 3 p3g 2 p 3p 2g1 p 3p 2 p1g 0 p 3p 2 p1p 0C0 Note that all the carry s are only dependent on input A and B and C 4 bit Carry Lookahead Adder CLA Carry Lookahead Logic C4 C3 g3 S3 A3 C2 p3 B3 g2 S2 A2 Si Ci A i Bi C1 p2 B2 g1 S1 C0 A1 p1 B1 g i A i Bi generate p i A i Bi propagate g0 S0 A0 p0 B0 Inefficient Implementation of Carry Lookahead Logic C0 C4 g3 p3 C3 C1 g 0 p 0C0 C 2 g 1 p1C1 g 1 p1g 0 p1p 0C0 S3 A3 B3 some gate output C 3 gReuse 2 p 2C 2 g 2 p 2 g 1 p 2p 1g 0 p 2p 1p 0C 0 g2 p2 C2 S2 A2 B2 results Improvement C4 gLittle 3 p 3C 3 g 3 p 3 g 2 p 3p 2 g 1 p 3p 2p 1g 0 p 3p 2p 1p 0 C 0 Carry Delay is 4 DAND 2 DOR for Carry C4 g1 p1 C1 g0 p0 S1 A1 B1 S0 A0 B0 Implementation of Carry Lookahead Logic Carry Lookahead Logic C0 C4 g3 C1 g 0 p 0C0 p3 C3 S3 A3 B3 C 2 g 1 p1C1 g 1 p1g 0 p1p 0C0 C 3 g 2 p 2C 2 g 2 p 2g 1 p 2p1g 0 p 2p1p 0C0 g2 p2 C2 S2 A2 B2 g1 p1 C1 g0 p0 S1 A1 B1 S0 A0 B0 Only 3 Gate Delay for each Carry Ci DAND 2 DOR C4 g 3 p 3C 3 g 3 p 3 g 2 p 3p 2g 1 p 3p 2p1g 0 p 3p 2p1p 0C0 4 Gate Delay for each Sum Si DAND 2 DOR DXOR Cascading CLA Similar to ripple adder but different latency A 15 12 B 15 12 A 11 8 B 11 8 A 7 4 B 7 4 A 3 0 B 3 0 4 4 A B Cout CLA Cin S 4 4 A B Cout CLA Cin S 4 4 A Cout B CLA Cin S 4 4 S 15 12 S 11 8 4 4 A B Cout CLA Cin S 4 S 7 4 4 S 3 0 Delay of each stage is 3 gate levels instead of 9 of ripple adders Subtractor Design B3 B2 B1 B0 Subtract A3 A2 A C B Full Cin Adder Cout A1 A B Full Cin Adder Cout A0 A B Full Cin Adder Cout A B Full Cin Adder Cout S S S S S3 S2 S1 S0 A B A B Take 2 s complement of B Perform addition of A and 2 s complement of B Overflow Underflow for Signed Arithmetic 8 bit Signed number addition 8 bit Signed number addition 01001000 72 00111001 57 129 What is largest positive number represented by 8bit 10000001 127 11111010 6 133 What is smallest negative number represented by 8bit Overflow Underflow Detection Cn 1 An 1 Bn 1 Sn 1 Cn 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Discarded OF Examine the MSB bit Bottom line P positive N negative N N N P P …
View Full Document
Unlocking...