Binary Adder Design(COA).ppt

CS 140 LECTURE 14 STANDARD COMBINATIONAL MODULES PROFESSOR CK CHENG CSE DEPT. UC SAN DIEGO 1 Some slides from Harris and Harris

PART III. STANDARD MODULES 2 A. Interconnect B. Operators. Adders Multiplier Adders 1. Representation of numbers 2. Full Adder 3. Half Adder 4. Ripple-Carry Adder 5. Carry Look Ahead Adder 6. Prefix Adder ALU Multiplier Division

OPERATORS • Specification: Data Representations • Arithmetic: Algorithms • Logic: Synthesis • Layout: Placement and Routing 3

1. REPRESENTATION • 2’s Complement -x: 2n-x • 1’s Complement -x: 2n-x-1 4

Id 2’s comp. 1’s comp. 0 0 15 -1 15 14 -2 14 13 -3 13 12 -4 12 11 -5 11 10 -6 10 9 -7 9 8 -8 8 5 1. Representation • 2’s Complement -x: 2n-x e.g. 16-x • 1’s Complement -x: 2n-x-1 e.g. 16-x-1

Id -Binary sign mag 2’s comp 1’s comp 0 0000 1000 0000 1111 -1 0001 1001 1111 1110 -2 0010 1010 1110 1101 -3 0011 1011 1101 1100 -4 0100 1100 1100 1011 -5 0101 1101 1011 1010 -6 0110 1110 1010 1001 -7 0111 1111 1001 1000 -8 1000 6 1. Representation

REPRESENTATION 1’s Complement For a negative number, we take the positive number and complement every bit. 2’s Complement For a negative number, we do 1s complement and plus one. (bn-1, bn-2, …, b0): -bn-12n-1+ sumi<n-1 bi2i 7

REPRESENTATION 2’s Complement • x+y • x-y: x+2n-y= 2n+x-y • -x+y: 2n-x+y • -x-y: 2n-x+2n-y = 2n+2n-x-y • -(-x)=2n-(2n-x)=x 8 1’s Complement • x+y • x-y: x+2n-y-1= 2n-1+x-y • -x+y: 2n-x-1+y=2n-1-x+y • -x-y: 2n-x-1+2n-y-1 = 2n-1+2n-x-y-1 • -(-x)=2n-(2n-x-1) -1=x

9 EXAMPLES 2 + 3 = 5 0 0 1 0 0 0 1 0 + 0 0 1 1 0 1 0 1 2 - 3 = -1 (2’s) 0 0 0 0 0 0 1 0 + 1 1 0 1 1 1 1 1 2 - 3 = -1 (1’s) 0 0 1 0 + 1 1 0 0 1 1 1 0 -2 - 3 = -5 (2’s) 1 1 0 0 1 1 1 0 + 1 1 0 1 1 0 1 1 -2 - 3 = -5 (1’s) 1 1 0 0 1 1 0 1 + 1 1 0 0 1 0 0 1 1 1 0 1 0 3 + 5 = 8 0 1 1 1 0 0 1 1 + 0 1 0 1 1 0 0 0 C4C3 Check for overflow (2’s) -3 + -5 = -8 1 1 1 1 1 1 0 1 + 1 0 1 1 1 0 0 0 C4C3

10 Addition: 2’s Complement Overflow In 2’s complement: overflow = cn xor cn-1 Exercise: 1.Demonstrate the overflow with more examples. 2.Prove the condition.

11 Adder MUX Sum minus b b’ a Cout overflow C4 C3 Cin Addition and Subtraction using 2’s Complement

1-BIT ADDERS A B 0 0 0 1 1 0 1 1 0 1 1 0 S Cout 0 0 0 1 S = A  B Cout = AB Half Adder A B S Cout + A B 0 0 0 1 1 0 1 1 0 1 1 0 S Cout 0 0 0 1 S = A  B Cin Cout = AB + ACin + BCin Full Adder Cin 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 A B S Cout Cin + 12

13 HALF ADDER a b Cout Sum 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Sum = ab’ + a’b = a + b Cout = ab Cout Sum a b HA a b Sum Cout

