Reed–Muller expansion - Alchetron, The Free Social Encyclopedia

In Boolean logic, a 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 :

f x i ( x ) = f ( x 1 , … , x i − 1 , 1 , x i + 1 , … , x n ) f x ¯ i ( x ) = f ( x 1 , … , x i − 1 , 0 , x i + 1 , … , x n ) ∂ f ∂ x i = f x i ( x ) ⊕ f x ¯ i ( x )

as the positive and negative cofactors of f , and the boolean derivation of f , where ⊕ denotes the XOR operator.

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

f = f x ¯ i ⊕ x i ∂ f ∂ x i .

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

f = f x i ⊕ x ¯ i ∂ f ∂ x i .

Repeated application of the Reed–Muller expansion results in an XOR polynomial in x 1 , … , x n :

f = a 1 ⊕ a 2 x 1 ⊕ a 3 x 2 ⊕ a 4 x 1 x 2 ⊕ … ⊕ a 2 n x 1 ⋯ 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 x ¯ 1 x ¯ 2 ⊕ ∂ f x ¯ 2 ∂ x 1 x 1 ⊕ ∂ f x ¯ 1 ∂ x 2 x 2 ⊕ ∂ 2 f ∂ x 1 ∂ x 2 x 1 x 2

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

Derivation

The Reed–Muller expansion can be derived from the XOR-form of the Shannon decomposition, using the identity x ¯ = 1 ⊕ x :

f = x i f x i ⊕ x ¯ i f x ¯ i = x i f x i ⊕ ( 1 ⊕ x i ) f x ¯ i = x i f x i ⊕ f x ¯ i ⊕ x i f x ¯ i = f x ¯ i ⊕ x i ∂ f ∂ x i

References

Reed–Muller expansion Wikipedia

(Text) CC BY-SA