0:00

So, here in lecture 6.2, we're going to continue our exploration of multilevel

logic by introducing a new mathematical model of the logic that goes inside the

nodes in the Boolean network model. And that Mathematics has a name, it's

called the algebraic model. And what's actually rather interesting

about it is that it starts with its premise.

Let's take Boolean equations and let's throw away the parts that make them hard.

Let's actually throw away the parts that make them not look like polynomials over

real numbers. And in fact, if we through away those

difficult parts, we can do some really useful operations on these Boolean

equations in the algebraic model. And the really important thing we can do

is we can factor them. We can take big equations apart and pull

out common small pieces to make the networks smaller and less complex.

So, let's go take a look at what the algebraic model does.

So, before I start a little bit of context here.

Multilevel synthesis, just like 2-level synthesis, is a heuristic.

And more interestingly, it's a lot of heuristics.

And you've already seen in ESPRESSO, there are a lot of interesting heuristics that

were involved in the reduced expanding redundant loop.

Multilevel synthesis is just more complicated because there's a lot more

going on. And what turns out to be the case is that,

one actually writes scripts of basic operators.

One writes things that amount to little programs in a little programming language,

where there are many, many kinds of operators that each do a certain kind of

optimization iteratively over the surface of the Boolean logic network.

So, we'll do several different passes of different kinds of optimizations.

We'll do some cleanup kinds of steps to get rid of the too small nodes and remove

them. We'll look for certain kinds of easy

factors that are just sitting around in a logic network and we'll say, hey, are you

somebody's divisor? Can I sort of profitably reduce somebody's

the inside of somebody's Boolean network node by, you know, using you as a factor?

We'll look for hard factors where we take a bunch of big complicated nodes and we'll

do the difficult work too, and let me use the proper verb, extract them.

And try to keep the good factors and, you know, kind of plug them back in and we'll

do 2-level optimization on the insides of each logic network.

Now, their is a whole lot of art in the engineering of these scripts.

People get paid real money to write these kinds of scripts and different kinds of

logic, design, scenarios, have different kinds of scripts.

But the one big, big thing that you just don't know, that's the heart of most

Boolean multi the, the, at the heart of multilevel logic synthesis using a Boolean

logic network, is how to factor things. So let's talk about that.

I need another new model. I need a new mathmatical model.

So, how are we really going to do factoring?

This is actually a very cool idea. We're going to develop another model of

Boolean functions that's just specifically designed to let us do this factoring

thing. And the trade off, and this is may,

perhaps a surprise, is we're going to be willing to lose some expressivity.

Some aspects of Boolean behavior and some Boolean optimizations we're going to agree

we cannot do. They're just unavailable to us.

But what we gain is that we make it possible to do practical factoring in a,

in a, in a good way. You know, in a, in a, in a practical

useful way. So, not perfect.

There's somethings we, we agreed to give up, but we're going to get practical

factoring. The model's called, the Algebraic model

and the term Algebraic comes from pretending that the Boolean expressions

behave like polynomials of real numbers, not like Boolean algebra and we're going

to, end up with the new Boolean operator which is called Algebraic division because

it is using the Algebraic model. It's also called weak division because of

this loss of expressivity thing. Okay there's some things that we are just

unable to do. It's not fully you know, fully Boolean

kind of a model. Turns out that's a surprisingly good

trade-off. So, here's the basic idea of the Algebraic

model. We're going to keep just those rules or

technically those axioms that work for polynomials of reals and also for Boolean

algebra formulas, and we're going to dump the rest.

This is kind of surprising. So what I'm showing you here, on the left

hand side, I'm showing you some of the axioms for how operations work on real

numbers and on the right, I'm showing you how axioms of how things work on Boolean

algebra. And the things on the left ought to be

familiar for anybody whose done, you know, algebra for the last, you know, let's say

maybe 10 years. So there's somethings about real numbers a

times b equals b times a. A plus b equals b plus a.

That's commutativity. It doesn't matter what order you do things

in. A times b times c, equals a times b times

c. You can put the parentheses around the b,

c or the a, b. A plus parenthesis b plus c, equals

parentheses a plus b plus c. That is associativity, it doesn't matter

what order you do the times and the adds. A times b plus c is a times b plus a times

c, that's distributivity. A times one is a, a times zero is zero, a

plus zero is a, that's, that's the way identities work for you know real numbers

where you are actually adding and you are actually you know, multiplying.

Now, in Boolean algebra, those things that are listed in blue are also the same, a

and b, equals b and a, a or b equals b or a.

You know, as long as or is plus and, and is dot.

A and b and c in parenthesis is a and b and c.

A plus parenthesis b plus c, equals parenthesis a plus b plus c.

It doesn't matter the order in which you do ands and ors.

They associate. A and b plus c is a and b, plus a and c.

They distribute. A and 1 is a, a and 0 is 0, a or 0 is a.

Now, those are all the same. The problem is that Boolean algebra is not

the algebra of real numbers. And there's some other stuff, right?

So, for example, there are some rules for how things behave when you start doing

compliments. Right, a plus a bar is 1, a and a bar is

0. We don't really have compliments in real

numbers. That's just not there.

A and a is a, a plus a is a. That's a set of, of laws, those are called

the idempotent laws. A plus 1 is one.

That's another one of those rules for how identity works.

But you know, a plus 1 is not 1 for real numbers and, and then, there's another

