Combinational Logic Circuits

Section 7.1 Combinational Logic Circuits

Combinational logic circuits have no memory. The output at any given time depends completely upon the circuit configuration and the input(s).

Subsection 7.1.1 Adder Circuits

One of the most fundamental operations performed in the CPU is to add two bits. We begin with two definitions. (The reason for the names will become clear later in this section.)

Half Adder

A combinational logic device that has two 1-bit inputs, $x_{i}$ and $y_{i}\text{,}$ and two outputs that are related as shown by the truth table:

$x_{i}$	$y_{i}$	$Carry_{i+1}$	$Sum_{i}$
$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{1}$
$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{1}$
$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{0}$

where $x_{i}$ is the $i^{th}$ bit of the multiple bit value, $x\text{;}$ $y_{i}$ is the $i^{th}$ bit of the multiple bit value, $y\text{;}$ $Sum_{i}$ is the $i^{th}$ bit of the multiple bit value, $Sum\text{;}$ $Carry_{i+1}$ is the carry from adding the next-lower significant bits, $x_{i}\text{,}$ $y_{i}\text{.}$

Full Adder

A combinational logic device that has three 1-bit inputs, $Carry_{i}\text{,}$ $x_{i}\text{,}$ and $y_{i}$ and two outputs that are related as shown by the truth table:

$Carry_{i}$	$x_{i}$	$y_{i}$	$Carry_{i+1}$	$Sum_{i}$
$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{1}$
$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{1}$
$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{0}$
$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$
$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{1}$

First, let us look at the Karnaugh map for the sum:

There are no obvious groupings. We can write the function as a sum of product terms from the Karnaugh map.

\begin{align} Sum_i(Carry_i,x_i,y_i) &= Carry_i' \cdot x_i' \cdot y_i + Carry_i' \cdot x_i \cdot y_i'\notag\\ &\quad +\ Carry_i \cdot x_i' \cdot y_i' + Carry_i \cdot x_i \cdot y_i\label{eq-sum}\tag{7.1.1} \end{align}

We can readily see three groupings on the Karnaugh map for carry:

These groupings yield a three-term function that defines when $Carry_{i+1} = 1\text{:}$

\begin{gather} Carry_{i+1} = x_i \cdot y_i + Carry_i \cdot y_i + Carry_i \cdot x_i \label{eq-carry}\tag{7.1.2} \end{gather}

Equation (7.1.1) together with Equation (7.1.2) lead directly to the circuit for a full adder in Figure 7.1.1.

Figure 7.1.1. A full adder circuit.

For a different approach, we look at the definition of half adder. The sum is simply the XOR of the two inputs, and the carry is the AND of the two inputs. This leads to the circuit in Figure 7.1.2.

Figure 7.1.2. A half adder circuit.

Instead of using Karnaugh maps, we will perform some algebraic manipulations on Equation (7.1.1). Using the distribution rule, we can rearrange:

\begin{align} Sum_i(Carry_i,x_i,y_i) &= Carry_i' \cdot (x_i' \cdot y_i + x_i \cdot y_i') + Carry_i \cdot (x_i' \cdot y_i' + x_i \cdot y_i)\notag\\ &= Carry_i' \cdot (x_i \oplus y_i ) + Carry_i \cdot (x_i' \cdot y_i' + x_i \cdot y_i)\label{eq-maybexor}\tag{7.1.3} \end{align}

Let us manipulate the last product term in Equation (7.1.3).

