The first term, where Ben and Corey vote YES, and Alisha votes NO is this
term. Note that this term corresponds to:
A = 0 - which means NOT-A
is 1
B = 1
C = 1
so, when you AND all these
terms together, you get 1
under the conditions here.
There are three other
terms and we could make similar observations about them.
Now, with the minterm expressions, we can write an expression for the 3-person
voting function, V. We have:
This expression leads
directly to a circuit implementation using ANDs, ORs and Inverters.
Each minterm can be generated using a 3-input AND gate. The first
minterm is shown below.
You'll need three more circuits somewhat like this one for the complete
solution. Now, you should be able to construct the other three.
They are similar to the one above. Here they are. Each circuit
shows the output term from the truth table.
Next, consider how these small circuits must interact. The function
is 1 whenever the first term is 1,
OR when the second term is 1, OR when the
third term is 1, OR when the fourth term is
1.
To implement that you need the following circuit.
Keep in mind how this circuit comes about.
Each AND gate senses just one of the terms in the truth table, and is 1
whenever that corresponding element in the table is selected (by selecting
the correct inputs for that point in the truth table. In the expression
we saw earlier, the outputs of each AND gate are ORed together to produce
the output. Here's that function again.
Be sure that you can see how the circuit
above implements this function.
This function is composed of four minterms,
and as noted above each minterm corresponds to one entry of 1 in the truth
table. That implies the following algorithm for generating a Boolean
algebra function from a truth table.
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.
Note the properties of this algorithm:
It will always work to
allow you to generate a Boolean function from a truth table.
The Boolean function will
be a number of minterms ORed
together
The number of minterms
will be the number of places (1s)
in the truth table where the function takes on a value of 1.
This kind of function
is often referred to as a "sum of products"
form.
The sum of products form
leads directly to a "two layer"
implementation with ANDs
in the first layer and a single OR
in the second layer.
The number of ANDs
will be the number of places (1s)
in the truth table where the function takes on a value of 1.
That's one AND gate for
every minterm in the sum of products form you get for the function.
When we say two layers,
we are ignoring the possibility that you might require some inverters (NOTs)
to complement some of the input signals. (On the other hand, those
inverted signals might be available in the system, and you might not need
the inverters!)
Using minterms is not always the most efficient way to implement a circuit.
Although a minterm expansion will always produce a function you can implement,
for any truth table, there are better ways - ways that use fewer gates
and which therefore cost less to implement. We'll look at those next.
Circuit
Simplification
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 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.