14 Full Adder Composed of Half Adders HA HA a b cin x sum cout OR sum cout cout sum y z

15 Full Adder Composed of Half Adders HA HA a b cin x sum cout sum cout cout sum y z Id a b cin x y z cout sum 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 2 0 1 0 0 1 0 0 1 3 0 1 1 0 1 1 1 0 4 1 0 0 0 1 0 0 1 5 1 0 1 0 1 1 1 0 6 1 1 0 1 0 0 1 0 7 1 1 1 1 0 0 1 1 Id x z cout 0 0 0 0 1 0 1 1 2 1 0 1 3 1 1 -

ADDER A B S Cout Cin + N N N 16 • Several types of carry propagate adders (CPAs) are: – Ripple-carry adders (slow) – Carry-lookahead adders (fast) – Prefix adders (faster) • Carry-lookahead and prefix adders are faster for large adders but require more hardware. Symbol

RIPPLE-CARRY ADDER S31 A30 B30 S30 A1 B1 S1 A0 B0 S0 C31 C30 C2 C1 Cout + + + + A31 B31 Cin 17 • Chain 1-bit adders together • Carry ripples through entire chain • Disadvantage: slow

RIPPLE-CARRY ADDER DELAY 18 • The delay of an N-bit ripple-carry adder is: tripple = NtFA where tFA is the delay of a full adder

CARRY-LOOKAHEAD ADDER 19 • Compress the logic levels of Cout • Some definitions: – Generate (Gi) and propagate (Pi) signals for each column: • A column will generate a carry out if Ai AND Bi are both 1. Gi = Ai Bi • A column will propagate a carry in to the carry out if Ai OR Bi is 1. Pi = Ai + Bi • The carry out of a column (Ci) is: Ci+1 = Ai Bi + (Ai + Bi )Ci = Gi + Pi Ci

CARRY LOOK AHEAD ADDER 20 C1 = a0b0 + (a0+b0)c0 = g0 + p0c0 C2 = a1b1 + (a1+b1)c1 = g1 + p1c1 = g1 + p1g0 + p1p0c0 C3 = a2b2 + (a2+b2)c2 = g2 + p2c2 = g2 + p2g1 + p2p1g0 + p2p1p0c0 C4 = a3b3 + (a3+b3)c3 = g3 + p3c3 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0 qi = aibi pi = ai + bi a3 b3 g3 p3 a2 b2 g2 p2 a1 b1 g1 p1 a0 b0 g0 p0 c1 c2 c3 c4 c0

CARRY-LOOKAHEAD ADDITION 21 • Step 1: compute generate (G) and propagate (P) signals for columns (single bits) • Step 2: compute G and P for k-bit blocks • Step 3: Cin propagates through each k-bit propagate/generate block

32-BIT CLA WITH 4-BIT BLOCKS B0 + + + + P3:0 G3 P3 G2 P2 G1 P1 G0 P3 P2 P1 P0 G3:0 Cin Cout A0 S0 C1 B1 A1 S1 C2 B2 A2 S2 C3 B3 A3 S3 Cin A3:0 B3:0 S3:0 4-bit CLA Block Cin A7:4 B7:4 S7:4 4-bit CLA Block C4 C8 A27:24 B27:24 S27:24 4-bit CLA Block C24 A31:28 B31:28 S31:28 4-bit CLA Block C28 Cout 22

CARRY-LOOKAHEAD ADDER DELAY 23 • Delay of an N-bit carry-lookahead adder with k-bit blocks: tCLA = tpg + tpg_block + (N/k – 1)tAND_OR + ktFA where – tpg : delay of the column generate and propagate gates – tpg_block : delay of the block generate and propagate gates – tAND_OR :delay from Cin to Cout of the final AND/OR gate in the k-bit CLA block • An N-bit carry-lookahead adder is generally much faster than a ripple-carry adder for N > 16

PREFIX ADDER 24 • Computes the carry in (Ci-1) for each of the columns as fast as possible and then computes the sum: Si = (Ai  Bi)  Ci • Computes G and P for 1-bit, then 2-bit blocks, then 4-bit blocks, then 8-bit blocks, etc. until the carry in (generate signal) is known for each column • Has log2N stages

