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