Arithmetic Circuits • Number representations • Addition, subtraction • Performance issues -- ripple carry -- carry bypass -- carry skip -- carry lookahead 6.111 Fall 2008 1 Lecture 8 Lab #3 due Thursday, report next Tuesday, no LPSets this weekEncoding numbers ∑−==1n0iiib2v211 210 29 28 27 26 25 24 23 22 21 20 0 1 1 1 1 1 0 1 0 0 0 0 03720 Octal - base 8 000 - 0 001 - 1 010 - 2 011 - 3 100 - 4 101 - 5 110 - 6 111 - 7 0x7d0 Hexadecimal - base 16 0000 - 0 1000 - 8 0001 - 1 1001 - 9 0010 - 2 1010 - a 0011 - 3 1011 - b 0100 - 4 1100 - c 0101 - 5 1101 - d 0110 - 6 1110 - e 0111 - 7 1111 - f Oftentimes we will find it convenient to cluster groups of bits together for a more compact notation. Two popular groupings are clusters of 3 bits and 4 bits. It is straightforward to encode positive integers as a sequence of bits. Each bit is assigned a weight. Ordered from right to left, these weights are increasing powers of 2. The value of an n-bit number encoded in this fashion is given by the following formula: = 200010 Seems natural to me! 0 2 7 3 0 d 7 6.111 Fall 2008 2 Lecture 8• Three common schemes: – sign-magnitude, ones complement, twos complement • Sign-magnitude: MSB = 0 for positive, 1 for negative – Range: -(2N-1 – 1) to +(2N-1 – 1) – Two representations for zero: 0000… & 1000… – Simple multiplication but complicated addition/subtraction Binary Representation of Numbers How to represent negative numbers? _ • Ones complement: if N is positive then its negative is N – Example: 0111 = 7, 1000 = -7 – Range: -(2N-1 – 1) to +(2N-1 – 1) – Two representations for zero: 0000… & 1111… – Subtraction is addition followed by ones complement 6.111 Fall 2008 3 Lecture 8Representing negative integers To keep our arithmetic circuits simple, we’d like to find a representation for negative numbers so that we can use a single operation (binary addition) when we wish to find the sum of two integers, independent of whether they are positive are negative. We certainly want A + (-A) = 0. Consider the following 8-bit binary addition where we only keep 8 bits of the result: 11111111 + 00000001 00000000 which implies that the 8-bit representation of -1 is 11111111. More generally -A = 0 - A = (-1 + 1)- A = (-1 - A) + 1 = ~A + 1 € 1 1 1 1 1 1 1 1− A7A6A5A4A3A2A1A0A7A6A5A4A3A2A1A0~ means bit-wise complement Negation: Complement and add 1 6.111 Fall 2008 4 Lecture 8Signed integers: 2’s complement 20 21 22 23 … 2N-2 -2N-1 … … N bits 8-bit 2’s complement example: 11010110 = –27 + 26 + 24 + 22 + 21 = – 128 + 64 + 16 + 4 + 2 = – 42 If we use a two’s complement representation for signed integers, the same binary addition mod 2n procedure will work for adding positive and negative numbers (don’t need separate subtraction rules). The same procedure will also handle unsigned numbers! By moving the implicit location of “decimal” point, we can represent fractions too: 1101.0110 = –23 + 22 + 20 + 2-2 + 2-3 = – 8 + 4 + 1 + 0.25 + 0.125 = – 2.625 “sign bit” “decimal” point Range: – 2N-1 to 2N-1 – 1 6.111 Fall 2008 5 Lecture 8Sign extension Consider the 8-bit 2’s complement representation of: -5 = ~00000101 + 1 = 11111010 + 1 = 11111011 42 = 00101010 What is their 16-bit 2’s complement representation? 42 = ________00101010 -5 = ________11111011 42 = 0000000000101010 -5 = ________11111011 42 = 0000000000101010 -5 = 1111111111111011 Extend the MSB (aka the “sign bit”) into the higher-order bit positions 6.111 Fall 2008 6 Lecture 8Adder: a circuit that does addition Here’s an example of binary addition as one might do it by “hand”: 1101 + 0101 10010 1 0 1 1 Carries from previous column Adding two N-bit numbers produces an (N+1)-bit result If we build a circuit that implements one column: we can quickly build a circuit two add two 4-bit numbers… “Ripple- carry adder” 6.111 Fall 2008 7 Lecture 8“Full Adder” building block A B C S CO 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 € S = A ⊕ B ⊕ C€ CO = ABC + ABC + ABC + ABC= (A + A)BC + (B + B)AC + AB (C + C)= BC + AC + ABThe “half adder” circuit has only the A and B inputs 6.111 Fall 2008 8 Lecture 8Subtraction: A-B = A + (-B) Using 2’s complement representation: –B = ~B + 1 ~ = bit-wise complement So let’s build an arithmetic unit that does both addition and subtraction. Operation selected by control input: But what about the “+1”? 6.111 Fall 2008 9 Lecture 8Condition Codes Besides the sum, one often wants four other bits of information from an arithmetic unit: To compare A and B, perform A–B and use condition codes: Signed comparison: LT N⊕V LE Z+(N⊕V) EQ Z NE ~Z GE ~(N⊕V) GT ~(Z+(N⊕V)) Unsigned comparison: LTU ~C LEU ~C+Z GEU C GTU ~(~C+Z) Z (zero): result is = 0 big NOR gate N (negative): result is < 0 SN-1 C (carry): indicates an add in the most significant position produced a carry, e.g., 1111 + 0001 from last FA 11 −⊕−=NCINNCOUTVV (overflow): indicates that the answer has too many bits to be represented correctly by the result width, e.g., 0111 + 0111 1 1 1 1 1 1 - - - + - - - = N S N B N A N S N B N A V 6.111 Fall 2008 10 Lecture 8Condition Codes in Verilog 6.111 Fall 2008 11 Lecture 8 Z (zero): result is = 0 N (negative): result is < 0 C (carry): indicates an add in the most significant position produced a carry, e.g., 1111 + 0001 V (overflow): indicates that the answer has too many bits to be represented correctly by the result width, e.g., 0111 + 0111 wire [31:0] a,b,s; wire z,n,v,c; assign {c,s} = a + b; assign z = ~|s; assign n = s[31]; assign v = a[31]^b[31]^s[31]^c; Might be better to use sum-of-products formula for V from previous slide if using LUT implementation (only 3 variables instead of 4).Modular Arithmetic The Verilog arithmetic operators (+,-,*) all produce full-precision results, e.g., adding two 8-bit numbers produces a 9-bit result. In many designs one chooses a “word size” (many computers use 32 or 64 bits) and all arithmetic results are truncated to that number of bits, i.e., arithmetic is performed modulo 2word size. Using
View Full Document
Unlocking...