Transcript Digital Fundamentals

Chapter 6 Digital Arithmetic:
Operations and Circuits
ECE 221 Intro. Digital Systems
Fall Semester 2002
ECE Department, UMASS-Amherst
Prof. Hill
Prof. Gong
Objectives
• Addition, subtraction, multiplication, and division
of two binary numbers.
• Addition and subtraction of hexadecimal numbers
• Difference between binary addition and OR addition.
• Comparison among three different systems for
representing signed numbers.
• Manipulate signed binary numbers using the 2’s –
complement system.
• BCD adder circuit and addition process.
• Basic operation of an arithmetic/logic unit
6-1 Binary Addition
• The addition of two binary numbers is performed in
exactly the same manner as the addition of decimal
numbers.
• Least-significant-digit first.
• “Carry” of 1 into the next position may be needed.
• 4 different cases for binary addition
00  0
1 0  1
1  1  10  0  carry of 1 into next position
1  1  1  11  1  carry of 1 into next position
•The operations of subtraction, multiplication, and division
actually use only addition as their basic operation
Example
011 (3)
 110(6)
1001(9)
 1111(15)
11.011(3.375)
 10.110(2.750)
1001(9)
11000(24)
110.001(6.125)
Review Question
• Add the following pairs of binary numbers.
– 10110+00111
– 011.101+010.010
– 10001111+00000001
Representing signed numbers (6.2)
Considerations: representing both positive
and negative numbers; efficient computation.
Sign-magnitude system
Sign-magnitude system: represents + and –
numbers, but we need to design special circuits
to add positive and negative numbers.
ex: 5 + (-5) = 0
use 8 bit signed-binary numbers and add using
full-adder circuits :
0 0 0 0 0 1 0 1 ( 5)
+
1 0 0 0 0 1 0 1 (-5)
_____________________
1 0 0 0 1 0 1 0 (-10)
1’s complement system
– Change each 0 to 1, and each 1 to 0.
– Example
(45)
1 0 1 1 0 1
original binary number

(-45)
0

1

0

0

1

0
complement each bit
1 0 1 1 0 1 (45)
+ 0 1 0 0 1 0 (-45)
____________________
1 1 1 1 1 1
Add one to this result, get zero.
2’s complement of a binary number:
– Take the 1’s complement of the number
– Add 1 to the least-significant-bit position
101101
010010

1
010011
binary equivalent of 45
complement each bit to form 1' s complement
add 1 to form 2' s complement
2' s complement of original binary number
Representing signed numbers
using 2’s complement form
• If the number is positive, the magnitude is
represented in its positional-weighted binary form,
and a sign bit of 0 is placed in front of the MSB.
• If the number is negative, the magnitude is
represented in its 2’s complement form, and a sign
bit of 1 is placed in front of the MSB.
example
Example
• Represent each of the following signed decimal
numbers as a signed binary number in the 2’scomplement system. Use a total of five bits including
the sign bit.
(a) +13 (b) –9 (c) +3 (d) –2 (e) -8
Negation
• Negation is the operation of converting a postive
number to its negative equivalent or a negative
number to its positive equivalent.
• We negate a signed binary number by 2’s-complementing
it.
• Example
– Each of the following numbers is a signed binary
number in the 2’s-complement system. Determine the
decimal value in each case:
(a)01100 (b) 11010 (c)10001
Special case in 2’s-complement
representation
• Whenever a signed number has a 1 in the sign bit and
all 0s for the magnitude bits, its decimal equivalent
is –2N, where N is the number of bits in the
magnitude.
• The complete range of values that can be represented
in the 2’s-complement system having N magnitude bits
is –2N to +(2N - 1).
• What is the range of unsigned decimal values that can
be represented in a byte?
• What is the range of signed decimal values that can
be represented in a byte?
Review Questions
•
•
•
•
•
•
•
Represent each of the following values as an eight-bit
signed number in the 2’s-complement system
(a)+13 (b) –7 (c)-128
Each of the following is a signed binary number in the 2’scomplement system. Determine the decimal equivalent for
each.
(a)100011 (b)1000000 (c)01111110
What range of signed decimal values can be represented in
12 bits(including the sign bit)?
How many bits are required to represent decimal values
ranging from –50 to +50?
What is the largest negative decimal value that can be
represented by a two-byte number?
Perform the 2’s-complement operation on each of the
following.
(a)10000 (b)10000000 ©1000
Define the negation operation
6-3 Addition in the 2’scomplement system
• Case I: Two Postive Numbers.
+9
+4


