Reed-Muller code

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

Contents

1 Construction

2 Example

3 Properties

3.1 Proof

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 {d \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

There are

$\sum_{s=0}^d { d \choose 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$ .

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.

Omitted.

By induction.

The RM(d,0) code is the repetition code of length n=2^d and weight n = 2^{d-0^{= 2^d-0}}. By 1 RM(d,d) = $\mathbb{F}_2^n$ and has weight 1 = 2^{0^{= 2^d-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

min{2 w (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)^{= 2^d-r}}

then the bar product has weight

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

Reed-Muller code

Construction

Example

Properties

Proof

See also: Reed-Muller code, Bar product (coding theory), Error-correcting code, Hamming weight, Linear code