0:01

So, here in lecture 5.2, we're going to continue looking at 2-level logic

synthesis. And I have to admit, this is probably one

of the most complex sounding talk titles I've got, The Reduced-Expand-Irredundant

Loop, which sounds very impressive, indeed.

And is the name of an extremely famous heuristic for doing 2-level synthesis,

2-level optimization, that uses the idea of reshaping a cover so that we get a

good, but not necessarily perfect, solution.

And so, what we're going to do in this lecture is, we're going to take a high

level tour through all of the key steps of this famous heuristic method for 2-level

logic optimization. So, let's go see how that works.

So, let's assume we are starting with a truth table.

But just to make this a little more realistic, let's note that we're going to

start with a truth table that can have input don't cares.

And what input don't cares means is that each row of the truth table can match many

rows of the full truth table and we do that by just allowing people to put an

asterisk which says, you can match either a 0 or a 1.

So, for example on the input truth table that I'm showing on the, on the bottom

right here there are one, two, three, four, five rows of the truth table, table

and they're going to each turn into some sort of a cube and they're called P, Q, R,

S and T, respectively. And I've got a Karnaugh map on the upper

right of the diagram four by four, a typical four by four grid ab on the top,

cd on the left. 1s in the top, left two by two squares,

bottom right, two by two squares, the entire bottom row is 1s, and the entire

second row of the Karnaugh map is 1s. And I've got a bunch of covers here, I'm

going to talk through them one at a time. So, let's talk about the, the row of the

truth table 0 star 0 star that's really just this 1 right here, the upper left two

by two. This is cubed P because obviously a is 0

for those 1s and c is 0 for those 1s, but b and d can be anything.

So, that's just a very simple way of specifying more than one row of the truth

table, more than one single one in the Karnaugh map.

0 star 10, which is cube Q will be this one here on the bottom.

That will be the bottom left two, bottom column left two 1's, that's cube Q.

Of course, if you'd like, it's always possible to specify individual 1s in, in

the Karnaugh map that, that's these guys right here.

So, this one in the Karnaugh map is S and this one in the Karnaugh map is R.

Second row of the Karnaugh map, right two squares.

And T is going to turn out to be the bottom right corner bottom right corner of

the Karnaugh map. That will be cube T.

So, this just makes it easy to specify a function with lots and lots of variables.

You know, you got a function with like 25 variables in it, you do not want to write

out a truth table with two to the 25 rows, believe me.

You just want to specify where the function is a one and that's probably a

whole lot less than two to the 25 rows. You can specify these with these input

don't cares. It makes a very, very tidy and very

convenient way of doing that. So, this truth table with its input don't

cares each row with its pattern match ability, specifies a product, a cube, it

might not be prime, that's important to know.

There's nothing that says this is a very good cover, but it surely is a cover of

all the 1s. So, if you will, it's a bad Karnaugh map.

Our goal is to start with this, and then, do some optimization.

Now, the first step is to expand each cube to be a prime.

So, expand is a heuristic and this is actually going to get done one cube at a

time. So, we're going to take each cube in some

appropriate heuristic order and we're going to make it as big as we can possibly

be and what that means is that we're going to make it prime.

Now, let's be clear. There might be different ways of doing

this for any specific cube. You know, you might be able to grow it in

one direction or a different direction. And we're not really talking yet about how

we do that. And so, we've got three cubes in our

current design that have been expanded. The S cube is no longer a single one in

the Karnaugh map. The S cube is now the entire second row of

the Karnaugh map. And the R cube is no longer a single one

in the Karnaugh map. The R cube is a two by two square of cubes

in the Karnaugh map, it's the middle two rows in the right two columns.

And the Q cube is no longer the left two 1s in the bottom row of the Karnaugh map,

the Q cube as it has been expanded is now the whole bottom row of the Karnaugh map.

So, the new solution is a prime cover. Every cube is as big as it can be.

But it's not the best we can necesarily do.

There's more work we might be able to do on this to improve it.

