So, here we are in lecture 3.4. We're going to complete our exploration of binary decision diagrams as a, a really powerful and important data structure for doing Computational Boolean Algebra. And up to this point, we showed how we could represent complicated sets of Boolean functions using a shared set of BDD nodes. And life just sounded really, really good. And as we're going to show in this lecture, you can answer some very complicated questions, like whether two complicated pieces of, of digital logic are the same. How they're different. Can you find an input that can make a complicated Boolean function equal to 1? We're going to see some really wonderful and, and seemingly simple ways to answer those questions. And so, in anything that's wonderful, there's got to be a catch, right? And the problem is that, the ordering of the variables has a profound effect on our ability to actually make the BDD. Not every BD, not every Boolean function can turn into a manageably sized BBD. And for some orderings of the variables, the BDDs are small and friendly. And for some orderings of the BDD variables, the BDDs are exponential and horrible. And sometimes we can fix that, and sometimes we can't. It's just the way life works here. And so, let's go look at how ordering affects life in BDDs. So let's talk a bit now about how BDDs are really implemented. And one of the things I said when we were beginning the development of BDDs is that I cannot honestly implement them the way I, I sort of conceptually introduced them. Which is to say, I cannot build the entire decision diagram flat out to like 2 to the 100 in leaf nodes at the bottom for a function of a 100 variables, and then apply reductions. There's got to be a better way, and there is a better way. And we're going to talk just in a very high level about that better way in this, in this bit of our lecture. How BDDs are really implemented are recursive methods. And it's, it's going to be a kind of a recurring theme in this class. You know, if you ask me, well, that's a really complicated CAD problem there, Rob. How do you think we're going to solve it? The answer's going to be, I don't know. Could we break it up into two pieces? Solve them recursively and then glue the answer back together, and the answer maybe 9 times out of 10 is going to be yes. So, even for BDDs, the trick is there's, there's some Shannon co-factor divide and conquer kinds of things. And the big idea here is that a BBD package is, is actually functionally implemented as a set of operators, we call them ops, on the BDDs. So, you get all the things that you would imagine from, say, gates, you know, you get an And, you get an Or. Not exclusive or exclusive nor. You get the Shannon kinds of operations, you know, co-factor or variable, or variables out. Because you have co-factors and Ands and Ors, you can do things like universal quantification. Where you co-factor things out, and, And them together. You can do existential quantification. You co-factor them out, and Or them. You can do satisfiability, which is to say you can tell me what makes the function a one by tracing a path to the one node down at the bottom. All of these things are implemented on top of the basic BDD data structure. And the basic idea is that we're going to operate on the universe of Boolean data as input and output, so we're going to have constants 0 and 1 are sum of our data objects. We're going to have variables, and we're going to have Boolean functions represented as shared BDD graphs. So, the big trick, the really big trick is that we're going to implement each operator so that if the inputs to the operator are shared, reduced, ordered BDDs, then the outputs of the operator reduced ordered BBDs. So, the other way to say this is that we never build an unreduced, badly ordered version of the BDD. We always start with things that are reduced and ordered and shared, and we maintain them. And roughly speaking, we use recursive methods to sort of take the function apart down to the bottom. And then, we sort of put it back together from the bottom up, just like URP, and we sort of, by putting them up back together in this sort of bottom up manner every time the recursion comes back up, we make sure the variables are in the right order and that we're doing whatever the appropriate reductions are. So that, you know, the way to sort of think about this thing, I've got a little, just a little example here, I'll put a little star by it. H equals BDD, and I've kind of writing this in a C-like style, you know, casting this as a, as a BDD up, a data object. You know, operator is some kind of a subroutine that takes an F bdd and a G bdd and produces and H bdd. And you want to think about that is well, here's F, right? F is the pointer to the top of some graph, here in the big cloud of BDD nodes. And G is a pointer to another graph in this cloud of BDD nodes. And perhaps, F and G overlap, maybe. Right? And then, when we call whatever op is, it's some kind of operation on BDDs F and BDDs G, we get a new BDD. And maybe BDD H is over here somewhere, and perhaps it also overlaps some. Or, you know, might be over here somewhere. Maybe that's BDD H, or kind of draw it with the dotted lines here. Maybe, maybe BDD H is some really big complicated messy thing, and F and G are mostly buried down inside of H, I don't really know. It depends on F, depends on G, depends on the operator as to what H is. But you start with shared reduced ordered binary decision diagrams. And you build the operators that you need to do real engineering. So that they return to you shared reduced order BDDs, and everything works beautifully. So, how do you actually build the BDD for something complicated? And the most standard example would be, that I give you something like a logic network, like a big logic network, a logic network with 10,000 logic gates in it and, you know, 50 inputs and 20 outputs. And the answer is, you can build back up by basically walking the gate-level network in a, in an incremental fashion. So, each input is a BDD. Each gate becomes an operator that produces a new output BDD. And we build the BDD for out, which is the, the value that we're looking for here. Basically is a script of calls to basic BDD operations. So, I've got the basic BDD operators script shown here on the right. It's kind of a very high level. It's kind of a pseudo code kind of thing. You know, step one says A equals create variable A. And that's just a kind of a shorthand for this, you know, this step over here that says, oh, okay. I'm, I'm going to create a variable A. And it is a, a function and it is a Boolean function. And it's pointing to you know, the 0 to the, to this variable node here. And the, the second one is a B which is creating a variable, you know, B and B is a function pointing to it. And the third one is a variable C, which is creating a function pointing to that. And each of those are the single node BDDs, you know, one, one vertex pointing to constant zero in one children, low child high child respectively. And then, it gets interesting. T1, as we see over here, T1 is the And of A and B. Going to put little check marks over here because I did one, two and three. T1 is the And of the A function and the B function so I'm going to assume that I have And implemented as an operator in my BDD package. And as a consequence, like in call, it would BDDs A and BDDs B, and I will get back BDD T1, which points at this particular little BDD as the result of step 4. And if you just stare at this for a while, you can see, yeah, that's actually the BDD for And because the only way I can get a one node is if a variable, variable A and variable B are both 1. Like okay, you know, that works. What happens next? Well, T2 is the And of quantities B and C. All right, well, T2 is going to be that. And T2 is going to be the result of step 5, and that is going to be a little BDD for B and C. And we can see again, it's sort of the trivial B BDD. The only way to get a 1 in this small, trivial BDD is to have B and C each be 1. All other paths lead to the 0 node. And then, we'll do the next step. Obviously, out is equal to T1 and T2. T1 is a BDD, T2 is a BDD. Or is an operator that our BDD package will provide for us. And so, we call the Or on T1 and T2, and this is what I'll get. I'll get out is equal to this, and this is going to be A,B plus B,C. And again, if we stare at this for a while, we can see, oh yeah, this makes sense. You know, the ways to get a 1 are A and B is 1, or B and C is 1, and everything else gives you a 0. So, how do you do something really complicated? What if I gave you 50,000 logic gates? I could, I could actually do that now. If I gave you a BDD scripting package, which I'm actually going to do. And if I gave you a whole bunch of logic gates, you could interrogate the graph that represents the logic network. You could even determine an appropriate order for building these BDDs representing each of the internal nodes in an appropriate order. And you could build them up one by one by just making simple calls to And, Or Not, Nand, Nor, Xor, Xnor and so forth. Until you had BDDs for every single one of your gate level outputs even for a very complicated network. And the only decision that you have to make is what are you going to do with the variable ordering? Now, you also get some other wonderful capabilities from any real well-implemented BDD package. And that's for comparing things. So, one of the most important engineering application for something like a BDD package is asking, are these two Boolean functions, F and G, the same? Very often, because they are representing different pieces of logic that are supposed to be the same, and you actually want to know it they're actually really the same. And so, the way you do that is you build the BDD for F and you build the BDD for G, and then you just compare the pointers. And let's remember that reduced order BDDs are canonical. If F and G are in fact the same Boolean function, they are the same graph. But because we are building shared, emphasize that, shared BDDs, not only are they the same graph, they're the exact same graph. The pointers point to the same place. So, you know, the way this is going to work is you build the BDD for F. Okay, there it is. And then, you build the BDD for G, and what you get is a pointer to exactly the same thing. You don't get another copy of it. This is very important. You don't get another copy of it. You don't get another version of it that happens to have the same nodes in the same places. You get the same graph, okay? And so, if you build BDD for F and you build the BDD for G, and if they are the same function, then the pointers are the same. Literally, this turns something that sounds extraordinarily complex, are these two 50,000 gate logic networks the same, into you know, two integer address comparisons on the F pointer and the G pointer, are they both pointing to the same node in computer memory that represents the top variable? That's a pretty amazing kind of a powerful result. So, are two Boolean functions the same? You build F, you build G, if the pointers are the same, they are. But what if they are not the same? Well then, we've got another interesting thing we can do. After we get over our you know, our unhappiness that perhaps F and G are not the same, the question we might want to ask is can you find me an input that makes them different? And, you know, the way you would think about doing that is that here's F and it's got, you know, a bunch of inputs. And here's G and, you know, it's got the same inputs, call it, call it x. What I would do is I would build myself an exclusive Or gate for that output. So, I would build a new function, let's call it H, right? And that new function H makes a 1 only when F disagrees with G. It makes a 1 only if F makes a different output than G for the same input, okay? So, I'm going to build the BDD for F. There it is. I'm going to build the BDD for g. There it is. I'm going to assume they share something because they're supposed to be the same function, right? Then, I'm going to build the BDD for H, right? I don't really know how to draw that, but let's just assume that it's something really big and complicated, and sort of subsumes them both. And then, I'm going to ask if H is satisfiable, which means I'm going to ask if there's a path from the top of H to the one node. And if that's the case, every such path that goes from the top of H to the 1 node specifies the values of variables that makes H equal to 1. Those are the values that make F and G as pieces of hardware, have different outputs, a 0,1, or a 1, 0. Those are inputs that make F disagree with G. You know, maybe you can use those things to figure out why F is not equal to G. When you think F is supposed to be equal to G, or perhaps F is not suppose to be equal to G. And you just want to know what makes them different. Here's the way you do it. And again, you build F, you build G, you, you know, invoke the operation of built into the BDD package of exclusive Or-ing two Boolean functions. And wham, you've actually got the result again. So very, very powerful things, BDDs. You can do some, you know, amazing, amazing you know, operational stuff in an engineering kind of a context, more useful BDD applications. Well, you can do tautology checking. We already kind of, kind of mentioned this. I spent a whole lecture showing you how to do Unate Recursive Paradigm cube list tautology because it was a really nice warm up. But you'd never actually do that. Well, mostly you're not going to do that. Because probably, you just build a BDD. Because look, with a BDD, it's trivial. If a function is equal to one, then that is the only way it can happen because we are canonical. There's only one representation. And we are shared. If we have multiple functions that all are supposed to be the same truth table, they all point to the same node. So, if that's just supposed to be a 1, it just points to the 1 node. So, wow, that's a heck of a lot less work. What about satisfiability? And it gets satisfiability's when, when you solve a Boolean equation. You say, what value makes it equal to one? Well, I have no idea how to do that with cubelist. But here, you know, as long as you can find a path from the root to the leaf with the one node, you can do it. So, one way to satisfy this function, for example, X1 is a 1, X2, I don't care about what the value is. X3, I don't care what the value is. X4 is 1. So, for this little BDD, you know, it just works. And similarly, that's another pattern that'll do it. So, X1 is a 0, X2 is 1, X3 we don't care about, and X4 is 1, that'll also do it. So, as long as you build the BDD, so basically you can go backwards from the one node, you can have pointers going both ways this is all very easy to do. So, this is just another I'm just going to write this here. This is just another operator implemented in your BDD package. You can ask the question, is it satisfiable? And you can ask for some values that satisfy. So all of this seems just too good to be true. So, at this point, if you're thinking sort of hard, you ought to be a little suspicious. And one of the, the reasons you ought to be a little suspicious is that, boy, it looks like I can take just about any profoundly theoretically exponentially difficult, you know, computer science problem. And if I can, you know, build a BDD, you know, like, wow. It looks like I can solve it. How come we all still have jobs? You know, how come there are any problems left to solve? And there's a problem. There's a, actually, a really big problem. And the problem is that the variable ordering that you used to build the BDD matters. And what does it mean that it matters? And the answer is that, if you can find a good ordering, you could build the BDD in a reasonable amount of space. So, here's a BDD for a, a very simple function. A1 and a1 plus a2 and b2 plus a3 and b3. So, I'm going to say that n equals 3 here because you can make this thing you know n as big as you like. The BDD on the left has a good ordering. That ordering is a1, b1, a2, b2, a3, b3. It's this nice tight little linear chain. It shows linear growth, which N, which is to say that it's size looks to be sort of ordering as N, you know, kind of some constant times N, right? But the ordering on the right, in which you do all of the a's first and then you do all of the b's makes an exponentially sized BDD. Which is to say that the size of this BDD is ordered 2 to the N, and that is a very unhappy circumstance. And so, the problem, you know, which makes this really, just very interesting is that there are lots of problems that have very efficient solutions. If, and I'm emphasizing this, if you can build the BDD. And the problem is, you can't always build the BDD. So I'm just sort of writing this down here you know, it's a really interesting problem. Some problems that are known to be exponentially hard are very easy on a BDD so that's, that's pretty amazing. The problem is that you can't solve every instance of those problems. The trouble is they're easy only if the size of the BDD for the problem is reasonable. Some problems make nice small BDDs, others make pathological large BDDs. And there's no universal solution. I'm just going to emphasize that. There's no universal solution, or we could always solve exponentially hard problems easily and we'd all be out of a job. How do people handle this thing? Well, there are, there's a lot of work on variable ordering heuristics. How do you figure out an ordering to make a nice BDD for a reasonable problem. There a lot of work on that. There's characterization, you know, you should just know which problems never make nice BDDs, so just don't try. I'll give you some examples. Multipliers are one of those things. Adders are great, multipliers are terrible. There's also dynamic ordering techniques. A dynamic ordering technique lets the BDD software package pick the order by itself and adjust it dynamically as your script executes to try to you know, make the best ordering. That's actually pretty interesting. We don't have time to talk about that, but that's actually one of the things that people do in practice today. Let me give you a little bit of intuition about BDD ordering. Here's some rules of thumb. So, I'm showing the same function again, a1, b1 plus a2, b2 plus a3, b3. And so, here's the linearly ordered BDD, the linearly-sized BDD on the left and exponentially-sized one on the right. What's going on here? So, let's just read my rules of thumb. Related input should be near each other in the order. Groups of inputs that determine the function all by themselves should be one, close to each other, and two, near the top of the BDD. This is a, a heuristic, this is not you know, a perfect solution. But let's just observe on the left that, you know, the a1, ai bi pairs are all next to each other in the order. Because, you know, in this function that I'm showing over here ai and bi, right? Can together determine the value of the function. So, by having the ai, bi pairs close to each other every time you get an ai, bi pair, you know, you, you, you choose an ai, let's say an a2 value, and then you choose a b2 value. Well, you actually know whether you can, you know, make a1 if the a2 and the b2 are 0. And if not, you don't need to know anything more about the a and the b. You can sort of, you know, not show a bunch more of them in the order and you can just move on. You know, look at the one on the right hand side. This is honestly, basically, this is basically the worst order you can do. This is just terrible. And if you sort of stare at this for a while, you get this, this, this sort of interesting little house picture here. This one has all the a's first, and then all the b's. That's terrible. And the reason is that you need a ai, bi pair to be able to determine the value of the function. Which means that if you give me all the ai's first, I have to remember them all. And so, the first level of the diagram has an a1, and I can't tell you anything about the value of the function. So, the next level of the diagram has two a2's, and I have to remember them all. Because I can't tell you anything about the value of the function. And the thrid level of the BDD has four a3's because I can't tell you anything about the value of the function. If I had 40 a's and 40 b's, I would have 2 to the 40 things at this rank. Because I have no b's yet, I can't tell you the value of the function. And it's not until I introduce some b's into the BDD that I can actually make a decision and tell you the value of the function. So, groups of inputs that can determine the function by themselves need to be close to each other, not widely separated. Because if you make them widely separated, then the BDD just gets big. It just gets wide. It gets fat in the middle because you have to remember all the possible values of that BDD. And the way a BDD remembers all of its possible values is by having a lot of nodes and a lot of edges. And that makes everybody unhappy, right? So related input should be near each other. Groups of inputs that can determine the function by themselves should be close to each other. And as far as you can, you can shove them up toward the top of the BDD. Can't always do it, but that's the basic heuristics. It's worth knowing just like, you know, what works for BDDs and what doesn't work for BDDs. So arithmetic currents are really important, you know, people build data paths all the time. How are their BDDs? Circuits that have their based-on carry chains have linear-sized reduced order BDDs, so adders, subtractors, comparitors, you know, things that decide whether a is greater than b in priority encoders. Those, those have you know, at their heart, they have carry chains, those have linear-sized BDDs. And the rule is that you always alternate the variables in BBD order for carry chain circuits. So, if you're going to remember anything about ordering, remember this, right? A0, b0, a1, b1, a2, b2. There's usually an obvious order for, you know, kind of whatever the low order bid is whatever the one you can compute with the least work that goes first in the order. And always, always, always alternate. Never, never, never do all the a's and do all the b's. So, it would be wonderful if all arithmetic circuits were easy and they all made friendly BDDs, but that is unfortunately false. Addition, the best order is linear. That makes us happy. The worst order is exponential. So that's good, that's bad. Linear ordering, alternate the a's and b's. Exponential ordering, don't. Multiplication, oh, that's very unfortunate. Multiply two things together. It's always an exponential BBD. It's just really bad. Turns out you need a different data structure, and they actually exist. They're other kinds of decision diagrams that have other kinds of canonical forms to represent things like multipliers. We don't have time to talk about them, but they actually exist. So, the general experience with binary decision diagrams is that many tasks have reasonable ordered BDD-sized, reduced-order BDD sizes. The algorithms are practical to like, you know, 100 million nodes which is a, you know a really big amount of memory. And, you know, people spend a lot of effort finding orderings that work. That's the only downside for BDDs. So here we are. We're at the end of our, our, our lecture on, you know, the first really practical and important data structure for us, Reduced, Ordered, Binary Decision Diagrams, ROBDDs, or what everybody just calls them BDDs these days. They're a canonical form. They're a data structure for Boolean functions. Two Boolean functions are the same if and only if they have an identical BDD. A Boolean function is just a pointer to the root node of the BDD graph. Every node in a shared BDD represents some function, and we can use that sharing very intelligently. Within a shared BDD, you can test if a function F is equal to a function G just by checking their pointers for equality. Do the actually point to the root node? That's really cool. The basis for much of today's general manipulation of, of Boolean stuff. Bdds are very, very, very widely used in, in the CAD industry, and actually in a lot of other applications. The problem is that variable ordering matters, and, and it matters a lot. It can be the difference between needing, you know, a 1 million nodes of BDD and, you know, 2 to the 100 nodes of BDD, and sometimes the BDD is just too big and you just can't build it. Which leads us to whole other class of representations and algorithms. Because, you know, it's surprising. But sometimes, you just want to know something that's called SAT. Sometimes you just want to build the Boolean function and ask what appears to be a simpler question, is there a way to satisfy this Boolean function and make it a 1? If so, can you please give me a value of the variable that does that? And if it's not possible to satisfy this Boolean function, please prove it for me. And just return that information. No, I cannot satisfy this Boolean function. It's quite surprising how many practical things can be cast in that different form, which will lead us to our next series of lectures about representation schemes and solvers for Boolean satisfiability.