The Reed-Muller codes are a family of linear error-correcting codes used in communications.

Construction

---

The following describes how to construct a generating matrix of a Reed-Muller code of length n = 2^d. Let us write:

$X\; =\; \backslash mathbb\{F\}\_2^d\; =\; \backslash \{\; x\_1,\; \backslash ldots,\; x\_\{2^d\}\; \backslash \}$

We define in n-dimensional space $\backslash mathbb\{F\}\_2^n$ the indicator vectors:

$\backslash mathbb\{I\}\_A\; \backslash in\; \backslash mathbb\{F\}\_2^n$

on subsets $A\; \backslash subset\; X$ by:

together with, also in $\backslash mathbb\{F\}\_2^n$, the binary operation:

$w\; \backslash wedge\; z\; =\; (w\_1\; \backslash times\; z\_1,\; \backslash ldots\; ,\; w\_n\; \backslash times\; z\_n\; )$

referred to as the wedge product.

$\backslash mathbb\{F\}\_2^d$ is a d-dimensional vector space over the field $\backslash mathbb\{F\}\_2$, so it is possible to write

$(\backslash mathbb\{F\}\_2)^d\; =\; \backslash \{\; (y\_1,\; \backslash ldots\; ,\; y\_d)\; |\; y\_i\; \backslash in\; \backslash mathbb\{F\}\_2\; \backslash \}$

We define in n-dimensional space $\backslash mathbb\{F\}\_2^n$ the following vectors with length n : $v\_0\; =\; (1,1,1,1,1,1,1,1)$ and

$v\_i\; =\; \backslash mathbb\{I\}\_\{\; H\_i\; \}$

where H_i are hyperplanes in $(\backslash mathbb\{F\}\_2)^d$ (with dimension 2^d-1):

$H\_i\; =\; \backslash \{\; y\; \backslash in\; (\; \backslash mathbb\{F\}\_2\; )\; ^d\; \backslash mid\; y\_i\; =\; 0\; \backslash \}$

The Reed-Muller RM(d, r) code of order r and length n=2^d is the code generated by v₀ and the wedge products of up to r of the $v\_i$ (where by convention a wedge product of fewer than one vector is the identity for the operation).

Example 1

---

Let d=3. Then n=8, and

$X\; =\; \backslash mathbb\{F\}\_2^3\; =\; \backslash \{\; (0,0,0),\; (0,0,1),\; \backslash ldots,\; (1,1,1)\; \backslash \}.$

and

$$

\begin{matrix} v_0 & = & (1,1,1,1,1,1,1,1) \\ v_1 & = & (1,0,1,0,1,0,1,0) \\ v_2 & = & (1,1,0,0,1,1,0,0) \\ v_3 & = & (1,1,1,1,0,0,0,0) \\ \end{matrix}

The RM(3,1) code is generated by the set

$\backslash \{\; v\_0,\; v\_1,\; v\_2,\; v\_3\; \backslash \}$

or more explicitly by the rows of the matrix:

$$

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{pmatrix}

Example 2

---

The RM(3,2) code is generated by the set:

$\backslash \{\; v\_0,\; v\_1,\; v\_2,\; v\_3,\; v\_1\; \backslash wedge\; v\_2,\; v\_1\; \backslash wedge\; v\_3,\; v\_2\; \backslash wedge\; v\_3\; \backslash \}$

or more explicitly by the rows of the matrix:

$$

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}

Properties

---

The following properties hold:

1 The set of all possible wedge products of up to d of the $v\_i$ form a basis for $\backslash mathbb\{F\}\_2^n$.

2 The RM(d, r) code has rank:

$\backslash sum\_\{s=0\}^r\; \{d\; \backslash choose\; s\}$

3 The RM(d, r) = RM(d-1,r) | RM(d-1,r-1) where '|' denotes the bar product of two codes.

4 RM(d, r) has minimum Hamming weight 2^d-r.

Proof

1

There are

$\backslash sum\_\{s=0\}^d\; \{\; d\; \backslash choose\; s\; \}\; =\; 2^d\; =\; n$

such vectors and $\backslash mathbb\{F\}\_2^n$ has dimension n so it is sufficient to check that the n vectors span; equivalently it is sufficient to check that RM(d, r) = $\backslash mathbb\{F\}\_2^n$.

Let x_i be an element of X and define

Then $\backslash mathbb\{I\}\_\{\; \backslash \{\; x\; \backslash \}\; \}\; =\; y\_i\; \backslash wedge\; \backslash ldots\; \backslash wedge\; y\_d$

Expansion via the distributivity of the wedge product gives $\backslash mathbb\{I\}\_\{\; \backslash \{\; x\; \backslash \}\; \}\; \backslash in\; \backslash mbox\{\; RM(d,d)\}$. Then since the vectors $\backslash \{\; \backslash mathbb\{I\}\_\{\; \backslash \{\; x\; \backslash \}\; \}\; \backslash mid\; x\; \backslash in\; X\; \backslash \}$ span $\backslash mathbb\{F\}\_2^n$ we have RM(d, r) = $\backslash mathbb\{F\}\_2^n$.

2

By 1, all such wedge products must be linearly independent, so the rank of RM(d, r) must simply be the number of such vectors.

3

Omitted.

4

By induction.

The RM(d,0) code is the repetition code of length n=2^d and weight n = 2^{d-0 = 2d-0}. By 1 RM(d, d) = $\backslash mathbb\{F\}\_2^n$ and has weight 1 = 2^{0 = 2d-d}.

The article bar product (coding theory) gives a proof that the weight of the bar product of two codes C₁ , C₂ is given by

$\backslash min\; \backslash \{\; 2w(C\_1),\; w(C\_2)\; \backslash \}$

If 0 < r < d and if

i) RM(d-1,r) has weight 2^d-1-r

ii) RM(d-1,r-1) has weight 2^{d-1-(r-1) = 2d-r}

then the bar product has weight

$\backslash min\; \backslash \{\; 2\; \backslash times\; d^\{d-1-r\},\; 2^\{d-r\}\; \backslash \}\; =\; 2^\{d-r\}\; .$

coding theory

Reed-Muller-Code | Code de Reed-Müller | Reed-Muller-code