# Number-crunching Circuits (Part I) Randy H. Katz College of California, Berkeley Fall 2005 - PowerPoint PPT Presentation

Number-crunching Circuits (Part I) Randy H. Katz College of California, Berkeley Fall 2005

1 / 33

## Number-crunching Circuits (Part I) Randy H. Katz College of California, Berkeley Fall 2005

##### Presentation Transcript

1. Arithmetic Circuits(Part I)Randy H. KatzUniversity of California, BerkeleyFall 2005

2. Motivation Arithmetic circuits are excellent examples of comb. logic design • Time vs. Space Trade-offs Doing things fast requires more logic and thus more space Example: carry lookahead logic • Arithmetic Logic Units Critical component of processor datapath Inner-most "loop" of most computer instructions

3. Binary Number Representation Sign & Magnitude, Ones Complement, Twos Complement Binary Addition Full Adder Revisted ALU Design BCD Circuits Combinational Multiplier Circuit Design Case Study: 8 Bit Multiplier Sequential Multiplier Circuit Overview

4. Representation of positive numbers same in most systems Major differences are in how negative numbers are represented Three major schemes: sign and magnitude ones complement twos complement Assumptions: we'll assume a 4 bit machine word 16 different values can be represented roughly half are positive, half are negative Number Systems Representation of Negative Numbers

5. Number Systems Sign and Magnitude Representation High order bit is sign: 0 = positive (or zero), 1 = negative Three low order bits is the magnitude: 0 (000) thru 7 (111) Number range for n bits = +/-2 -1 Representations for 0 n-1

6. Cumbersome addition/subtraction Must compare magnitudes to determine sign of result Number Systems Sign and Magnitude Ones Complement N is positive number, then N is its negative 1's complement n 4 N = (2 - 1) - N 2 = 10000 -1 = 00001 1111 -7 = 0111 1000 Example: 1's complement of 7 = -7 in 1's comp. Shortcut method: simply compute bit wise complement 0111 -> 1000

7. Subtraction implemented by addition & 1's complement Still two representations of 0! This causes some problems Some complexities in addition Number Systems Ones Complement

8. Only one representation for 0 One more negative number than positive number Number Representations Twos Complement like 1's comp except shifted one position clockwise

9. Number Systems Twos Complement Numbers n N* = 2 - N 4 2 = 10000 7 = 0111 1001 = repr. of -7 sub Example: Twos complement of 7 4 Example: Twos complement of -7 2 = 10000 -7 = 1001 0111 = repr. of 7 sub Shortcut method: Twos complement = bitwise complement + 1 0111 -> 1000 + 1 -> 1001 (representation of -7) 1001 -> 0110 + 1 -> 0111 (representation of 7)

10. Number Representations Addition and Subtraction of Numbers Sign and Magnitude 4 + 3 7 0100 0011 0111 -4 + (-3) -7 1100 1011 1111 result sign bit is the same as the operands' sign when signs differ, operation is subtract, sign of result depends on sign of number with the larger magnitude 4 - 3 1 0100 1011 0001 -4 + 3 -1 1100 0011 1001

11. Number Systems Addition and Subtraction of Numbers Ones Complement Calculations 4 + 3 7 0100 0011 0111 -4 + (-3) -7 1011 1100 10111 1 1000 End around carry 4 - 3 1 0100 1100 10000 1 0001 -4 + 3 -1 1011 0011 1110 End around carry

12. Number Systems Addition and Subtraction of Binary Numbers Ones Complement Calculations Why does end-around carry work? Its equivalent to subtracting 2 and adding 1 n n n M - N = M + N = M + (2 - 1 - N) = (M - N) + 2 - 1 (M > N) n n -M + (-N) = M + N = (2 - M - 1) + (2 - N - 1) = 2 + [2 - 1 - (M + N)] - 1 n-1 M + N < 2 n n after end around carry: n = 2 - 1 - (M + N) this is the correct form for representing -(M + N) in 1's comp!