0
0
0
Sign bits
1001
0100
1101
(augend)
(addend)
(sum = +13)
Addition, cont.
• Case II: Positive Number and Smaller Negative Number
+9  0 1001 (augend)
-4  1 1100 (addend)
1 0 0101
Sign bits
This carry is disregarded; the result
is 01001(sum=+5)
Addition, cont.
• Case III: Positive Number and Larger Negative Number
-9 
+4 
10111
00100
11011
(sum = -5)
Negative sign bit
Addition, cont.
• Case IV: two negative Numbers
-9  10111
-4  11100
1 10011
Sign bit
This carry is disregarded; the result is
10011(sum =-13)
Addition, cont.
• Case V: Equal and Opposite Numbers
-9  10111
+9  01001
0
100000
Disregard; the result is
00000(sum = +0)
Review Questions
• Assume the 2’s complement system for both questions
– True or False: Whenever the sum of two signed
binary numbers has a sign bit of 1, the magnitude
of the sum is in 2’s complement form.
– Add the following pairs of signed numbers. Express
the sum as a signed binary number and as a decimal
number
• (a) 100111+111011
• (b) 100111+011001
6-4 Subtraction in the 2’scomplement System
• The procedure for subtracting one binary number(the
subtrahend) from another binary number(the minuend)
– Negate the subtrahend. This will change the
subtrahend to its equivalent value of opposite
sign.
– Add this to the minuend. The result of this
addition will represent the difference between the
subtrahend and the minuend.
Arithmetic Overflow
• When two positive or two negative numbers are being
added, an overflow could occur if there is a carry
happening to the sign-bit position.
• Overflow can occur when the minuend and subtrahend
have different signs.
Review Questions
• Perform the subtraction on the following pairs of
signed numbers using the 2’s-complement system.
Express the results as signed binary numbers and as
decimal values.
(a)01001-11010 (b)10010-10011
• How can arithmetic overflow be detected when signed
numbers are being added? Subtracted?
6-5 Multiplication of Binary
numbers
• The same manner as the multiplication of decimal
numbers.
1001
 multiplicand = 910
1011
 multiplier=1110
1001
1001
0000
1001
1100011
final product = 9910
Multiplication in the 2’sComplement System
• If the two numbers to be multiplied are positive,
they are already in true binary form and are
multiplied as they are.
• When the two numbers are negative, they will be in
2’s-complement form. Each is converted to a positive
number, and then the two numbers are multiplied. The
product is kept as a positive number and is given a
sign bit of 0.
• When one of the number is positive and the other is
negative, the negative number is first converted to a
positive magnitude by taking its 2’s complement. The
product will be in true-magnitude form, should be
changed to 2’s complement form and given a sign bit
of 1.
Review Question
• Multiply the unsigned numbers 0111 and 1110
6-6 Binary Division
• The same as for decimal numbers---long division
0010
11
1001
011
0011
11
0
0010.1
100 1010.0
100
100
100
0
The division of signed numbers is handled
in the same way as multiplication.
6-7 BCD ADDITION
• Sum Equals 9 or Less
0101
 BCD for 5
 4  0100
9
1001
 BCD for 4
 BCD for 9
5
45
0100 0101  BCD for 45
 33
78
 0011 0011  BCD for 33
0111 1000  BCD for 78
6-8 Hexadecimal Arithmetic
• Hex Addition
– Add the two hex digits in decimal, mentally
inserting the decimal equivalent for those digits
larger than 9.
– If the sum is 15 or less, it can be directly
expressed as a hex digit.
– If the sum is greater than or equal to 16,
subtract 16 and carry a 1 to the next digit
position.
• Examples
– Add the hex numbers 58 and 24
– Add the hex numbers 58 and 4B
– Add 3AF and 23C
Hex subtraction
•
•
How to get the 2’s-complement of a hex number?
Convert to binary, take the 2’s complement of the binary
equivalent, and then convert back to hex.
73A
0111
0011
1010
1000
1100
0110
8C6
• A quicker procedure: subtract each hex digit from F;
then add 1.
F
F
F
-7
-3
-A
8
C
5
8
C
}
 Subtract each digit from F
+1
 Add 1
6
 Hex equivalent of 2’s complement
