Binary decision diagram
From ScienceZero
Revision as of 16:33, 6 May 2014 by Bjoern (Talk | contribs) (Created page with "# Decider order of variables # Create truth table # Create tree from truth table # Merge equivalent leaves -> We want two leaves, [ 1 ] and [ 0 ] ...")
- Decider order of variables
- Create truth table
- Create tree from truth table
- Merge equivalent leaves -> We want two leaves, [ 1 ] and [ 0 ]
Redirect all edges from the removed nodes to the equivalent leave
- Merge isomorphic nodes -> Remove all nodes that have the same variable and identical children as another node
Redirect all edges that went into the redundant node into the one copy that you kept
- Eliminate Redundant Tests -> Remove all nodes that has the same child twice
Redirect all edges into redundant node into the child node
- Repeat steps 4 5 6 until no more improvements can be made
We now have a canonical Reduced Ordered Binary Decision Diagram