Reed-Muller Code

The Reed-Muller codes are a family of linear , error-correcting codes that are used in the field of channel coding for secure data transmission and data storage. This class of codes was developed by Irving S. Reed and David E. Muller.

practice

The binary Reed-Muller code was used by NASA in the Mariner expeditions (1969 to 1976) to Mars to send the photos taken of Mars to Earth . In particular, Mariner 9 used an RM code (1, 5) without a control matrix as Hadamard code (32, 6, 16), which means that six information bits were encoded in 32-bit long words and the minimum weight of the words was at least 16 which allowed 7 bits of error correction . The gray values ​​of a pixel were coded with the code words. More on this in Example 3 below for NASA's Mariner 9 spacecraft. ${\displaystyle 2^{6}=64}$

construction

The following describes how a generator matrix of a Reed-Muller codes of length constructed ${\displaystyle n=2^{d}}$

${\displaystyle X=\mathbb {F} _{2}^{d}=\{x_{1},\ldots ,x_{2^{d}}\}}$.

${\displaystyle \mathbb {F} _{n}}$is a subset of the nonnegative integers

${\displaystyle \mathbb {F} _{n}=\{a\in \mathbb {N} _{0}\;|\;a<n\}}$.

We define the indicator vectors in n-dimensional space : ${\displaystyle \mathbb {F} _{2}^{n}}$

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

on subsets by: ${\displaystyle A\subset X}$

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

and - also in - the binary operation: ${\displaystyle \mathbb {F} _{2}^{n}}$

${\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}$

which is referred to as a wedge product .

${\displaystyle \mathbb {F} _{2}^{d}}$is a -dimensional vector space over , so it is possible to write: ${\displaystyle d}$ ${\displaystyle \mathbb {F} _{2}}$

${\displaystyle (\mathbb {F} _{2})^{d}=\{(y_{1},\ldots ,y_{d})\;|\;y_{i}\in \mathbb {F} _{2}\}}$

We define the following vectors of length in -dimensional space ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle n}$

${\displaystyle v_{0}=(1,1,\ldots ,1)}$ and

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

where hyperplanes are in (with dimension ): ${\displaystyle H_{i}}$ ${\displaystyle (\mathbb {F} _{2})^{d}}$ ${\displaystyle d-1}$

${\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{d}\mid y_{i}=0\}}$

The Reed-Muller RM (d, r) code of order and length is the code generated by and the wedge product of up to the (where by agreement a wedge product of less than one vector equals the identity for this operator is). ${\displaystyle r}$ ${\displaystyle n=2^{d}}$ ${\displaystyle v_{0}}$ ${\displaystyle r}$ ${\displaystyle v_{i}}$

properties

The following properties apply

1. The set of all possible wedge products of up to d of forming a base of . ${\displaystyle v_{i}}$ ${\displaystyle \mathbb {F} _{2}^{n}}$
2. The RM (d, r) code has the rank: ${\displaystyle \sum _{s=0}^{r}{d \choose s}}$
3. It applies , where the bar product denotes two codes ${\displaystyle RM(d,r)=RM(d-1,r)|RM(d-1,r-1)}$ ${\displaystyle |}$
4. RM (d, r) has the minimum Hamming distance . ${\displaystyle 2^{d-r}}$

example 1

Be . Then , and ${\displaystyle d=3}$ ${\displaystyle n=8}$

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

and