So, what's the next step we do? Well, the next step is we try to remove

redundant cubes. And the name of this heuristic is

irredundant. Okay.

The irredundant operation removes redundant cubes from the cover, and a cube

is redundant if I can remove it, and all of its 1s are still covered by other cubes

in the rest of the cover. And it's important to note that we can

clearly remove cube R. And I'm just going to put some little hash

marks across R here, so you can sort of see it.

Cube R is the right two columns intersected with the middle two rows.

Cube R is covered entirely by every, by, by some combination of the other cubes.

So, we can get rid of it and if we remove it, the new solution will still be a prime

cover and it is technically minimal and what minimal means is I cannot remover

another cube without breaking it, without uncovering some 1s.

This is one of these local minimum things like I showed on this conceptual graph a

couple of slides ago. However, we might not be done.

We might still be able to do better, so what do we do next.

6:26

This is a very interesting idea. We're going to reduce the prime cover.

Reduce is another heuristic. We're going to take each cube.

And we're going to shrink it as much as possible, but we are not allowed to

uncover any 1. So, we're not allowed to break the

function, but we're simply going to take the cubes that are covering the function

and shrink them, so that none of them overlap.

What's going to happen here is that we can shrink the S cube.

Which is suddenly going to become the right two 1s in the second column and

we're going to shrink the Q cube and so we're going to become the left two 1s in

the bottom most row. This is our reduced reshaped cover, this

is a really strange beast. This is, if it uses a Karnaugh map, I'd

failed you, right? I mean this is this is a bad solution.

But this is a really amazing essential step.

This new solution has a different shape and what's going to happen is that from

this seed, we are going to expand it again and perhaps when we expand it, we'll be

able to find yet another superior solution.

This is the critical step in this key chain of heuristics that we're showing

here. This is the idea that I said in the intro

talk. I need a way of, of you know, making a big

step from one solution to a different solution, from one local minimum to a

different local minimum. And the big trick is you reduce things to

the strange non-overlapping non-prime cover, and then, when you expand it again

you might get a different answer. You might get a better answer.

You might find some new cubes that are redundant that you can kill.

So, if we apply the same heuristic expand heuristic again you might get a different

answer because you started from a different starting point.

And again, when you run expand, part of the goal is going to be to see if you can

overlap some other cubes so that they can go away.

Oh, look, I've done that in this particular example.

I've expanded the S cube by basically growing it down and I've expanded the Q

cube, which is the bottom row, by growing it to the right.

And suddenly, if we will go take a look at the T cube, we see, oh, look, I can make

the T cube go away. Because I had a different solution after

reduction, because when I did expand I got a new solution, I found a new local

minimum. I can, I can work with this.

So now, we, again, run the irredundant heuristic, but it is starting from a

different cover so I can get a different answer.

We took each cube and we expanded it to make it prime, but we also tried to cover

the cubes to make them redundant. It's part of the heuristic.

So, in this example we can kill the T cube, and I'm just drawing that in.

So, the T cube is now the bottom right two by two square, right most 2 columns,

bottom most 2 rows of the Karnaugh map. That cube can go away.

Just going to circle that and sort of draw it.

That cube can go away as the result of, of redundant.

After this, the cover is again and prime and it's irredundant and I can't remove

anything to make it smaller. So, it's still some sort of a, of a local

optimum, we're just not sure how good a local optimum.

Now, look, in this particular example, I got lucky, I got the best answer.

Right, after that set of reduce expand irredundant heuristics, I got the best

answer. This will generally not happen, you know,

exclamation point, exclamation point, I cannot guarantee you that this is going to

happen, but what I can guarantee you and this is the big important takeaway, what I

can guarantee you is that this thing is prime.

I can't take any cube and make it bigger. This thing is minimal, can't remove

anything and irredundant, which is sort of the same thing.

This is a really good local minimum. This is a really good local solution.

And it turns out in practice that this iterative improvement by reshaping can

produce really excellent solutions and can do so really fast.