[SOUND]. So here in lecture 8.3, we're going to start to look in detail at how we actually calculate, and compute, and extract the don't cares in a multilevel logic network. It turns out don't cares come in three kinds of categories, and they all actually have famous names. There are Satisfiability Don't Cares, there are Controlability Don't cares, and there are Observability Don't Cares. And in this lecture, we're going to look at the satisfiability don't cares. The satisfiability don't cares can be thought of as belonging to each internal wire of the Boolean logic network. And the satisfiability don't cares tell you what are the possible patterns of variables associated with the node that made this wire as an output inside the Boolean logic network. It turns out that they're actually pretty easy to extract. So, let's go look at satisfiability don't cares. So in our informal tour of implicit don't cares and multi-level logic networks, we showed a variety of different kinds of don't care's that we could extract. but we did it by basically staring at the structure of the logic network and figuring out patterns that were either impossible or rendered things in such a way that we really did not care what the value was, and so we could use them. it turns out that implicit don't cares actually come technically in three categories. There are things called satisfiability don't cares, things called controllability don't cares and things called observability don't cares. And they have acronyms, SDCs, CDCs and ODCs. We're going to see how we can compute all of these automatically over the next couple of lectures. But for now, let's start with the first kind that are sort of the foundational kinds of don't cares. We use these to compute other things, the satisfiability don't cares. They belong to the wires inside the Boolean logic network. So, let's go see what that means. So, let's do a little background first, because there's some interesting stuff happening in terms of the, the style in which we, we compute don't cares. Here's a big important question. How will we represent the don't care patterns at a node? I've just been listing them as basically lines in a rows in a truth table. But there's a much more subtle and sophisticated answer. We're going to represent them as a Boolean function that makes a 1 when the pattern is impossible, and that has a name. That's often called a Don't Care Cover. So, when we talk about impossible patterns of satisfability don't cares, or impossible patterns of controlability don't cares, Or I just don't care about them patterns of observability don't cares, we're not really listing values of a truth table. We're actually providing a Boolean function. and when the Boolean function is a 1, the pattern of inputs that made that function over one is impossible. That's pretty cool. why are we doing it like this? Well one, because the math works and it makes it possible to do and use and exploit all the advanced Boolean algebra we did at the start of the class. But even more importantly, we can use all the computational Boolean algebra techniques we know, notably, binary decision diagrams, to solve for and manipulate all these don't care patterns. So, I'm actually going to give you a computational recipe for every one of these kinds of don't cares, the SDCs, the CDCs, the ODCs. That if you were really going to build something like this, you probably want to be doing something likeBDDs or, or another sort of real serious, you know, computational data structure. This turns out to be hugely important to making this stuff practical. So, the easiest way to think about the satisfiability don't cares is that they belong to wires. Or said differently, there's a satisfiability don't care for every internal wire in a Boolean logic network, and the SDC represents impossible patterns of the inputs to the node that makes this wire as its output. So, if the node is function say, F, and it has inputs a, b, c whatever, we write this as SDC subscript F, and then it's a function of F and a and b and c. Now, one of the things that I will note, and I'm just going to write a little kind of line under here, it's a little weird to have a Boolean function where we sort of think of the input variables as the output of a node and the inputs to a node. But, let's remember that the Boolean node itself is a Boolean function. You know, F is a function of a, b, c. But the satisfiability don't care is a representation of impossible patterns, right? And so, it has f as an input just like it has the other inputs to the node. So, I've got a new network shown below X, X is equal to a plus b, Y is equal to ab, and the f node is Xc plus X Yd plus acd. and there are primary inputs a, b, c, d and one primary output small f. I've got somethings labelled here. So, for example, the satisfiability don't care for X. And so, there's a wire in the design labelled X. The satisfiabiltiy don't care for X is a function of X in a and b, and it's a Boolean function that makes a 1 for impossible patterns of X and a and b. And similarly, there's a wire in the network design called Y, and I'm labeling it here. That's the Y. And the satisifiability don't care for Y is a function of Y and a and b. That's a Boolean function that makes a 1 for impossible patterns of Y and a and b. So, we sort of know what they are now and we sort of, we stared at the Boolean network in the previous lecture. And we sort of figured out how to do it by eye. What we need to do is figure out a computational recipe for extracting this stuff. What's amazing is that it's actually easy. So, how do you compute the satisfiability don't care for an output wire of a node in a Boolean logic network? let's just think about it for a minute. What you want is a Boolean expression that's equal to 1 when X is not equal to the Boolean equation for X, right? So, you remember the X equals a and b node? What you're looking for is a Boolean equation that has the property that it's 1 when the value of X is not what a and b would equal. Well, that's actually simple. That's actually just X exclusive or the Boolean expression for X. And let's remember that the Boolean expression for X doesn't have any X's in it because it's the thing on the right-hand side of the equal sign. And so, let's just also note that this is, in fact, the compliment of the gate consistency function from the SAT stuff that we did a couple of lectures ago. Let's just look at an example here. So, I've got a Boolean node, X equals ab plus c. It's got three inputs, a, b, and c, and one output, X. And I'd like to calculate the satisfiability don't care for X. And so, that's just going to be, I'm going to think of it as associated with the output wire of X. And that's just going to be X exclusive-OR for the expression for X, right? Which is the thing inside the node, X equals ab plus c. So, this is X exclusive-OR with ab plus c. If you do the Boolean algebra, you can get this particular sum of products for them, X bar ab plus X bar c plus Xa bar c bar plus Xb bar plus c bar. Anything that makes this function a 1, any pattern of X and a and b and c that makes this thing a 1 is an impossible pattern for node X, and you can use it as So, let's just look at one. Here's an impossible pattern. X bar ab is a term in this SOP form. What makes that term 1? Well, if you look at it clearly, X has to be a 0, and a has to be a 1, and b has to there's no c's in that product term. So 0,1,1 anything is impossible, is that right? Well you know, I think the easy thing to do is to draw the node again. this is the X node. But I'm just drawing it as logic because it makes it a little easier to see. So, this is ab plus c. So there's an ab AND gate, connecting its output to an OR gate that also connects to c, and that connects to X. So, let's look at this pattern again. X equals I'm sorry, Xabc equals 011 don't care, what does that say? Well, the first that says is that, I think X equals 0 is part of this don't care pattern. And the next thing it says is that, a and b are both ones, and so that says a and b are both ones, so there's two 1s going into this AND gate. So, there's a 1 coming out of this AND gate, the don't care pattern. Also says, that c is a, I'm sorry, the impossible pattern, says that C is a don't care. So, I'm going to put a big slash through it. I don't care what c is, but you can tell from what I'm drawing that, that's true. If a and b are 1, the AND gate makes a 1. A 1 going into an Or gate, I don't need to know what c is. And so, this pattern says that 011 don't care is impossible, and you can see that that's true. If two 1s go into the AND gate, then 1 goes into the OR gate, a 1 comes out of the OR gate, and this pattern says X must That's impossible. That cannot happen. And so, yes, I'm going to put a big check mark by it. Xabc equals 011 don't care is impossible. This nice simple little formula calculates the satisfiability don't care. So, where are we? Satisfiability don't cares are associated with every internal wire in a Boolean logic network. The satisfiability don't cares explain impossible patterns of inputs to and the output of each mode. And the good news is, that they are easy to compute. But satisfiability don't cares are not really the don't cares used to simplify nodes. Put an emphasis on not. They are the foundational elements of what we need for the recipe to start computing the don't cares. We use the SDCs to build, in this case, the CDCs, the Controlability Don't Cares. Those things give impossible patterns at the input of the nodes. So, let's go see how to do that in the next lecture. [MUSIC]