PREFIX ADDER 25 • A carry in is produced by being either generated in a column or propagated from a previous column. • Define column -1 to hold Cin, so G-1 = Cin, P-1 = 0 • Then, the carry in to col. i = the carry out of col. i-1: Ci-1 = Gi-1:-1 Gi-1:-1 is the generate signal spanning columns i-1 to -1. There will be a carry out of column i-1 (Ci-1) if the block spanning columns i-1 through -1 generates a carry. • Thus, we rewrite the sum equation:Si = (Ai  Bi)  Gi-1:-1 • Goal: Compute G0:-1, G1:-1, G2:-1, G3:-1, G4:-1, G5:-1, … (These are called the prefixes)

PREFIX ADDER 26 • The generate and propagate signals for a block spanning bits i:j are: Gi:j = Gi:k + Pi:k Gk-1:j Pi:j = Pi:kPk-1:j • In words, these prefixes describe that: – A block will generate a carry if the upper part (i:k) generates a carry or if the upper part propagates a carry generated in the lower part (k-1:j) – A block will propagate a carry if both the upper and lower parts propagate the carry.

PREFIX ADDER SCHEMATIC 0:-1 -1 2:1 1:-1 2:-1 0 1 2 4:3 3 6:5 5:3 6:3 4 5 6 5:-1 6:-1 3:-1 4:-1 8:7 7 10:9 9:7 10:7 8 9 10 12:11 11 14:13 13:11 14:11 12 13 14 13:7 14:7 11:7 12:7 9:-1 10:-1 7:-1 8:-1 13:-1 14:-1 11:-1 12:-1 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Bi Ai Gi:i Pi:i Gk-1:j Pk-1:j Gi:k Pi:k Gi:j Pi:j i i:j Bi Ai Gi-1:-1 Si i Legend 27

PREFIX ADDER DELAY 28 • The delay of an N-bit prefix adder is: tPA = tpg + log2N(tpg_prefix ) + tXOR where – tpg is the delay of the column generate and propagate gates (AND or OR gate) – tpg_prefix is the delay of the black prefix cell (AND-OR gate)

ADDER DELAY COMPARISONS 29 • Compare the delay of 32-bit ripple-carry, carry- lookahead, and prefix adders. The carry-lookahead adder has 4-bit blocks. Assume that each two-input gate delay is 100 ps and the full adder delay is 300 ps.

ADDER DELAY COMPARISONS 30 • Compare the delay of 32-bit ripple-carry, carry- lookahead, and prefix adders. The carry-lookahead adder has 4-bit blocks. Assume that each two-input gate delay is 100 ps and the full adder delay is 300 ps. tripple = NtFA = 32(300 ps) = 9.6 ns tCLA = tpg + tpg_block + (N/k – 1)tAND_OR + ktFA = [100 + 600 + (7)200 + 4(300)] ps = 3.3 ns tPA = tpg + log2N(tpg_prefix ) + tXOR = [100 + log232(200) + 100] ps = 1.2 ns

COMPARATOR: EQUALITY Symbol Implementation A3 B3 A2 B2 A1 B1 A0 B0 Equal = A B Equal 4 4 31

COMPARATOR: LESS THAN A < B - B A [N-1] N N N 32 • For unsigned numbers

ARITHMETIC LOGIC UNIT (ALU) ALU N N N 3 A B Y F F2:0 Function 000 A & B 001 A | B 010 A + B 011 not used 100 A & ~B 101 A | ~B 110 A - B 111 SLT 33

ALU DESIGN + 2 0 1 A B Cout Y 3 0 1 F2 F1:0 [N-1] S N N N N N N N N N 2 Zero Extend F2:0 Function 000 A & B 001 A | B 010 A + B 011 not used 100 A & ~B 101 A | ~B 110 A - B 111 SLT 34

SET LESS THAN (SLT) EXAMPLE + 2 0 1 A B Cout Y 3 0 1 F2 F1:0 [N-1] S N N N N N N N N N 2 Zero Extend 35 • Configure a 32-bit ALU for the set if less than (SLT) operation. Suppose A = 25 and B = 32.

