Difference between revisions of "Binary decision diagram"
From ScienceZero
(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 ] ...") |
|||
| Line 2: | Line 2: | ||
# Create truth table | # Create truth table | ||
# Create tree from truth table | # Create tree from truth table | ||
| − | # Merge equivalent leaves | + | # 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 | |
| − | # Merge isomorphic nodes | + | # Eliminate Redundant Tests - Remove all nodes that has the same child twice. Redirect all edges into redundant node into the child node |
| − | + | ||
| − | # Eliminate Redundant Tests | + | |
| − | + | ||
# Repeat steps 4 5 6 until no more improvements can be made | # Repeat steps 4 5 6 until no more improvements can be made | ||
We now have a canonical Reduced Ordered Binary Decision Diagram | We now have a canonical Reduced Ordered Binary Decision Diagram | ||
Revision as of 16:34, 6 May 2014
- 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
