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. 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. 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. 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. 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.