\begin{align*} x_i' \cdot y_i' + x_i \cdot y_i &= x_i \cdot x_i' + x_i \cdot y_i + x_i' \cdot y_i' + y_i \cdot y_i'\\ &= x_i \cdot (x_i' + y_i) + y_i' \cdot (x_i' + y_i)\\ &= (x_i + y_i') \cdot (x_i' + y_i)'\\ &= (x_i \oplus y_i)' \end{align*}

Thus,

\begin{align} Sum_i(Carry_i,x_i,y_i)&= Carry_i' \cdot (x_i \oplus y_i ) + Carry_i \cdot (x_i \oplus y_i)'\notag\\ &= Carry_i \oplus (x_i \oplus y_i)\tag{7.1.4} \end{align}

Similarly, if we ignore the two overlapping groupings on the Karnaugh map that gave us Equation (7.1.2), we get:

to give the equation:

\begin{align} Carry_{i+1}&= x_i \cdot y_i + Carry_i \cdot x_i' \cdot y_i + Carry_i \cdot x_i \cdot y_i'\notag\\ &= x_i \cdot y_i + Carry_i \cdot (x_i' \cdot y_i + x_i \cdot y_i')\notag\\ &= x_i \cdot y_i + Carry_i \cdot (x_i \oplus y_i)\label{eq-fullcarry}\tag{7.1.5} \end{align}

Notice that the first product term in Equation (7.1.5), $x_i \cdot y_i\text{,}$ is generated by the $Carry$ portion of a half-adder, and that the exclusive or portion, $x_i \oplus y_i\text{,}$ of the second product term is generated by the $Sum$ portion. A logic gate implementation of a full adder is shown in Figure 7.1.3.

Figure 7.1.3. Full adder using two half adders.

You can see that it is implemented using two half adders and an OR gate. And now you understand the terminology “half adder” and “full adder.”

We cannot say which of the two adder circuits, Figure 7.1.1 or Figure 7.1.3, is better from just looking at the logic circuits. Good engineering design depends on many factors, such as how each logic gate is implemented, the cost of the logic gates and their availability, etc. The two designs are given here to show that different approaches can lead to different, but functionally equivalent, designs.

Subsection 7.1.2 Ripple-Carry Addition/Subtraction Circuits

An $n$-bit adder can be implemented with $n$ full adders. Figure 7.1.4 shows a 4-bit adder.

Figure 7.1.4. Four-bit adder.

Addition begins with the full adder on the right receiving the two lowest-order bits, $x_0$ and $y_0\text{.}$ Since this is the lowest-order bit there is no carry and $c_0 = 0\text{.}$ The bit sum is $s_0\text{,}$ and the carry from this addition, $c_1\text{,}$ is connected to the carry input of the next full adder to the left, where it is added to $x_1$ and $y_1\text{.}$

So the $^{th}$ full adder adds the two $i^{th}$ bits of the operands, plus the carry (which is either $\binary{0}$ or $\binary{1}$) from the $(i-1)^{th}$ full adder. Thus, each full adder handles one bit (often referred to as a “slice”) of the total width of the values being added, and the carry “ripples” from the lowest-order place to the highest-order.

The final carry from the highest-order full adder, $c_4$ in the 4-bit adder of Figure 7.1.4, is stored in the CF bit of the Flags register (see Section 8.2). And the exclusive or of the final carry and penultimate carry, $c_4 \oplus c_3$ in the 4-bit adder of Figure 7.1.4, is stored in the OF bit.

Recall that in the 2's complement code for storing integers a number is negated by taking its 2's complement. So we can subtract $y$ from $x$ by doing:

\begin{align} x - y&= x + (\textrm{2's complement of}\ y)\notag\\ &= x + [(y\textrm{'s bits flipped}) + 1]\tag{7.1.6} \end{align}

Thus, subtraction can be performed with our adder in Figure 7.1.4 if we complement each $y_i$ and set the initial carry in to $\binary{1}$ instead of $\binary{0}\text{.}$ Each $y_i$ can be complemented by XOR-ing it with $\binary{1}\text{.}$ This leads to the 4-bit circuit in Figure 7.1.5 that will add two 4-bit numbers when $func = 0$ and subtract them when $func = 1\text{.}$

Figure 7.1.5. Four-bit adder/subtracter.

There is, of course, a time delay as the sum is computed from right to left. The computation time can be significantly reduced through more complex circuit designs that pre-compute the carry.

Subsection 7.1.3 Decoders

Each instruction must be decoded by the CPU before the instruction can be carried out. In the ARM architecture the instruction for adding the 32 bits in one source register to the 32 bits in another source register and leaving the 32-bit result in a destination register is

\begin{equation*} \binary{111100001000} xxxx dddd \binary{00000000} yyyy \end{equation*}

where “$xxxx$” specifies one source register, “$yyyy$” the other source register, and “$dddd$” specifies the destination register. The Control Unit must select the correct three registers based on these three 4-bit patterns in the instruction. It uses a decoder circuit to perform this selection.

Decoder: A device with $n$ binary inputs and $2^n$ binary outputs. Each bit pattern at the input causes exactly one of the $2^n$ outputs to equal $\binary{1}\text{.}$

So a decoder can be thought of as a device for converting an n-bit input to one of $2^n$ outputs. In some applications not all the $2^n$ outputs are used. For example, Table 7.1.6 is a truth table that shows how a decoder can be used to convert a BCD value to its corresponding decimal numeral display.

Table 7.1.6. BCD decoder. The 4-bit input causes the numeral with a $\binary{1}$ in its column to be displayed.

\(x_{3}\)
\(x_{2}\)
\(x_{1}\)
\(x_{0}\)
‘9’
‘8’
‘7’
‘6’
‘5’
‘4’
‘3’
‘2’
‘1’
‘0’

\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)