Example
• Subtract 3A516 from 59216.
Review Questions
• Add 67F+2A4
• Subtract 67F-2A4
• Which of the following hex numbers represent positive
values: 2F, 77EC, C000, 6D, FFFF?
6-9 Arithmetic Circuits
6-10 Parallel binary adder
Parallel adder
Review Questions
• How many inputs does a full adder have? How many
outputs?
• Assume the following input levels in Parallel Adder:
– A4A3A2A1A0=01001; B4B3B2B1B0=00111; C0=0
(a)What are the logic levels at the outputs of FA#2?
(b)What is the logic level at the C5 output?
6-11 Design of a Full Adder
•Truth table for a full-adder circuit
K Mappings for the full-adder
outputs
Complete circuitry for a full
adder
6-12 Complete parallel adder
with registers
Sequence of operations
•
•
•
•
•
[A]=0000
[M]-> [B]
[S]*->[A]
[M]->[B]
[S]->[A]
Review Questions
• Suppose that four different four-bit numbers are to
be taken from memory and added by the circuit in the
last figure, how many CLEAR pulses will be needed?
How many TRANSFER pulses? How many LOAD pulses?
• Determine the contents of the A register after the
following sequence of operations:
– [A]=0000, [0110]->[B], [S]->[A]
[1110]->[B], [S]->[A]
6-14 Integrated-Circuit
Parallel Adder
Example
• Determine the logic levels at the inputs and outputs
of the eight-bit adder in Figure 6-10(b) when 7210 is
added to 13710.
Review Questions
• How many 74HC283 chips are needed to add two 20-bit
numbers?
• If a 74HC283 has a maximum propagation delay of 30 ns
from C0 to C4, what will be the total propagation
delay of a 32-bit adder constructed from 74HC283s?
• What will be the logic level at C4 in Last Example?
6-15 2’s Complement system
• The operations of addition and subtraction of signed
numbers can be performed using only the addition
operation if we use the 2’s complement form to
represent negative numbers.
Addition
Subtraction
Combined Addition and
Subtraction
Review Questions
• Why does C0 have to be a 1 in order to use the adder
circuit in Figure 6-12 as a subtractor?
• Assume that [A]=0011 and [B]=0010 in Figure 6-13. If
ADD=1 and SUB=0, determine the logic levels at the OR
gate outputs.
• Repeat question 2 for ADD=0, SUB=1
• Ture or False: When the adder/Subtractor circuit is
used for subtraction, the 2’s complement of the
subtrahend appears at the input of the adder.
6-16 BCD ADDER
• Add the BCD code groups for each decimal digit
position; use ordinary binary addition.
• For those positions where the sum is 9 or less, the
sum is in proper BCD form and no correction is needed
• When the sum of two digits is greater than 9, a
correction of 0110 should be added to that sum to
produce the proper BCD result. This will produce a
carry to be added to the next decimal position.
– A3A2A1A0 
BCD code group
– B3B2B1B0 
BCD code group
S4S3S2S1S0 
straight binary sum
Truth table
S4
S3
S2
S1
S0
0
1
0
1
0
(10)
0
1
0
1
1
(11)
0
1
1
0
0
(12)
0
1
1
0
1
(13)
0
1
1
1
0
(14)
0
1
1
1
1
(15)
1
0
0
0
0
(16)
1
0
0
0
1
(17)
1
0
0
1
0
(18)
X=S4+S3(S2+S1)
A BCD adder
Example
• Determine the inputs and outputs when the below
circuit is used to add 53810 to 24710. Assume CARRY
IN=0.
Review Questions
• What are the three basic parts of a BCD adder
circuit?
• Describe how the BCD adder circuit detects the need
for a correction and executes it.
6-17 ALU Integrated Circuits
Operations
•
•
•
•
•
•
•
CLEAR
ADD
SUBTRACT
XOR
OR
AND
PRESET
Example
• Determine the 74HC382 outputs for the following
inputs: S2S1S0=010, A3A2A1A0=0100, B3B2B1B0=0001, and
CN=1.
• Change the select code to 011 and repeat.
Expanding the ALU
Example
• How would the arrangement in the last figure have to
be changed in order to perform the subtraction(B-A)?
Review Questions
• Apply the following inputs to the ALU of Figure 6-16,
and determine the outputs: S2S1S0=001, A3A2A1A0=1110,
B3B2B1B0=1001, CN=1.
• Change the select code to 011 and CN to 0, and repeat
question 1.
• Change the select code to 110 and repeat question 1.
• Apply the following inputs to the circuit of Figure
6-17, and determine the outputs: B=01010011,
A=00011000.
• Change the select code to 111, and repeat question 4.
• How many 74HC382s are needed to add two 32-bit
numbers?