Transcript Arithmetic Circuits

Arithmetic Circuits I
Iterative Combinational Circuits
• Like a hierachy, except functional
blocks per bit
2
Adders
• Great example of Iterative design
• Design a 1-bit adder circuit, then
expand to n-bit adder
• Look at
♦ Half adder – which is a 2-bit adder
♦ Inputs are bits to be added
• Outputs: result and possible carry
♦ Full adder – includes carry in, really a 3-bit
adder
3
Half Adder
• S=XY
• C = XY
Fig. 4-2
4
Full Adder
• Three inputs. Two are operand bits,
third is Cin
• Two outputs: sum and carry
5
K Map for S
• What is this?
In a half adder the sum bit:
S=XY
6
K Map for C
In a half adder the carry bit:
C = XY
7
Using two half Adders to Build a Full
Adder
• Full adder functions
• Half adder functions
S=XY
C = XY
8
Two Half Adders (and an OR)
X Y
XY
 X Y  Z
Z (X Y )
 XY  Z (X Y )
Fig. 4-4
9
Ripple-Carry Adder
• Straightforward – connect full adders
• C4 : Chain carry-out to carry-in of FA
of bits A4 & B4
♦ C0 in case this is part of larger chain
♦ otherwise just set to zero
10
Hierarchical 4-Bit Adder
•
•
•
•
We can easily use hierarchy here
Design half adder
Use in full adder
Use full adder in 4-bit adder
11
Binary Subtraction
• Example:
♦ Let M = (19)10 ; N = (30)10 ; How is M-N computed?
• In decimal notation: (19)10 – (30)10 = - (11)10
• In binary: (10011)2 - (11110)2 = - (01011)2
12
Using 2’s & 1’s Complement
Representation of Signed
Numbers
• People use complemented
interpretation for signed numbers
♦ 1’s complement
♦ 2’s complement
13
1’s Complement
• Given: binary number N with n digits
1’s complement is defined as
(2n – 1) - N
• Note that (2n – 1) is a number with n
bits, all of them 1
♦ For n = 4, (2n – 1) = (15)10 = 1111
14
Example:
Find 1’s Complement of N =101 1001
•1’s Complement of N is (2n – 1) - N
n= 7; 2n - 1
1
1
1
1
1
1
1
-N
1’s Compl.
1
0
0
1
1
0
1
0
0
1
0
1
1
0
• Notice that 1’s complement is
complement of each bit
15
2’s Complement
• Given: binary number N with n digits
2’s complement defined as
2n – N for N  0
0 for N = 0
• Note that since 1’s complement is
(2n – 1) – N
♦ 2’s complement is just a 1 added to 1’s
complement
16
Example:
Find 2’s Complement of N =101 1001
• 2’s Complement of N is 2n - N
N
1
0
1
1
0
0
1
1’s Compl.
0
1
0
0
1
1
0
+1
0
0
0
0
0
0
1
2’s Compl.
0
1
0
0
1
1
1
• To find 2’s complement of N
♦ Find is 1’s complement of N then add 1
17
Important Property
• Complement of a complement
generates original number
18
Subtraction Using 2s Complement:
Compute M-N
1. Add 2’s complement of N to M
♦
M + (2n – N) = { M – N + 2n } = F
2. If M  N, this addition will generate a carry, 2n
•
Discard carry; the result gives the answer of M-N which is
positive
3. If M < N, no carry; M-N is negative; the
answer is –(N-M). To compute the answer:
•
Take 2’s complement of F
•
•
2n – F = 2n - { M – N + 2n } = N-M
Place minus sign in front { - (N-M) }; This is the answer
4. Hence to compute (M-N): do 1 & 2 if M  N;
OR 1 & 3 If M < N
19
Compute M-N;
Example 1: M > N
• M = (84)10= (101 0100)2
• N = (67)10 = (100 0011)2;
♦ 2’s comp N = ( 011 1100 ) + 1 = 011 1101
M
1 0 1 0 1 0 0
+ 2’s comp N
Sum
0 1 1 1 1 0 1
0 0 1 0 0 0 1
1
1710
M > N; Carry generated; Discard carry; Result is positive M - N
20
Compute M-N; Example 2: M < N;
M = 6710 = 100 0011; N = 8410 = 101 0100
• M = 100 0011 minus N = 101 0100
M
1 0 0 0 0 1 1
+ 2’s comp N
Sum
0 1 0 1 1 0 0
1 1 0 1 1 1 1
• No end carry
♦ Answer: - (2’s complement of Sum)
• Answer: - 0010001
We said numbers are unsigned. What does this mean?
How is -1710 represented?
21
Subtractor
•
Compute M-N
♦ Add 2’s complement of N to M:
M + (2n – N)
• If M >= N, need only “one adder” and a
“complementer of N” to do the
subtraction.
• If M < N, we also need to take 2’s
complement of adder’s output to produce
magnitude of result
2n -{ M + (2n – N)} = N-M
22
Adder-Subtractor Design: (A+B)
OR (A-B)
S is low for add,
high for subtract
Inverts each bit
of B if S is 1
Add 1 to
make 2’s
complement
Fig. 4-7
• Output is result if A >= B; Discard carry
• Output is 2’s complement of result if B > A
23
Signed Binary
1. Signed magnitude
♦ Left bit is sign, 0 positive, 1 negative
♦ Other bits are number
2. 2’s complement
3. 1’s complement
24
Example in 8-bit byte
• Represent -910 = -(0000 1001) in different
ways
“Signed magnitude” of - (0000 1001) is
1000 1001
“Signed 1’s Complement” of - (0000 1001) is
1111 0110
“Signed 2’s Complement” of - (0000 1001) is
1111 0111
25
Observations (assume 4-bit
numbers)
• 1’s C and
Signed
Magnitude have
two zeros
• 2’s C has more
negative
numbers than
positive
• All negative
numbers have 1
in highest-order
bit
26
Advantages/Disadvantages
• Signed magnitude & One’s
complement has a positive and
negative zero
• Two’s complement is most popular
♦ Arithmetic operations easy
27
Two’s Complement
• Addition easy on any combination
of positive and negative numbers
• To compute A - B
♦ Take 2’s complement of subtrahend B to
produce -B
♦ Add to A
• This performs A + ( -B), same as A – B
28
Examples
•
•
Assume we use 2’s complement
representation of signed numbers
Store each number in 8 bits
6 = (0000 0110) ; 13 = (0000 1101)
-6 = (1111 1010) ; -13 = (1111 0011)
•
•
Addition
♦
♦
♦
♦
6 + 13
-6 + 13
6 + (- 13)
(-6) + (-13)
Subtraction
♦ -6 - (-13)
♦ 6 - (- 13)
29
Overflow
• Overflow means that result can not be
represented with the number of bits
used
• Two cases of overflow for addition of
signed numbers
♦ Two large positive numbers overflow
into sign bit
• Not enough bits for result
♦ Two large negative numbers added
• Same – Not enough bits for result
30
Examples:
Work on Board
Assume
1- We use “2’s complement representation”
of signed numbers
2- Store each number in 4 bits : b3 b2 b1 b0
31
Example 1
• 7+7
• Overflow: can not represent 14 using
only 4 bits
• Generates NO CARRY, C4 = 0
32
Example 2
• -7 - 7
• Overflow: can not represent -14
using only 4 bits
• Generates CARRY, C4 = 1
33
Example 3
• 4+4
• Overflow: can not represent 8 using
only 4 bits
• Generates NO CARRY, C4 = 0
34
Example 4
• 7–7
• NO Overflow
• Generates CARRY, C4 = 1
35
Overflow Detection
• Condition for overflow:
♦ either Cn-1 or Cn is high, but not both
Fig.
5-9 Overflow Detection for Addition and Subtraction
Fig.
4-8
---------------------------------------------------------
♦ 7 + 7; only Cn-1 (C3) is high ; overflow
♦ -7 - 7; only Cn (C4) is high ; overflow
♦ 4 + 4; only Cn-1 (C3) is high ; overflow
♦ 7 – 7; BOTH Cn-1 & Cn (C4 & C3) are high; no
overflow
36