Chapter 1 Basic Principles of Digital Systems outlin e 1

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

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

sum of two single digits is too large to be expressed as a single digit.

K E Y T E R M S

K E Y T E R M S

numbers.

two binary numbers.

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.

(Carry from sum of 2nd LSBs)

1

10010

11100

(Carry bits)

1 11

10111

101001

❘❙❚ SECTION 6.1A REVIEW PROBLEMS

6.1 Add 11111 _ 1001.

6.2 Add 10011 _ 1101.

subtracted.

number.

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,

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:

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

1110

0101

1111

_ 101 problem) _ 101 from higher-order bits)

1011

❘❙❚

❘❙❚ SECTION 6.1B REVIEW PROBLEMS

6.3 Subtract 10101 _ 10010.

6.4 Subtract 10000 _ 1111.

positive or negative.

number is (i.e., its magnitude).

in true binary.

created by complementing all bits of a number, including the sign bit.

created by adding 1 to the 1’s complement form of the number.

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

leading zeros as required, and set the sign bit to 0 for a positive number and 1 for a negative

number.

a. 011001 b. 111001 c. 001100 d. 101100

N O T E

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

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)

❘❙❚

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.

a. 5710 b. _5710 c. 7210 d. _7210

a. 57 _ 00111001

b. _57 _ 11000110 (1’s complement)

1

11000111 (2’s complement)

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

Signed binary arithmetic Arithmetic operations performed using signed binary

numbers.

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.

_30 00011110

_75 _01001011

_105 01101001

(Magnitude bits)

(Sign bit)

❘❙❚

Subtraction

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.

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

K E Y T E R M

K E Y T E R M

→

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)

_65 _ 10111111

_15 1 00001111

(Discard carry)

8010 _ 01010000

6510 _ 01000001

_6510 _ 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)

_80 _ 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

←

6.3 • Signed Binary Arithmetic 229

00001111 _ _1510. We generated this number by complementing 11110001. Thus,

11110001 __1510. ❘❙❚

Range of Signed Numbers

The largest positive number in 2’s complement notation is a 0 followed by n 1s for a number

with n magnitude bits. For instance, the largest positive 4-bit number is 0111 __710.

The negative number with the largest magnitude is not the 2’s complement of the largest

positive number. We can find the largest negative number by extension of a sequence of 2’s

complement numbers.

The 2’s complement form of _710 is 1000 _ 1 _ 1001. The positive and negative

numbers with the next largest magnitudes are 0110 (_ _610) and 1010 (_ _610). If we

continue this process, we will get the list of numbers in Table 6.1.

We have generated the 4-bit negative numbers from _110 (1111) through _710 (1001)

by writing the 2’s complement forms of the positive numbers 1 through 7. Notice that these

numbers count down in binary sequence. The next 4-bit number in the sequence (which is

the only binary number we have left) is 1000. By extension, 1000 __810. This number is

its own 2’s complement. (Try it.) It exemplifies a general rule for the n-bit negative number

with the largest magnitude.

A 2’s complement number consisting of a 1 followed by n 0s is equal to _2n.

Therefore, the range of a signed number, x, is _2n _ x _ 2n _ 1 for a number with

n magnitude bits.

❘❙❚ EXAMPLE 6.10 Write the largest positive and negative numbers for an 8-bit signed number in decimal and

2’s complement notation.

SOLUTION

01111111 _ _127 (7 magnitude bits: 27 _ 1 _ 127)

10000000 _ _128 (1 followed by seven 0s: _27 _ _128)

❘❙❚ EXAMPLE 6.11 Write _1610

a. As an 8-bit 2’s complement number

b. As a 5-bit 2’s complement number

(8-bit numbers are more common than 5-bit numbers in digital systems, but it is useful

to see how we must write the same number differently with different numbers of bits.)

a. An 8-bit number has 7 magnitude bits and 1 sign bit.

_16 _ 00010000

_16 _ 11101111 (1’s complement)

_ 1

11110000 (2’s complement)

to represent 16. However, a 1 followed by n 0s is equal to _2n. For a 1 and four 0s, _2n

__24__16. Thus, 10000 __1610.

❘❙❚

Complement Numbers

_7 0111

_5 0101

_3 0011

_1 0001

_1 1111

_3 1101

_5 1011

_7 1001

The last five bits of the binary equivalent of _16 are the same in both the 5-bit and 8-bit

numbers.

The 8-bit number is padded with leading 1s. This same general pattern applies for