SET LESS THAN (SLT) EXAMPLE + 2 0 1 A B Cout Y 3 0 1 F2 F1:0 [N-1] S N N N N N N N N N 2 Zero Extend 36 • Configure a 32-bit ALU for the set if less than (SLT) operation. Suppose A = 25 and B = 32. – A is less than B, so we expect Y to be the 32-bit representation of 1 (0x00000001). – For SLT, F2:0 = 111. – F2 = 1 configures the adder unit as a subtracter. So 25 - 32 = -7. – The two’s complement representation of -7 has a 1 in the most significant bit, so S31 = 1. – With F1:0 = 11, the final multiplexer selects Y = S31 (zero extended) = 0x00000001.

SHIFTERS • Logical shifter: shifts value to left or right and fills empty spaces with 0’s • Ex: 11001 >> 2 = 00110 • Ex: 11001 << 2 = 00100 • Arithmetic shifter: same as logical shifter, but on right shift, fills empty spaces with the old most significant bit (msb). • Ex: 11001 >>> 2 = 11110 • Ex: 11001 <<< 2 = 00100 • Rotator: rotates bits in a circle, such that bits shifted off one end are shifted into the other end • Ex: 11001 ROR 2 = 01110 • Ex: 11001 ROL 2 = 00111 37

SHIFTER DESIGN A3:0 Y3:0 shamt1:0 >> 2 4 4 A3 A2 A1 A0 Y3 Y2 Y1 Y0 shamt1:0 00 01 10 11 S1:0 S1:0 S1:0 S1:0 00 01 10 11 00 01 10 11 00 01 10 11 2 38

SHIFTER Can be implemented with a mux s d yi En 1 0 3 2 1 0 xi+1 xi-1 xi s d xn x0 x-1 xn-1 yn-1 y0 En s / n l / r yi = xi-1 if En = 1, s = 1, and d = L = xi+1 if En = 1, s = 1, and d = R = xi if En = 1, s = 0 = 0 if En = 0

BARREL SHIFTER O or 1 shift O or 2 shift O or 4 shift x s0 s1 s2 y 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 shift

SHIFTERS AS MULTIPLIERS AND DIVIDERS • A left shift by N bits multiplies a number by 2N • Ex: 00001 << 2 = 00100 (1 × 22 = 4) • Ex: 11101 << 2 = 10100 (-3 × 22 = -12) • The arithmetic right shift by N divides a number by 2N • Ex: 01000 >>> 2 = 00010 (8 ÷ 22 = 2) • Ex: 10000 >>> 2 = 11100 (-16 ÷ 22 = -4) 41

MULTIPLIERS • Steps of multiplication for both decimal and binary numbers: • Partial products are formed by multiplying a single digit of the multiplier with the entire multiplicand • Shifted partial products are summed to form the result Decimal Binary 230 42 x 0101 0111 5 x 7 = 35 460 920 + 9660 0101 0101 0101 0000 x + 0100011 230 x 42 = 9660 multiplier multiplicand partial products result 42

4 X 4 MULTIPLIER x x A B P B3 B2 B1 B0 A3 B0 A2 B0 A1 B0 A0 B0 A3 A2 A1 A0 A3 B1 A2 B1 A1 B1 A0 B1 A3 B2 A2 B2 A1 B2 A0 B2 A3B3 A2B3 A1B3 A0B3 + P7 P6 P5 P4 P3 P2 P1 P0 0 P2 0 0 0 P1 P0 P5 P4 P3 P7 P6 A3 A2 A1 A0 B0 B1 B2 B3 4 4 8 43

DIVISION ALGORITHM • Q = A/B • R: remainder • D: difference R = A for i = N-1 to 0 D = R - B if D < 0 then Qi = 0, R’ = R // R < B else Qi = 1, R’ = D // R  B R = 2R’ 44

Binary Adder Design(COA).ppt

More Related Content

Similar to Binary Adder Design(COA).ppt

More from RohitPaul71

Recently uploaded

Binary Adder Design(COA).ppt