Reed–Muller expansion

In Boolean logic, a Reed–Muller (or Davio) expansion is a decomposition of a boolean function.

For a boolean function $f(x_{1},\ldots ,x_{n})$ we set with respect to $x_{i}$:

${\displaystyle {\begin{aligned}f_{x_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\\[3pt]f_{{\overline {x}}_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})\\[3pt]{\frac {\partial f}{\partial x_{i}}}&=f_{x_{i}}(x)\oplus f_{{\overline {x}}_{i}}(x)\,\\\end{aligned}}}$

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:

${\displaystyle f=f_{{\overline {x}}_{i}}\oplus x_{i}{\frac {\partial f}{\partial x_{i}}}.}$

Similar to binary decision diagrams (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