Boolean functions are
somewhat peculiar because a complex Boolean function can often be a simple
function masquerading in a more complex form. In this section we're going to
examine that phenomenon.
It's important to look at
this because simpler Boolean functions translate directly into less expensive
circuits with fewer gates. It's economically important to produce the simplest
possible circuit for any design work that you do! We'll begin by looking at the
example function for the voting circuit. Here's the function again in all its
glory.
There are some things in
the function that suggest some actions to take. For example, the last two terms
in the function are:
Let's work on those last two
terms. These two terms differ just in the way A enters the two terms. It shows
up both as A and as its inverse. You are probably tempted to write this
expression as:
Actually, that will prove to be a
good strategical move, but we have to consider some basic Boolean algebra
first. There are some simple Boolean algebra facts we need to know first. Be
sure you understand why these are true.
For ANDs
In the X-terms, X can be
either 0 or 1.
If X = 0, the inverse is 1 &
vice versa.
For ORs
In the X-terms, X can be
either 0 or 1.
If X = 0, the inverse is 1 & vice
versa.
Going back to the last two
terms of the voting function, we have:
Last two terms =
=
Here, we take advantage of the
last item in the table for the OR function to eliminate the A-terms.
Using the results we have
been able to generate, we can now note that the voting function, F, can be
simplified.
can be simplified to:
We can combine the last two terms
into one, simpler, term, eliminating A in that term. However, we are still
stuck with terms that involve three variables for the first two terms in F.
If you think about
what we did, you realize that the term, ABC
(the term with no inverted variables), could have been combined with any of the
other three terms. Each such combintation would have eliminated a different
variable in the shorter result. It was an arbitrary decision to combine it with
the third term.
However, by
combining with one of the three terms, we "used up" the
ABC term. Or did we?
It would have been
nice if we could have combined the term ABC
with all three of the other terms. It seems a shame to have used it up with
just one term.
There's something peculiar
with logic expressions however. We can actually do what we want to do - combine
ABC with all three of
the other terms. To do that we have to notice that
ABC = ABC + ABC
This is just a restatement
that if you OR
anything with itself, you get the original quantity back (X
+ X = X). Remember 0 + 0 = 0 and 1 + 1 = 1 and
the expression ABC is
either 0 or 1.
Now, we can generate a
much simpler expression for the voting function. We start with the original
voting function.
Expand R with multiple copies of
the last term.
Then use our earlier method to get
a simpler version of the voting function:
Here's a circuit that
implements the simplified form we found. Putter with this circuit to see how it
works. Notice how the circuit is wired, and notice that we had to "snake" the A
line around the entire circuit to get it inot the lowest AND gate.
What If?
There are obvious "What
If?" questions here. What if the circuit is really large? Then you will need
to have formal algorithms that are programmed and use the program. That's what
is done. There are sets of design tools to help you do that. Of course, those
sets of design tools usually use templates of smaller circuits, and large
circuits often have large parts that are just repeated use of a template of a
smaller circuit.
There is some hope that
you can understand a really large circuit. The material in this lesson should
help you understand how the small, but reusable, parts of a large circuit are
designed.
On the Structure of the Result and Points to Note
The structure that comes
out of our approach is a two-layer structure, with all AND gates in the first
layer and all OR gates in the output layer. You will always get that kind of
structure if you use the minterm-based approach. Minterms are often referred to
as sum-of-product expressions. Sum-of-product expressions give rise naturally
to two layer AND-OR structures when they are implemented.
Secondly you should note
that the structure we found is not necessarily always the simplest. There may
be, for example, simpler three layer structures.
Finally, you may be
a bit perplexed at all this. Maybe we were just lucky to get an expression that
was simpler. It's not clear how to do that consistently, and how to figure out
how to do it when it's possible. In the next section we'll look at
Karnaugh maps which are a way
of visualizing how to group terms in a way that permits you to simplify complex
expressions.
Two Layer Structures
Here is an example of a
two-layer circuit we saw earlier. The input layer is composed of ANDS and the
output layer is a single OR. This circuit implements a sum of products
expression.
What needs to be stressed
here is that you can always use the algorithm we indicated above.
Given a truth table
with one or more places in which the function takes on a value of
1,
Write out the
minterms for each place in the table where the function takes on a value
of 1.
OR
all of those minterms together.
and this algorithm will always result in a two-layer
structure like the one above. (We don't count the inverters as a layer.)
This is a straight forward procedure that guarantees that
you will be able to build a circuit for any function you have that is
represented with a truth table. While this process guarantees a circuit, it
does not guarantee the best circuit!
Consider a
simple example. Here is a simple truth table.
P
Q
F
0
0
1
0
1
0
1
0
1
1
1
0
Next, look at the minterms that are represented in
the truth table.
P
Q
F
Minterms
0
0
1
0
1
0
1
0
1
1
1
0
Once you have the table
like this, then:
Form the function represented
by the truth table by determining the minterm that produces each one in the
truth table.
The minterms are shown to
the right of the entries which are ones in the table above.
From the minterm expression,
generate a two layer circuit that implements the function found in the
previous step.
From the minterm expression,
generate a two layer circuit that implements the function found in the
previous step.
There are some cautions here.
The function consists of
variables and complements of variables ANDed
together.
This assumes you have the
complements. But you can generate complements
by inverting signals.
Now, consider this circuit in
light of deMorgan's Theorem. deMorgan's Theorem
says:
deMorgan's Theorem also can be construed to say
the following if we invert both sides of the above equation.
If we consider the function earlier, we have:
If we are to implement this function, it would
look like this:
Now, apply the inverted form of deMorgan's
Theorem, and we have:
In words, we can NAND the input
terms (at the very left) and then NAND the result. Note the structure of this
result.
There are multiple NAND
operations. For example, P and Q are NANDed, as are their inverses.
In effect, both minterms
are inverted. Those are the two terms ANDed and inverted on the right
hand side of the last equation above.
After the minterms are
inverted they are inverted and ANDed again, effectively NANDing them.
That implies that the
entire thing can be implemented using only NAND
gates.
This function (above) can be implemented with the
circuit below.
Can we generalize this approach?
Functions of more variables
will have larger truth tables, but every entry that is a one corresponds to
a minterm - even in larger truth tables.
Every minterm can be
generated by ANDing together variables and complements of variables (NOT the
variable!).
Thus, a minterm can be
implemented with an AND gate, as long as the complements are available as
necessary.
Complements can be generated
by inverting a variable - passing the signal through an inverter.
Don't Cares
There is one thing we need to
point out about truth tables. Sometimes we don't care about certain elements in
the truth table. You might have trouble visualizing that, so consider the
following.
If you are wearing a digital
wristwatch, look at it. Somewhere within the watch there is a counter that
drives each digit displayed. If the digit runs from zero to nine, it takes
a four bit counter. However, the count will never be 10 or anything higher,
so when you design the decoder, you don't care about those numbers that will
never be seen. It will never be thirty-eleven minutes after fourteen
o'clock.
There are many other
situations in which Don't Cares
arise. The problem is what to do about them when they arise. What to do is
this.
If you have a function with
Don't Cares in the truth table, you may do whatever works best for you.
Choose any Don't Care as a one or zero as you wish. You don't have to
choose all of the Don't Cares as ones or as zeroes, and if you truly want
you can choose them randomly. (That might not be wise, but you can do it if
you want.)
When you get to circuit
simplification you will find that there is an art to choosing Don't Cares to
give the simplest possible circuit implementation.