13. Number Systems Addition and Subtraction of Binary Numbers Twos Complement Calculations 4 + 3 7 0100 0011 0111 -4 + (-3) -7 1100 1101 11001 If carry-in to sign = carry-out then ignore carry if carry-in differs from carry-out then overflow 4 - 3 1 0100 1101 10001 -4 + 3 -1 1100 0011 1111 Simpler addition scheme makes twos complement the most common choice for integer number systems within digital systems

14. Number Systems Addition and Subtraction of Binary Numbers Twos Complement Calculations Why can the carry-out be ignored? -M + N when N > M: n n M* + N = (2 - M) + N = 2 + (N - M) n Ignoring carry-out is just like subtracting 2 n-1 -M + -N where N + M < or = 2 n n -M + (-N) = M* + N* = (2 - M) + (2 - N) = 2 - (M + N) + 2 n n After ignoring the carry, this is just the right twos compl. representation for -(M + N)!

15. Number Systems Overflow Conditions Add two positive numbers to get a negative number or two negative numbers to get a positive number -1 -1 +0 +0 -2 -2 1111 0000 +1 1111 0000 +1 1110 1110 0001 0001 -3 -3 +2 +2 1101 1101 0010 0010 -4 -4 1100 +3 1100 +3 0011 0011 -5 -5 1011 1011 0100 +4 0100 +4 1010 1010 -6 -6 0101 0101 +5 +5 1001 1001 0110 0110 -7 -7 +6 +6 1000 0111 1000 0111 -8 -8 +7 +7 -7 - 2 = +7! 5 + 3 = -8!

16. Number Systems Overflow Conditions 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 5 3 -8 -7 -2 7 Overflow Overflow 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 5 2 7 -3 -5 -8 No overflow No overflow Overflow when carry in to sign does not equal carry out

17. Networks for Binary Addition Half Adder With twos complement numbers, addition is sufficient Ai Ai 0 1 0 1 Ai Bi Sum Carry Bi Bi 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 Carry = Ai Bi Sum = Ai Bi + Ai Bi = Ai + Bi A i Sum B Half-adder Schematic i Carry

19. Networks for Binary Addition Full Adder S = CI xor A xor B CO = B CI + A CI + A B = CI (A + B) + A B

20. Networks for Binary Addition Full Adder/Half Adder Standard Approach: 6 Gates Alternative Implementation: 5 Gates + A B + CI (A xor B) = A B + B CI + A CI

21. Networks for Binary Addition Adder/Subtractor A B B A B B A B B A B B 3 3 3 2 2 2 1 1 1 0 0 0 Sel Sel Sel Sel 0 1 0 1 0 1 0 1 A B A B A B A B Add/Subtract CO + CI CO + CI CO + CI CO + CI S S S S S S S S 3 2 1 0 Overflow A - B = A + (-B) = A + B + 1

22. Networks for Binary Addition Carry Lookahead Circuits Critical delay: the propagation of carry from low to high order stages late arriving signal two gate delays to compute CO 4 stage adder final sum and carry

23. Networks for Binary Addition Carry Lookahead Circuits Critical delay: the propagation of carry from low to high order stages 1111 + 0001 worst case addition T0: Inputs to the adder are valid T2: 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 sum but last carry not ready until 6 delays later

24. Networks for Binary Addition Carry Lookahead Logic Carry Generate Gi = Ai Bi must generate carry when A = B = 1 Carry Propagate Pi = Ai xor Bi carry in will equal carry out here Sum and Carry can be reexpressed in terms of generate/propagate: Si = Ai xor Bi xor Ci = Pi xor Ci Ci+1 = Ai Bi + Ai Ci + Bi Ci = Ai Bi + Ci (Ai + Bi) = Ai Bi + Ci (Ai xor Bi) = Gi + Ci Pi

25. Networks for Binary Addition Carry Lookahead Logic Reexpress the carry logic as follows: C1 = G0 + P0 C0 C2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0 C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0 C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0 Each of the carry equations can be implemented in a two-level logic network Variables are the adder inputs and carry in to stage 0!

26. Networks for Binary Addition Carry Lookahead Implementation Adder with Propagate and Generate Outputs Increasingly complex logic