0:00
[NOISE].
So here in lecture 8.4, were going to introduce the controllability don't
cares. Now in the previous lecture we introduced
the satisfy ability don't cares that explain impossible patterns of inputs and
outputs associated with individual wires in the network.
But those turn out to be, don't care patterns.
Those turn out not to be impossible patterns that I can actually use to
optimize the two level structure of something inside a node.
Turns out there's a pretty easy recipe to go from the satisfiability don't cares,
to controllability don't cares that turn into real don't cares so we can actually
use to optimize something. So lets go see how we actually find
controllability don't cares. We've finished describing what the
satisfiability don't cares are, they belong to the wires inside the Boolean
logic network. What we have left are the controllability
and observability don't cares and in this lecture, we're going to talk about the
control ability don't cares. These are the first don't cares that are
really things that you can use to actually compute something to simplify
the inside of a logic node. The control ability don't cares actually
specify patterns that can not happen at the inputs to a network node.
So, how do you get the impossible patterns at the input to a node?
So I've got a nice little example here. I've got a node that says F equals
expression, then I got a bunch of nodes feeding it.
So X1 equals dot, dot, dot, X2 equals dot, dot, dot and then there's a vertical
set of dot, dot, dot that says Xn equals dot, dot, dot.
So we've got n Boolean network nodes, feeding F as an expression.
And I want to figure out what are the impossible patterns of F.
There's a suprisingly simple computational recipe.
So, the first thing you do, is you get all of the satisfiability don't cares on
all of the wires input to this node in the Boolean logic network.
So that's basically all of the X1 nodes and then you or together all of those
satisfy ability don't cares and remember their just Boolean functions 1 of the
great reasons for representing things as Boolean functions is that as we're going
to be able to see we can do things like. The union of all the patterns as a simple
operation of oaring together the Boolean functions that represent those patterns
and so, a really great thing about being able to do serious computational Boolean
algebra. So, you get the satisfiability don't
cares on all the wires input to the nodes, so those are the satisfiability
don't cares for the Xi's. You wore them all together and then you
universally quantify a way all the variables that are not used inside this
node because the Xi's could be in functions of many many different
variables. But if they do not appear in F, It's not
relevant. We have to get rid of those variables,
and universally quantifying them away is the right answer.
And the result is a Boolean function, which would be called CDCF below, that's
one for the impossible patterns of inputs to the node.
So, I can write this in a sort of a more mathematically precise form.
The controllability don't care for F, right is, well, what is it?
It starts with the sum on all the input wires Xi going into f of the
satisfiability don't care on the wire. Now, that sum sign, that big summation
sign is a Boolean, or so I'm going to order satisfy ability don't care for X1,
X2, x3, dot, dot, dot Xn. And then I'm going to universally
quantified all the variables that are just not used inside F.
If there's the variable inside there that does not show up on the right-hand side
of the F equation I universally quantified away.
And the result will be a Boolean function that makes a one for patterns of inputs
that are impossible for F. why does this work?
Alright, so I'm showing the same diagram at the top X1, X2, dot dot dot, Xn as
inputs to the F node, and again I've got the same formula.
The controlability don't care function is the universal quantification over all
variables not in f of the or sum of all the satisfyability don't cares on the
wires leading into F. Roughly speaking, why this works is that
the satisfyability factors on the input wires explain all of the impossible
patterns involving Xi's that are input to the F node.
So anything that's impossible that involves an Xi, which is an input to the
F expression, anything, okay, is possible.
Anything that's connected to the F node, the satisfyability don't cares explain
all the impossible patters. The OR operation on the Boolean
functions, representing the satisfyability Don't Cares, is the union
of all these impossible patterns. It's sort of a beautiful, simple thing if
you can do computation Boolean algebra You can do lots of set manipulations,
this is one of them. The universal quantify removes the
variables not used by F and it does so in the right way: we want patterns that are
impossible FOR ALL values of the removed variables and whenever you say I want
this result to be true for all of the things that I removed you use the for
all. You use the universal quantifier, the
upside down A quantifier. And so that's why this stuff actually
works, so let's go do a real one. So let's apply this computational scheme
for controllability don't care extraction to the F node below.
So I've got an X equals A plus B node and a Y equals A, B node and those thing feed
in f equals Xc plus Yd plus acd function. There's also the primary inputs ABCD
going into the left and the output f going out the right.
Our formula says that the way this works is, the controlability for f is the
universal quantification over all the variables not input to f of the or sum of
all of the satisfy ability don't care on the wires going into f and so if we just
sort of say well what are we looking at here.
The input variables, the things we have to look at for f, are X and Y.
The output of some internal Boolean nodes and the primary inputs ACD.
It looks like I need satisfyability Don't Cares for X, Y, a, c, and d.
What exactly are the variables not input into f?
The answer is b, b is the only variable that's not in f.
Right, a is in f, c is in f, d is in f, X is in f, Y is in f.
The only thing that's not in f that's in all this other stuff is b, we have to
quantify out the b. So a good question here, because we
haven't really addressed it so far, is, what about the satisfiability don't cares
on the primary inputs, you know, the things that don't have a network node in
front of them because in this case A goes right straight into the F node.
And C goes right straight into the F node, and D goes right straight into the
F node. And so, you know, those are things that
you know, conceivably should be important in this particular problem, but you can
take the words, I'm going to start by this statement it's important.
You can ignore the satisfy ability don't cares on the primary inputs, the a, c,
and d so wires that come in from the outside because their primary, why?
What would this satisfy ability to cares for a be?
It would be a, the output, if you will, it's a wire, right?
It's sort of like a a, a null Boolean network node.
it's the output, which is A, exclusive word with an expression for the thing
that makes A, which in this case is A, right.
So to satisfy the ability you don't care for a wire named a is a exclusive OR a
which is 0. There's no impact on the OR so you can
just ignore it, so our recipe just got a little bit simpler.
We still need to calculate the, the, the controllability don't care by quantifying
the way the variables not input to f and summing over all of the inputs that are
the satisfiability don't cares but the only things that matter are X and Y.
And so I'm just going to put two checkmarks by the Boolean nodes.
When you do this calculation, you just have to look at the stuff that came out
of an internally computed node in the Boolean network.
You only have to look at the arrows out of bubbles.
You don't have to look at the external inputs.
There's just nothing going on there. So, we only have to OR together the
satisfiability don't cares for X and Y, and then we have to quantify away the
stuff that does not appear in f. So if we just do that this is what we
get. So, again, I've got the networks shown
here x equals a plus b node y equals ab node feeding an f equals Xc plus Yd plus
acd node. I've got X and Y highlighted here just to
we can short of highlight the fact that that's what were working on.
Here's what happens, the controllability don't care for f is the universal
quantification with respect to be of the following quantity.
If this satisfy ability don't care for X, Melanie the check mark, which is X
exclusive, or a plus b, ORed with the satisfyability don't care for Y, which is
Y exclusive for ab, so I'm going to put a check on the network node for that.
if we do that, let's, let's take the universal quantification and just make it
happen, so we can see what's going to happen.
Well, we're going to get that expression X exclusive word a plus b plus Y,
exclusive word with ab. We're going to cofactor that by setting b
equal to one and you were going to and that with the same expression X exclusive
a plus b plus Y exclusive word ab cofactored with respective b equals zero.
That will get us the universal quantification if we just do that boolean
algebra, we will get this result. I get a Boolean function, which I can
write in any way I like, but I'm going to write it in sum of products form.
X bar a plus X bar Y plus Y bar a, those are the impossible patterns for F.
As long as I can represent this thing as a Boolean function and ask questions
about what satisfies this Boolean function.
And so, you know, for example, bdds would be beautiful for this.
I can get everything I need to know about impossible patterns for the inputs to f.
X bar a plus X bar Y plus Y bar a That is a representation of a cover of the
impossible patterns for f. So, I've got it written down here again
at the top, just for clarity. The controllability don't cares for f,
which is a function of everything input to f.
Which is X and Y, and a, and c, and d, is the Boolean function, X bar a plus X bar
Y plus Y bar a. So, let's just take one of those
patterns, and I'm just highlighted it here to be clear, to give a concrete
example. Let's take the X bar Y part of this
Boolean expression what that says Right, is that anytime X is a 0 and Y is a 1, I
think that's impossible. That's what this Boolean expression tells
us. I think this makes sense, and if we just
go down and look in the logic diagram, and I've drawn the same diagram X is a
plus b, Y is ab, feeding f is Xc equals Yd equals acd.
Let's just go look at that. We think that the controlability Don't
Care tells us that X is 0 and Y is 1 at the same time as impossible.
If we look at the network, if X is 0 then the output of the X node, which is an a
plus b equals 0, if the output of them or gait is zero, then a has to be a zero and
b has to be a zero. So I'm going to draw a little arrow like
that. So if the output of X is a zero than the
inputs a and b have to be zero. Okay, so I'm just going to draw zeros on
the a and b inputs, while if the a and b inputs are both zeros.
Then when we trace this around to the Y node if a and b are both zero, then the Y
node has to be a zero. And what the impossible pattern told us
was you know, if X is a zero, Y cannot be a 1.
Yes, correct, going to write correct exclamation point, X, Y, 0, 1 is
impossible. If X is a 0, you cannot have Y be a 1.
We have just seen that, so X is 0 and Y is 1 is impossible.
We can use that as a don't care, because that pattern cannot happen at the f node,
maybe we can simplify f using that pattern.
Now, there's one more kind of controllability don't care that I really
have to talk about. And those are things that are technically
called external controllability don't cares.
This is back to the very first slides and I don't care lecture.
What if there really are just Don't Cares for the network input itself, out at the
level of the primary inputs. External patterns for the primary inputs
themselves, a, b, c, d that we just do not care what f does?
What if those, for example, they're really impossible patterns of abc and d?
how do I put that in the mix? Or, or said differently, what if I go
back to the very simple, very traditional kinds of don't cares that we taught you
back in your digital logic carnel map days, what if one of those kinds of don't
cares happens? So let's just be concrete let's say that
b equals 1, c equals 1, d equals 1 cannot happen.
Now what do I do? Well, I've got a little, a little you
know, box over here. That says, don't care B equals 1, c
equals 1, d equal 1, at the, network inputs.
How do I compute the contrallability, don't care for f now.
And the answer is pretty simple. You come up with a Boolean function that
covers those external don't cares. Okay, and you OR it in and, and let me be
very clear about what that means, in case I'm not.
So, here's the formula again for the controllability don't cares.
The controllability don't cares for f are, we quantify away b because those b
variables do not appear in f. And we have the satisfiability don't care
for X, that's X exclusive or a plus b. We or in the satisfiability don't care
for Y, that's Y, X or ab. And now, we or in a cover of the external
don't cares, which is to say. We create a Boolean function that's a 1
for these new patterns of Don't Cares that happened way back at the primary
inputs. That little red bcd, that's the external
don't care, just to be very clear, that bcd is a Boolean function that makes a 1
for the external don't care patterns. It is a cover of those don't cares,
though just like everything else in this idea, when you want to represent a set of
patterns of variables, you make a Boolean functions that makes a one for the
patterns you care about. So, I need a Boolean function that makes
a 1 when b is a 1 and c is a 1 and d is a 1, that's bcd.
If I had a bunch of those kinds of patterns, right, I would have a bunch
more terms and I just OR them all in. And if you do this, okay, if you do this
OR and you this exclusive ORs and you quantify away the b, you get the prior
result which was X bar a plus X bar Y plus Y bar a plus 2 new terms in the way.
I'm choosing to write this Boolean expression, A bar cdX plus acdX bar.
There's some new patterns of things that can't happen because of the external
Don't Cares. The new controlability Don't Care
function is the old stuff, X bar a plus X bar Y plus Y bar a plus 2 new terms.
A bar cdx plus acd x bar, those are the new impossible things for f.
And I've got the network again, shown at the bottom X equals a plus b node feeding
the f node. Y equals ab node feeding the f equals Xc
plus Yd plus acd. And I've got the little table of don't
cares drawn at the left, b equals 1, c equals 1, d equals 1.
And I've got 1 of these terms circled, a bar cdx, okay?
What does that say? A bar cdx says a couple of things.
First thing I'm going to tell you, that it says, is that it says that A is 0 and
X is 1, right? That's the only way you can make this
thing a 1, a is 0 and X is 1. Okay, so let's just go look in the logic
network. If a is 0, and X is a 1, then it must be
the case, that b is a 1. I'm putting a star by, b is a 1.
So, I'm going to over here, I'm going to put next to the sort of the don't care,
I'm going to write b equals one because you know, my pattern requires that b is 1
and a is a zero. I don't seem to care about that but the
rest of the patter, the sort of the cd part of the pattern.
Says that c equals 1 and d equals 1, because the only way to make a bar cdx 1
is a is 0, c is 1, d is 1 and X is 1. If a is 0 and X is 1, then b must be 0.
But this pattern also says that C must be equal to 1 and D must be equal to 1.
And oh, look, what have I discovered? I've discovered that this pattern is
impossible. It's impossible because it touches and
requires at the inputs of the overall network one of the impossible external
patterns. So the new terms that you get in the
controllability don't care, they light up.
They turn on only when you're doing something impossible that involves an
impossible pattern at the input, which in this case is c, bcd equals 111.
So, again,[SOUND] it all just works. So, we now have the controllability don't
cares. Controllability don't cares give
impossible patterns at the input to node f.
I can use them as don't cares to simplify things.
They're impossible because of the network structure of the nodes feeding f.
Controlability Don't Cares can be computed mechanically from the
satisfyability Don't Cares on wires input to f.
There are internal local versions of the controlability Don't Cares.
That was the first part of this lecture. You just compute those from the
satisfyability from the wires that don't go into f.
There are also these things called external global computability Don't
Cares. Those're the Don't Care patterns that the
network input You can include those too. The result is control ability don't cares
give patterns of things that are impossible.
That cannot happen, that you can use as don't cares to simplify individual nodes.
But, it's important to know that the control ability don't cares are not all
the don't cares available. Roughly speaking, the control ability
don't cares are derived from the structures of nodes in front of node f.
As we showed in the beginning part of this lecture there's also, what also
matters are the nodes in back of node f. The things between you and the output, so
we need to go look at what happens with those kinds of don't cares, in the next
lecture. [MUSIC]