[SOUND] So here in lecture 7, we're going to continue our exploration of the multilevel logic model. What we learned in the previous lecture is that the kernels and the co-kernels of Boolean equations expressed in the algebraic model, are where all the interesting divisors live. We know that that's where we should go look. But we don't know, yet, how to actually find divisors in a big, industrially sized logic network. So what we're going to do in this lecture is show how you actually extract the factors. And so in this first part, we're going to do the simplest case. Which is extracting common divisors that are made up of exactly one cube. So let's go look at how we pull out a single cube divisor. >> So the question we’re all about here is, how do we find good divisors? Now just to be clear, this has a name. This is called extraction. So the verb we like is, how do we extract good divisors? And we're interested in extracting both single-cube divisors from multiple expressions and multiple-cube divisors from multiple expressions. So I got a little picture here that is illustrating this. If we have nodes in our Boolean network, F and G. What we'd like to do is be able to extract a divisor, a lowercase d here. And then we would rewrite f as being d. And a quotient, plus a remainder. And we'd represent g as d, and a second quotient. The different quotient, plus a different remainder. And the question on the table is how do we mechanically extract a single cubed divisor? For example, a divisor like an A, right, or an AB. And how do we extract something like a multiple cube divisor where for example we might be extracting something like a plus b c? And what we know is that if we want a single cube divisor, we should be looking at the co-kernels. And we know that if we want a multiple cube divisor, we should be looking at the kernels. But what we don't know is, mechanically, how do we do that? So let's go look. So here's sort of the overview of what lecture seven is about. For the single cube case, we're going to build a very large matrix of 0s and 1s. And we're going to heuristically look for something called prime rectangles. I'll explain that a bit in this matrix. Each such prime is a good common single cube divisor. For the case of multiple cube extraction, we're going to build a different, large matrix as zeros and ones. And we're, again, going to look for these things called prime rectangles. And each such prime is again, a good divisor in this case a multiple cube divisor. And what's really just amazing about this stuff, is how much this stuff looks like Karnaugh maps. Except for the fact that I can do it all automatically. I can do this computationally as a piece of software. Nevertheless, it's still a very unifying and it's kind of a familiar idea, which is kind of maybe a bit of a surprise. So what's the matrix that we're going to be using to form the basis of the single cube extraction? So here's how that works. Given a set of SOP algebraic model Boolean equations, in this case, they're P and Q and R. We're going to construct something called the cube-literal matrix, and it's constructed like this. There's a row for each unique product term in any of the Boolean equations in our logic network. So if we take a look, what we're going to see is that there's an abc row, an abd row. An eg row, because that's P. An abfg row, because that's Q. A bd row and an ef row, because that's R. And we're also just numbering the rows. One, two, three, four, five, six just for sort of convenience when you want to refer to them. There is one row for each unique product term. And if the product appears in a bunch of places, I don't need multiple rows. One row for each unique product term. There's one column for each unique literal. That's really even simpler. What are the literals in these P and Q and R bowline equations abcdefg? That's what they are. Those are the columns of my matrix, 1,2,3,4,5,6,7. So, what do you put in the matrix? Okay, that is the next thing. So what you put in the matrix. And that's the second bullet is, you put a 1 in the matrix if this product term uses this literal, else, a dot. A dot just means I don't care. So, let's go look at the very first row. The very first row is the abc cube in the P equation. And it really as simple as this. What is in abc? And the answer is there's an a in there. And a b in there, and a c in there. And so I put a 1 in the a column, a 1 in the b column, and a 1 in the c column. And I put the dots in the d column, e column, and the f column, and the g column, because there isn't a d or an e or an f or a g. It is just that simple. So the abd row, row 2, has 1s in the a, b and d columns, 1,2, and 4. The eg row has 1s in e and g columns, 5 and 7. The abfg row has 1s in the abf and g columns. Columns 1,2,6, and 7. Row five bd has 1s in columns 2 and 4 bd. Row six has 1s in columns e and f, row 6, columns 5 and 6. That's it, it's as simple as that. So, this is the matrix. The next question is, what do we do with this matrix? Here's the complete matrix with everything filled in. And what we're going to be looking for is a special kind of a cover on this matrix. Now, we already saw one covering in the work on two level synthesis in a espresso. This is a different kind of a cover up. This is a different kind of a meaning. So let's define a few things. What is a rectangle in this cube literal matrix? A rectangle is a set of rows, R and a set of columns, C. That has a one in every intersection of the rows and Rs in the columns in C. And what's interesting is that in this definition, a rectangle does not have to be a contiguous row. So unlike a Karnaugh map, they don't have to be rows in order in the matrix or columns in order in the matrix. And a prime rectangle is a rectangle that can not be made any bigger by adding another row or adding another column. And so here's just an example of what a prime rectangle looks like. So, it's column a and b. And its rows abc, abd, and abfg. Now the point about things not necessarily having to be contiguous is just shown very clearly here. The first two rows are part of this prime rectangle. And the fourth row is part of this prime rectangle but the third row is not. And the other thing that is critical here is that there is a 1 every place in this rectangle, at every intersection of the rows and the columns, there's a 1. So this is very Karnaugh map-like. Except for the fact that I don't need a power of two on the rows and the columns. And that things don't need to have this special adjacency structure that we do in Karnaugh maps. But, all I need is it to be the case that there's a one in every row column intersection. And a prime just like a prime implicate to the Karnaugh map means I cannot make this thing any bigger. I cannot add another row to this thing and make it more rows. And I cannot add another column to this thing and make it have more columns. So this thing is as big as it can be. Now, why is this interesting? Why this thing is interesting is because prime rectangles are divisors. And in particular, the columns of the prime rectangles create the divisors that we seek. And this sort of makes sense if you just look at what I've got drawn here. Look on the left hand side. P = abc + abd + eg. I've got the abs written in red and sort of bigger, because those are columns. And Q is equal to abfg. And I got the ab written in red and big, because Q has also got this in it. R doesn't have any abs in it, so I can't really do anything. If you take the a and the b that tag the columns and simply and them together. So let's say, x is equal to a anded with B, then, hey, I've found myself a single cube divisor. And I can rewrite my original function. P = Xc + Xd + eg. Q = Xfg. R is the same, bd + ef. And X, a new node they're going to add to our Boolean network, is equal to ab. And hey, I have done an extraction. It was as simple as making the matrix and going and looking at the columns of a prime rectangle to identify a good single cube divisor. Now, there's something else that's important. Remember that we factor the network. Which is to say we extract good common divisors for a purpose. And that purpose is to reduce the literals in the logic network. In this particular presentation about multilevel synthesis, we're just really going to be talking about complexity. We haven't really talked at all about timing in a Boolean logic network yet. So, we're just trying to make the logic network smaller. But, it would be really nice if there was a simple formula to compute from a prime rectangle how many literals we've actually saved. And, luckily, there is. So here's the recipe. You start with a prime rectangle. Let C be the number of columns in the rectangle. And then for each row, r, in the rectangle, let the Weight(r) be the number of times this product appears in the network. So then the formula for computing how many literals are saved, and that's what L is. Is C-1, times the sum over all of the rows in the rectangle of the weight of the row. Which we just defined, and then from this multiplied quantity, you subtract C. It's just accounting, it's just book keeping. But the nice result is for a prime rectangle, L is the number of literals you save. And so to be precise, if you count the literals before extracting this divisor cube. And then in the new network after you have extracted this divisor cube. And replace the variables with the name of this new divisor. If you count the literals after, L is how many literals you save. So let's just go try it. This is a little example, a new example, a different example that just illustrates some things that I want you to see. So, on the left we have R = abw + wz and S = abw + aby. And then we've got our little cube literal matrix. And so it's got three rows, abw, row 1, aby, row 2, wz, row 3. And it's got 1,2,3,4,5 columns. Column 1, b, column 2, w, column 3, y, column 4, z, column 5. And then, the abw rows has 1s in ab and w. The aby has 1s in ab and y and the wz row has 1s in w and z. And I've got a little prime rectangle here. It's the first two rows, abw and aby in the first two columns, a and b. It's clearly a rectangle because it's got 1s in all the intersections and it's clearly prime. I can't add any columns and I can't add any rows. So if we take the product of the labels on the columns, we get a nice new single cube factor. Which is x=ab. And so again, let's go look at the formula. (C-1) times the sum of the Weights(r)- C. So C is two columns, right, that's easy. What about the weights? The weights are a little more subtle. So the Weight of abw is 2. And the reason for that, is that abw appears twice in the network. And this is important, because every place abw appears is going to be replaced by something new. And so we have to account for that. However, the weight of aby is just 1. Because aby appears just once in the network. So in only one place, we're going to actually replace that. And then if we do the math, C- 1, 2- 1 times the sum of Weight(r) 2 + 1- C = 1, and it works. We did, in fact, say just one literal. So you go to the left hand side and you count things. If you count the appearance of every literal on the right hand side of the equal sign, you'll find there is 11 of them. If you go to the right hand side, what you see is X=ab has been extracted. And R is now rewritten on the top as Xw+wz. And S is rewritten as Xw+Xy. And if we count the literals. One, two, three, four, five, six, seven, eight, nine, ten. Yeah there's ten and we saved just one literal by doing that. And it's just book keeping. But if I was to sort of explain this. The formula counts all the places ab appeared before we started doing any extraction. So there was six places at the six literals. And then, the savings to replace each one of those things with a new variable x. Which was the name of the extracted divisors. So there are three literals there. And then, the new overhead of actually adding the X=ab term in. Because there's a new node in a new right-hand side of an equal sign, which is 2. -6 + 3 + 2 = 1. It's doing the right thing. It's actually computing things. And really, that's all there is to taking a very large, very complicated Boolean logic network. And automatically extracting a single cube divisor. Assuming, of course, that we can actually find the prime rectangle. Which is something we're going to be talking about in a while. But that's really all there is to it for extracting a single cube divisor. So what we need to do next is, look to see whether or not an idea of this type can actually be used to extract a multiple cube divisor. So let's go do that. [SOUND]
