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.