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 ] ...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
  1. Decider order of variables
  2. Create truth table
  3. Create tree from truth table
  4. Merge equivalent leaves -> We want two leaves, [ 1 ] and [ 0 ]
                               Redirect all edges from the removed nodes to the equivalent leave
  1. 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 
  1. Eliminate Redundant Tests -> Remove all nodes that has the same child twice
                               Redirect all edges into redundant node into the child node
  1. Repeat steps 4 5 6 until no more improvements can be made

We now have a canonical Reduced Ordered Binary Decision Diagram