# Logic Gates and Circuits

There are many kinds of circuits inside the modern CPU (Central Processing Unit) chip:

• ANDs and ORs (used to test and set individual bits in memory)
• 1's complement circuits (or invertors)
• multipliers
• shift registers (used to shift strings of bits left and right)
and so on. All of these circuits are constructed using the basic logical operations we have discussed previously. As we noted earlier, we use the notation of Boolean Algebra when these operations are implemented in computers. For each elementary Boolean operation there is an associated "gate" symbol: a diagram which represents the electrical components used to implement the operation:

• the AND gate:
• the OR gate:
• the NOT gate (or invertor):
As we discussed earlier, the XOR operation is not considered one of the fundamental logical operations. However, as we will see below, it is an extremely useful operation in computers and appears in circuits as the XOR gate:
In addition to these, there are two more gates which combine operations commonly used together. These are the NAND (or NOT AND) gate:
and the NOR (or NOT OR) gate:
In order to illustrate the usefulness of Boolean Algebra in computer design, let us consider how one might go about constructing a circuit to add two bits. We first construct a
truth table with columns for the inputs a and b (the operands of the addition operation) and columns for the outputs s (the sum) and c (the carry):
 a b s c 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
Here we have reversed the order of 1s and 0s in the truth table in order to accommodate our "natural" ordering for numbers when we do arithmetic. For instance, the last row corresponds to "1 + 1 equals 0 with a carry of 1".

It is straightforward to recognize that the column representing the sum of a and b is just the output of an XOR operation, and that the column representing the carry is the output of an AND. Using this knowledge, is easy to construct a circuit whose purpose is to add two bits and produce a sum bit and a carry bit as output:

1. intersecting wires which are electrically connected (such as the wires which connect the inputs a and b to the AND gate) are marked with a solid dot representing the connection;
2. intersecting wires which are not electrically connected cross each other using a "bridge" (as when the connection from the input b to the XOR gate crosses the wire for the input a leading to the the AND gate).
The above circuit has a special name: it is a "half adder". It differs from a "full adder" in that it is not capable of adding in the carry from a previous addition operation. A full adder implements the truth table:
 a b c (in) s c (out) 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
As before, the last row represents "1 + 1 + a carry of 1 from the previous place is equal to 1 with a carry into the next place". The sum of products form for the sum is
s = a' b' c + a' b c' + a b' c' + a b c
from the second, third, fifth and last rows (where c is the carry in from the previous place). The sum of products form for the carry out is
cout = a' b c + a b' c + a b c' + a b c
from the fourth and last three rows. We can use the distributive properties to "factor" these expressions into
s = a' (b' c + b c') + a (b' c' + b c)
and
cout = (a' b + a b') c + a b (c' + c)
and finally simplify the carry out into
= (a' b + a b') c + a b
using the Complement and Identity axioms, since
c + c' = 1
and
a b * 1 = ab.
This implementation of a full adder might be constructed as
But can we do better than this? A golden rule in chip design is to conserve "real estate": the surface area of the chip on which circuits are built is an expensive and limited resource, and you don't want to waste it. If we examine the sum closely, and use what we learned when we studied logic, we can express it as
s = a' (b X c) + a (b ↔ c)
= a' (b X c) + a (b X c)'

= a X (b X c)

(we said that XOR would be useful!)
We can use the associativity of XOR to write this as
s = (a X b) X c
which will allow us to share a gate with the carry out:
cout = (a X b) c + a b
This enables us to construct the full adder as the following circuit using less than half the number of gates from our previous naive design:

(Kudos to student Justin Von Wahlde for pointing out some of these simplifications!)

If we connect a half adder:
in the least significant bit to a series of full adders
as follows:
with the carry outs wired to the carry ins of the next most significant bits, we have an adder for a pair of signed integers. Here, the subscripts indicate which power of 2 each adder is working on. For instance, one half adder and 15 full adders (n = 15) make up an adder for a short integer, a half adder and 31 full adders (n = 31) make up an adder for a long integer, etc.
It should be clear that computer chip design is quite complicated; while adders are ubiquitous in CPU chips, our example here only scratches the surface (consider the complications involved in floating point operations). And our adder is not the end of that particular story.

Many modern computers use Intel CPU chips. During their relatively brief history, there have been:

• the 8080 (an 8-bit CPU);
• the 8086 (a 16-bit CPU);
• the 80386 (a 32-bit CPU); and
• the Xeon DP (a 64-bit CPU),

among a host of others. Because the early chips could add only 8 or 16 bits at a time, there had to be a way to string addition operations together. Those chips had both an ADD instruction and an ADC instruction; this latter carried the carry out of the previous addition into the next addition, allowing addition of arbitrarily long integers.

Do you suppose that Intel put separate adders on their CPU chips for those two instructions? Instead of using one half adder and 7 full adders on the 8080, strung together as we described above, they probably strung together 8 full adders. They then "latched" the carry in to zero (forced it to be zero) when an ADD instruction was executed, but connected it to the carry out of the previous operation when an ADC was executed. In this way they could avoid wasting space with two almost identical circuits, when one would do.

We suggest you design efficient circuits for some additional Boolean expressions:

1. (((c * b) + b')' + (c + b)) + (a * c)
2. (((a + b) * (b * a))' + (a * c)) + a'
3. ((a' * (a + c))' * (c + b)) * (a * b)

In the last section of this chapter we explore another example of a Boolean Algebra: set theory.