[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]

Multilevel Logic—Controllability Don't Cares

VLSI CAD Part I: Logic

Rencontrer les enseignants