Digital design with CPLD applications and VHDL (R. Dueck, 2000)
.pdf222 |
C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits |
Hexadecimal arithmetic is used for calculations that would be awkward in binary due to the large number of bits involved. Important applications of hexadecimal arithmetic are found in microcomputer systems.
In addition to positional number systems, binary numbers can be used in a variety of nonpositional number codes, which can represent numbers, letters, and computer control codes. Binary coded decimal (BCD) codes represent decimal digits as individually encoded groups of bits. Gray code is a binary code used in special applications. American Standard Code for Information Interchange (ASCII) represents alphanumeric and control code characters in a 7- or 8-bit format.
There are a number of different digital circuits for performing digital arithmetic, most of which are based on the parallel binary adder, which in turn is based on the full adder and half adder circuits. The half adder adds two bits and produces a sum and a carry. The full adder also allows for an input carry from a previous adder stage. Parallel adders have many full adders in cascade, with carry bits connected between the stages.
Specialized adder circuits are used for adding and subtracting binary numbers, generating logic functions, and adding numbers in binary-coded decimal (BCD) form. ■
6.1 Digital Arithmetic
K E Y T E R M S
Signed binary number A binary number of fixed length whose sign is represented by one bit, usually the most significant bit, and whose magnitude is represented by the remaining bits.
Unsigned binary number A binary number whose sign is not specified by a sign bit. A positive sign is assumed unless explicitly stated otherwise.
Digital arithmetic usually means binary arithmetic, or perhaps BCD arithmetic. Binary arithmetic can be performed using signed binary numbers, in which the MSB of each number indicates a positive or negative sign, or unsigned binary numbers, in which the sign is presumed to be positive.
The usual arithmetic operations of addition and subtraction can be performed using signed or unsigned binary numbers. Signed binary arithmetic is often used in digital circuits for two reasons:
1.Calculations involving real-world quantities require us to use both positive and negative numbers.
2.It is easier to build circuits to perform some arithmetic operations, such as subtraction, with certain types of signed numbers than with unsigned numbers.
Unsigned Binary Arithmetic
K E Y T E R M S
Operand A number upon which an arithmetic function operates (e.g., in the expression x y z, x and y are the operands).
Augend The number in an addition operation to which another number is added.
Addend The number in an addition operation that is added to another.
Sum The result of an addition operation.
Carry A digit that is “carried over” to the next most significant position when the sum of two single digits is too large to be expressed as a single digit.
6.1 • Digital Arithmetic |
223 |
Sum bit (single-bit addition) The least significant bit of the sum of two 1-bit binary numbers.
Carry bit A bit that holds the value of a carry (0 or 1) resulting from the sum of two binary numbers.
Addition
When we add two numbers, they combine to yield a result called the sum. If the sum is larger than can be contained in one digit, the operation generates a second digit, called the carry. The two numbers being added are called the augend and the addend, or more generally, the operands.
For example, in the decimal addition 9 6 15, 9 is the augend, 6 is the addend, and 15 is the sum. Since the sum cannot fit into a single digit, a carry is generated into a second digit place.
Four binary sums give us all of the possibilities for adding two n-bit binary numbers:
0 |
0 |
00 |
|
1 |
0 |
01 |
|
1 |
1 |
10 |
(110 110 210) |
1 1 1 11 |
(110 110 110 310) |
Each of these results consists of a sum bit and a carry bit. For the first two results above, the carry bit is 0. The final sum in the table is the result of adding a carry bit from a sum in a less significant position.
When we add two 1-bit binary numbers in a logic circuit, the result always consists of a sum bit and a carry bit, even when the carry is 0, since each bit corresponds to a measurable voltage at a specific circuit location. Just because the value of the carry is 0 does not mean it has ceased to exist.
EXAMPLE 6.1 |
Calculate the sum 10010 1010. |
|
|
|
|
||
|
SOLUTION |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
10010 |
|
|
|
|
|
|
|
1010 |
|
|
|
|
|
|
|
11100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EXAMPLE 6.2 |
Calculate the sum 10111 10010. |
(Carry from sum of 2nd LSBs) |
|||||
|
SOLUTION |
||||||
|
|
|
|
|
|
|
(Carry bits) |
|
|
|
|
|
|
|
|
|
1 |
11 |
|
||||
|
10111 |
|
|||||
|
10010 |
|
|||||
|
101001 |
|
SECTION 6.1A REVIEW PROBLEMS
6.1Add 11111 1001.
6.2Add 10011 1101.
224 |
C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits |
Subtraction
K E Y T E R M S
Difference The result of a subtraction operation.
Minuend The number in a subtraction operation from which another number is subtracted.
Subtrahend The number in a subtraction operation that is subtracted from another number.
Borrow A digit brought back from a more significant position when the subtrahend digit is larger than the minuend digit.
In unsigned binary subtraction, two operands, called the subtrahend and the minuend, are subtracted to yield a result called the difference. In the operation x a b, x is the difference, a is the minuend, and b is the subtrahend. To remember which comes first, think of the minuend as the number that is diminished (i.e., something is taken away from it).
Unsigned binary subtraction is based on the following four operations:
0 0 0
1 0 1
1 1 0
10 1 1 (210 110 110)
The last operation shows how to obtain a positive result when subtracting a 1 from a 0: borrow 1 from the next most significant bit.
Borrowing Rules:
1.If you are borrowing from a position that contains a 1, leave behind a 0 in the borrowedfrom position.
2.If you are borrowing from a position that already contains a 0, you must borrow from a more significant digit that contains a 1. All 0s up to that point become 1s, and the last borrowed-from digit becomes a 0.
EXAMPLE 6.3 |
Subtract 1110 1001. |
SOLUTION
(New 2nd LSB) |
(Bit borrowed from 2nd LSB) |
01
11101001 0101
EXAMPLE 6.4 |
Subtract 10000 101. |
|
|
|
|
SOLUTION |
|
|
|
|
|
|
1111 |
|
|
10000 |
(original |
10000 |
(After borrowing |
|
101 |
problem) |
101 |
from higher-order bits) |
|
|
|
1011 |
|
|
|
|
|
6.2 • Representing Signed Binary Numbers |
225 |
SECTION 6.1B REVIEW PROBLEMS
6.3Subtract 10101 10010.
6.4Subtract 10000 1111.
6.2Representing Signed Binary Numbers
K E Y T E R M S
Sign bit A bit, usually the MSB, that indicates whether a signed binary number is positive or negative.
Magnitude bits The bits of a signed binary number that tell us how large the number is (i.e., its magnitude).
True-magnitude form A form of signed binary number whose magnitude is rep-
resented in true binary.
1’s complement A form of signed binary notation in which negative numbers are created by complementing all bits of a number, including the sign bit.
2’s complement A form of signed binary notation in which negative numbers are created by adding 1 to the 1’s complement form of the number.
N O T E
Positive numbers are the same in all three notations.
Binary arithmetic operations are performed by digital circuits that are designed for a fixed number of bits, since each bit has a physical location within a circuit. It is useful to have a way of representing binary numbers within this framework that accounts not only for the magnitude of the number, but for the sign as well.
This can be accomplished by designating one bit of a binary number, usually the most significant bit, as the sign bit and the rest as magnitude bits. When the number is negative, the sign bit is 1, and when the number is positive, the sign bit is 0.
There are several ways of writing the magnitude bits, each having its particular advantages. True-magnitude form represents the magnitude in straight binary form, which is relatively easy for a human operator to read. Complement forms, such as 1’s complement and 2’s complement, modify the magnitude so that it is more suited to digital circuitry.
True-Magnitude Form
In true-magnitude form, the magnitude of a number is translated into its true binary value.
The sign is represented by the MSB, 0 for positive and 1 for negative.
EXAMPLE 6.5 |
Write the following numbers in 6-bit true-magnitude form: |
|
|||
|
a. 2510 |
b. 2510 |
c. 1210 |
d. 1210 |
|
|
SOLUTION Translate the magnitudes of each number into 5-bit binary, padding with |
||||
|
leading zeros as required, and set the sign bit to 0 for a positive number and 1 for a nega- |
||||
|
tive number. |
|
|
|
|
|
a. 011001 |
b. 111001 |
c. 001100 |
d. 101100 |
|
|
|
|
|
|
226 |
C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits |
1’s Complement Form
True-magnitude and 1’s complement forms of binary numbers are the same for positive numbers—the magnitude is represented by the true binary value and the sign bit is 0. We can generate a negative number in one of two ways:
1.Write the positive number of the same magnitude as the desired negative number. Complement each bit, including the sign bit; or
2.Subtract the n-bit positive number from a binary number consisting of n 1s.
EXAMPLE 6.6 |
Convert the following numbers to 8-bit 1’s complement form: |
|||
|
a. 5710 |
b. 5710 |
c. 7210 |
d. 7210 |
SOLUTION Positive numbers are the same as numbers in true-magnitude form. Negative numbers are the bitwise complements of the corresponding positive number.
a.5710 00111001
b.5710 11000110
c.7210 01001000
d.7210 10110111
We can also generate an 8-bit 1’s complement negative number by subtracting its positive magnitude from 11111111 (eight 1s). For example, for part b:
11111111 |
|
00111001 ( 5710) |
|
11000110 ( 5710) |
|
|
2’s Complement Form
Positive numbers in 2’s complement form are the same as in true-magnitude and 1’s complement forms. We create a negative number by adding 1 to the 1’s complement form of the number.
EXAMPLE 6.7 |
Convert the following numbers to 8-bit 2’s complement form: |
|||
|
a. 5710 |
b. 5710 |
c. 7210 |
d. 7210 |
SOLUTION
a.57 00111001
b. 57 |
11000110 |
(1’s complement) |
|
|
1 |
|
|
|
11000111 |
(2’s complement) |
|
c. 72 |
01001000 |
|
|
d. 72 |
10110111 |
(1’s complement) |
|
|
1 |
|
|
|
10111000 |
(2’s complement) |
|
|
|
|
A negative number in 2’s complement form can be made positive by 2’s complementing it again. Try it with the negative numbers in Example 6.7.
6.3 • Signed Binary Arithmetic |
227 |
6.3 |
Signed Binary Arithmetic |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K E Y T E R M |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Signed binary arithmetic Arithmetic operations performed using signed binary |
|
||||||||
|
|
numbers. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Signed Addition |
|
|
|
|
|
|
|
|
||
|
Signed addition is done in the same way as unsigned addition. The only difference is that |
||||||||||
|
both operands must have the same number of magnitude bits, and each has a sign bit. |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
EXAMPLE 6.8 |
Add 3010 and 7510. Write the operands and the sum as 8-bit signed binary numbers. |
|
|||||||||
|
SOLUTION |
|
|
|
|
|
|
|
|
||
|
30 |
00011110 |
|
|
|||||||
|
75 |
01001011 |
|
|
|||||||
|
105 |
01101001 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
(Magnitude bits) |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
(Sign bit) |
|
|
|
|
|
|
|
|
|
|
|
|
Subtraction
The real advantage of complement notation becomes evident when we subtract signed binary numbers. In complement notation, we add a negative number instead of subtracting a positive number. We thus have only one kind of operation—addition—and can use the same circuitry for both addition and subtraction.
This idea does not work for true-magnitude numbers. In the complement forms, the magnitude bits change depending on the sign of the number. In true-magnitude form, the magnitude bits are the same regardless of the sign of the number.
Let us subtract 8010 6510 1510 using 1’s complement and 2’s complement addition. We will also show that the method of adding a negative number to perform subtraction is not valid for true-magnitude signed numbers.
1’s Complement Method
K E Y T E R M
End-around carry An operation in 1’s complement subtraction where the carry
bit resulting from a sum of two 1’s complement numbers is added to that sum.
Add the 1’s complement values of 80 and 65. If the sum results in a carry beyond the sign bit, perform an end-around carry. That is, add the carry to the sum.
8010 |
01010000 |
|
6510 |
01000001 |
|
6510 |
10111110 |
(1’s complement) |
80 |
|
01010000 |
65 |
|
10111110 |
|
1 |
00001110 |
|
|
→ 1 (End-around carry) |
|
|
|
|
|
|
15 |
|
00001111 |
228 |
C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits |
2’s Complement Method
Add the 2’s complement values of 80 and 65. If the sum results in a carry beyond the sign bit, discard it.
8010 |
01010000 |
|
|
|
6510 |
01000001 |
|
|
|
6510 |
10111110 |
(1’s complement) |
||
|
|
1 |
|
|
|
|
10111111 |
(2’s complement) |
|
|
|
|
80 |
01010000 |
|
|
|
65 |
10111111 |
|
|
|
15 |
1 00001111 |
(Discard carry)
True-Magnitude Method
8010 01010000
6510 010000016510 11000001
80 |
|
01010000 |
65 |
|
11000001 |
? |
1 |
00010001 |
If we perform an end-around carry, the result is 00010010 1810. If we discard the carry, the result is 00010001 1710. Neither answer is correct. Thus, adding a negative true-magnitude number is not equivalent to subtraction.
Negative Sum or Difference
All examples to this point have given positive-valued results. When a 2’s complement addition or subtraction yields a negative sum or difference, we can’t just read the magnitude from the result, since a 2’s complement operation modifies the bits of a negative number. We must calculate the 2’s complement of the sum or difference, which will give us the positive number that has the same magnitude. That is, ( x) x.
EXAMPLE 6.9 |
Subtract 6510 8010 in 2’s complement form. |
|
||
|
SOLUTION |
|
|
|
|
6510 |
|
01000001 |
|
|
8010 |
|
01010000 |
|
|
8010 |
|
10101111 |
(1’s complement) |
|
|
|
1 |
|
|
|
|
10110000 |
(2’s complement) |
65 0100000180 10110000 11110001
Take the 2’s complement of the difference to find the positive number with the same magnitude.
11110001 |
|
( 15)← |
|
||
|
|
||||
00001110 |
(1’s complement) |
|
|
|
|
|
1 |
|
|
|
|
00001111 |
(2’s complement) |
( 15) |
|
|
|
|
|