Logic Gates and Circuits

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

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": a diagram which represents the electrical components used to implement the operation:

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 logic gates 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):
absc
0000
0110
1010
1101
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:

There are two important things to notice about this circuit:
  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:
abc (in) sc (out)
00000
00110
01010
01101
10010
10101
11001
11111
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
c out = 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
c out = (a' b + a b') c + a b (c' + c)
With the Complement and Identity axioms we can write the carry out as
c out = (a' b + a b') c + a b
since
c + c' = 1
and
a b * 1 = ab.
This enables us to construct the full adder as the following circuit:
Be sure and check this!

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 comlicated; without the benefits of Boolean Algebra, it is probable that you would not have the opportunity to learn this fascinating subject in preperation for your fascinating career in computers!

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

Go to:Title PageTable of ContentsIndex

©2002, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.