1:43
So let's start our discussion of how Don't Cares show up in multilevel logic
with a little bit of background. So let's recall that we made progress on
muli-level logic by simplifying the model.
The algebraic model really gets rid of a lot of the difficult Boolean behaviors to
let us do things like division and factor extraction.
But we lose some of the optimality, some of the result quality, some of the
expressivity of the model in the process. So an interesting question is how you get
it back, and one of the surprising answers is Don't Cares.
So recall that we run an espresso-style simplification on the two-level sum of
products formed in each node of a Boolean logic network.
And to help this, what's going to turn out to be the case is that we extract
Don't Cares from the surrounding logic, and then we use them inside each node.
And the big difference in multilevel logic is that the Don't Cares just
happen. They are a natural biproduct of the
Boolean network model and so there's a word for that, this is the title of this
lecture. They're called implicit Don't Cares
because they just happen as a natural consequence of the structure of the
graph. For the Boolean network model.
They're all over the place. In fact there're a lot of them.
They're very very useful for simplification, but they're not explicit.
The new thing is that we have to go hunt for them.
We need computational procedures to find them.
Let's just review a little bit about Don't Cares first.
In basic digital design, you probably learned this about Don't Cares.
And what we said was that a Don't Care was an input pattern that can never
happen. So I've got a little logic function here
a little grey box. F has inputs a b c d and I've got a carno
map shown on the right-hand side. Two by two, a b on the horizontal axis, c
d on the vertical axis. This carno map have, has ones in the a b
c d one o o o. 1001 and 0111 squares.
But it's also got a bunch of d's in it and the d's are Don't Cares.
And so what if we just tell you that the following patterns of a b c d cannot
happen? 1010, 1111.
Here I'm just going to check them now. 1100, 1101, 1110, 1111.
What if we tell you that those things cannot happen?
Then each of those things can become a Don't Care in the Karnaugh map.
And we get Don't Cares in, you know, one, two, thee, four, five, six places
corresponding to those patterns. And so we're to, free to decide if f is a
0 here or f is a 1 here because those things don't happen.
You know that output is not going to happen, so we get to decide what the
function should do to simplify things. And it's clear that we can simplify
things much further. with all these Don't Cares, I can circle
some nice big circles in the Karnaugh map.
So that's probably what you know about Don't Cares so far.
What's different in the multi level model?
Well, don't cares arise implicitly as a result of the Boolean logic network
structure, and you have to go find them. We actually have to go search for them
explicitly They don't just get handed to us like that previous slide.
There's a bunch of good references for these ideas.
the Giovanni DeMicheli book on Synthesis and Optimization of Digital Circuits is
good; some of my development is based on some of the ideas in Chapter 8.
ALthought I, I'm doing sort of a different version of the math.
the book by Devadas, Keutzer, and Ghosh on logic synthesis is also good.
And there's a very complete paper by a lot of authors, Bartlett, Brayton,
Hachtel, Jacoby, Morrison, Rudell, Sangiovanni-Vincentelli and Wang, on
implicit Don't Cares. That's a good place if you want to see
how it, how it really works. So let's do a, a sort of an informal tour
of how multilevel Don't Cares arise implicitly in the structure of the
Boolean network model, and let's start with this little Boolean network, and
let's look at the node called f. This is a very simple Boolean network.
It's got one node. F equals Xb plus bY plus XY.
And the question I would ask is, can I tell you anything just looking at this
network, about the Don't Cares and the node?
And the answer is no. I, I don't know any context for the
surrounding parts of the network. I cannot tell you that any patterns of X,
b, and Y are impossible. So as far as you know, all eight of the
patterns of X, b and Y are possible. And there's a little Karnaugh map shown
at the right, four squares by two squares, Xb on the horizontal axis, Y on
the vertical axis. And there's three groups of 1's circled
a, Xb pair, the bY pair and the XY pair. So what changes here?
Well, suppose we know something about the input.
In particular, suppose we know that X is not an input from the outside.
Suppose we know that X is computed inside the Boolean network.
So, just to be clear I'm labeling pis as the primary inputs, things that come into
the overall Boolean network, and pos as primary output, things that leave the
overall network. And so now x is not a primary input, it's
co-, computed thing inside the network. now can I say something about whether
there are any impossible patterns for the inputs to node f.
and the answer is yes. because there is some relationships
between a and b and X now, some things just can't happen because X is a function
of a and b. There are now some impossible patterns of
the variables X and b and Y. So let's just go look at those.
7:08
I'm showing again my Boolean network model with the X equals ab node connected
to the f equals Xb plus bY plus XY node. And I've got a little truth table here.
with the x equals ab node pointing at it, and it's got three columns, abX.
and under it all of the Boolean values of ab and X from 000 to 111, so there's
eight rows. And then there's another column that says
can it occur? And what we're really asking here is
inside this logic network, now that we know that X is ab.
Can each of these eight patterns of a and b and X actually occur?
The first thing we can do is just say, well, four of them can certainly occur
because X is equal to a and b. The patterns associated with X equals to
a and b can occur. So 000 can occur, 010 can occur, 100 can
occur, and 111 can occur. We have yes's in all of those rows.
So, it seemed that all the other rows are no's and yeah that's actually correct.
There are four patterns that can not happen to a b and X, 001, 011, 101 and
110. And you know, we can illustrate one of
those clearly, by just pointing at one of the rows.
So, let's point at the 001 row and say, well why is it that cannot occur?
And the answer is, well, a and b are 0's, and X is an end gate output, you can't
put two 0's into an AND gate and have a 1 come out.
So that's just not possible. So here's all of the possible and
impossible patterns for a and b and X. Now, however, I'm not that interested in
the patterns of a and b and X. I'm interested in the patterns of X and B
and Y. Because that's actually what f is a
function of. I need to figure out how I can take the a
b X patterns and I know something about what can't happen, and turn those things
into X b Y patterns. And all I can [COUGH] all I can tell you
at this point is you just have to sort of stare at things.
we're going to figure out computationally how to do this in a bit.
So the first thing is that there are three pairs of rows.
the rows that start 0, 0. The rows that start 0, 1.
And the rows that start 1, 1 in this table of xbY eight rows, patterns.
Because look, Y as far as we know, is a primary input.
It just you know, it's not dependent on anything.
So Y can be anything. But X and b are dependent on each other.
And the Xb00 pattern can happen. The Xb01 pattern can happen.
And the Xb11 pattern can happen. And that would seem to suggest that these
two rows, XbY is 100, and 101, cannot happen and, and that's actually correct.
And why that can't happen is that this is trying to put b equals 0 in to what is
actually an AND gate, and get X equals 1 out.
You don't put a 0 in an and gate and get a 1 out.
A 0 cannot go into the X node and have a 1 come out.
So any of the patterns that have X is 1 and b is 0 are impossible.
And so we found a couple of impossible patterns for our f node.
And so we can use those things. We can check in our Karnaugh map which
I've got drawn here again. For the Xb versus y, four variables
horizontally two variables vertically I've got the same Karnaugh map drawn with
the same three terms, XbbXY. Now, I'm going to say, what happens if we
add the impossible patterns? The answer is we have two impossible
patterns. XbY is 100 and 101.
I get two Don't Cares. The entire right column of the Karnaugh
map 100 and 101 are now Don't Cares. Suddenly, I can circle the Karnaugh map
in a different way. I can circle this in what I think is a
nicer solution. if I'm going to write the function now.
I have that the function is equal to x plus bY.
And that's simpler than Xb plus bY plus XY.
And so it looks like I've saved something.
So I can actually simplify this network. It is no longer Xb plus bY plus XY, it's
now X plus bY. It looks like I saved three literals.
And actually saved a product term. This is actually really good.
So, just because of the context of how X is a function of a and b, there are
patterns of X and b and Y that cannot happen.
So we can continue this and just try another one.
now what happens if Y is also a pattern, what happens if Y is b plus c?
It's again computed internally. We can do this again, we can say, are
there impossible patterns of the inputs and outputs of the Y node of b, and c,
and Y? And so, I've got another truth table here
that has three columns, bcY, with eight rows from 000 to 111.
And the column to the right says, can it occur.
And you start just like before, with the patterns that can occur.
You can send 2 0's into an OR gate and have a 0 come out.
The 0 0 0 is a yes. If you send any 1 in to an OR gate, you
get a 1 out. The 011, 101 and 110 rows for bcY are a
yes. Which leaves the other rows as a no.
001, 010, 100 and 110 cannot happen. We can draw those to be clear, the 001
row says you cannot put two 0's in an OR gate and have a 1 come out.
That's not possible. And the 110 row says, similarly, you
can't put two 1's into an or gate and have a 0 come out.
All four of the rows in this truth table are impossible because they're just not
legitimate patterns of inputs and outputs for the Y node in this network.
Now, we can take all of the information we've got, I'll admit a rather
complicated looking slide here. I've got the logic network, again, X
equals ab node. Y equals b plus c node.
Feeding the f equals Xb plus bY plus XY node.
I've got the impossible patterns for abX, again, drawn above it.
001, 011, 101, 110. And I've got the newly found impossible
patterns of bcY drawn above, above it 001, 010, 100, 110.
And I've got another truth table xbY, eight rows, 000 to 111 and another column
that says, can it occur? And just as before, I don't really want
The abx impossible patterns and the bcy impossible patterns.
I want po-, impossible patterns I can do something with, that I can use to create
maybe some Don't Cares for the f node. And so right now, you have no
computational technique for doing this other than to stare at this and try to
figure out what can and can't happen. So the first thing you do is you say,
alright, look, I stare at it. And I believe that XbY is 000, 001, 011
and 111 can happen. And if you just try all those patterns on
your x equals ab and y equals b plus c nodes.
You'll see that you can find other values for the inputs not specified.
In this case. A and C, that make that work and so that
leaves us with these four patterns. Zero 1, 0.
One, 0, 0. One, 0, 1.
One, 1, 0. For X, B, Y, as impossible and we can
again look at them. Why is 0,1, 0, and impossible pattern for
X, B, Y? Because you are trying to put a 1 in an
orgate and get a 0 out. Y is 1, 1, 0, impossible, because you're
trying to put a 1 in an OR gate and get a 0 out.
Why are the two patterns, 1, 0, 0, and 1, 0, 1 impossible?
Because you're trying to put a 0 and an AND gate and get a 1 out.
Because of the context of this network of what X is as a function of a and b and
what Y is as a function of b and c. Certain patterns of X and b and Y are
impossible jointly. And these things become Don't Cares.
And so, we get some more good stuff, okay?
So if we take these impossible patterns, and so I'm drawing the Boolean network
again, X is ab, Y is b plus c, f is Xb plus bY plus XY.
I'm drawing the impossible pattern above the XbY inputs to f 010, 100, 101, 110
for X b and Y. Those are impossible.
I've now got four don't cares that I can use, and what I actually get is to new
Don't Cares. I get a Don't Care for the XbY 010 and I
get a Don't Care for the XbY 111. So it's in this Karnaugh map four columns
wide by two rows deep. Only the Xb00 column has 0's in it.
Everything else has a Don't Care or a 1 in it.
So if I was to circle this Karnaugh map, I'd just circle this.
I'd circle the two middle columns. And if I write this as a Boolean
equation, this is now f equals b. And that's pretty surprising, because
that means that. I don't really care about the X node, and
I don't really care about the Y node. I only really care about the b primary
input. Just because of the context of X and Y
now being related because they share some variables.
And I don't even have to circle one of those previous ones in this Karnaugh map,
because become a Don't Care because as this context.
So wow, f was Xb plus bY plus XY. That looks like three AND gates in an OR
gate with three inputs and that whole thing gets replaced by a wire.
Wow, thatâs pretty surprising. That's pretty impressive.
And so this is just the first start of our examples for how we find Don't Cares.
This is one kind of a Don't Care. These are actually things called
Satisfiability Don't Cares and Controlability Don't Cares.
But these are the only kinds, there's actually some more kinds.
So in the next lecture, we're going to look at some other implicit Don't Cares
that we can pull out of this network.