So here in Lecture 8, we're going to complete our overall study of multilevel

logic synthesis by looking at Don't Cares.

Now, Don't Cares are probably familiar to you from just basic logic design.

in basic logic design, we said for some pieces of logic, some input just won't

happen, because of something we know about the surrounding context or the

usage of that hardware. And so you are free to decide whether the

hardware design that you're making, makes a one for the output when that input

shows up, or it makes a zero. And it, it lets you actually optimize

things in a more rich and flexible way. The same thing is true for multilevel

logic networks. But a new, and very important, thing

happens, Don't Cares simply arise naturally and organically and implicitly

inside one of the logic networks that we're working on as a consequence of the

Boolean network model. As a consequence of the algebraic model

for the nodes, they just happen. Not only do they just happen, they happen

a lot. They happen all over the place.

They are a rich source of optimization for our logic, but the new and

interesting challenge is, you've got to go hunt for them.

Turns out, all the computational Boolean algebra techniques that we thought at the

beginning of the class are exactly what you need to go find them.

So in this starting lecture, what we're going to go do is, walk through a nice

interesting example to show you how these Don't Cares just implicitly arise in the

networks we are studying. So let's go take a look.

So let's start our discussion of how Don't Cares show up in multilevel logic

with a little bit of background. So let's recall that we made progress on

muli-level logic by simplifying the model.

The algebraic model really gets rid of a lot of the difficult Boolean behaviors to

let us do things like division and factor extraction.

But we lose some of the optimality, some of the result quality, some of the

expressivity of the model in the process. So an interesting question is how you get

it back, and one of the surprising answers is Don't Cares.

So recall that we run an espresso-style simplification on the two-level sum of

products formed in each node of a Boolean logic network.

And to help this, what's going to turn out to be the case is that we extract

Don't Cares from the surrounding logic, and then we use them inside each node.

And the big difference in multilevel logic is that the Don't Cares just

happen. They are a natural biproduct of the

Boolean network model and so there's a word for that, this is the title of this

lecture. They're called implicit Don't Cares

because they just happen as a natural consequence of the structure of the

graph. For the Boolean network model.

They're all over the place. In fact there're a lot of them.

They're very very useful for simplification, but they're not explicit.

The new thing is that we have to go hunt for them.

We need computational procedures to find them.

Let's just review a little bit about Don't Cares first.

In basic digital design, you probably learned this about Don't Cares.

And what we said was that a Don't Care was an input pattern that can never

happen. So I've got a little logic function here

a little grey box. F has inputs a b c d and I've got a carno

map shown on the right-hand side. Two by two, a b on the horizontal axis, c

d on the vertical axis. This carno map have, has ones in the a b

c d one o o o. 1001 and 0111 squares.

But it's also got a bunch of d's in it and the d's are Don't Cares.

And so what if we just tell you that the following patterns of a b c d cannot

happen? 1010, 1111.

Here I'm just going to check them now. 1100, 1101, 1110, 1111.

What if we tell you that those things cannot happen?

Then each of those things can become a Don't Care in the Karnaugh map.

And we get Don't Cares in, you know, one, two, thee, four, five, six places

corresponding to those patterns. And so we're to, free to decide if f is a

0 here or f is a 1 here because those things don't happen.

You know that output is not going to happen, so we get to decide what the

function should do to simplify things. And it's clear that we can simplify

things much further. with all these Don't Cares, I can circle

some nice big circles in the Karnaugh map.

So that's probably what you know about Don't Cares so far.

What's different in the multi level model?

Well, don't cares arise implicitly as a result of the Boolean logic network

structure, and you have to go find them. We actually have to go search for them

explicitly They don't just get handed to us like that previous slide.

There's a bunch of good references for these ideas.

the Giovanni DeMicheli book on Synthesis and Optimization of Digital Circuits is

good; some of my development is based on some of the ideas in Chapter 8.

ALthought I, I'm doing sort of a different version of the math.

the book by Devadas, Keutzer, and Ghosh on logic synthesis is also good.

And there's a very complete paper by a lot of authors, Bartlett, Brayton,

Hachtel, Jacoby, Morrison, Rudell, Sangiovanni-Vincentelli and Wang, on

implicit Don't Cares. That's a good place if you want to see

how it, how it really works. So let's do a, a sort of an informal tour

of how multilevel Don't Cares arise implicitly in the structure of the

Boolean network model, and let's start with this little Boolean network, and

let's look at the node called f. This is a very simple Boolean network.

It's got one node. F equals Xb plus bY plus XY.

