Reed–Muller code

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=\mathbb {F} _{2}^{d}=\{x_{1},\ldots ,x_{2^{d}}\}$

We define the indicator vectors:

$\mathbb {I} _{A}\in \mathbb {F} _{2}^{n}$

on subsets $A\subset X$ by:

$\left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}$

together with the binary operation:

$x\wedge y=(x_{1}\times y_{1},\ldots ,x_{n}\times y_{n})$

referred to as the wedge product.

Let

$v_{i}=\mathbb {I} _{H_{i}}$

where the H_i are the co-ordinate hyperplanes (of dimension 2^d-1):

$H_{i}=\{y\in \mathbb {F} _{2}^{n}\mid y_{i}=0\}$

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 upto r of the $v_{i}$ (where by convention a wedge product of fewer than one vector is the identity for the operation).

Example

Let d=3. Then n=8, and

$X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),\ldots ,(1,1,1)\}.$

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

$\{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}$

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}}$

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

${\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 upto d of the v_i form a basis for $\mathbb {F} _{2}^{n}$.

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

$\sum _{s=0}^{r}{\binom {(}{d}},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

$\sum _{s=0}^{d}{\binom {(}{d}},s)=2^{d}=n$

such vectors and $\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) = $\mathbb {F} _{2}^{n}$.

Let x_i be an element of X and define

$y_{i}={\begin{cases}v_{i}&{\mbox{ if }}x_{i}=0\\1+v_{i}{\mbox{ if }}x_{i}=1\\\end{cases}}$

Then $\mathbb {I} _{\{x\}}=y_{i}\wedge \ldots \wedge y_{d}$

Expansion via the distributivity of the wedge product gives $\mathbb {I} _{\{x\}}\in {\mbox{ RM(d,d)}}$. Then since the vectors $\{\mathbb {I} _{\{x\}}\mid x\in X\}$ span $\mathbb {F} _{2}^{n}$ we have RM(d,r) = $\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) = $\mathbb {F} _{2}^{n}$ and has weight 1 = 2^{0 = 2d-d}.

It can be shown that the weigth of the bar product of two codes C₁ , C₂ is given by

$\min\{2w(C_{1}),w(C_{2})\}$

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

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