Introduction To Digital Electronics and Logic (Chapter 3: Digital Arithmetic)

3.0       DIGITAL ARITHMETIC

Data presentation and representation is for a purpose, haven discussed different ways of representing digital data, and the next step is to study how this data are manipulated in specific operations.

The types of manipulative operations data are performed on data include arithmetic operations²⁰ and logic operations²¹. Basic arithmetic operations include addition, subtraction, multiplication and division. While basic logic operations are; AND, OR and NOT. In this chapter, we will discuss the rules that govern arithmetic operations on digital data. In later chapters we will study logic operations on digital data.

3.1       Binary Addition and Subtraction Rules

Arithmetic rules for binary numbers are quite straightforward, and similar to those used in decimal arithmetic. The rules for addition of binary numbers are:

Table 3.1: Rules of binary addition

Addition	Sum	Carry
0  +  0	0	0
0  +  1	1	0
1  +  0	1	0
1  +  1	0	1
1 + 1 + 1	1	1

 

 Binary addition²² is carried out just like the decimal addition that we are used to, in decimal addition, when the result of the addition in a particular digit is equal or greater than the radix/base value of the system (i.e. ten for decimal), it produces a carry to the next higher bit and the sum will be the ‘result’ of addition minus the radix/base value.

For example:

 

  

For  7 +  3, the result is ‘10’ which is equal to the radix/base of decimal system a carry is produce to the next higher digit and radix value (‘10’) is deducted from the result ‘10’ remain ‘0’ as the sum. For 8 + 7, result is ‘15’ obviously greater than the radix value ‘10’ carry ‘1’ is produced to the next higher digit, radix value ‘10’ is deducted from ‘15’, thus remaining sum  of  ‘5’. In the case of 2 + 8, the result is 8 which is less than the radix value, no carry is produce and the sum is ‘8’.

This same process applies for the binary arithmetic rule described in table 3.1 above, 0 + 0 result to ‘0’, this result is less than the binary radix value which is ‘2’, thus leaving the sum as ‘0’ and no carry is produced. Same for 0 + 1 and 1 + 0 which produces a sum of ‘1’ and no carry i.e. ‘0’.

For 1 + 1,  the result of addition is 2 which is equal/greater than the radix value ‘2’, thus produces a carry ‘1’ and by deducting the radix value ‘2’ from the result of addition ‘2’ it leaves the sum as ‘0’. For 1 + 1 +1,  the result is ‘3’ obviously will produce a carry ‘1’, deducting radix value ‘2’ from addition result ‘3’, we are left with sum of ‘1’.

Binary subtraction rules

Again likened to the decimal rules of subtraction, when we deduct a lesser number from a larger number the subtraction is straight forward e.g.  8 – 2  = ‘difference’   6 (in decimal). But when a large number is being subtracted from a lesser number, a borrow is required from the next higher digit e.g. 5 – 8 = ‘Difference’   7 ‘borrow’ 1, in this case, the borrow from the higher digit takes up the radix value ‘10’ in the next lower digit. The rules for binary subtraction²³ are summarized in table 3.2 bellow.

Table 3.2: Rules of binary subtraction

Subtraction	Difference	Borrow
0  -  0	0	0
0  -  1	1	1
1  -  0	1	0
1  -  1	0	1
1 – 1 -1	1	1

 

3.2 Binary Addition and Subtraction with larger bits

Our illustration so far has been on one bit binary and in a practical situation; addition and subtraction in binary are usually in larger bits. We discuss with examples the process of adding and subtracting binary numbers of larger bits.

In the examples above we have illustrated how binary numbers of more bits can be added or subtracted from one another. But there is a clause; what if we have a situation where we are required to subtract 11₁₀ (1011)  from 9₁₀ (1001) i.e.  1011 – 1001.

for example;

  

9          1001

-  11       - 1011This operation is not possible with unsigned binary representation

-    2                    

 

So far we have dealt with binary additions of only POSITIVE numbers or subtractions that yield only POSITIVE results. The reason for this is that it is not possible in PURE (or unsigned) binary to signify whether a number is positive or negative. This we lead us to the next topic on Signed binary numbers.

3.3   Signed Binary²⁴

