Difference between revisions of "Binary decision diagram"
From ScienceZero
(5 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | # | + | # Decide order of variables |
# Create truth table | # Create truth table | ||
# Create tree from 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 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 - 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 | + | # 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 | # Repeat steps 4 5 6 until no more improvements can be made | ||
− | We now have a canonical reduced ordered binary decision diagram. All nodes represents different functions that all are canonical. | + | We now have a canonical reduced ordered binary decision diagram. All nodes now represents different functions that all are canonical. |
− | + | ||
− | + | ||
+ | '''Problem:''' This procedure becomes impossible with many variables. | ||
'''Solution:''' Build the reduced tree directly from the boolean expression. | '''Solution:''' Build the reduced tree directly from the boolean expression. | ||
'''How:''' To be determined... | '''How:''' To be determined... | ||
+ | # Recursively walk the circuit gate by gate from the input to the output and perform each operation on the BDD tree. |
Latest revision as of 10:43, 8 May 2014
- Decide 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. All nodes now represents different functions that all are canonical.
Problem: This procedure becomes impossible with many variables.
Solution: Build the reduced tree directly from the boolean expression.
How: To be determined...
- Recursively walk the circuit gate by gate from the input to the output and perform each operation on the BDD tree.