Chapter 6: Computer Arithmetic
In this chapter, we introduce arithmetic circuits which are the central building blocks of computers. Computers and digital logic perform many arithmetic functions: addition, subtraction, comparisons, shift, multiplication and division. This module describes hardware implementations for all of these operations.
Objectives
By the end of this chapter you should be able to:
- Demonstrate knowledge of 1-bit half and full adders
- Demonstrate knowledge of four-bit adder and subtractor
- Recall how to operate four-bit adder-subtractor
- Evaluate the arithmetic operation with four-bit adder-subtractor
- Execute arithmetic logic operations with Arithmetic logic unit
- Differentiate logical shift and arithmetic shift
- Apply arithmetic and shift operations for multiplication and division
6.1 Boolean Addition
Let’s look at how the computer execute the Boolean addition, , with binary numbers.
We assume an 8-bit computer. The decimal number 5 will be converted to an 8-bit binary number, 0000 0101. The decimal number 6 will be converted to an 8-bit binary number, 0000 0110, as shown in the below figure:
Fig. 6‑1. Boolean Addition: 5 + 6
As we calculate the decimal addition, the rightest digits will be added first and then the next digits will be executed. The sum of 1 and 0 is 1 with a carry 0 (Cout). In the second column from the right side, the sum of 0, 1, and the carry 0 (Cin) is 1 with a carry 0 (Cout). In the third column from the right side, the sum of 1, 1 and the carry 0 (Cin) is 0 with a carry 1 (Cout). In the fourth column, the sum of 0, 0, and the carry 1 (Cin) is 1 with a carry 0 (Cout).
We can execute the Boolean addition using 1-bit full adders. A 1-bit half adder is used for adding together the two least significant digits in a binary sum. It has two inputs A and B, and two outputs, Sum and Cout. But it lacks a Cin (carry) input.
1-Bit Full Adders
1-bit full adder can perform addition of numbers, where it has the following inputs and outputs:
- Inputs: A, B, Carry in (Cin)
- Outputs: Carry out (Cout), Sum (S)
Fig. 6‑2. 1-Bit Full Adder
The following table describes the operation of the adder. Here, the sum S will be ‘1’ if the number of the input ‘1’ is odd. For example, if the inputs A, B, and Cin are 001, the sum S is ‘1’. If the inputs A, B, and Cin are 110, the sum S is ‘0’. The Cout will be ‘1’ if the number of the input ‘1’ is greater than or equal to 2. For example, if the inputs A, B, and Cin are 110, the Cout is ‘1’.
Table 6‑1. Truth Table of 1-bit Full Adder
A | B | Cin | S | Cout |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
We can simplify the outputs S and Cout using K-map. The following figure shows K-map representation of the output S.
Fig. 6‑3. K-map representation of the output S
From the above figure, we can express the output S in terms of input variables as follows:
In order to produce the output S, there are four AND gates and one OR gate needed as shown in Fig. 6-4:
Fig. 6‑4. Logic gate circuit for the Output S
Each AND gate has the following inputs:
- AND1:
,
, and
- AND2:
,
, and
- AND3:
,
, and
- AND4:
,
, and
All outputs of the AND gates fed into the OR gate that produces the sum S.
The following figure shows K-map representation of the output Cout.
Fig. 6‑5. K-map representation of the output Cout
From the above figure, we can express the output Cout in terms of input variables as follows:
In order to produce the output Cout, there are three AND gates and one OR gate needed as shown in Fig. 6-6:
Fig. 6‑6. Logic gate circuit for the Output Cout
Each AND gate has the following inputs:
- AND5:
and
- AND6:
and
- AND7:
and
All outputs of the AND gates fed into the OR gate that produces the carryout Cout.
By combining Figs. 6-4 and 6-6, we can draw the 1-bit full adder with the carry-in Cin, as shown in the following figure:
Fig. 6‑7. Logic gate circuit for the 1-Bit Full Adder
In the above figure, the 1-bit full adder has three inputs, A, B and Cin; and two outputs, S and Cout. All the logic gates (ANDs and ORs) for the outputs S and Cout are placed in a single block. The sum S is produced with four AND gates and one OR gate in the same way to generate the output S in Fig. 6-4. The Cout is produced with three AND gates and one OR gate in the same way to generate the output Cout in Fig. 6-6.
Four-Bit Adders
How can we design four-bit adders? The four-bit adder is designed with four 1-bit full adders by connecting them in a parallel manner. The carryout Cout of the first full adder connected to the carry-in Cin of the second full adder, Cout of the second full adder connected to Cin of the third fuller adder, and Cout of the third full adder connected to Cin of the fourth fuller adder, as shown in the following figure:
Fig. 6‑8. Four-bit Adder
where the binary input A includes A3, A2, A1 and A0, the binary input B includes B3, B2, B1 and B0, Cin is C0, the output S includes S3, S2, S1 and S0, and the Cout is C4.
Exercises
Add 3 and 4 using the four-bit adder.
,
Inputs A (0011) and B (0100) are fed into a 4-bit full adder. The sum of A0, B0 and C0 is 1 (S0), the sum of A1, B1 and C1 is 1 (S1), the sum of A2, B2 and C2 is 1 (S2), and the sum of A3, B3 and C3 is 0 (S3). By collecting all the bits S3 – S0, it produces 0111 (=7) which is the sum of 3 and 4.
Fig. 6‑9. Add 3 and 4 using four-bit adder
6.2 Boolean Subtraction
Let’s look at how the computer execute the Boolean subtraction, 12 − 5, with binary numbers.
We assume an 8-bit computer. The decimal number 12 will be converted to an 8-bit binary number, 0000 1100. The decimal number 5 will be converted to an 8-bit binary number, 0000 0101, as shown in the below:
The logic operation of the above is not appreciate with the logic gates. Instead of the above operation, the Boolean subtraction is converted to the addition by converting the subtracted value to negate using two’s complement.
We can negate the number 5 by flipping all the bits and adding one to the lsb (least significant bit), as shown below:
The Boolean subtraction is now converted to the addition, as shown below:
The most left carry bit (9th bit) will be ignored because the operation is executed in an 8-bit computer. The overflow may occur when there are insufficient bits in a binary number representation to portray the result of an arithmetic operation.
Four-Bit Subtractor
Four-bit subtractor can be designed with a 4-bit full adder, by adding NOT gate to each input B and carry-in Cin = 1 to the lsb, as shown in the below figure:
Fig. 6‑10. Four-bit Subtractor
where the input bits A3 through A0 are fed into the full adder directly, the input bits B3 through B0 are fed into the full adder after flipping the bits with NOT gates, and the first carryin C0 set to 1, C0 = 1. The Boolean equation of the above block diagram is expressed as shown below:
The subtractor produces the output Y, Y3 through Y0, and the carryout C4.
Let’s subtract 3 from 7 using the four-bit subtractor.
- 7 = 0111 (A); A3 = 0, A2 = 1, A1 = 1, A0 = 1,
- 3 = 0011 (B); B3 = 0, B2 = 0, B1 = 1, B0 = 1.
The binary inputs A and B (A3 – A0 and B3 – B0) are fed into the subtractor as shown below:
Fig. 6‑11. Subtract 3 from 7
Starting from the rightest side, we can execute the full adder operation with ,
, and
, producing the outputs
and
, where
become the carryin for the next full adder. The second full adder executes with the following inputs;
,
, and
, producing the outputs
and
, where
become the carryin for the next full adder. The third and fourth full adders execute in a similar manner: the inputs
,
, and
produce the outputs
and
; and the inputs
,
, and
produce the outputs
and
, where the carryout
will be ignored because this is a 4-bit computer system. The output bits
(= 0100) is equal to 4.
6.3 Adder-Subtractor
The hardware configure of the adder is very similar to that of the subtractor. Since the hardware configuration is related to the cost. We can design this two hardware by sharing some components, i.e. full adders. A four-bit Adder-Subtractor can be designed with 4-bit full adder, four exclusive OR gates and a mode bit M, as shown in the below:
Fig. 6‑12. Four-bit Adder-Subtractor
where the input bits A3 through A0 are fed into the full adder directly, the input bits B3 through B0 are fed into the full adder after executing exclusive OR operation with a mode bit M. The mode bit M determines either an adder (M = 0) or a subtractor (M = 1). The Adder-Subtractor produces the output bits S3 through S0, and the carryout C4, where the carryout C4 is used for overflow detection.
The following figure shows the case when the mode bit M is equal to 0, executing the add operation.
Fig. 6‑13. Four-bit Adder-Subtractor: M = 0
Since the mode bit M = 0, the outputs of exclusive OR gates are equal to B3, B2, B1 and B0. Then the four-bit Adder-Subtractor produces the output bits, S3 through S0, and the carryout C4. It works as a 4-bit full adder.
If the mode bit M = 1, as shown in Fig. 6-14, the outputs of exclusive OR gates are equal to ,
,
, and
, where the carryin C1 of the first full adder is equal to 1.
Fig. 6‑14. Four-bit Adder-Subtractor: M = 1
Then the four-bit Adder-Subtractor produces the output bits, S3 through S0, and the carryout C4. It works as a 4-bit subtractor.
Let’s look at how this circuit works with the following example inputs;
- A = 5 (0101)
- B = 7 (0111)
- The mode bit M = 1
The input bits A3 through A0 are directly fed into the adders. On the other hand, the input bits B3 through B0 are fed into the exclusive OR gates. Since the mode bit M = 1, the outputs of the exclusive OR gates are (B complement).
Fig. 6‑15. Four-bit Adder-Subtractor with Example Inputs: A = 5, B = 7, and M = 1
From the rightest side of the above figure,
- Three inputs A0 = 1,
= 0, carryin C0 = 1 fed into the first FA, and then produce S0 = 0 and carryout C1 = 1.
- Three inputs A1 = 0,
= 0, carryin C1 = 1 fed into the second FA and then produce S1 = 1 and carryout C2 = 0.
- Three inputs A2 = 1,
= 0, carryin C2 = 0 fed into the third FA, and then produce S2 = 1 and carryout C3 = 0.
- Three inputs A3 = 0,
= 1, carryin C3 = 0 fed into the fourth FA, and then produce S3 = 1 and carryout C4 = 0.
Let’s collect all the sum bits, (= 1110), which is equal to -2 (two’s complete number).
Exercises
Eight-bit Adder-Subtractor can be designed with eight 1-bit full adders by connecting them in a parallel manner.
Fig. 6‑16. Eight-bit Adder-Subtractor
- Cout (C1) of the first full adder connected to Cin of the second fuller adder, Cout (C2) of the second full adder connected to Cin of the third fuller adder, etc.
- Binary input A includes A7 through A0
- Binary input B includes B7 through B0
- Cin: C0
- Output S includes S7 through S0.
- Cout: C4
If A = 32 (00100000), B = 63 (00111111), and M = 1, what is the output S?
6.4 Comparators
A 1-bit comparator is designed with an exclusive OR gate, as shown in Fig. 6-17.
Fig. 6‑17. Eight-bit Adder-Subtractor
There are two AND gates and one OR gate. AND1 gate has two inputs, A and . AND2 gate has also two inputs,
and B. The two outputs of AND gates are fed into the OR gate that produces the output Y.
Equality
1-bit equality comparator is simply designed with exclusive NOR gate. What about 4-bit equality comparator? 4-bit equality comparator is designed by connecting 4 exclusive NOR gates parallelly, as shown below:
Fig. 6‑18. Four-bit Equality Comparator
Each XNOR gate compares the inputs A and B as follows:
- XNOR3 for two inputs A3 and B3
- XNOR2 for two inputs A2 and B2
- XNOR1 for two inputs A1 and B1
- XNOR0 for two inputs A0 and B0
The outputs of all XNOR gates are fed into 4-input AND gate, which produces the logic “1” if only if all the inputs are “1”.
Less Than
The Less Than comparator can be designed with magnitude comparison by computing A – B and looking at the sign bit (msb: most significant bit), as shown in the below:
Fig. 6‑19. Less Than Comparator
where the term ‘N’ means the M-bit input or output, and [N-1] represents the sign bit, i.e. the most significant bit. If the sign bit is 1, A is less than B. If the sign bit is 0, A is greater than or equal to B.
6.5 Arithmetic Logic Unit
An ALU (Arithmetic Logic Unit) combines a variety of mathematical and logical operations, e.g. addition, subtraction, magnitude comparison, AND operation, OR operation, etc., into a single unit. The following figure shows a simplified ALU.
Fig. 6‑20. Simplified ALU
There are the two inputs A and B. Both of them are N bits. The operation of ALU determined by the function bits, F2 F1 F0. For example, if F2 F1 F0 = 000, ALU executes AND operation. If F2 F1 F0 = 001, ALU executes OR operation. The following table explains the operation of the ALU with the function bits.
Table 6‑2. ALU Operation with Function Bits
F2 | F1 | F0 | Function |
0 | 0 | 0 | A AND B |
0 | 0 | 1 | A OR B |
0 | 1 | 0 | A + B |
0 | 1 | 1 | Not used |
1 | 0 | 0 | A AND ~B |
1 | 0 | 1 | A OR ~B |
1 | 1 | 0 | A – B |
1 | 1 | 1 | SLT |
N-bit ALU
The simplified N-bit ALU of Fig. 6-20 is designed with 2-to-1 Multiplexer, full adder, zero extend, NOT gate, OR gate, AND gate, and 4-to-1 Multiplexor, as shown in Fig. 6-21, where all the units are N bits.
Fig. 6‑21. Design of N-bit ALU
Input A (n-bit) directly is fed into the full adder, OR gate, or AND gate. Input B (n-bit) is fed into 2-to-1 Multiplexor with and without NOT gate, where 2-to-1 Multiplexor produce either B or depending on the function bit F2 value. If the function bit F2 is true (F2 = 1), the multiplexor produces
. If the function bit F2 is false (F2 = 0), it produces B. The full adder has two inputs A and B (or
). In a similar manner, each logic OR or AND gate has two inputs A and B (or
). Zero extend detects the most significant bit of the full adder output (the sum S) and produces a total of N bits, where the other bits except the least significant bit are filled with ‘0’.
4-to-1 Multiplexor has the following four inputs:
- the output of zero extend
- the output of the adder
- The output of OR gate
- The output of AND gate
It forward one of inputs to the output Y depending on the two function bits F1 F0.
Let’s look at an example how the ALU operates with the following inputs:
- Input A = 25
- Input B =32
- Function bits F2 F1 F0 = 111
where we assume this is a 32-bit ALU. Input A = 25 (32-bit) is directly fed into the full adder, whereas input (32-bit) is fed into the full adder because 2-to-1 Multiplexor produces
with F2 = 1. Here, the full adder works as subtractor. Note that the carryin of the full adder is F2 = 1.
Fig. 6‑22. SLT Operation of N-bit ALU
The output of the adder is -7, i.e. A – B = 25 – 32 = -7. The most significant bit (msb) S31 is equal to 1 because the output value of the adder is negative. The zero-extend extends the msb and produces 0x00000001. Since F1 F0 = 11, the output of zero-extend is forwarded to the output of 4-to-1 Multiplexer, i.e. Y = 0x00000001.
Exercises
Let’s execute the designed 32-bit ALU with the following inputs:
- Input A = 16
- Input B =31
- Function bits F2 F1 F0 = 110
where we assume this is a 32-bit ALU. Input A = 16 (32-bit) directly is fed into the full adder, whereas input (32-bit) is fed into the full adder because 2-to-1 Multiplexor produces
with F2 = 1. Here, the full adder works as subtractor.
Fig. 6‑23. Subtract Operation of N-bit ALU
The adder executes the following operation:
- Binary input A = 0000|0000|0000|0000|0000|0000|0001|0000
- Binary input = 1111|1111|1111|1111|1111|1111|1110|0000
- Carryin F2 = 0000|0000|0000|0000|0000|0000|0000|0001
- Binary output S = 1111|1111|1111|1111|1111|1111|1111|0001 (=-15)
Since two function bits F1 F0 = 10, the 4-to-1 Multiplexer forwards the binary output S to the output value Y = S = 0xFFFFFFF1.
Logical Shift
A logical shift is a bitwise operation that shifts all the bits. The two base variants are the logical left shift and the logical right shift. In the logic left shift, shift all the bits to left and fill empty spaces with 0’s:
11001011 LSL 1 = 10010110
where the underlined zero is added to fill the empty spaces. The most significant bit is discarded.
In the logical right shift, shift all the bits to right and fill empty spaces with 0’s:
11001011 LSR 2 = 00110010
where the underlined zeros are added to fill the empty spaces. The least significant bits are discarded.
Arithmetic Shift
An arithmetic shift is also a bitwise operation that shifts all the bits. The two base variants are the arithmetic left shift and the arithmetic right shift. The operation of the arithmetic left shift is the same as the logic left shift. The vacant least significant bit is fill with zero and the most significant bit is discarded.
The arithmetic left shift is equivalent to multiplication. After we execute ALS by 1 bit, the original value is multiplied with 21-bit. For example, if you execute ALS by 1 bit with 00010111 (=23), the operation returns 00101110 (= 46). If you execute ALS by 2 bits with 00010111 (=23), it returns 01011100 (=23 × 22 = 92).
The arithmetic right shift is equivalent to division. After we execute ARS by 1 bit, the original value is divided by 21-bit. For example, if you execute ARS by 1 bit with 00010111 (=23), the operation returns 00001011 (=11), where the result is always round down.
where the vacant most significant bit is filled with a copy of the original msb zero, where the original number is positive. If the number is negative, the vacant most significant bit is filled with one.
Let’s execute ARS by 1 bit with 11101001 (=-23). The operation returns 11110100 (-12), where the vacant msb is filled with a copy of the original msb one. The result is always round down.
Exercises
Execute the logical shift operation of the following values:
- 11001 LSR 2 = 00110
The original value 11001 is shifted right. The vacant msb is filled with zero and the lsb is discarded.
- 11001 LSL 2 = 00100
The original value 11001 is shifted left. The vacant lsb is filled with zero and the msb is discarded.
Execute the arithmetic shift operation of the following values:
- 11001 ASR 2 = 11110
The original value 11001 is shifted right. The vacant msb is filled with a copy of the original msb.
- 11001 ASL 2 = 00100
The original value 11001 is shifted left. The vacant lsb is filled with a copy of the original lsb.