To represent a binary number signifying its sign, we have to device a means of identifying the sign within the range of symbols available to the binary number system, i.e. {0 and 1}. In signed binary number, we represent the sign of a particular number, using the MSB of the number as the sign bit and remaining bits as the magnitude bits.  ‘0’ denotes Positive (+)  and ‘1’ mean Negative (-), for example;

In the eight bit binary representation of decimal +27 and -27 above, the MSB denotes the sign of the number, while the remaining seven bits represents the magnitude of the number. 

The use of signed binary with sign bit to perform arithmetic operation in digital system involves a lot more work, because certain bit in the stream must be treated as special, this means it will require a more complex and thus expensive circuits. Aim of digital electronics designers is to optimize design by making the circuit simpler, more functional and less expensive.

A better means of performing digital arithmetic with adequate representation and interpretation of signed numbers is the use of complements of binary numbers. These are One’s complement and Two’s complement representation.

 

3.4   Complements of binary numbers

Complements are used in digital computers to simplify the subtraction operation and for logical manipulation. Simplifying operations leads to simpler, less expensive circuits to implement the operations. For binary numbers, we have 1’s complement and 2’s complement.

In mathematics, subtraction can be implemented in a variety of different ways as A – B, is the same as saying A + (-B) or –B + A. Using complements, subtraction of two binary numbers can be performed by simply using addition, i.e. A – B = A + (-B), -B is the complement of B.

3.4.1   One’s  Complement²⁵

The complement (or opposite) of +4 is −4.  One’s Complement (1’s complement) is a way of representing negative binary numbers in a signed binary number system. In 1’s complement, positive numbers (also called non-complements) remain unchanged as before with the sign-magnitude numbers.

Negative numbers however, are represented by taking the 1’s complement of the positive number. To obtain 1’s compliment of a binary number, we subtract each digit of the number from 1. For example;

We will observe in the examples above that, when subtracting binary digit from ‘1’, we can have either 1 – 0  = 1 or  1 – 1 =  0, which causes the bit to change from 0 to 1 or from 1 to 0m respectively. Therefore, 1’s complement of a binary number is formed by changing 1’s to 0’s and 0’s to 1’s.

For example:

+5₁₀ is 00000101₂ and   −5₁₀ is 11111010₂ (1’s Complement)

In the example above, the most significant bit (MSB) in the negative number –5₁₀ is 1, just as in signed binary. The remaining 7 bits of the negative number however are not the same as in signed binary notation. They are just the complement of the remaining 7 bits, and these give the value or magnitude of the number.

Binary Addition²⁶  and Subtraction with 1’s Complement

Both addition and subtraction in 1’s complement are addition; subtraction is just the addition of the 1’s complement of the Subtrahend i.e.  8 – 3 = 8 + (-3). 

The steps are as follows;

1.      Convert negative numbers to its equivalent 1’s complements

2.      Leave all positive numbers unchanged

3.      Perform binary addition on the numbers

4.      Add any carry out of the sign bit to the result.

5.      It the result is negative (i.e. MSB = 1) find its 1’s complement.

6.      If the result is positive (i.e. MSB = 0) leave the result as it is.

Let’s illustrate these steps with examples.

Example 3.4 Add -4 and + 6 using ones compliment

The result in this case is a negative number because the MSB =  1, therefore we have to determine the complement of the number i.e. the positive value of the number by finding its 1’compliment;

1’s complement of 11111000 ≡  00000111  =  +7,  therefore the answer 11111000 = -7 (correct)

Note that, n-bit notation can be used to represent numbers in the range from –(2^n-1 – 1) to +(2^n-1-1) using the 1’s complement format.

Using 1’s complement in binary addition and subtraction has limitation in that we have to consider the overflow into a non-existing bit to obtain a correct value of our operation. This took us to the next better option which is 2’s complement.

3.4.2   Two’s Complement²⁷

Two’s complement (2’s Complement) notation solves the problem of the relationship between positive and negative numbers, and achieves accurate results in subtractions without the need to consider the carry into a non-existing binary bit.

To perform binary subtraction²⁸ the twos complement system uses the technique of complementing the number to be subtracted.

To produce a negative number in two complement system, we simply find the 1’s complement of the number and add 1.

For example;

2’s complement of +6 ≡  000000110  =  11111001  (1’s complement)

                                                                      +           1

                                                                     11111010   (2’s complement)

