Transcript CS 315: Computer Logic and Digital Design

Chapter 5
Arithmetic Functions
• Arithmetic functions
– Operate on binary vectors
– Use the same subfunction in each bit position
• Can design functional block for subfunction and
repeat to obtain functional block for overall function
• Cell - subfunction block
• Iterative array - a array of interconnected cells
• An iterative array can be in a single dimension (1D)
or multiple dimensions
Henry Hexmoor
1
Adders
Henry Hexmoor
2
Block Diagram of a 1D Iterative Array
Figure 5-1
•
Example: n = 32
–
–
–
–
–
•
Number of inputs = ?
Truth table rows = ?
Equations with up to ? input variables
Equations with huge number of terms
Design impractical!
Iterative array takes advantage of the regularity to make design feasible
Henry Hexmoor
3
Half-Adder
5-2
• A 2-input, 1-bit width binary adder that performs the
following computations:
X
0
0
1
+Y
+0
+1
+0
CS
00
01
01
• A half adder adds two bits to produce a two-bit sum
• The sum is expressed as a
X Y C
sum bit , S and a carry bit, C
0 0 0
• The half adder can be specified
0 1 0
as a truth table for S and C 
1 0 0
1 1 1
Henry Hexmoor
4
1
+1
10
S
0
1
1
0
Half Adder
5-2
S = XY
C = XY
X
S
Figure 5-2
C
Y
Henry Hexmoor
5
Full-Adder
• A full adder is similar to a half adder, but includes a
carry-in bit from lower stages. Like the half-adder, it
computes a sum bit, S and a carry bit, C.
Z
0
0
0
– For a carry-in (Z) of
X
0
0
1
0, it is the same as
the half-adder:
+Y
+0
+1
+0
– For a carry- in
(Z) of 1:
Henry Hexmoor
0
1
+1
CS
00
01
01
10
Z
X
+Y
1
0
+0
1
0
+1
1
1
+0
1
1
+1
CS
01
10
10
11
6
Full Adder Table
A
0
0
0
0
1
1
1
1
Henry Hexmoor
B Cin
0 n
0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
S
0
1
1
0
1
0
0
1
7
C
0
0
0
1
0
1
1
1
Logic Optimization: Full-Adder
• Full-Adder Truth Table:
X Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
• Full-Adder K-Maps:
S
S
0
1
1
0
1
0
0
1
Y
0
X
C
0
0
0
1
0
1
1
1
1
4
1
1
5
3
1
1
C
Y
2
0
7
6
X
Z
4
1
1
5
Z
Henry Hexmoor
8
1
1
3
7
2
1
6
Equations: Full-Adder
• From the K-Map, we get:
S = XYZ+ XY Z+ XYZ+ XYZ
C = XY+XZ+YZ
• The S function is the three-bit XOR function:
S = XYZ
• The Carry bit C is 1 if both X and Y are 1 (the sum is 2), or
if the sum is 1 and a carry-in (Z) occurs. Thus C can be
re-written as:
C = X Y + ( X  Y) Z
• The term X·Y is carry generate.
• The term XY is carry propagate.
Henry Hexmoor
9
Full Adder
Henry Hexmoor
10
4 bit Full Adder
Henry Hexmoor
11
4-bit Ripple-Carry Binary Adder
• A four-bit Ripple Carry Adder made from four 1-bit Full Adders.
•
A carry 1 may propagate through many FAs to the most
significant bit just as a wave ripples outward…
B3
A3
FA
C4
S3
B2
C3
A2
FA
B1
C2
A1
FA
S2
S1
Figure 5-5
Henry Hexmoor
12
B0
C1
A0
FA
S0
C0
Carry Propagation & Delay
• One problem with the addition of binary numbers is
the length of time to propagate the ripple carry from
the least significant bit to the most significant bit.
• The gate-level propagation path for a 4-bit ripple
carry adder of the last example:
A3
B3
A2
C3
A1
B2
C2
B1
A0
C1
B0
C0
C4
S3
S2
S1
S0
• Note: The "long path" is from A0 or B0 though the
circuit to S3.
Henry Hexmoor
13
Carry Lookahead
• Given Stage i from a Full Adder, we
know that there will be a carry
generated when Ai = Bi = "1", whether
or not there is a carry-in.
• Alternately, there will be
a carry propagated if the
“half-sum” is "1" and a
carry-in, Ci occurs.
• These two signal conditions
are called generate, denoted
as Gi, and propagate, denoted
as Pi respectively and are
identified in the circuit:
Gi
Pi
Ci+1
Henry Hexmoor
Ai Bi
14
Si
Ci
Carry Lookahead (continued)
• In the ripple carry adder:
– Gi, Pi, and Si are local to each cell of the adder
– Ci is also local each cell
• In the carry lookahead adder, in order to reduce the
length of the carry chain, Ci is changed to a more global
function spanning multiple cells
• Defining the equations for the Full Adder in term of the Pi
and Gi:
S i = Pi  Ci
Pi = A i  B i
Henry Hexmoor
Ci +1 = G i + Pi Ci
Gi = A i Bi
15
Group Carry Lookahead Logic
• Figure 5-6 in the text shows shows the implementation of
these equations for four bits. This could be extended to
more than four bits; in practice, due to limited gate fan-in,
such extension is not feasible.
• Instead, the concept is extended another level by
considering group generate (G0-3) and group propagate
(P0-3) functions:
• Using these two equations:
G 0- 3 = G 3 + P3 G 2 + P3 P2 G1 + P3 P2 P1 P0 G 0
P0- 3 = P3 P2 P1 P0
C4 = G 0- 3 + P0- 3 C0
• It is possible to have four 4-bit adders use one of the same
carry lookahead circuit to speed up 16-bit addition
Henry Hexmoor
16
Subtraction table
bin
0
0
0
0
1
1
1
1
Henry Hexmoor
x
0
0
1
1
0
0
1
1
y
0
1
0
1
0
1
0
1
bout
0
1
0
0
1
1
0
1
17
D
0
1
1
0
1
0
0
1
Half subtractor
X
Y
Half
Subtractor
D
Difference
D
X
Y
B-OUT
B-out
Henry Hexmoor
18
Full Subtraction circuit for A - B
D = (A  B)  BI
BO = A’(B + BI )+ A B BI
Henry Hexmoor
19
Binary Subtraction
5-3
Subtraction of two n-digit numbers, M – N
1. Subtract the subtrahend N from the minuend M.
2. if no end borrow occurs, then M>= N,
and the result is nonnegative and correct.
3. If an end borrow occurs, then N > M,
and the difference, M – N + 2n, is subtracted from 2n,
and a minus sign is appended to the result.
See Example 5-1 and Figure 5-7
Henry Hexmoor
0
1001
- 0111
A
0010
20
1
0100
- 0111
1101
10000
- 1101
(-) 0011
Adder-subtractor
A
B
Binary adder
Borrow
Complement
Subtract/Add
Binary subtractor
Selective
2's complementer
0
1
Quadruple
2-to-1
S
multiplexer
Result
Figure 5-7
Henry Hexmoor
21
Complements
5-3
1’s complement of a binary n digit number N is obtained by changing
all 1’s to 0 and all 0’s to 1.
2’s complement of a binary n digit number N is obtained by
adding 1 to its 1’s complement.
e.g.,
1’s complement:
1011001  0100110
0001111  1110000
2’s complement:
10110  010011 + 1 = 010100
Henry Hexmoor
22
Alternate 2’s Complement Method
• Given: an n-bit binary number, beginning at the least
significant bit and proceeding upward:
– Copy all least significant 0’s
– Copy the first 1
– Complement all bits thereafter.
• 2’s Complement Example:
10010100
– Copy underlined bits:
100
– and complement bits to the left:
01101100
Henry Hexmoor
23
Subtraction with
complements
5-3
1. Add the 2’s complement of the subtrahend N to the minuend M.
2. If M>= N, the sum produces an end carry, 2n.
Discard the end carry, leaving result M – N.
1. If M < N, the sum does not produce an end carry
since it is equal to 2n – (N – M), the 2’s complement of N –M.
Perform a correction, taking the 2’s complement of the sum
and placing a minus sign in front to obtain the result – (N – M).
OR Gate
A
Henry Hexmoor
24
Unsigned 2’s Complement Subtraction
Example 1
• Find 010101002 – 010000112
1
01010100
01010100
2’s comp
– 01000011
+ 10111101
00010001
• The carry of 1 indicates that no correction of the
result is required.
Henry Hexmoor
25
Binary Adder-Subtractors
5-4
S = 0, adder
S = 1, subtractor
B3
A3
Figure 5-8
B2
A2
B1
A1
B0
A0
S
FA
C3
FA
C2
C1
FA
A
C4
Henry Hexmoor
S3
S2
S1
S0
26
C0
OR Gate
FA
Overflow Detection
• Overflow occurs if n + 1 bits are required
to contain the result from an n-bit addition
or subtraction
• Overflow can occur for:
– Addition of two operands with the same sign
– Subtraction of operands with different signs
• Detection can be performed by examining
the result signs which should match the
signs of the top operand
Henry Hexmoor
27
Two bit Multiplication
a
b
ab
0
0
0
0
1
0
1
0
0
1
1
1
Henry Hexmoor
28
a
b
ab
0
0
0
0
1
0
1
0
0
1
1
1
Three bit Multiplication
• Partial products are: 101 × 1, 101 × 1,
and 101 × 0
1 0
• Note that the partial product
× 0 1
summation for n digit, base 2
1 0
numbers requires adding up
1 0 1
to n digits (with carries) in
0 0 0
a column.
0 0 1 1 1
• Note also n × m digit
multiply generates up to an m + n digit
result (same as decimal).
Henry Hexmoor
29
1
1
1
1
Multiplier Boolean Equations
• We can also make an n × m “block” multiplier and use that to
form partial products.
• Example: 2 × 2 – The logic equations for each partial-product
binary digit are shown below:
• We need to "add" the columns to get
the product bits P0, P1, P2, and P3.
• Note that some columns may generate carries.
Henry Hexmoor
+
P3
b1
b0
a1
a0

