Chapter 5 Arithmetic Functions Computer Organisation and Architecture

Chapter 5 Arithmetic Functions Computer Organisation and Architecture

1. Henry Hexmoor 1
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

2. Henry Hexmoor 2
Adders

3. Henry Hexmoor 3
Cell n-1
X
n-1
Y
n-1
A
n-1B
n-1
C
n-1
X
n
Y
n
Cell 1
X
1
Y
1
A
1
C
1
Cell 0
X
0
Y
0
B
0
C
0
X
2
Y
2
Block Diagram of a 1D Iterative Array
•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
Figure 5-1

4. Henry Hexmoor 4
Half-Adder
5-2
•A 2-input, 1-bit width binary adder that performs the
following computations:
•A half adder adds two bits to produce a two-bit sum
•The sum is expressed as a
sum bit , S and a carry bit, C
•The half adder can be specified
as a truth table for S and C 
X 0 0 1 1
+ Y + 0 + 1 + 0 + 1
C S 0 0 0 1 0 1 1 0

X Y C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

5. Henry Hexmoor 5
Half Adder
5-2
XX
YY
SS
CC
YXC
YXS


Figure 5-2

6. Henry Hexmoor 6
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.
–For a carry-in (Z) of
0, it is the same as
the half-adder:
–For a carry- in
(Z) of 1:
Z 0 0 0 0
X 0 0 1 1
+ Y+ 0+ 1+ 0+ 1
C S0 00 10 11 0
Z 1 1 1 1
X 0 0 1 1
+ Y+ 0+ 1+ 0+ 1
C S0 11 01 01 1

7. Henry Hexmoor 7
Full Adder Table
ABCin
n
SC
00000
00110
01010
01101
10010
10101
11001
11111

8. Henry Hexmoor 8
Logic Optimization: Full-Adder
•Full-Adder Truth Table:
•Full-Adder K-Maps:
XYZC S
0000 0
0010 1
0100 1
0111 0
1000 1
1011 0
1101 0
1111 1
X
Y
Z
0 1 3 2
4 5 7 6
1
1
1
1
S
X
Y
Z
0 1 3 2
4 5 7 6
1 11
1
C

9. Henry Hexmoor 9
Equations: Full-Adder
•From the K-Map, we get:
•The S function is the three-bit XOR function:
•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:
•The term X·Y is carry generate.
•The term XY is carry propagate.
ZYZXYXC
ZYXZYXZYXZYXS


ZYXS 
Z)YX(YXC 

10. Henry Hexmoor 10
Full Adder

11. Henry Hexmoor 11
4 bit Full Adder

12. Henry Hexmoor 12
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…
B
3 A
3
FA
B
2 A
2
FA
B
1
S
3C
4
C
0
C
3 C
2 C
1
S
2 S
1 S
0
A
1
FA
B
0 A
Figure 5-5

13. Henry Hexmoor 13
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:
•Note: The "long path" is from A
0
or B
0
though the circuit to S
3
.
A
3
B
3
S
3
B
2
S
2
B
1
S
1 S
0
B
0
A
2 A
1 A
0
C
4
C
3 C
2 C
1 C
0

14. Henry Hexmoor 14
Carry Lookahead
•Given Stage i from a Full Adder, we
know that there will be a carry
generated when A
i = B
i = "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, C
i
occurs.
•These two signal conditions
are called generate, denoted
as G
i, and
propagate, denoted
as P
i respectively and are
identified in the
circuit:
A
iB
i
C
i
C
i+1
G
i
P
i
S
i

15. Henry Hexmoor 15
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, C
i
is changed to a more global
function spanning multiple cells
•Defining the equations for the Full Adder in term of the P
i
and G
i
:
iiiiii BAGBAP 
iii1iiii CPGCCPS 


16. Henry Hexmoor 16
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 (G
0-3
) and group propagate (P
0-3
) functions:
•Using these two equations:
•It is possible to have four 4-bit adders use one of the same
carry lookahead circuit to speed up 16-bit addition
012330
0012312323330
PPPPP
GPPPPGPPGPGG




030304 CPGC 


17. Henry Hexmoor 17
Subtraction table
b
in
x y b
out
D
0 0 0 0 0
0 0 1 1 1
0 1 0 0 1
0 1 1 0 0
1 0 0 1 1
1 0 1 1 0
1 1 0 0 0
1 1 1 1 1

18. Henry Hexmoor 18
Half subtractor
Half
Subtractor
X
Y
D
B-OUT
X
Y
Difference D
B-out

19. Henry Hexmoor 19
Full Subtraction circuit for A - B
D = (A B) BI
BO = A’(B + BI )+ A B BI


20. Henry Hexmoor 20
Binary Subtraction
5-3
A
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 + 2
n
, is subtracted from 2
n
,
and a minus sign is appended to the result.
See Example 5-1 and Figure 5-7 0 1
1001 0100
 0111  0111
0010 1101
10000
1101
() 0011

21. Henry Hexmoor 21
A B
Binary adder Binary subtractor
Selective
2's complementer
Quadruple 2-to-1
multiplexer
Result
Borrow
Complement
S
0 1
Subtract/Add
Figure 5-7
Adder-subtractor

22. Henry Hexmoor 22
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

23. Henry Hexmoor 23
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

24. Henry Hexmoor 24
Subtraction with
complements
5-3
OR Gate
A
1.Add the 2’s complement of the subtrahend N to the minuend M.
2.If M>= N, the sum produces an end carry, 2
n
.
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 2
n
– (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).

25. Henry Hexmoor 25
Unsigned 2’s Complement Subtraction
Example 1
•Find 01010100
2
– 01000011
2
01010100 01010100
– 01000011 + 10111101
00010001
•The carry of 1 indicates that no correction of the
result is required.
1
2’s comp

26. Henry Hexmoor 26
Binary Adder-Subtractors
5-4
OR Gate
A
Figure 5-8
FA FA FA FA
S
B
3
C
3
S
2 S
1 S
0S
3C
4
C
2 C
1 C
0
A
3 B
2 A
2 B
1 A
1 B
0 A
0
S = 0, adder
S = 1, subtractor

27. Henry Hexmoor 27
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

28. Henry Hexmoor 28
Two bit Multiplication
abab
000
010
100
111
aba

b
000
010
100
111

29. Henry Hexmoor 29
Three bit Multiplication
•Partial products are: 101 × 1, 101 × 1,
and 101 × 0
•Note that the partial product
summation for n digit, base 2
numbers requires adding up
to n digits (with carries) in
a column.
•Note also n × m digit
multiply generates up to an m + n digit
result (same as decimal).
101
×011
101
101
000
001111

30. Henry Hexmoor 30
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.
b
1
b
0
 a
1 a
0
(a
0
b
1
)(a
0

b
0
)
+ (a
1

b
1
)(a
1
b
0
)
P
3
P
2
P
1
P
0

31. Henry Hexmoor 31
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 C
3-C
0 are the product, not
carries!
B1 B0
x A1 A0
A0B1A0B0
+ A1B1A1B0
C3 C2 C1 C0
HAHA

32. Henry Hexmoor 32
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 (in decimal, 6 ÷ 2 = 3)

33. Henry Hexmoor 33
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

34. Henry Hexmoor 34
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)

35. Henry Hexmoor 35