Reed-Muller code

Encyclopedia : R : RE : REE : Reed-Muller code

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

Contents

1 Construction
2 Example 1
3 Example 2
4 Properties

4.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_2^d = \ \} ]

We define in n-dimensional space [\mathbb_2^n] the indicator vectors:

[\mathbb_A \in \mathbb_2^n]

on subsets [ A \subset X ] by:

[\left( \mathbb_A \right)_i = \begin 1 & \mbox x_i \in A \\ 0 & \mbox \\ \end ]

together with, also in [\mathbb_2^n], the binary operation:

[ w \wedge z = (w_1 \times z_1, \ldots , w_n \times z_n ) ]

referred to as the wedge product.

[\mathbb_2^d] is a d-dimensional vector space over the field [\mathbb_2], so it is possible to write

[(\mathbb_2)^d = \_2 \} ]

We define in n-dimensional space [\mathbb_2^n] the following vectors with length n : [v_0 = (1,1,1,1,1,1,1,1)] and

[ v_i = \mathbb_ ]

where H_i are hyperplanes in [(\mathbb_2)^d] (with dimension 2^d-1):

[H_i = \_2 ) ^d \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 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 = \mathbb_2^3 = \. ]

and

[\beginv_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]

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

[ \ ]

or more explicitly by the rows of the matrix:

[\begin1 & 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]

Example 2

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

[ \ ]

or more explicitly by the rows of the matrix:

[\begin1 & 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]

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 [\mathbb_2^n].

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

:[ \sum_^r ]

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_^d = 2^d = n ]

such vectors and [\mathbb_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_2^n].

Let x_i be an element of X and define

:[y_i = \begin v_i & \mbox x_i = 0 \\ 1+v_i & \mbox x_i = 1 \\ \end ]

Then [\mathbb_ } = y_i \wedge \ldots \wedge y_d ]

Expansion via the distributivity of the wedge product gives [ \mathbb_ } \in \mbox ]. Then since the vectors [\_ } \mid x \in X \} ] span [\mathbb_2^n] we have RM(d, r) = [\mathbb_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_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 \ ]

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^ \} = 2^ .]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.