So here, we are at Lecture 3.3. We're continuing our exploration of Computational Boolean Algebrea and Binary Decision Diagrams. Up til now, we've shown you how you make. A BDD for a Boolean function. But honestly, in the real world who wants, to manipulate one Boolean output? Right? You know a block of logic on a real chip has lots and lots of inputs and lots and lots of outputs. We need to be able to manipulate lots of Boolean equations at the same time. It turns out that BDDs naturally support that. In fact, we can share nodes in BDDs so that many different functions can be using the same ecosystem of nodes in the BDD. And it turns out that one actually gets more efficient BDDs. So in this lecture, we're going to show you some examples of how sharing actually enables us to represent complicated sets of functions with one set of BDD nodes. So now that we know how you build a reduced order BDD by starting with a decision diagram. At least conceptually, requiring a total variable ordering from the root to a leaf, and then reducing the BDD so that there are no redundancy so that you get the smallest, tightest possible BDD. Let's just talk a little bit about the interesting things you can do. So, the first thing is that you can represent any function. And any Boolean function of anything is a reduced ordered BDD. And you can do so in a canonical way. So some lovely things happen. What if I told you, that my function of variables x1 through xn is a 0? Right? How might we represent that as a reduced ordered BDD? Well, really, there is only one option. There's exactly one option, and it is that. If this function is equal to 0, for all possible inputs, then it has to just be a pointer to the 0 node. What if the Boolean function is a 1? All right, well, then the same thing is going to happen. If the Boolean function is a 1, then it has to be a pointer to just the 1 node. And I'm going to go off to the side with this little text box here and, box here and say let's, let's just remember something. In a Reduced Ordered BDD, a Boolean function is really just a pointer to the root node of a canonical graph data structure. So you point to the top node of the BDD. And then you descend the BDD and that's how you determine the values of the function for the variables of interest. If f is a 0, it's a pointer to the 0 node. Period. There's no other way of, of that happening. And if the function is a 1, it's a pointer to the 1 node. There's no other way of doing it, because reduced ordered BDD's are canonical. There is one and only one way to represent every function. So that's just a very nice simple thing. What if in contrast, the function is of a, of variables x1, x2, dot, dot, dot, xn. And we just pick one of those variables, we just call it x. And we say that the, that function is just x and we ignore all the other variables. That well, then, we're going to get a variable node. And the low child is going to point to a 0. And the high child is going to point to a 1. And the function itself is going to point to that x node. So it's really a very nice, simple kind of a thing. What if we have a more interesting function, you know, a function that's got a little bit of complexity to it. Let us assume that we have a function and that it's a function of four variables, x1, x2, x3, and x4. And that the ordering is in fact x1, x2, x3 and x4 in that order. So here's just a simple function on the left. X1 plus x2 and x4. What we'll notice is that interestingly enough, there is no vertex labelled x3, would be, in here somewhere if it existed. Because it has to be after x2 and before x4. But this particular function does not depend on x3 and so there are no x3's. And lots of graphs are shared, we're going to, we're going to talk about that more extensively in this talk. And you know, this particular you know, function is really just again a point or two the top node on this BDD. Because a BDD is really just a pointer to the, to the, to the variable that defines the top of the BDD graph data structure. And you can see, if you just think about this for a little bit, that this, that this BDD actually makes sense for, you know. For example you know this thing is really x1, x4 plus x2 x4. And so what I expect is the only two ways to make this function a 1. Okay? Are I need to make the first term a 1. Or I need to make the second term a 1, right? And the way to make the first term a 1 is to go down this path, which says x1 has to be a 1 and x4 has to be a 1. And the way to make the second path a one is to go down this path which insists that x2 is a 1 and x4 is a 1. So it actually works. Odd parity is a more interesting, kind of a denser, if you will, a more compact function. Odd parity is x1 exclusive or x2 exclusive or x3 exclusive or x4. And its odd parity which means that it makes a 1 if and only if there is an odd number of 1's among the inputs. So, for example, if we just think about lets say, x1, x2, x3, x4. Imagine we have 1, 1, 1 0. Let's see if this works. Okay. Here's a x1 is a 1. Here's is x2 is a 1. Here's x3 is a 1. Here's is x4 is a 0. Yeah, makes a 1. All right. So this is this sort of zigzag sort of path back and forth. This is very dense way of capturing the fact that I only care about when an odd number of the representative variables take the value 1. That's the only way I can get to a 1. Any path with an even number of zigzags takes me to a 0. It's a very tight representation. It's a very, kind of elegant and compact representation. And it is also illustrating another very important technical point. And that's sort of the, the substantial part point of this particular lecture. Every BDD node, not just the root, but every BDD node represents some Boolean function in a canonical way. Now, you might create the BDD on the left because you chose to want to manipulate x1 plus x2 and x4, and that's great. But every node inside the BDD is the root of some subgraph. And every single one of those represent some other function. Even of you didn't want it, even of you didn't try to create it, it just happens. Right? So for example this, right, is f. And this is f, right, x1 plus x2 plus x times x4. That's great, What if I tell you that, that function is a g? What is that? Right? And the answer is, if you kind of stare at it for a little bit. That g is equal to x2 x4. And that makes you know really good sense. The only way be able to get to the 1 node from starting from g, is x2 is 1 and x4 is 1. So g is x2 x4. That's just you know that's just an end gate with x2 and x4 as its inputs. If we look at the, the BDD on the right, okay? And, and we say all right now, this is f, all right? So f is equal to x1 exclusive or x2 exclusive or x3 exclusive or x4. And now I start pointing at intermediate nodes like that node. You know, what do I get? Well, if you stare at that one that node is actually the root of the function x3 exclusive or x4. Right? The only way you can get to the 1 node is if x3 disagrees with x4, if they have different values. And conversely, the 1 on this side, right, the 1 on the right hand side of the B, of the exclusive word BDD is x3 exclusive nor x4. And just by way of a reminder, that's just an exclusive or gate with a inverter bubble on the output of it. And that's actually the even parity function for two inputs. And similarly, the one on the right-hand side here the x4 node, that's actually just the root of the function x4 bar, right? And you stare at it, you'll say, yeah, if x4 is 0, I get a 1. And if x4 is a 1, I get a 0. Okay. That must be not x4. Now, we can take this idea that every node inside a BDD represents a function. And we can take this to sort of the, the next logical step, which is that we can do something useful with this fact. So, here's a more interesting, rather more realistic example. So let us consider a 4-bit adder. And so the yellow box that I'm showing you on the left hand side is a four bit adder. It has two sets of 4 bit numbers as its input. It has a3, a2, a1, a0, that's a 4 bit number. And it has b3, b2, b1, b0, it's another 4 bit number. It adds those numbers together. It produces a sum, s3, s2, s1, s0. But I don't care about anything other than the most significant bit, the high order bit of the sum. That's s3. And it's gotta carry out. And I will note here, just for completeness, that there is no carry in, in this example. Alright, so there's only a carry out. And there's a high order sum bit. If I were to build the BDD for the sum bit, S3, that is the BDD shown on the left, it's got a lot of exclusive or kind of structure, because, you know, things on the inside of adders are, you know, lots of exclusive or kinds of things. And it's got a positive logic carry chain that tells you when, you know, the carry wants to be a 1. And it's got a negative logic carry chain that tells you when the carry into the high order bit wants to be a 0. And then you can decide, you know, based on those two things. With a little bit of x or computation at the top, you know. Whether the sum3 bit is a 1 or a 0. If you then go look on the right hand side at the other BDD for the carry out, you see it's got really quite a lot of the same structure. In fact, the big gray box, which is what I am highlighting. So I'm just going to sort of outline it here. There's this big gray BDD over here. And there's this big gray BDD over here. Those things are basically the same shared function, sub function. And I, I , I can say that even more, even more strongly, those things are identical graphs. There is nothing different, those things are exactly the same. And so we get an interesting question. Which is you know, in any realistic kind of a digital design scenario, you don't build a BDD for one function. You build a BDD for a whole lotta functions. I mean, you know, maybe hundreds and hundreds of functions. So, you know, it's not at all unreasonable that I'd like to build the BDD for the sum3 bit. And I'd like to build a BDD for the carry out bit. Do I actually have to build all the stuff in gray twice? If I physically build a BDD package, and I physically build the data structures for the sum3 bit and the carry out bit, do I have to physically build two copies of those gray nodes? Gosh, I hope not. That would be very, very inefficient. And it turns out that there is really good news. One doesn't have to represent it twice. One can have the BDD have multiple entry points or multiple roots. Right? One can simply share that subgraph. And so, as I'm showing it here again in gray. All right. The carry out function gets to use it. I'm going to circle the, the parts of the carry out function that use it. And, in addition, the sum3 function gets to use it. And, you know, the way it gets to use it, right, is that there's this shared BDD sub function and the carry out gets to send some edges pointing to it to use it. And the sum3 gets descend some edges into it getting to use it and you just share it. Right? And so these things are called multi-rooted, which just means that there's more than one pointer pointing to the node. There's a single node up there at the top that defines the entry point of the BDD. So these things are called multi-rooted BDDs. And again, every node in a BDD represents some Boolean function. So this multi-rooting idea is just explicitly exploiting all of this to better share stuff. So it turns out it's sort of an engineering idea, but it's a wonderful and simple idea, it actually makes things very efficient. You ask, how efficient? Oh, it makes things wonderfully, magnificently efficient. And so here's a, a, a lovely example from, from Randal Bryant again. Why stop at two roots, right? You know, why not have as many roots as you want, right? So if I have a, you know, sort of a, a shared subfunction here. You know, I can have all kinds of people wanting to use that thing. As, as, as, as many as I like. So these are big savings for sets of functions. You can minimize the size over several separate BDDs by maximizing this sharing. So the thing that I'm actually showing you on the right is, the full 4-bit adder. Right? So this is the full, 4-bit adder. Right? And so what you're seeing are the four sum bits, okay, and also the carry outs. So, four things, um,eight things go in. Four As and four Bs, as you can see here. A0 through 3 and B0 through 3, and four things come out for sum bits and one carry out comes out. Now, how much savings do you actually get when you do stuff like this? Well, if you were to build the BDD separately for each of the bits of the sum and the carry out. If you had a 4-bit adder, it would be 51 nodes. And it would be almost well, 12,500 nodes for the 64-bit adder. But if you shared them, and so 31 nodes for the 4-bit adder and 571 nodes for the 64-bit adder. Now, look. The difference between 51 nodes and 31 nodes is no big deal. The difference between 12,000 nodes and 600 nodes is a factor of, of what, 20? That's a gigantic savings and it just gets bigger as things get bigger. So the multi-rooted idea, the sharing idea, the fact that we can exploit the fact that every node in a BDD is a Boolean function. And if somebody else needs to use it, they can just point to it. That's a wonderful thing. That's just a really great, great thing about binary decision diagrams. And so, this lecture has been all about the fact that BDDs are shared data structures that we can build lots of Boolean functions in the same data structure. That every node in a BDD represents a Boolean function and that we kind of reuse those things in appropriate ways with multi-rooted graphs to do really significant amounts of, of, of engineering savings. So, next, what we want to talk with a little about is how people actually implement these things.