Addition and Subtraction using 2’s complement

1.      Convert negative numbers to its equivalent 2’s complements

2.      Leave all positive numbers unchanged

3.      Perform binary addition on the numbers

4.       Discard any carry out of the sign bit.

5.      It the result is negative (i.e. MSB = 1) find its 2’s complement.

6.      If the result is positive (i.e. MSB = 0) leave the result as it is.

Example 3.6: Add +5 and -5 in binary using 2’s complement.

 

Again, n-bit notation can be used to represent numbers in the range from –(2^n-1 ) to +(2^n-1-1) using the 1’s complement format.

Overflow²⁹

In order to obtain a correct answer, we must ensure that the result had a sufficient number of bits to accommodate the sum. If we start with two n-bit numbers and the sum occupies n + 1 bits, we say that an overflow occurs.  When one performs the addition with paper and pencil, an overflow is not a problem, because we are not limited by the width of the page. We just add another 0 to a positive number or another 1 to a negative number in the most significant position to extend the number to n+1 bits and then perform the addition. Overflow is a problem in computer because the number of bits that hold a number is finite, and a result that exceeds the finite value by 1 cannot be accommodated.

For example;

 

Example 3.8:

            With four bits perform -6 -3 using 2’s complement..

            + 6 ≡  0110 

            + 3 ≡  0011 

            -  6 ≡  1010  (2’s complement)

            -  3 ≡  1101 (2’s complement)

The result obtain in example 3.8 is obviously wrong, -6-3 = -9 not +7, discrepancy in the answer is due to the fact that the expected result can not be accommodate in four bit binary, for a sign binary representation as mentioned earlier, N bit number will represent from – 2^N-1-1  to +2N^-1-1 decimal number.  In this example, 4 bit can represent -2^4-1to +2^4-1-1 i.e. -8 to +7. The expected result of -9 is not within this range and thus overflow occurs. To detect overflow in signed binary addition; if the carry-in to the sign bit is not equal to carry-out of the sign bit, overflow has occur. That, is to obtain correct result with addition in 2’s complement, the carry-in to the sign bit must be the same with the carry out of the sign bit. For example 3.8, carry-in to the sign bit is ‘0’ while carry-out of the sign bit is ‘1’.

           

Earlier in the this chapter, we stated that the basic binary arithmetic operations are addition, subtraction, multiplication and division. We have been able to discuss how digital circuit perform addition and subtraction as addition of negative numbers.We will not cover binary multiplication and division in this text, but it is worth mentioning that multiplication is performed as repeated addition while subtraction is performed as repeated subtraction in digital circuit. In this chapter we have extensively discussed the process of binary addition and subtraction, earlier we mentioned that the basic binary arithmetic operations are addition, subtraction, multiplication and division. We will not cover binary multiplication and binary division in this text, but it is helpful for exploration reader to mention here that, binary multiplication is simply repeated addition³⁰ while binary division is simply repeated subtraction³¹.

Exercise 3

a.      Obtain the 1’s and 2’s Complements of the following binary numbers:

i.  00010000  ii. 00000000  iii.  11011010           iv.  10101010

v. 10000101  vi. 11111111

b.      Write the eight-bit 2’s complement representation of (-23)₁₀

c.      What is the first thing you must do in order to solve the subtraction problem 11₁₀ – 4₁₀ using 2’s compliment.

d.      What is the general technique for subtracting binary numbers using 2’s compliment.

e.      Solve each of the following 5-bit subtraction problems using 2’s complement representation.

i.        00110₂ - 00101₂

ii.     01100₂ - 01010₂

iii.   00100₂ - 00101₂

iv.   01001₂ -01011₂

v.      00011₂ - 01100₂

f.       Solve each of the following 8-bit subtraction problems using 2’s complement representation:

i.        01111111₂ - 78₁₀

ii.     00110010₂ - 123₁₀

iii.   01001001₂ - 111₁₀

iv.   00000111₂ - 35₁₀

g.      Perform operation (3E91)₁₆ – (1DEF)₁₆ using 2’s complement arithmetic.

h.      Convert your answers from question (3) to decimal.

i.        Prove that 16-bit 2’s complement arithmetic cannot be used to add +18150 and +14618, while it can be sued to add -18150 and -14618