Reed–Muller Expansion

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

For a Boolean function $f(x_1,\ldots,x_n) : \mathbb^n \to \mathbb$ we call

:$\begin f_(x) & = f(x_1,\ldots,x_,1,x_,\ldots,x_n) \\ f_(x)& = f(x_1,\ldots,x_,0,x_,\ldots,x_n) \end$

the positive and negative cofactors of $f$ with respect to $x_i$, and
:$\begin \frac & = f_(x) \oplus f_(x) \end$
the boolean derivation of $f$ with respect to $x_i$, where $$ denotes the XOR operator.

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

:$f = f_ \oplus x_i \frac.$

Description

This equation is written in a way that it resembles a Taylor expansion of $f$ about $x_i=0$. There is a similar decomposition corresponding to an expansion about $x_i=1$ (negative Davio expansion):

:$f = f_ \oplus \overline_i \frac.$

Repeated application of the Reed–Muller expansion results in an XOR polynomial in $x_1,\ldots,x_n$:

:$f = a_1 \oplus a_2 x_1 \oplus a_3 x_2 \oplus a_4 x_1 x_2 \oplus \ldots \oplus a_ x_1\cdots x_n$

This representation is unique and sometimes also called Reed–Muller expansion.

E.g. for $n=2$ the result would be

:$f(x_1, x_2) = f_ \oplus \frac x_1 \oplus \frac x_2 \oplus \frac x_1 x_2$

where

:$= f_ \oplus f_ \oplus f_ \oplus f_$.

For $n = 3$ the result would be

:$f(x_1, x_2, x_3) = f_ \oplus x_1 \oplus x_2 \oplus x_3 \oplus x_1 x_2 \oplus x_1 x_3 \oplus x_2 x_3 \oplus x_1 x_2 x_3$

where

:$= f_ \oplus f_ \oplus f_ \oplus f_ \oplus f_ \oplus f_ \oplus f_ \oplus f_$.

Geometric interpretation

This $n = 3$ case can be given a cubical geometric interpretation (or a graph-theoretic interpretation) as follows: when moving along the edge from $\bar x_1 \bar x_2 \bar x_3$ to $x_1 \bar x_2 \bar x_3$, XOR up the functions of the two end-vertices of the edge in order to obtain the coefficient of $x_1$. To move from $\bar x_1 \bar x_2 \bar x_3$ to $x_1 x_2 \bar x_3$ there are two shortest paths: one is a two-edge path passing through $x_1 \bar x_2 \bar x_3$ and the other one a two-edge path passing through $\bar x_1 x_2 \bar x_3$. These two paths encompass four vertices of a square, and XORing up the functions of these four vertices yields the coefficient of $x_1 x_2$. Finally, to move from $\bar x_1 \bar x_2 \bar x_3$ to $x_1 x_2 x_3$ there are six shortest paths which are three-edge paths, and these six paths encompass all the vertices of the cube, therefore the coefficient of $x_1 x_2 x_3$ can be obtained by XORing up the functions of all eight of the vertices. (The other, unmentioned coefficients can be obtained by symmetry.)

Paths

The shortest paths all involve monotonic changes to the values of the variables, whereas non-shortest paths all involve non-monotonic changes of such variables; or, to put it another way, the shortest paths all have lengths equal to the Hamming distance between the starting and destination vertices. This means that it should be easy to generalize an algorithm for obtaining coefficients from a truth table by XORing up values of the function from appropriate rows of a truth table, even for hyperdimensional cases ($n = 4$ and above). Between the starting and destination rows of a truth table, some variables have their values remaining fixed: find all the rows of the truth table such that those variables likewise remain fixed at those given values, then XOR up their functions and the result should be the coefficient for the monomial corresponding to the destination row. (In such monomial, include any variable whose value is 1 (at that row) and exclude any variable whose value is 0 (at that row), instead of including the negation of the variable whose value is 0, as in the minterm style.)

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

Derivations

The Reed–Muller expansion can be derived from the XOR-form of the Shannon decomposition, using the identity $\overline = 1 \oplus x$:

:$\begin f & = x_i f_ \oplus \overline_i f_ \\ & = x_i f_ \oplus (1 \oplus x_i) f_ \\ & = x_i f_ \oplus f_ \oplus x_i f_ \\ & = f_ \oplus x_i \frac. \end$

Derivation of the expansion for $n = 2$:

:$\begin f & = f_ \oplus x_1 \\ & = \Big( f_ \oplus x_2 \Big)_ \oplus x_1 \\ & = f_ \oplus x_2 \oplus x_1 \Big( \oplus x_2 \Big) \\ & = f_ \oplus x_2 \oplus x_1 \oplus x_1 x_2 . \end$

Derivation of the second-order boolean derivative:

:$\begin & = \Big( \Big) = (f_ \oplus f_) \\ & = (f_ \oplus f_)_ \oplus (f_ \oplus f_)_ \\ & = f_ \oplus f_ \oplus f_ \oplus f_. \end$

See also

* Algebraic normal form (ANF)
* Ring sum normal form (RSNF)
* Zhegalkin polynomial
* Karnaugh map
* Irving Stoy Reed
* David Eugene Muller
* Reed–Muller code

References

Further reading

*
*
*
*
*
*
* (188 pages)

{{DEFAULTSORT:Reed-Muller expansion
Boolean algebra