Reed–Muller code

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

Practice

The binary Reed -Muller code was developed by NASA in the Mariner expeditions ( 1969-1976 ) used to Mars, to send the pictures taken from Mars to Earth. In particular, 9 is an RM code (1, 5) without any control matrix as Hadamard code (32, 6, 16 ) at Sea used, which means that six information bits into 32 bits were long words coded and the minimum weight of the words of at least 16 was what allowed a correction of 7 bits. With the codewords gray values ​​of an image point were coded. More in Example 3 below for NASA space probe Mariner 9

Construction

The following procedure describes how to construct a generator matrix of a Reed -Muller codes of length n = 2d.

We define the n-dimensional space, the indicator vectors:

On subsets by:

And - also - the binary operation:

Which is referred to as a wedge - product.

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

We define the n-dimensional space, the following vectors of length n: and

Where Hi hyperplanes in (with dimension d -1):

Reed -Muller RM ( D, R ) code of order r and the length n = 2 d is the one code, which is generated by V0 and the wedge - product up to the R ( in which following agreement of a key - less product as a vector of the identity for this operator is the same).

Properties

Apply the following properties

Example 1

Let d = 3 Then, N = 8, and

And

RM (3,1 ) code is produced by the amount

Or more precisely by the rows of the matrix

Example 2

RM (3,2 ) code is produced by the amount

Or more precisely by the rows of the matrix

Example 3: NASA space probe Mariner 9

The NASA space probe Mariner 9 in 1971 a Reed -Muller code ( 1, 5) was used with the lack of check matrix, which is a special case of generalized Reed -Muller codes. This code was finally a Hadamard code with parameters (32, 6, 16). With this code RM (32, 6, 16) were transferred 32-bit code words, the values ​​encoded, the code words with each other had a Hamming distance of 16. These parameters were chosen based on the channel characteristics, the image resolution and the recording and transmission times, which made a word length of 30 bits plenty of sense.

Due to the large distance between Mars and Earth, and then compared to today unprogressive transmission equipment, the assumed bit error probability was 5 %. This is due to the encoding of a gray value in 6 bits without additional error correction mechanisms within a monochrome error probability of 26%. That is, about a quarter of a transferred image are in error at the receiver. By the use of the RM code (32, 6, 16) was 5%, the greyscale error probability can be reduced to 0.01 % with the same bit error probability.

Construction

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

Constructing is performed recursively from the Hadamard matrix

And the production rule

This design by Sylvester generates the so-called Walsh matrices

Represent the normalized Hadamard matrices of degree.

If now the Hadamard matrix interpreted as a bit pattern ( where a 1 to the binary number 1, and is the binary number 0), then we obtain 32 code words with 32 bit length. Each of the code words has for every other code word to a Hamming distance of 16 or 32. By combining the Hadamard matrix by the inverse Hadamard matrix to obtain 64 code words of 32 bits in length, where each codeword to every other code word having a Hamming distance of 16. This combination of and defines a Hadamard code that can encode values ​​by corresponding to a value n of the n -th row of the code. The figure shows the complete Hadamard code for RMC (32, 6, 16 ), with the color black for the binary digit 1 and the color white for the binary digit 0.

Alternative characterization

A picture is uniquely determined by its images if their order is known. Therefore, one can also represent by the associated image vector, where the arguments are the -adic development of elements from the domain of definition. On one can define a component-wise addition and multiplication according to the arithmetic operations. Strictly speaking, there is a ring isomorphism between the set of mappings and the set of image vectors, so you can identify a picture with his image vector. In are special images that S. G. Coordinate functions. These are defined as follows:

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

Now, the following applies:

Decoding

The idea is as follows: Each code word of the Reed-Muller code RM ( r, m ) can be considered as a function of, according to the above alternative characterization - with basis representation in opposite coordinate functions, ie with uniquely determined coefficients with the amount of coordinate functions - indexes. The function is passed as an image vector through the noisy channel. The receiver decodes the afflicted with error code word by successively reconstructs the coefficients. He begins with the coefficients belonging to the highest degree monomial. To this end, it calculates the dot product of the sg characteristic functions of the monomial. These are all illustrations of degrees, the coordinates generating functions can also occur in opposite directions. The value that is calculated by the scalar products mainly, the original Monomkoeffizient. The process is repeated with the monomials of degree and is finally obtained this way - if the error is not too large.

Summary

Encoding and decoding process by means of Reed -Muller codes at a glance: