And by that I mean they're low pointers which point to their zero children, both
go to a y node and their high pointers. Which go, when the value is set to a 1,
both go to the z node. And they don't go to any old y, random y
node or z node, they both go to the same. X y node and this same z node.
The exact same nodes. And so what happens up here is that I
don't need both of them. I can get rid of one of them.
And so I can simply replace it with one, any one, It doesn't matter.
And I can keep the children. Right?
As I'm just drawing here, right. So there's an x node.
Its low child goes to y, and its high child goes to z, and then y and z are
unaffected, but there are two pointers that go into, in this case, go into the x
nodes. One of them goes into the left x node, and
one of them goes into the right x node. And what now happen is that you simply
redirect them both. To go into the x node.
So whatever was happening above the x node in this BDD, right?
And that traversed some edge with a variable decision to get to x.
Those pointers, they just point to the single copy of x.
And there's a little gray box over at the side here.
That just, just gives the recipe. You remove the redundant node, which in
this case is the extra x node. You redirect all the edges that went into
the redundant node into the one copy that you kept.
So in this case the edges into the right x node are not going into the left x node as
well. That is an example of merging isomorphic
nodes to reduce the complexity of the BDD. So let us apply Rule 2 to our example.
And if we stare at it for a little while, the big thing that we have to look for is,
what are some nodes that have the same variable label.
And identical children. So, you know, there's just no other node
then x1, so it can't be x1. And if we look at the x2's, they don't
have identical children. But if we stare at the x3's for a little
while. What we will discover is that those folks,
the right most x3's, those are all isomorphic.
They all have 0 as the low child, and 1 as the high child.
And so I only need one of them. I don't need all of them.
So I can redraw this BDD. It's got an x1.
Okay, at the top. And then it's got at the next rank, it's
got two x2 nodes, right? And the low child goes to the left x2
node. And the high child goes to the right x2
node. And then on the right side, there is a
single x3 child, right? And there is the high child of x2 and the
low child of x2 both go to that single x3 node.
I'm going to put little stars by them because those are new edges.
On the left hand side, the x2 node also goes, its low child goes to the x3 node.
And down at the bottom, I have a single 0 constant and a single 1 constant.
The x3 child on the left, both of its children low and high, go to the 0 node.
The x3 node on the right, the low child goes to the 0 node, but the high child
goes to the 1 node. And the x2 node on the left, write that,
high child goes to x3. I'm going to put a little star by that,
all right? So, those are all of the things that I
redid, right? As a consequence of killing two of the
three x3 nodes. And replacing them with a single x3 node.
And one of the things you can immediately see is there's less to this graph.
There's just less of it, it's a lot less complicated, that's a good thing.
You know simpler's gotta be better. But wait, there's more, there's another
rule that we can use to eliminate redundant, nodes.
And this is the rule called, eliminate redundant test, and this is another one of
the ones that feels kind of simple, when you look at it.
A test in this case means a variable node, right?
So this is If x equals 1 what do I do? If x equals 0 what do I do?
Redundant tests are the circumstance where a variable has both of its children going
to the same node. And that's just dumb, right?
I don't need, in the diagram above, I don't need to know what x is.
If x is 0, I go ask the y node what to do. If x is 1, I go ask the y node what to do.
That's not necessary. Right?
And so I can kill the x node. I can keep the y node.
Right? And again when I look at the, the in this
case, the edges that were going into the x node, however, many them there are.
I simply redirect them to go into the y node.
Instead, I bypass the x node. The x node goes away.
I do not care what value it takes. It does not affect the output of my
function and so I get rid of it. And so, again, there is a little gray box
at the upper right that gives you a little formula, says, remove the redundant node,
redirect all the edges into the redundant node which was x in this case, into the
child, y in this case, of the removed node.
So that's the, that's the recipe but it, it simplifies things.
So, if we go back to our evolving BDD and we apply rule three, what I have drawn on
the left was the same example. That I did by hand a couple of slides ago.
X1 is the top rank node it has low children and high child x2 respectively.
Right? The next rank are two x3's, right?
The x2 on the left has a low child that goes to x3.
The high child is the right x3. The x2 on the right, both of the children,
go to the right x3. The x3 on the left, both of them, go to 0.
And the x3 on the right, low goes to 0, high goes to 1.
We can immediately look at this and we can see that the x3 on the left is redundant
because both of its children go to the 0 node.
And the x2 on the right is redundant because both if its children go to the x3
node. And so, I can kill both of them.
I can just kill them both and I can redirect the edges.
I'm going to put little stars by them. I can redirect the edges that go into
those nodes that I kill. I can simply send them to their children.
Right? And so in the right-hand diagram, I'm
going to put a little star by each of these edges that were redirected.
And we have a vastly simpler BDD. There's a x1 node at the top, and there's
a single x2 node at the second rank. X1's low child is this x2 node.
There's a single x3 node at the third rank.
X1's high child is that x3 node. X2's child is that x3 node.
And then there are constants at the bottom.
X2's low child is the 0. X3's low child is the 0.
X3's high child is the 1. Wow, this is way less BDD than I started
with. This is way less graph than I started
this. This is way fewer nodes and way fewer
edges. Now, if you might ask.
How does one apply these rules? And for now I'm just going to say
iteratively. When you can't find another graph match,
the graph is reduced. Is, is this how programs really do it?
No. Absolutely not.
Not only no, no with two exclamation points.
Look, if I give you a function with a hundred variables, the way I just showed
you, you have to build the decision diagram with 2 to the 100 you know, nodes
at the bottom. And then you have to apply this reduction
stuff, that's crazy. There's no way you could do that.
There's actually a much smarter set of ways, and we'll do a very high level
overview of what those ways are. But for now, and for some homework
problems and sort of getting kind of intellectually on top of this stuff.
If I give you a function with three or four variables and I ask you to do the BDD
its perfectly okay for you to do this by hand.
You'll get the right answer and you'll get some insight in to how this stuff works.
Now, the big thing going on here is that we started with a decision diagram and it
was really big. And we ordered the variables and we said,
let's see if that makes the graph that we get canonical.
If we always get the same graph, and the answer was no because there could be
redundancies. Even if you always visit all the variables
in the same order from the root to the leaf, as you do decisions, you can still
get a different graph. So then we reduce the diagram by all of
these merging operations. And we got a new thing.
We got a thing called a Reduced Ordered BDD.
And the result of that is a really, really cool result.
And the really cool result is that a Reduced Ordered BDD is a canonical form.
Right? So I'm just going to say data structure.
For any Boolean function. I'm even going to stop it with an
exclamation point. Our reduced order BDD is a canonical form.
The same function always generates exactly the same graph, exactly the same nodes,
with exactly the same edges, with exactly the same children.
If you give me the same variable ordering. Two Boolean functions are identical if and
only if their Reduced Ordered BDD graphs are isomorphic which is a fancy way of
saying they are the same. Now, you might think, wow, how hard is
that to check? And the answer is going to be, amazingly
trivial. It's a wonderful result.
And this is a really beautiful property to have.