And the question I would ask is, can I tell you anything just looking at this

network, about the Don't Cares and the node?

And the answer is no. I, I don't know any context for the

surrounding parts of the network. I cannot tell you that any patterns of X,

b, and Y are impossible. So as far as you know, all eight of the

patterns of X, b and Y are possible. And there's a little Karnaugh map shown

at the right, four squares by two squares, Xb on the horizontal axis, Y on

the vertical axis. And there's three groups of 1's circled

a, Xb pair, the bY pair and the XY pair. So what changes here?

Well, suppose we know something about the input.

In particular, suppose we know that X is not an input from the outside.

Suppose we know that X is computed inside the Boolean network.

So, just to be clear I'm labeling pis as the primary inputs, things that come into

the overall Boolean network, and pos as primary output, things that leave the

overall network. And so now x is not a primary input, it's

co-, computed thing inside the network. now can I say something about whether

there are any impossible patterns for the inputs to node f.

and the answer is yes. because there is some relationships

between a and b and X now, some things just can't happen because X is a function

of a and b. There are now some impossible patterns of

the variables X and b and Y. So let's just go look at those.

I'm showing again my Boolean network model with the X equals ab node connected

to the f equals Xb plus bY plus XY node. And I've got a little truth table here.

with the x equals ab node pointing at it, and it's got three columns, abX.

and under it all of the Boolean values of ab and X from 000 to 111, so there's

eight rows. And then there's another column that says

can it occur? And what we're really asking here is

inside this logic network, now that we know that X is ab.

Can each of these eight patterns of a and b and X actually occur?

The first thing we can do is just say, well, four of them can certainly occur

because X is equal to a and b. The patterns associated with X equals to

a and b can occur. So 000 can occur, 010 can occur, 100 can

occur, and 111 can occur. We have yes's in all of those rows.

So, it seemed that all the other rows are no's and yeah that's actually correct.

There are four patterns that can not happen to a b and X, 001, 011, 101 and

110. And you know, we can illustrate one of

those clearly, by just pointing at one of the rows.

So, let's point at the 001 row and say, well why is it that cannot occur?

And the answer is, well, a and b are 0's, and X is an end gate output, you can't

put two 0's into an AND gate and have a 1 come out.

So that's just not possible. So here's all of the possible and

impossible patterns for a and b and X. Now, however, I'm not that interested in

the patterns of a and b and X. I'm interested in the patterns of X and B

and Y. Because that's actually what f is a

function of. I need to figure out how I can take the a

b X patterns and I know something about what can't happen, and turn those things

into X b Y patterns. And all I can [COUGH] all I can tell you

at this point is you just have to sort of stare at things.

we're going to figure out computationally how to do this in a bit.

So the first thing is that there are three pairs of rows.

the rows that start 0, 0. The rows that start 0, 1.

And the rows that start 1, 1 in this table of xbY eight rows, patterns.

Because look, Y as far as we know, is a primary input.

It just you know, it's not dependent on anything.

So Y can be anything. But X and b are dependent on each other.

And the Xb00 pattern can happen. The Xb01 pattern can happen.

And the Xb11 pattern can happen. And that would seem to suggest that these

two rows, XbY is 100, and 101, cannot happen and, and that's actually correct.

And why that can't happen is that this is trying to put b equals 0 in to what is

actually an AND gate, and get X equals 1 out.

You don't put a 0 in an and gate and get a 1 out.

A 0 cannot go into the X node and have a 1 come out.

So any of the patterns that have X is 1 and b is 0 are impossible.

And so we found a couple of impossible patterns for our f node.

And so we can use those things. We can check in our Karnaugh map which

I've got drawn here again. For the Xb versus y, four variables

horizontally two variables vertically I've got the same Karnaugh map drawn with

the same three terms, XbbXY. Now, I'm going to say, what happens if we

add the impossible patterns? The answer is we have two impossible

patterns. XbY is 100 and 101.

I get two Don't Cares. The entire right column of the Karnaugh

map 100 and 101 are now Don't Cares. Suddenly, I can circle the Karnaugh map

in a different way. I can circle this in what I think is a

nicer solution. if I'm going to write the function now.

I have that the function is equal to x plus bY.

And that's simpler than Xb plus bY plus XY.

And so it looks like I've saved something.

So I can actually simplify this network. It is no longer Xb plus bY plus XY, it's

now X plus bY. It looks like I saved three literals.

And actually saved a product term. This is actually really good.

So, just because of the context of how X is a function of a and b, there are

patterns of X and b and Y that cannot happen.

