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.