Reed–Muller code

Reed-Muller codes are a family of linear error-correcting codes used in communications. They are named after their discoverers, Irving S. Reed and D. E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the first time. A first order Reed-Muller code is equivalent to a Hadamard code. Reed-Muller codes are listed as RM(d,r), where d is the order of the code, and r is parameterrelated to the length of code, $n=2^r$. RM codes are related to binary functions on field $GF(2^r)$ over the elements [0,1] .

RM(0,r) codes are repetition codes of length $n=2^r$, rate $\{R=\; frac\{1\}\{n$ and minimum distance $d\_\{min\}\; =\; frac\{n\}\{2\}$.

RM(1,r) codes are parity check codes of length $n=2^r$, rate $R=\; frac\{r+1\}\{n\}$ and minimum distance $d\_\{min\}\; =\; frac\{n\}\{2\}$.

RM(r-1,r) codes are parity check codes of length $n=2^r$.

RM(r-2,r) codes are the family of extended Hamming codes of length $n\; =\; 2^r$ with minimum distance $d\_\{min\}=4$. [Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.]

Construction

A generating matrix for a Reed–Muller code of length "n" = 2^"d" can be constructed like this. Let us write:

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

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

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

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

:

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

:$w\; wedge\; z\; =\; (w\_1\; imes\; z\_1,\; ldots\; ,\; w\_n\; imes\; z\_n\; ),$

referred to as the "wedge product".

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

$(mathbb\{F\}\_2)^d\; =\; \{\; (y\_d,\; ldots\; ,\; y\_1)\; |\; y\_i\; in\; mathbb\{F\}\_2\; \}$
We define in "n"-dimensional space $mathbb\{F\}\_2^n$ the following vectors with length "n": "v"₀ = (1, 1, 1, 1, 1, 1, 1, 1) and

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

where the "H"_"i" are hyperplanes in $(mathbb\{F\}\_2)^d$ (with dimension d −1):

:$H\_i\; =\; \{\; y\; in\; (\; mathbb\{F\}\_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\{F\}\_2^3\; =\; \{\; (0,0,0),\; (0,0,1),\; ldots,\; (1,1,1)\; \},$

and

:

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

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

or more explicitly by the rows of the matrix

:

Example 2

The RM(3,2) 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:

:

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\{F\}\_2^n$.

2 The RM ("d", "r") code has rank::$sum\_\{s=0\}^r\; \{d\; choose\; s\}.$

3 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\; \{\; 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, d) = $mathbb\{F\}\_2^n$.

:Let "x" be an element of "X" and define

::

: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, d) = $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 = 2^d-0". By 1 RM(d, d) = $mathbb\{F\}\_2^n$ and has weight "1 = 2⁰ = 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\; \{\; 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) = 2^d-r

:then the bar product has weight

::$min\; \{\; 2\; imes\; d^\{d-1-r\},\; 2^\{d-r\}\; \}\; =\; 2^\{d-r\}\; .$

Decoding RM codes

RM(r,m) codes can be decoded using the majority logic decoding. The basic idea of majority logic decoding isto build several checksums for each received code word element. Since each of the different checksums must all have the same value (i.e the value of the message word element weight), we can use a majority logic decoding to decipherthe value of the message word element. Once each order of the polynomial is decoded, the received word is modifiedaccordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage.So for a $r$-th order RM code, we have to decode iteratively r+1, times before we arrive at the finalreceived code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculatethe codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of r+1-stage decodingthrough the majority logic decoding. This technique was proposed by Irving. S. Reed, and is more general when appliedto other finite geometry codes.

See also

* Reed-Solomon code

References

* Chapter 4.
* Chapter 4.5.