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 (C_out). In the second column from the right side, the sum of 0, 1, and the carry 0 (C_in) is 1 with a carry 0 (C_out). In the third column from the right side, the sum of 1, 1 and the carry 0 (C_in) is 0 with a carry 1 (C_out). In the fourth column, the sum of 0, 0, and the carry 1 (C_in) is 1 with a carry 0 (C_out).

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 C_out. But it lacks a C_in (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 (C_in)
• Outputs: Carry out (C_out), 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 C_in are 001, the sum S is ‘1’. If the inputs A, B, and C_in are 110, the sum S is ‘0’. The C_out 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 C_in are 110, the C_out is ‘1’.

Table 6‑1. Truth Table of 1-bit Full Adder

We can simplify the outputs S and C_out 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:

• AND₁: , , and
• AND₂: , , and
• AND₃: , , and
• AND₄: , , 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 C_out.

Fig. 6‑5. K-map representation of the output C_out

From the above figure, we can express the output C_out in terms of input variables as follows:

In order to produce the output C_out, 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 C_out

Each AND gate has the following inputs:

• AND₅: and
• AND₆: and
• AND₇: and

All outputs of the AND gates fed into the OR gate that produces the carryout C_out.

By combining Figs. 6-4 and 6-6, we can draw the 1-bit full adder with the carry-in C_in, 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 C_in; and two outputs, S and C_out. All the logic gates (ANDs and ORs) for the outputs S and C_out 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 C_out is produced with three AND gates and one OR gate in the same way to generate the output C_out 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 C_out of the first full adder connected to the carry-in C_in of the second full adder, C_out of the second full adder connected to C_in of the third fuller adder, and C_out of the third full adder connected to C_in of the fourth fuller adder, as shown in the following figure:

Fig. 6‑8. Four-bit Adder

where the binary input A includes A₃, A₂, A₁ and A₀, the binary input B includes B₃, B₂, B₁ and B₀, C_in is C₀, the output S includes S₃, S₂, S₁ and S₀, and the C_out is C₄.

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 A₀, B₀ and C₀ is 1 (S₀), the sum of A₁, B₁ and C₁ is 1 (S₁), the sum of A₂, B₂ and C₂ is 1 (S₂), and the sum of A₃, B₃ and C₃ is 0 (S₃). By collecting all the bits S₃ – S₀, 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 (9^th 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 C_in = 1 to the lsb, as shown in the below figure:

Fig. 6‑10. Four-bit Subtractor

where the input bits A₃ through A₀ are fed into the full adder directly, the input bits B₃ through B₀ are fed into the full adder after flipping the bits with NOT gates, and the first carryin C₀ set to 1, C₀ = 1. The Boolean equation of the above block diagram is expressed as shown below:

The subtractor produces the output Y, Y₃ through Y₀, and the carryout C₄.

Let’s subtract 3 from 7 using the four-bit subtractor.

• 7 = 0111 (A); A₃ = 0, A₂ = 1, A₁ = 1, A₀ = 1,
• 3 = 0011 (B); B₃ = 0, B₂ = 0, B₁ = 1, B₀ = 1.

The binary inputs A and B (A₃ – A₀ and B₃ – B₀) 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 A₃ through A₀ are fed into the full adder directly, the input bits B₃ through B₀ 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 S₃ through S₀, and the carryout C₄, where the carryout C₄ 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 B₃, B₂, B₁ and B₀. Then the four-bit Adder-Subtractor produces the output bits, S₃ through S₀, and the carryout C₄. 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 C₁ 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, S₃ through S₀, and the carryout C₄. 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 A₃ through A₀ are directly fed into the adders. On the other hand, the input bits B₃ through B₀ 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 A₀ = 1, = 0, carryin C₀ = 1 fed into the first FA, and then produce S₀ = 0 and carryout C₁ = 1.
• Three inputs A₁ = 0, = 0, carryin C₁ = 1 fed into the second FA and then produce S₁ = 1 and carryout C₂ = 0.
• Three inputs A₂ = 1, = 0, carryin C₂ = 0 fed into the third FA, and then produce S₂ = 1 and carryout C₃ = 0.
• Three inputs A₃ = 0, = 1, carryin C₃ = 0 fed into the fourth FA, and then produce S₃ = 1 and carryout C₄ = 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

• C_out (C₁) of the first full adder connected to C_in of the second fuller adder, C_out (C₂) of the second full adder connected to C_in of the third fuller adder, etc.
• Binary input A includes A₇ through A₀
• Binary input B includes B₇ through B₀
• C_in: C₀
• Output S includes S₇ through S₀.
• C_out: C₄

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. AND₁ gate has two inputs, A and . AND₂ 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:

• XNOR₃ for two inputs A₃ and B₃
• XNOR₂ for two inputs A₂ and B₂
• XNOR₁ for two inputs A₁ and B₁
• XNOR₀ for two inputs A₀ and B₀

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, F₂ F₁ F₀. For example, if F₂ F₁ F₀ = 000, ALU executes AND operation. If F₂ F₁ F₀ = 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

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 F₂ value. If the function bit F₂ is true (F₂ = 1), the multiplexor produces . If the function bit F₂ is false (F₂ = 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 F₁ F₀.

Let’s look at an example how the ALU operates with the following inputs:

• Input A = 25
• Input B =32
• Function bits F₂ F₁ F₀ = 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 F₂ = 1. Here, the full adder works as subtractor. Note that the carryin of the full adder is F₂ = 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) S₃₁ is equal to 1 because the output value of the adder is negative. The zero-extend extends the msb and produces 0x00000001. Since F₁ F₀ = 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 F₂ F₁ F₀ = 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 F₂ = 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 F₂ = 0000|0000|0000|0000|0000|0000|0000|0001
• Binary output S = 1111|1111|1111|1111|1111|1111|1111|0001 (=-15)

Since two function bits F₁ F₀ = 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 2^1-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 × 2² = 92).

The arithmetic right shift is equivalent to division. After we execute ARS by 1 bit, the original value is divided by 2^1-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.