any negative number with a power-of-2 magnitude. (_2n _ n 0s preceded by all 1s

within the defined number size.)

❘❙❚ SECTION 6.3 REVIEW PROBLEM

6.5 Write _32 as an 8-bit 2’s complement number.

6.6 Write _32 as a 6-bit 2’s complement number.

Sign Bit Overflow

from a sum or difference larger than can be represented by the number of

magnitude bits.

Signed addition of positive numbers is performed in the same way as unsigned addition.

The only problem occurs when the number of bits in the sum of two numbers exceeds the

number of magnitude bits and overflows into the sign bit. This causes the number to appear

to be negative when it is not. For example, the sum 75 _ 96 _ 171 causes an overflow

in 8-bit signed addition. In unsigned addition the binary equivalent is:

1001011

_ 1100000

In signed addition, the sum is the same, but has a different meaning.

0 1001011

_ 0 1100000

1 0101011

(Sign bit) (Magnitude bits)

The sign bit is 1, indicating a negative number, which cannot be true, since the sum of

two positive numbers is always positive.

A sum of positive signed binary numbers must not exceed 2n _ 1 for numbers having

n magnitude bits. Otherwise, there will be an overflow into the sign bit.

Overflow in Negative Sums

Overflow can also occur with large negative numbers. For example, the addition of _8010

and _6510 should produce the result:

_8010 _ (_6510) _ _14510

N O T E

K E Y T E R M

In 2’s complement notation, we get:

_8010 _ 01010000

_8010 _ 10101111 (1’s complement)

_ 1

10110000 (2’s complement)

_6510 _ 10111110 (1’s complement)

_ 1

10111111 (2’s complement)

_ (_65)8 _ 10111111

? 1 01101111

(Incorrect magnitude _ 11110)

(Erroneous sign bit _ 0)

(Discard carry)

This result shows a positive sum of two negative numbers—clearly incorrect. We can

extend the statement we made earlier about permissible magnitudes of sums to include

negative as well as positive numbers.

A sum of signed binary numbers must be within the range of _2n _ sum _ 2n _1

for numbers having n magnitude bits. Otherwise, there will be an overflow into the

sign bit.

For an 8-bit signed number in 2’s complement form, the permissible range of sums is

10000000 _ sum _ 01111111. In decimal, this range is _128 _ sum __127.

A sum of two positive numbers is always positive. A sum of two negative numbers

is always negative. Any 2’s complement addition or subtraction operation that appears

to contradict these rules has produced an overflow into the sign bit.

❘❙❚ EXAMPLE 6.12 Which of the following sums will produce a sign bit overflow in 8-bit 2’s complement notation?

How can you tell?

a. 6710 _ 3310

b. 6710 _ 6310

c. _9610 _ 2210

d. _9610 _ 4210

SOLUTION A sign bit overflow is generated if the sum of two positive numbers appears

to produce a negative result or the sum of two negative numbers appears to produce a positive

result. In other words, overflow occurs if the operand sign bits are both 1 and the sum

sign bit is 0 or vice versa. We know this will happen if an 8-bit sum is outside the range

(_128 _ sum _ _127).

a. _6710 01000011 (no overflow;

_3310 00100001 sum of positive numbers

10010 01100100 is positive.)

N O T E

N O T E

b. _6710 01000011 (Overflow; sum of

_6310 00111111 positive numbers is negative.

13010 10000010 Sum __127; out of range.)

c. _96 _ 01100000

_96 _ 10011111 (1’s complement)

_ 1

10100000 (2’s complement)

_22 11101001 (1’s complement)

_ 1

11101010 (2’s complement)

_22 11101010

_118 1 10001010

(Magnitude bits)

(Sign bit)

(Discard carry)

(No overflow; sum of two negative numbers is negative.)

d. _96 _ 01100000

_96 _ 10011111 (1’s complement)

_ 1

_42 _ 00101010

_42 11010101 (1’s complement)

_ 1

_96 10100000

_42 11010110

_138 1 01110110

(Magnitude bits)

(Sign bit)

(Discard carry)

(Overflow; sum of two negative numbers is positive. Sum __128; out of range.)

❘❙❚

The carry bit generated in 1’s and 2’s complement operations is not the same as an

bit, which leads us to believe that the number is opposite in sign from its true value.

A carry is the result of an operation carrying beyond the physical limits of an n-bit

number. It is similar to the idea of an odometer rolling over from 999999.9 to

1 000000.0. There are not enough places to hold the new number, so it goes back to

the beginning and starts over.