\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{1}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{0}\)
\(\binary{1}\)
\(\binary{1}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{1}\)
\(\binary{1}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)
\(\binary{0}\)

A $\binary{1}$ in a “display” column means that is the numeral that is selected by the corresponding 4-bit input value. There are six other possible outputs corresponding to the input values $1010$–$1111\text{.}$ But these input values are illegal in BCD, so these outputs are simply ignored.

It is common for decoders to have an additional input that is used to enable the output. The truth table in Table 7.1.7 shows a decoder with a 3-bit input, an enable line, and an 8-bit ($2^3$) output.

Table 7.1.7. Truth table for a $3 \times 8$ decoder with $enable\text{.}$ If $enable = 0\text{,}$ $y = 0\text{.}$ If $enable = 1\text{,}$ $y_x = 1$ and $y_j = 0$ for all $j \neq x\text{.}$

$enable$	$x_{2}$	$x_{1}$	$x_{0}$	$y_{7}$	$y_{6}$	$y_{5}$	$y_{4}$	$y_{3}$	$y_{2}$	$y_{1}$	$y_{0}$
$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$
$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$
$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$
$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{1}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$	$\binary{0}$

The output is 0 whenever $enable = 0\text{.}$ When $enable = 1\text{,}$ the $i^{th}$ output bit is 1 if and only if the binary value of the input is equal to $i\text{.}$ For example, when $enable = 1$ and $x = 011_2\text{,}$ $y = 00001000_2\text{.}$ That is,

\begin{align} y_3 &= x_2' \cdot x_1 \cdot x_0\notag\\ &= m_3\tag{7.1.7} \end{align}

This clearly generalizes such that we can give the following description of a decoder:

For $n$ input bits (excluding an $enable$ bit) there are $2^n$ output bits.
The $i^{th}$ output bit is equal to the $i^{th}$ minterm for the $n$ input bits.

The $3 \times 8$ decoder specified in Table 7.1.7 can be implemented with 4-input AND gates as shown in Figure 7.1.8.

Figure 7.1.8. Circuit for a $3 \times 8$ decoder with enable.

Decoders are more versatile than it might seem at first glance. Each possible input can be seen as a minterm. Since each output is $\binary{1}$ only when a particular minterm evaluates to $\binary{1}\text{,}$ a decoder can be viewed as a “minterm generator.” We know that any logical expression can be represented as the OR of minterms, so it follows that we can implement any logical expression by ORing the output(s) of a decoder.

For example, let us rewrite Equation (7.1.1) for the Sum expression of a full adder using minterm notation (see Section 5.5.2):

\begin{gather} Sum_i(Carry_i,x_i,y_i) = m_1 + m_2 + m_4 + m_7\tag{7.1.8} \end{gather}

and for the Carry expression:

\begin{gather} Carry_{i+1}(Carry_i,x_i,y_i) = m_3 + m_5 + m_6 + m_7\tag{7.1.9} \end{gather}

where the subscripts on $x\text{,}$ $y\text{,}$ and $Carry$ refer to the bit slice, and the subscripts on $m$ are part of the minterm notation. We can implement a full adder with a $3 \times 8$ decoder and two 4-input OR gates, as shown in Figure 7.1.9.

Figure 7.1.9. Full adder implemented with $3 \times 8$ decoder. This is for one bit slice. An $n$-bit adder would require $n$ of these circuits.

Subsection 7.1.4 Multiplexers

There are many places in the CPU where one of several signals must be selected to pass onward. For example, as you will see in Chapter 11, values to be added in the CPU may come from a CPU register, come from memory, or actually be stored as part of the instruction itself. The device that allows this selection is essentially a switch.

Mutliplexer (MUX): A device that selects one of multiple inputs to be passed on as the output based on one or more selection lines. Up to $2^n$ inputs can be selected by $n$ selection lines.

A 4-way multiplexer requires 2 selection lines and could be implemented as shown in Figure 7.1.10.

Figure 7.1.10. A 4-way multiplexer.

The output is given by:

\begin{gather} Output = s_0' \cdot s_1' \cdot w + s_0' \cdot s_1 \cdot x + s_0 \cdot s_1' \cdot y + s_0 \cdot s_1 \cdot z\tag{7.1.10} \end{gather}

The symbol used for a multiplexer is shown in Figure 7.1.11.

$s_{1}$	$s_{0}$	$Output$
$\binary{0}$	$\binary{0}$	$w$
$\binary{0}$	$\binary{1}$	$x$
$\binary{1}$	$\binary{0}$	$y$
$\binary{1}$	$\binary{1}$	$z$

Figure 7.1.11. Circuit symbol and truth table for a 4-way multiplexer.