distributive law which is the other one, a plus b times c is a plus b times a plus c,

and trust me, as somebody who's taught, you know, digital design for a really long

time, this is the rule that people mess up.

So, the idea is the stuff on the top of the diagram in blue, it just works for

both reals AND Boolean algebra. The stuff on the bottom of the diagram in

red does not work. And so, what we're going to do is we're

going to structure our Boolean equations in ways that literally let us ignore these

stuff in red by insuring that it never happens.

And it turns out there is actually a surprising simple way to do that.

So, if you only get to use algebra rules from real numbers.

One consequence that's very important and very immediate is that a variable and its

complement must be treated as unrelated, totally unrelated.

And this is really one of the principal losses of expressive power for Booleans in

the Algebraic model. And we just tolerate this.

So, if you have a Boolean expression like ab, F is ab, plus a bar x, plus b.

Y, b bar y, I need to get rid of those confluence.

I can't have as and a bars floating around in the same Boolean expression.

I can't have bs and b bars, so I'm going to let R equals a bar and S equals b bar.

And, when I rewrite this expression, it's going to be ab plus Rx plus Sy.

And then, suddenly, this looks more like, you know an equation that you could see

in, in just, you know, a polynomial form. And you know, again, the reason for this

is that we don't want to see any circumstances where we try to do something

like x times x bar or, you know, x plus x bar b, which one can simplify, or x plus x

bar, we just don't want any of those things to happen.

And so, by sort of removing the things with compliments and replacing them with

just different variable names, we're going to, basically, make, make sure that, that

doesn't happen. We're going to lose some expressive power.

But we're going to gain some very interesting factoring techniques.

So Boolean functions are manipulated just as SOP expressions just like polynomials,

each product term in such, in such an expression is just a set of variables, you

know, a, b, r, y. And the SOP expression itself is just a

list of those products that are list of those cubes.

So, very much like the URP stuff with, you know, positional cube notation kinds of

ideas. You know, it's just a list of cubes,

nothing more to it. Now, Algebraic Division, this is what

we're really trying to accomplish for Our Model of Factoring.

If I give you F and I give you a function D, okay then, what we want to do is take F

and divide it by D to create a quotient Q and a remainder R.

So, F equals D times Q plus R. And the remainder, well, if it's zero,

then, we say the divisor is technically called a factor, and if not, it's just

called a divisor. Now this should be very familiar if you

replace all these things with real numbers, like I show on the left hand side

of the slide. 15, F, is equal to 7 times 2 plus 1.

I took 15 and I divided it by 7. That's the divisor, D.

I got a quotient, 2 but it did not divide evenly, and so, I got a remainder, 1 of R.

I can do exactly the same thing with a Boolean sum of products form.

F, in this case, on the right hand side, is ac plus ad plus bc plus bd plus e.

And so, that's the same as saying, well, that's actually equal to a plus b, my

divisor D, times Q, the quotient, c plus d, and there's a remainder left over

because it's not a factor. It doesn't leave 0 left over.

And, you know, this is really, this sounds simple, but it's really almost as easy as

saying, look if I had a Boolean expression like abc, plus bcd and I wanted to divide

it by bc, if you didn't know that those were Boolean algebra quantities, you could

say, oh gosh, that's easy, I just cross bc out of the top and bottom and I get a plus

d. That's really the heart of the Algebraic

model. If we can keep things looking as simple as

this. Going to write the a plus d a little more

legibly. If we can keep things to be as simple as

this, wow not so bad. Let's go look at some other examples.

So, suppose I got I want to do some algebraic division.

And I've got F is ac plus ad plus bc plus bd plus e.

And I want F to be B times Q plus R. So let's just divide some Ds and see what

happens. So, we've got D and what we're really

going to do is we're going to do F divided by D and we're going to get a quotient Q.

And maybe we're going to get a remainder. And then, we'll ask the question as to

whether or not we actually got a factor. Okay, so, what happens if you just divide

D by F. Well, you get a you know, you get a

quotient of 1. If you divide something by itself you get

a quotient of 1. You shouldn't be surprised and you get a

remainder of 0 you should also not be surprised.

Is it a factor? Yeah, but it's a, it's a, it's a trivial

factor, you know, it's not very exciting. That's like saying 15 is equal to 15 times

1. Yes, it's true, but it's not very

interesting. If I divide F by a plus b, it turns out I

will get c plus d as a quotient and a remainder of e.

So, is it a factor? No.

But it's still useful. If I divide by c plus d, I get a plus b,

that's symmetric, no surprise there. I also get a remainder of e and it's still

not a factor, but it's a useful divisor. If I divide by a I get c plus d with a big

remainder of bc plus bd plus c, it's not a factor because it's got a remainder.

If I divide by b, I also get the same thing, c plus d is the quotient.

Ac plus ad plus e as the remainder. Not a factor, but still may be useful.

If I divide by c, I get a plus b as the quotient, ad plus bd plus e, no, it's not

a factor, it's got a great big remainder. If I divide by d, I also get a plus b,

with ac plus bc plus e as the remainder. Not a factor.

If I divide by e, it turns out I just get 1 because there's not very much I can do,

and the remainder is the entire F. Right, so the question is, you know, how

do we actually do this, right, because it looks like it works, it looks like it

sorts of does the right thing in terms of us, being able to pull out factors but you

know the next big question is, you know, how do we do this?

So, let's go explore that in the next lecture.