boolean-logicboolean-operationsbooleanquerybinary-decision-diagram

Wha's the meaning and significance of 'path' in BDDs or FDDs?


I read a paper, named Multilevel logic synthesis based on functional decision diagrams, which is about Functional Decision Diagrams(FDDs), that is a variant of Binary Decision Diagrams(BDDs). In this, a paragraph mentions 'path':

As an important result it is observed, that even with nearly the same number of nodes we get a reduction of the number of paths compared to BDD (see tab. 1). Since the number of paths equals the number of pi-terms of the canonical two-level RME, this means a reduction of the complexity in the function representation.

tab. 1

I guess 'path' means the number of roads from root to terminal in BDDs or FDDs.

For example:

An graphical depiction of a FDD

The path of this example is 9(you can check this).

My question is what's the significance of this parameter or feature 'path'?


Solution

  • Yes, path is any single way from the root to a leaf. Roughly, the set of paths in a decision diagram can be seen as the minimum set of variables values that entirely describes the function.

    For example, you can draw a decision diagram leaving ALL the variables and ALL the paths. You can see that some of them are redundant (maybe from a node both links go to the same node). In this case we are wasting memory.

    The whole goal of decision diagrams is to represent a boolean function in the most compact and most efficient (operations wise) way possible. The authors are happy because they found a more compact way, don't know about efficiency.