236 Digital Electronics

of Boolean expressions. The following guidelines should be followed while choosing the preferred
form for hardware implementation:

1. The implementation should have the minimum number of gates, with the gates used having the
minimum number of inputs.
2. There should be a minimum number of interconnections, and the propagation time should be the
shortest.
3. Limitation on the driving capability of the gates should not be ignored.

It is difficult to generalize as to what constitutes an acceptable simplified Boolean expression. The

importance of each of the above-mentioned aspects is governed by the nature of application.

7.3 Arithmetic Circuits – Basic Building Blocks

In this section, we will discuss those combinational logic building blocks that can be used to perform
addition and subtraction operations on binary numbers. Addition and subtraction are the two most
commonly used arithmetic operations, as the other two, namely multiplication and division, are
respectively the processes of repeated addition and repeated subtraction, as was outlined in Chapter
2 dealing with binary arithmetic. We will begin with the basic building blocks that form the basis of
all hardware used to perform the aforesaid arithmetic operations on binary numbers. These include
half-adder, full adder, half-subtractor, full subtractor and controlled inverter.

7.3.1 Half-Adder
A half-adder is an arithmetic circuit block that can be used to add two bits. Such a circuit thus has two
inputs that represent the two bits to be added and two outputs, with one producing the SUM output
and the other producing the CARRY. Figure 7.4 shows the truth table of a half-adder, showing all
possible input combinations and the corresponding outputs.
The Boolean expressions for the SUM and CARRY outputs are given by the equations

SUM S = AB + AB (7.5)

CARRY C = AB (7.6)

An examination of the two expressions tells that there is no scope for further simplification. While
the first one representing the SUM output is that of an EX-OR gate, the second one representing the

Figure 7.4 Truth table of a half-adder.

Arithmetic Circuits 237

Figure 7.5 Logic implementation of a half-adder.

CARRY output is that of an AND gate. However, these two expressions can certainly be represented
in different forms using various laws and theorems of Boolean algebra to illustrate the flexibility that
the designer has in hardware-implementing as simple a combinational function as that of a half-adder.
We have studied in Chapter 6 on Boolean algebra how various logic gates can be implemented in the
form of either only NAND gates or NOR gates. Although the simplest way to hardware-implement a
half-adder would be to use a two-input EX-OR gate for the SUM output and a two-input AND gate
for the CARRY output, as shown in Fig. 7.5, it could also be implemented by using an appropriate
arrangement of either NAND or NOR gates. Figure 7.6 shows the implementation of a half-adder with
NAND gates only.
A close look at the logic diagram of Fig. 7.6 reveals that one part of the circuit implements
a two-input EX-OR gate with two-input NAND gates. EX-OR implementation using NAND was
discussed in the previous chapter. The AND gate required to generate CARRY output is implemented
by complementing an already available NAND output of the input variables.

7.3.2 Full Adder

A full adder circuit is an arithmetic circuit block that can be used to add three bits to produce a
SUM and a CARRY output. Such a building block becomes a necessity when it comes to adding
binary numbers with a large number of bits. The full adder circuit overcomes the limitation of the
half-adder, which can be used to add two bits only. Let us recall the procedure for adding larger
binary numbers. We begin with the addition of LSBs of the two numbers. We record the sum under
the LSB column and take the carry, if any, forward to the next higher column bits. As a result,
when we add the next adjacent higher column bits, we would be required to add three bits if there
were a carry from the previous addition. We have a similar situation for the other higher column bits

A
[A.(A .B)]

(A.B)
S

[B.(A .B)]
B

Figure 7.6 Half-adder implementation using NAND gates.

238 Digital Electronics

A B Cin SUM (S) Cout

0 0 0 0 0
A S 0 0 1 1 0
Full 0 1 0 1 0
B Adder 0 1 1 0 1
Cin Cout 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Figure 7.7 Truth table of a full adder.

also until we reach the MSB. A full adder is therefore essential for the hardware implementation of
an adder circuit capable of adding larger binary numbers. A half-adder can be used for addition of
LSBs only.
Figure 7.7 shows the truth table of a full adder circuit showing all possible input combinations and
corresponding outputs. In order to arrive at the logic circuit for hardware implementation of a full
adder, we will firstly write the Boolean expressions for the two output variables, that is, the SUM
and CARRY outputs, in terms of input variables. These expressions are then simplified by using any
of the simplification techniques described in the previous chapter. The Boolean expressions for the
two output variables are given in Equation (7.7) for the SUM output (S) and in Equation (6.6) for the
CARRY output (Cout :

S = ABCin + ABC in + ABC in + ABCin (7.7)

Cout = ABCin + ABCin + ABC in + ABCin (7.8)

The next step is to simplify the two expressions. We will do so with the help of the Karnaugh mapping
technique. Karnaugh maps for the two expressions are given in Fig. 7.8(a) for the SUM output and
Fig. 7.8(b) for the CARRY output. As is clear from the two maps, the expression for the SUM (S
output cannot be simplified any further, whereas the simplified Boolean expression for Cout is given
by the equation

Cout = BCin + AB + ACin (7.9)

Figure 7.9 shows the logic circuit diagram of the full adder. A full adder can also be seen to comprise
two half-adders and an OR gate. The expressions for SUM and CARRY outputs can be rewritten as
follows:

S = C in AB + AB + Cin AB + AB

S = C in AB + AB + Cin AB + AB (7.10)

Similarly, the expression for CARRY output can be rewritten as follows:

Cout = BCin A + A + AB + ACin B + B

= AB + ABCin + ABCin + ABCin + ABCin = AB + ABCin + ABCin + ABCin
= AB1 + Cin  + Cin AB + AB