Reed-Muller expansion

In logic synthesis Reed-Muller (or Davio) expansion is a decomposition of a boolean function.

For a boolean function $f(x\_1,...,x\_n)$ we set with respect to $x\_i$:

:

as the positive and negative cofactors of $f$, and the boolean derivation of $f$.

Then we have for the Reed-Muller or positive Davio expansion:

:$f\; =\; f\_\{overline\{x\_i\; oplus\; x\_i\; frac\{partial\; f\}\{partial\; x\_i\}.$

Similar to the BDDs, where nodes represent Shannon expansion with respect to the according variable, we can define a
decision diagram based on the Reed-Muller expansion. These decision diagrams are called functional BDDs (FBDDs).

References

*Kebschull, U. and Rosenstiel, W., "Efficient graph-based computation and manipulation of functional decision diagrams", Proceedings 4th European Conference on Design Automation, 1993, pp. 278-282

ee also

* Binary decision diagram