0:01

So here in lecture 6.3 we going to continue our exploration of multilevel

logic. We've seen that algebraic model simplifies

Boolean equations. It loses a bit of expressivity, but what

we gain is some simplicity, which makes it easier for us to do some sorts of

factoring operations, basically taking complex things apart by pulling out

divisors. So in order to pull out a divisor it would

seem necessarily that we need to divide something.

And that's true. We actually need to be able to divide one

Boolean equation by another to see how we can pull out useful factors.

And so there's a new operation that we need to talk about which is called

algebraic division. So, in this lecture, this is what we're

going to explore. So, let's go see how algebraic division

works. So it turns out there's a very nice

algorithm for this algebraic division thing.

So you give me a Boolean expression F and a divisor to divide by D, represented as

lists of cubes And each cube is a set of literals.

And I'm going to create for you a quotient, q equals f divided by d.

Right, this is what I'm going to do. And those are the cubes in the quotient or

it's going to be 0 or let's say empty if there aren't any.

And there's also a remainder r that's going to be computed which are the cubes

left over. When you divide d, or it's going to be

zero if d was a factor. Right?

If it, if it, divided in cleanly. And we're going to figure out q and figure

out r. We're going to figure out the quotient,

and figure out the remainder. So f equals d times q plus r.

Or, you know d times f over d equals r, and gosh that looks a lot like real

numbers. And the strategy turns out to be

surprisingly simple, which will be, become more apparent when an, an, an example for

you in much detail. This is a cube wise walk through, cubes in

the divisor d, trying to divide them one at a time into the function f.

Being careful to track which cubes do in fact divide into the function f.

So here's, here's the high level algorithm.

We're going to, we're going to sort of walk through this and then we're going to

do an example in a simple tabular form so you can see how it works.

So algebriac divisoin, you know we pass in f and d, we want to divide d into f.

And so it starts for each cube d and the divisor.

And that means for example this for each cube D in the divisor let C be the cubes

and F that contain this product term small d so for example if there was a cube in a

divisor that was yz. Cube xyzw contains yz and so we'd say yes.

Right, that one contains that product term.

Now if that set is empty then we just say oh, okay sorry there is no quotient.

You know, the quotient is 0 and the remainder is F.

Otherwise the next thing we do, from that set of cubes in F that contain this

product term D. And again we're walking through the

product terms in the divisor D one at a time.

The next line of the algorithm says let c equal cross out the literals of cube d in

each cube of C. And that just means that suppose C was

something like xyz plus yzw plus pqyz and suppose the divisor cube d was yz.

Then crossing out all of the yz parts is as simple as you know, going up here and

crossing out sorry all of the yz parts, all the yz parts all, of the yz parts.

And, what's going to be left over is an x from first term and a w from the second

term and pq from the third term. And, I'm going to get x plus w plus pq.

3:58

And then if d small cube, small d is the first cube of the divisor, that's actually

just the quotient. That's the running quotient.

We just set q to be that. Otherwise what we actually do is we take

the Current pass at the quotient and we intersect with the last pass at the

quotient. So for example if q is equal to x y z plus

y z w plus p q y z and suppose C is x y z then when we intersect them we just get

the cubes that are in both of these things.

And in that case it's just going to be, XYZ.

And then that when we're done with a inner-loop of that algorithm is going to

give us the real quotient. And then the final step is to create the

remainder, which you do by literally multipying, or if you will anding the

quotient and divisor back together and then just crossing out the terms you find

in F. Now this all sounds a little bit

complicated but it turns out it's not and it makes a lot more sense if I just show

you an example. So here's F, I want to divide F by D and

capital F is axc plus axd plus axe plus bc plus bd plus de and capital D Is ax plus

b. So I want to divide f by d, and I want to

see what happens. And, so their's a table here.

And the table has three column's. It has the cube, it whats they call the f

cube, because we're going to work on each cube of f.

5:27

That it has the D cube and it has one column that say ax and one column that

says b, because this algorithm is cube wise walk through the divisor.

And there's two cubes in the divisor, so the first cube is ax and the second cube

is b, so we're going to walk in that order.

And the rows of the table are for every cube of f, a x c plus a x d, a x e.

B c, b d, d e and then there's a blank row at the bottom where we do the work.

Okay so what's the first thing that we do. Right, The first thing we do is say okay

let's grab the first cube of the divisor which is a x.

Alright, and then what we're going to do is we're going to look at the cube in f

and we're going to see which one of them, which of them have a x in them.

So turns out that the a x c has an a x in it.

Great what do we do? We grab that cube and we cross out the a

and the x. What do we get?

We get a c. The next cube was axd.

Is there an ax in there? Yes there is, cross it out, you get a d.

The next cube is axe. Is there an ax in there?

Yes there is, cross it out, and you get an e.

Now you keep doing this for every cube in F and then you discover that the B C, B D,

and D E cubes do not have an A X in them, so you don't get anything in your list.

Your list is this thing called capital C. And then when you're done, you simply take

all of those things and you or them together.

6:56

And your first, running quotient is c plus d plus c.

Okay, and you're done with the first pass of the inner loop.

And then you go back, and you go back to the next cube of the divisor, and that

cube is b. And then you do the same thing, you walk