${\displaystyle {\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

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

or more precisely through the rows of the matrix

${\displaystyle {\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 quantity

${\displaystyle \{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 precisely through the rows of the matrix

${\displaystyle {\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}}}$

Example 3: NASA's Mariner 9 spacecraft

The NASA Mariner 9 space probe from 1971 used a Reed-Muller code (1, 5) with a missing control matrix, which represents a special case of general Reed-Muller codes. This code was ultimately a Hadamard code with the parameters (32, 6, 16). With this RM code (32, 6, 16), 32-bit long code words were transmitted which encoded values, the code words having a Hamming distance of 16 between one another. These parameters were chosen based on the channel characteristics, the image resolution and the recording and transmission times, which made a word length of more than 30 bits sensible. ${\displaystyle 2^{6}=64}$

Due to the great distance between Mars and Earth, and the transmission devices that were not advanced at the time compared to today, the assumed bit error probability was 5%. The coding of a gray value in 6 bits without additional error correction mechanisms results in a gray value error probability of 26%. This means that about a quarter of a transmitted image arrives incorrectly at the recipient. By using the RM code (32, 6, 16) it was possible to reduce the gray value error probability to 0.01% with the same bit error probability of 5%.

construction

Matrix of the Hadamard code (32, 6, 16) for the Reed-Muller code (1.5) of the NASA space probe Mariner 9 (1971/1972). The color black encodes the binary digit 1, and the color white encodes the binary digit 0.

The RM code (32, 6, 16) used is based on a Hadamard matrix . ${\displaystyle H_{32}}$

The construction of takes place recursively from the Hadamard matrix ${\displaystyle H_{32}}$

${\displaystyle H_{1}={\begin{pmatrix}1\end{pmatrix}}}$

and the generation rule

${\displaystyle H_{2n}={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}}$

This Sylvester construction creates the so-called Walsh matrices

${\displaystyle H_{1}={\begin{pmatrix}1\end{pmatrix}},H_{2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}},H_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}},\ldots }$

which represent normalized Hadamard matrices of degree . ${\displaystyle 2^{k}}$

If you now interpret the Hadamard matrix as a bit pattern (in which a 1 stands for the binary digit 1 and one for the binary digit 0), you get 32 ​​code words with a length of 32 bits. Each of these code words has a Hamming distance of 16 or 32 to every other code word. By combining the Hadamard matrix with the inverse Hadamard matrix , 64 code words with a length of 32 bits are obtained, in which each code word has a Hamming distance of 16 to every other code word. This combination of and defines a Hadamard code with which values ​​can be coded , in which a value corresponds to the -th line of the code. The illustration opposite shows the complete Hadamard code for RMC (32, 6, 16), where the color black stands for the binary digit 1 and the color white for the binary digit 0. ${\displaystyle H_{32}}$ ${\displaystyle -1}$ ${\displaystyle H_{32}}$ ${\displaystyle -H_{32}}$ ${\displaystyle H_{32}}$ ${\displaystyle -H_{32}}$ ${\displaystyle 2^{6}=64}$ ${\displaystyle n}$ ${\displaystyle n}$

Alternative characterization

The class of Reed-Muller codes can also be identified with a set of images. Look at the amount

${\displaystyle V=\{f{\text{ Abbildung}}\mid f\colon \mathbb {F} _{2}^{m}\rightarrow \mathbb {F} _{2}\}}$.

An image is clearly defined by its images, provided that their order is known. Therefore one can also represent by the associated image vector , whereby the arguments are the -adic expansion of the elements from the domain of definition . On one can define a component-wise addition and multiplication according to the arithmetic operations in . Strictly speaking, there is a ring isomorphism between the amount of figures and the amount of image vectors , so you can identify a picture with his image vector: . In are special images, the so-called coordinate functions . ${\displaystyle f\in V}$ ${\displaystyle {2^{m}}}$ ${\displaystyle f}$ ${\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))\in \mathbb {F} _{2}^{2^{m}}}$ ${\displaystyle 0,1,\dots ,2^{m}-1}$ ${\displaystyle 2}$ ${\displaystyle \mathbb {F} _{2}^{m}}$ ${\displaystyle V}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle V}$ ${\displaystyle \mathbb {F} _{2}^{2^{m}}}$ ${\displaystyle f=(f(0),f(1),\dots ,f(2^{m}-1))}$ ${\displaystyle V}$ ${\displaystyle Z_{i},\;i\in \{1\dots 2^{m}\}}$

These are defined as follows:

