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