So we can continue this and just try another one.

now what happens if Y is also a pattern, what happens if Y is b plus c?

It's again computed internally. We can do this again, we can say, are

there impossible patterns of the inputs and outputs of the Y node of b, and c,

and Y? And so, I've got another truth table here

that has three columns, bcY, with eight rows from 000 to 111.

And the column to the right says, can it occur.

And you start just like before, with the patterns that can occur.

You can send 2 0's into an OR gate and have a 0 come out.

The 0 0 0 is a yes. If you send any 1 in to an OR gate, you

get a 1 out. The 011, 101 and 110 rows for bcY are a

yes. Which leaves the other rows as a no.

001, 010, 100 and 110 cannot happen. We can draw those to be clear, the 001

row says you cannot put two 0's in an OR gate and have a 1 come out.

That's not possible. And the 110 row says, similarly, you

can't put two 1's into an or gate and have a 0 come out.

All four of the rows in this truth table are impossible because they're just not

legitimate patterns of inputs and outputs for the Y node in this network.

Now, we can take all of the information we've got, I'll admit a rather

complicated looking slide here. I've got the logic network, again, X

equals ab node. Y equals b plus c node.

Feeding the f equals Xb plus bY plus XY node.

I've got the impossible patterns for abX, again, drawn above it.

001, 011, 101, 110. And I've got the newly found impossible

patterns of bcY drawn above, above it 001, 010, 100, 110.

And I've got another truth table xbY, eight rows, 000 to 111 and another column

that says, can it occur? And just as before, I don't really want

The abx impossible patterns and the bcy impossible patterns.

I want po-, impossible patterns I can do something with, that I can use to create

maybe some Don't Cares for the f node. And so right now, you have no

computational technique for doing this other than to stare at this and try to

figure out what can and can't happen. So the first thing you do is you say,

alright, look, I stare at it. And I believe that XbY is 000, 001, 011

and 111 can happen. And if you just try all those patterns on

your x equals ab and y equals b plus c nodes.

You'll see that you can find other values for the inputs not specified.

In this case. A and C, that make that work and so that

leaves us with these four patterns. Zero 1, 0.

One, 0, 0. One, 0, 1.

One, 1, 0. For X, B, Y, as impossible and we can

again look at them. Why is 0,1, 0, and impossible pattern for

X, B, Y? Because you are trying to put a 1 in an

orgate and get a 0 out. Y is 1, 1, 0, impossible, because you're

trying to put a 1 in an OR gate and get a 0 out.

Why are the two patterns, 1, 0, 0, and 1, 0, 1 impossible?

Because you're trying to put a 0 and an AND gate and get a 1 out.

Because of the context of this network of what X is as a function of a and b and

what Y is as a function of b and c. Certain patterns of X and b and Y are

impossible jointly. And these things become Don't Cares.

And so, we get some more good stuff, okay?

So if we take these impossible patterns, and so I'm drawing the Boolean network

again, X is ab, Y is b plus c, f is Xb plus bY plus XY.

I'm drawing the impossible pattern above the XbY inputs to f 010, 100, 101, 110

for X b and Y. Those are impossible.

I've now got four don't cares that I can use, and what I actually get is to new

Don't Cares. I get a Don't Care for the XbY 010 and I

get a Don't Care for the XbY 111. So it's in this Karnaugh map four columns

wide by two rows deep. Only the Xb00 column has 0's in it.

Everything else has a Don't Care or a 1 in it.

So if I was to circle this Karnaugh map, I'd just circle this.

I'd circle the two middle columns. And if I write this as a Boolean

equation, this is now f equals b. And that's pretty surprising, because

that means that. I don't really care about the X node, and

I don't really care about the Y node. I only really care about the b primary

input. Just because of the context of X and Y

now being related because they share some variables.

And I don't even have to circle one of those previous ones in this Karnaugh map,

because become a Don't Care because as this context.

So wow, f was Xb plus bY plus XY. That looks like three AND gates in an OR

gate with three inputs and that whole thing gets replaced by a wire.

Wow, thatâs pretty surprising. That's pretty impressive.

And so this is just the first start of our examples for how we find Don't Cares.

This is one kind of a Don't Care. These are actually things called

Satisfiability Don't Cares and Controlability Don't Cares.

But these are the only kinds, there's actually some more kinds.

So in the next lecture, we're going to look at some other implicit Don't Cares

that we can pull out of this network.

Multilevel Logic—Implicit Don't Cares, Part 1

VLSI CAD Part I: Logic

Meet the Instructors