There are many kinds of circuits inside the modern CPU (Central Processing Unit) chip:
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):
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".
a b s c 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 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:
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
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
s = a' b' c + a' b c' + a b' c' + a b cfrom 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 cfrom 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 busing the Complement and Identity axioms, since
c + c' = 1and
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)We can use the associativity of XOR to write this as= a' (b X c) + a (b X c)'(we said that XOR would be useful!)
= a X (b X c)
s = (a X b) X cwhich will allow us to share a gate with the carry out:
cout = (a X b) c + a bThis enables us to construct the full adder as the following circuit using less than half the number of gates from our previous naive design:
If we connect a half adder:
(Kudos to student Justin Von Wahlde for pointing out some of these simplifications!)
in the least significant bit to a series of full adders
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.We suggest you design efficient circuits for some additional Boolean expressions:
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.
In the last section of this chapter we explore another example of a Boolean Algebra: set theory.
©2013, 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.