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.