Here in lecture 8.5, we're going to complete our treatment of Don't Cares in multilevel logic and how they arise implicitly from the structure of boolean logic network models. The final class of don't cares are the observability don't cares. Observability don't cares are patterns that mask the output of a node so that no matter what happens, the output of the overall boolean logic network is insensitive to your node when this value shows up. So these are different than the controlability don't cares, which kind of focus on the nodes in front of a node. The observability don't cares focus on the nodes in back of a node, between you and the output. But it turns out that the same computational Boolean algebra techniques we learned at the beginning of class will let us come up with a recipe to extract the don't cares. So let's go look at the observability don't cares. So here we are finally at the last kind of implicit don't cares. We've done the satisfiability don't cares, and the controllability don't cares. And now we want to talk about the observability don't cares. These are patters input to a node that make the network output insensitive to the output of the node, or patterns that mask the output from effecting anything. Let's see how we compute these. So, I've got a new benchmark here, got a new example. It's got 3 primary inputs, abc, and 1 output, Z. The node F, that we want to optimize is now in the middle of the network, it's interior to the network. It goes through a node, Z equals ab plus Fc bar, plus F bar b bar, in order to get out. So observability don't cares are patterns that mask a node's output, and in our case this is F at the network output, which in this case is Z. So, it's a really important point here, these are not impossible. These patterns can occur, but these patterns make the node's output not observable at the network output. And what that means, not observable means that the boolean value of the node, in this case F, does not affect any network output, which in this case is Z. So, it doesn't matter what F is. Z doesn't care. So it's, it's a real don't care in a different kind of way. So, you know, just to be clear the observability don't care for F is going to be patterns of a and b, because that's what's input to F that makes Z insensitive to F's value. Let's just go talk a little bit about that insensitive thing. When is the network output Z insensitive to the internal variable F? And note that we've got two nodes here in my kind of cartoon. There's an F equals stuff node with some arrows into it. And that has an arrow labeled F that goes into a Z node that says Z depends on F and Z has some other arrows going into it. What it means for Z to be insensitive to F is that Z is independent of the value of F, given some other inputs to Z. We can be clear about that with some little examples. So for example, if Z was just an AND gate, if any other input was a 0, Z is insensitive to F because if there's an, a 0 going into the gate, Z is just a 0. Similarly, if Z was an OR gate, Z would be insensitive to F if any other input was a 1 because if any other input is a 1, Z is just a 1. What we need is a general formula. We know that Z depends on F. How do we compute in the general case when Z is insensitive to F? Now it turns out, we've almost same as before. Leaves solved the flip problems. What makes F sensitive to X. Now note the change of variables names here, this is a blast from the past this is slide 21 a lecture 2.6 that talked about the boolean difference. And what that said was that any pattern dell F dell X equal 1 makes X observable at output F. So interpreting the boolean difference, we have a box that says a big blob of logic. And as an output that says F is a function of a, b, c...w and X. And there are arrows going into the big blob of logic that say a, b, c...w and X. And what the slide says is that any pattern of the other variables that are not X that makes a dell F dell X 1 makes F sensitive to X. And the words say when dell F dell X is a 1, it means that, if you apply a pattern of the other inputs a, b, c up to W, that makes dell F dell X 1, any change in X will force a change in the output of F. So we know what makes some output sensitive to some input we just want the opposite. We want the output to be insensitive to the input which is going to turn out to be easy. When is the Z output which is the output node of the diagram here, insensitive to the F input. Because F is an internal node. Well, you know, the slide title gives it away. It's when the boolean difference, dell Z, dell F complemented, is equal to 1. That makes sense. let's talk about that with a little bit more detail. when is the network output Z insensitive to internal variable F? Here's a good mathematical definition. When you can find some inputs to Z that make the cofactors Z with F set to 0 equal to Z set to F equals 1. So if ZF equals ZF bar, the Shannon cofactors, then Z is not dependent on F. Any inputs to the Z function that make ZF equal ZF bar make Z independent of F. If the cofactors are the same when you set F to 0 and F to 1, Z does not depend on F. That makes sense. How do you find when the cofactors are the same? Well you solve a little equation that says, I'm going to put an equality gate, and that's an exclusive NOR, in between the two cofactors, ZF equal 0, and ZF equals 1, and I'm going to solve for when that's a 1. Now note that Z exclusive NORed with ZF of 0 exclusive NORed with ZF of 1 is just the same thing as ZF of 0 exclusive ORed with ZF of 1 and, and compliment the whole thing. So that's nothing, you know, complicated. That's just the difference between an X NOR and an X OR gate where you just like put an invertor after the X OR gate. But the reason I wrote it like that, was that this is sort of familiar. The thing under the big bar, ZF equals 0, exclusive or ZF equals 1 is just the boolean difference. And so, I finally get the result I want. If you can compute dell Z dell F, and then compliment it and then find a pattern that makes it a 1. And then take that pattern, or those patterns, and apply them to the other inputs to Z that are not the F input. Any pattern that makes that thing a 1, dell Z dell F bar. Any pattern that makes that a 1, makes Z insensitive to F. Those patterns are the raw material of the don't care that I need to go compute. So, I have a recipe again. It looks a lot like the previous recipes we've seen for the don't cares. What do I start with? I start by computing dell Z dell F complement. Any patterns that make that thing a 1 mask F for Z. Make Z not depend on F, and then I universally quantified all away the variables that are not inputs to f because just like with the control ability don't cares, there's a lot more variables happening here, and the patterns of behavior that I'm interested in must stay true for all values of the variables that I get rid of. And the result will be the observability don't care is a boolean function that, it makes a 1 for these masking patterns. So here's the, here's the equation, and again showing you the same network. F is ab bar plus a bar b feed, Z is ab plus Fc bar plus F bar b bar, Z is the primary output, abc the primary input. circling the inputs to the Z node, the output don't care. Okay? Is something that we compute starting with this raw material. Okay? It's the universal quantification of the variables not used in F. Applied to the compliment of dell Z dell F, and then what that's going to do is that's going to let me actually go over and get some patterns that are don't cares for the F node. So using this recipe for the little network F equals ab bar plus a bar b, c is ab plus Fc bar plus F bar b bar, what do we get? We look at all the variables going into Z, we calculate dell Z dell F bar, and then we calculate the universal quantification of the variables not used in F, and we get some patterns to the input of F. That's going to turn out to be for all c, because those are the patterns, those are the variables that are not used in F. a is in F, b is in F, but there's not c in F. of the complement of the boolean difference, so the boolean difference is just ab plus F c bar plus F bar, b bar cofactored F equals 1. Exclusive or co-factored F equals 0. That's the difference, then you complement it. And then you quantify out the c. If you do that, you will be quantifying the c out of the boolean equation ab plus ac bar plus b bar c bar plus a bar bc. And when you're done, you get something useful. You get some patterns that you can actually apply to the inputs of the node that you are trying to simplify. So that's the computational recipe so far for the output don't care. Now as we did in the previous CDC example, it's good to just ask the question, does this make sense? if I tell you that the ODCF which is a function of a and b is ab. That means that we think a equals 1, b equals 1 masks F from affecting the Z output. Is, is that the case? Well, if a is 1 and b is 1 then the ab term in Z turns into a 1. And very clearly it forces the Z output itself to be a 1, and once you force the Z output to be a one with a equals 1, b equals 1, Z doesn't depend on F anymore. So yes, in fact a equals 1, b equals 1 is a don't care for node F. It all works because a equals 1, b equals 1 forces Z to be a 1. And if you actually look at F what you can see is that F is actually ab bar plus a bar b. F is actually an exclusive OR gate, right before we did any of the don't cares. And after we find this don't care pattern, which is a equals 1, b equals 1 what we're actually going to find is that we could if we choose, we could replace F as an OR gate because now one one is something that's a don't care pattern, we can circle it if we like. We can decide if an OR gate is simpler than an exclusive OR gate which is probably true. then in logic, in actual silicon then this is probably a good simplification. So that's what you actually get from this, this particular don't care pattern. Now we're not quite done yet, we have a new problem. What if F passes through many outputs? And is an input to many Z nodes, Z1, Z2, dot dot dot ZN each of which make a primary output. Well the big idea is that only the patterns that are unobservable at all of the outputs can be observe nobody don't cares. Because as soon as F affects even one of those nodes, then I can't, it's not mast and actually have to, I can't make it adult care have to be careful that computes to the right value. So I get a formula that looks much more like the controllability don't cares. So the general recipe for the general ODC is again, you quantify away all the variables that are not input to F, right? because that's, that's what we're working on over here. But, what you quantify is the boolean and of all of the complemented boolean differences. So, you take all the Zs. You calculate the boolean difference. You calculate the complement of the boolean difference. You and them all together, okay? And you quantify away the variables universally that don't show up in F. And then you solve for you know, 1's in this. Any pattern that makes that thing a 1 is an observability don't care. It makes F unobservable at all the Z outputs. And, that's the recipe. So, where are we with the ODCs? ODCs give patterns input to node F that mask F at the network output. They are not impossible. They can occur. Don't cares, why? Because the network output doesn't care what F is, because it, F does not affect the network output for these patterns. The ODCs can be queued mechanically from the boolean differences of all the outputs that are connected to F. Together, the CDCs and the ODCs give you the full don't care set you can use to simplify an internal node. With these patterns, you can call something like espresso and simplify the insides of the sum of product form for the node. Now a really good question at this point would be, are we done? I talked about satisfiability don't cares, I talked about controllability don't cares, I talked about observability don't cares and the answer is yes but only if your networks look just like this. And just like this means you have one layer of inputs in front of F, X1 to XM and one layer of output in back of F, Z1 to ZN that generate primary outputs. So if you only want to get the controlability don't cares from the nodes immediately before you, and you only want to get observability don't cares for one layer of nodes between you and the output, then all of the math and all of the recipes I've given you are all you need. Unfortunately, this is what a real network looks like. And so here on this slide, in general, I'm showing you X which is in the middle of a large network. And so there's several ranks of nodes with many nodes at every rank feeding X and several ranks of nodes with many nodes at every rank between X and some number of primary outputs. And the problem is that controllability don't cares are actually a function of all of the nodes in front of X, potentially. And observability don't cares are a function of all of the nodes between X and any outputs that it might influence. And in general, this is so complicated that you can never get all of the don't cares for node X in a really big boolean logic network. But even just representing all this stuff can be explosively large, even for BDDs. So, what do people actually do? Well, they generally don't get all of the don't cares. there are an enormous number of tricks that trade off some effort in time and computer memory for quality, for how many don't cares. So, for example, the formulas I gave you for the controllability don't cares, the so-called local controllability don't cares, which requires that you just look at the outputs of the nodes in front of you. The immediate antecedent vertices, the nodes in front of you, and you compute those satisfiability don't care patterns. That's a really common trick, and that works pretty well. There are also incremental node by node algorithms that walk the network from the inputs to your F node to compute the controllability don't cares and from your F node through layers of nodes to the output Zs to compute the observability don't cares. But they're just more complex and I don't have enough time to to talk about those thing. The references I gave earlier in the lecture are a really good source for those algorithms. But, for us, just knowing these limited don't care recipes is actually sufficient. You know understand why don't cares are implicit, you understand why you must find them. You understand how you can find them for a, a nice pretty realistic case. And you know the big difference between the satisfiability, controllability, and, and observability don't cares. This is great. You're really in a very very good position now to understand pretty much most of what happens in, in the, sort of a core version of conventional logic synthesis. So congratulations. Lots and lots of progress. What we're going to be doing next is moving on toward more physical layout kind of problems. because remember the title of the course is From Logic to Layout. We're almost done doing all the logic stuff, we're about to move up to the layout stuff.