# 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.

## construction

The following describes how a generator matrix of a Reed-Muller codes of length constructed

- .

is a subset of the nonnegative integers

- .

We define the indicator vectors in n-dimensional space :

on subsets by:

and - also in - the binary operation:

which is referred to as a *wedge product* .

is a -dimensional vector space over , so it is possible to write:

We define the following vectors of length in -dimensional space

and

- ,

where hyperplanes are in (with dimension ):

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).

## properties

The following properties apply

- The set of all possible wedge products of up to
*d*of forming a base of . - The RM (d, r) code has the rank:
- It applies , where the bar product denotes two codes
- RM (d, r) has the minimum Hamming distance .

## example 1

Be . Then , and

and

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

or more precisely through the rows of the matrix

## Example 2

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

or more precisely through the rows of the matrix

## 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.

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

The RM code (32, 6, 16) used is based on a Hadamard matrix .

The construction of takes place recursively from the Hadamard matrix

and the generation rule

This Sylvester construction creates the so-called Walsh matrices

which represent normalized Hadamard matrices of degree .

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.

## Alternative characterization

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

- .

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 .

These are defined as follows:

- for .

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

- .

Now applies:

- The system of monomials ( ) is a basis of .
- 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.

## 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.

## Summary

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

- Message is translated into codeword .
- Code word can be identified with illustration .
- Figure can also be represented as an image vector .
- Instead of the monomial coefficients of, transmit the associated image vector. This provides redundancy that enables the desired error correction.
- Send the image vector through the disturbed channel. It results with the error vector .
- Receive the image vector and obtain the original monomial coefficients by scalar multiplications with the coordinate functions.
- The monomial coefficients are used to calculate the original mapping / code word and thus .

## 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.)