through each individual cube of f, and you say...

Hey, any cubes with a b in them? Axc the first row of the table does not

have a b. We don't have to do any work, axd, no b's,

no work, axe, no b's, no work. But bc has a b in it.

We cross out the b and we get a c. Bd has a B in it, we cross out the B and

we get a D and the final cube in FD does not have a B in it so we're done.

Then the next step of the algorithm says okay look we're going to take these two

cubes that we just found, we're going to ore them together, that's sort of the new

part of the running quotient and then we're going to intersect them with the old

part. The previous quotient and what we get is

the new running quotient. And we are just going to keep this up

weather or not if there were more cubes indeed there would be more columns in this

table. But when I ran out of cubes in the device

or d, I would wbe done, and this is in fact the final answer.

So its a cube-wise walk through the cubes in f.

Looking at the cubes in d and asking sort of one cube at a time do you divide into

this guy, do you divide into this guy. And then doing the appropriate accounting

which is in this case intersecting things to make sure that you get everything

dividing appropriately. So that the actual quotient here is c plus

d. And then you got one more piece of work

which is this, this line of the algorithm here and I'm showing just a small version

of the algorithm, for, for hopefully for some navigation purposes.

I have to compute the remainder and you do that by literally taking the quotient that

you just calculated, c plus d. Right, and ending it with a divisor which,

when you do that, you know, creates a, sort of a big set of sum of products

terms. And then you simply remove them from f.

And so, on the left, there's a note that says, the remainder r is f minus q times

d. The minus here means, remove the cubes and

q times d that appear the same in f. So.

What are the cubes that I'm going to be removing?

Axc goes away, axd goes away, bc goes away, and bd goes away.

So I started with axc plus axd plus axe plus bc plus bd plus de.

When I multiplied c plus d, times ax, plus b, I got axc plus axd plus bc plus bd.

When I remove the similar cubes I'm going to be left with just.

Ax plus de, and that's the remainder. So that's R.

And so this is it. It's not very complicated.

There's really almost nothing of a, of a detailed Boolean nature going on here.

It's all just kind of a little bit of pattern matching.

10:01

Now the one thing I gotta sort of remind you of is that hey you don't get any

Boolean simplification there's only this algebraic stuff and what that means is

that if I gave you an equation like a guard F equals ab bar c bar plus ab plus

ac plus bc and I want to divide by G. Is ab plus c bar.

The first thing you have to do is transform it into something like, like let

capital X be b bar, let capital Y be c bar.

Then you get F is aXY plus ab plus ac plus bc.

You get G is ab plus Y. Then, and only then, are you allowed to

use the algebraic model, because then nothing bad's going to happen where you

try to employ any of the Boolean simplifications.

You must treat the true and complement forms of a variable as different for this

particular operation. One more constraint is that you actually

don't want any redundant cubes. To do F divided by D, F should really not

have any redundant cubes. There's a technical term for that, that is

said to be, minimal with respect to single-cube containment.

In words, it means no one cube is completely covered by other cubes in the

SOP cover. Here's sort of a simple little example.

F is a plus a b plus b c. If you were to just do this little

Karnaugh map, got a Karnaugh map on the right-hand side, four by two, a b on the

top, c on the left has got 1s on the right-most two by two squares and then 1,

a 1 on the bottom-right cell of the left 2 by 2 squares, if you were to, you know

just Karnaugh map this out the, the big 2 by 2 square on the right is a ab is the 1,

1 column. And bc turns out to be the middle two

squares in the bottom row. The problem is ab is completely contained

in a. And the problem is that you know, if you

were to do like, F divided by a The divisor was a, you know, what would

actually happen there is you would get something like the right answer is 1 plus

b and you know, we're just not suppose to be doing stuff like that in the algebraic

model. You're just, you're just suppose to be

keeping things with just this simple pattern matching on the variables.

You don't ever want to sort of resort to any of the Boolean optimization.

So this, is, you know, if, if, if the function f has redundant cubes in it, you

need to go try take those out before you actually do this.

And that turns out not to be too hard. So, here we are.

We've actually made some really good progress.

If I have a Boolean function, f, and a Boolean function d, and I put them in this

algebraic model, I can compute a equals, you know, q times d plus r.

I'm sorry, i can compute f. In this case, sorry, is equal to Q times D

plus R and I can actually do this via the algebraic model.

And this is great But it's still not enough.

I don't know how to, how to find these things.

I don't know how to find these interesting divisors.

So for example, on the left hand side, F1 is ab plus c plus x.

F2 is abx plus cx plus q. F3 is ab plus q.

And what I'd like to do is discover that d1 of factor AB + C can be divided into

all of these functions, or atleast it can be divided into F1 and F2 as shown here.

It can't be divided into F3. So said differently, if I give F and I

give you D I can compute F divided by D, but in a big logic network, there's a lot

of apps. And I have no idea what the d's are.

I need to go figure out how to find divisors, how to extract them from these

complicated f nodes. And what we're really going to be looking

for here are two kinds of divisors. We're going to be looking at divisors that

are a single cube, like d equals a b. And we're going to be looking at divisors

that are multiple-cube divisors, things like d equals ab plus cd plus e.

So let's go look at how we do that.