(a0 . b1) (a0 . b0)
(a1. b1) (a1 . b0)
P2
P1
P0
30
A 2x2 binary multiplier
•
•
•
The AND gates produce the
partial products.
For a 2-bit by 2-bit multiplier, we
can just use two half adders to
sum the partial products. In
general, though, we’ll need full
adders.
Here C3-C0 are the product, not
carries!
x
+
B1
B0
A1
A0
A 0B 1
A 0B 0
A 1B 1
A 1B 0
C2
C1
C3
Henry Hexmoor
HA
C0
31
HA
Multiplication: a special case
• In decimal, an easy way to multiply by 10 is to shift all the digits to
the left, and tack a 0 to the right end.
128 x 10 = 1280
• We can do the same thing in binary. Shifting left is equivalent to
multiplying by 2:
11 x 10 = 110
(in decimal, 3 x 2 = 6)
• Shifting left twice is equivalent to multiplying by 4:
11 x 100 = 1100 (in decimal, 3 x 4 = 12)
• As an aside, shifting to the right is equivalent to dividing by 2.
110 ÷ 10 = 11
Henry Hexmoor
(in decimal, 6 ÷ 2 = 3)
32
Other Arithmetic Functions
5-7
• Convenient to design the functional blocks by
contraction - removal of redundancy from
circuit to which input fixing has been applied
• Functions
–
–
–
–
–
Incrementing
Decrementing
Multiplication by Constant
Division by Constant
Zero Fill and Extension
Henry Hexmoor
33
HW 5
1. Perform the indicated subtraction with the
following unsigned binary numbers by taking
the 2’s complement of the subtrahend:
(a) 1111 – 10000, (b) 10110 – 1111, (c) 101111 –
1011110, (d) 101 – 101000
(Q 5-4)
2. Design a circuit that multiplies two 4-bit
unsigned numbers. Use AND gates and binary
adders. (Q 5-18)
Henry Hexmoor
34
Henry Hexmoor
35