BDD

• Binary decision Graph

• Logical function is something that returns 0 or 1 for a combination of 0s and 1s.

• Logical functions can be represented by BDDs.

  • 
    • https://ja.wikipedia.org/wiki/二分決定図 source

• BDDs can represent AND, OR, XOR, etc.

  • The size of the BDD is proportional to the number of variables, n.
  • By replacing the final outputs of 0 and 1, NAND, NOR, etc. can also be represented.

• The size of the BDD varies greatly depending on the order of variables.

• BDDs can be reduced and compressed.

  • 
    • https://www-alg.ist.hokudai.ac.jp/~thomas/publications/sigfpai06imz.pdf source
    • The left side is a tree (BDT) that represents the logical function as it is, and it can be compressed into the middle figure (BDD).
    • The right side is a ZDD (mentioned later).

• ZDD (Zero-suppressed BDD)

  • A compression method slightly different from the usual BDD.
    • To be more precise, it compresses more than BDD.
  • In addition to the compression criteria of BDD, it also eliminates the variables themselves when they lead to the final output of 0 when the output is 1.
    • In other words, the definition of what is considered “redundant” is different from BDD.
    • The right Graph in the above figure.
  • Effective when only the case where the final output is 1 is of interest.
    • For example, purchasing data of a store.
  • It has a significant effect when dealing with sparse sets (where most arrival points are 0) as it can be represented compactly.

• In short,

  • BDD: Suitable for dense logical functions, omits Don’t cares.
  • ZDD: Suitable for sparse logical functions, omits negative occurrences.

• If you want to create a BDD (or ZDD) from a logical function,

  • It can be done by creating a BDT and then compressing it.
  • However, performing this compression every time can be computationally/memory intensive.
  • Therefore, it is desired to directly generate a compressed BDD from a logical formula.
  • How to do it:
    • Bottom-up approach: Each variable is treated as a small BDD, and two BDDs are combined using AND, NOT, OR operations to create the final BDD.
    • Top-down approach: The BDT is created, and compression is done while creating it (e.g., counting the number of times 1 is used).
      • Frontier method

• In the framework of Discrete Structure Processing technology, BDDs, ZDDs, and other Decision Graphs correspond to “index structures.”

  • The method of performing “basic operations” such as logical operations, counting, linear function maximization, and sampling.
    • Decompose using Shannon decomposition and recursively perform operations until reaching $f$ that always returns 1/0.
    • Shannon Decomposition: $f_a=(\neg x_i\wedge f_{a0})\vee (x_i\wedge f_{a1})$
      • In essence, it is a mathematical representation of a branching point in a binary tree.
      • The operations between $f_a$ and $f_{a\prime }$ can be recursively performed after decomposition.

• Applications

  • Initially developed for the design of integrated circuits.
  • Recently, with the improvement of processing power, very large BDDs can be handled.
    • Path finding
    • Finding patterns of popular products from supermarket sales data
    • Investigating combinations of dangerous elements from traffic accident data
  • ZDDs are also used to solve the Combination Explosion Sister problem.
    • It seems very exciting to compete for the world record up to n=26 (blu3mo). #Discrete Algorithms (Expert in Information Science)