${\displaystyle Z_{i}(v):=v_{i}}$for . ${\displaystyle v=(v_{1},\dots ,v_{m})\in \mathbb {F} _{2}^{m}}$

In the vector representation introduced above, the coordinate functions can also be written as

${\displaystyle Z_{i}=(\underbrace {0,\dots ,0} _{2^{i-1}{\text{-mal}}},\underbrace {1,\dots ,1} _{2^{i-1}{\text{-mal}}},\underbrace {0,\dots ,0} _{2^{i-1}{\text{-mal}}},\dots )\in \mathbb {F} _{2}^{2^{m}}}$.

Now applies:

1. The system of monomials ( ) is a basis of . ${\displaystyle Z_{i_{1}}\cdot \dots \cdot Z_{i_{k}}}$ ${\displaystyle 1\leq i_{1}<\dots <i_{k}\leq m,k=0,\dots ,m}$ ${\displaystyle V}$
2. The subset corresponds to the Reed-Muller code RM (r, m). Here is the highest degree of monomial of the coordinate functions, the sum of which can be written according to 1. ${\displaystyle \{f\colon \mathbb {F} _{2}^{m}\rightarrow \mathbb {F} _{2}{\text{ Abbildung}}\mid \operatorname {grad} (f)\leq r\}\subseteq V}$ ${\displaystyle \operatorname {grad} (f)}$ ${\displaystyle f}$

Decoding

The idea is as follows: Each codeword of the Reed-Muller code RM (r, m) can be interpreted as a function from according to the above alternative characterization - with a basic representation in opposite coordinate functions, i.e. H. with uniquely determined coefficients where is the set of coordinate function indices. The function is sent as an image vector through the disturbed channel. The receiver decodes the error- prone code word by successively reconstructing the coefficients . He begins with the coefficients belonging to the monomial of the highest order . To do this, he calculates the scalar product of with the so-called characteristic functions of the monomial. These are all images of the degree , whereby the generating coordinate functions can also occur in the opposite direction. The value that is mostly calculated by the scalar products is the original monomial coefficient. The procedure is repeated with the monomials of the degree and one finally obtains - provided the error is not too large. ${\displaystyle f}$ ${\displaystyle V}$ ${\displaystyle m_{I}{\text{ mit }}I\subseteq M}$ ${\displaystyle M=\{1,\dots ,m\}}$ ${\displaystyle f}$ ${\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))}$ ${\displaystyle e}$ ${\displaystyle g=f+e}$ ${\displaystyle m_{I}}$ ${\displaystyle r}$ ${\displaystyle g}$ ${\displaystyle m-r}$ ${\displaystyle r-1,r-2,\dots ,0}$ ${\displaystyle f}$ ${\displaystyle e}$

Summary

An overview of the coding and decoding process using Reed-Muller codes:

1. Message is translated into codeword . ${\displaystyle n}$ ${\displaystyle c}$
2. Code word can be identified with illustration . ${\displaystyle c}$ ${\displaystyle f}$
3. Figure can also be represented as an image vector . ${\displaystyle f}$ ${\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))}$
4. Instead of the monomial coefficients of, transmit the associated image vector. This provides redundancy that enables the desired error correction. ${\displaystyle f}$
5. Send the image vector through the disturbed channel. It results with the error vector . ${\displaystyle g=f+e}$ ${\displaystyle e}$
6. Receive the image vector and obtain the original monomial coefficients by scalar multiplications with the coordinate functions. ${\displaystyle g}$ ${\displaystyle Z_{i}}$
7. The monomial coefficients are used to calculate the original mapping / code word and thus . ${\displaystyle f=c}$ ${\displaystyle n}$

Web links

• Recursive codes with the Plotkin construction (PDF; 1.7 MB) Dissertation on the construction and decoding of Reed-Muller codes and their subcodes (attention: information about the RM code (32, 6, 16) of the Mariner 9 mission are not correct, since only one cardinality of the code of values ​​is specified and explained.) ${\displaystyle 2^{5}=32}$