Reed–Solomon error correction

Reed -Solomon codes (short RS ) codes are a class of cyclic block codes and can be used in the context of channel coding for detecting and correcting transmission or storage errors as part of a forward error correction. They form a special subclass of the general class of BCH codes. RS codes are MDS codes, which they apply in the context of coding theory as the optimal codes.

Reed -Solomon codes were developed in 1960 by Irving S. Reed and Gustave Solomon at MIT Lincoln Laboratory, a research institute of the Ministry of Defense of the United States. At the time of the practical use of these codes has been limited because there is no efficient method for the decoding has been known. An efficient decoding algorithm was presented in 1969 by Elwyn Berlekamp and James Massey, in the form of usable also for BCH codes Berlekamp -Massey algorithm.

First applications of RS codes was the Voyager program of NASA in 1977. First commercial application found RS codes in 1982 as part of the error correction of compact disk Today's applications extend over a large area, such as the DVB standard for transmission of digital television signals in different cellular standards, the Digital Audio Broadcasting ( DAB), and in file formats such as PAR2 for data storage. Other application examples are two-dimensional bar codes; so, for example, put the QR Code, Data Matrix, Aztec Code and PDF417 Reed -Solomon error correction for a read error. In more recent applications RS codes are increasingly efficient codes such as low-density parity check codes ( LDPC ) or turbo codes replaced (TPC), such as is the case for example in the television DVB-S2 standard, which LDPC for forward error correction begins.

Motivation

It is a message of numbers (for example, a piece of text in ASCII encoding ) transmitted without error. On the transmission it can to eradicate or distortion of some of the numbers come ( in the first case, we know that an error occurred, not in the second ). In order to add redundancy to the message, the numbers of the message are interpreted as values ​​of a polynomial at agreed fixed reference points. A polynomial of degree or less can be represented as a sum of monomials. The coefficients of these monomials arise as a solution of a linear system of equations. Due to the special form of this system there is a solution formula, the Lagrange interpolation. The polynomial so obtained is then extrapolated to other nodes, so that the encoded message is a total of numbers.

Remain are now extinguished in the transfer a few numbers so that still receive more than the numbers, so the polynomial can again be reconstructed by interpolation from the correct transmitted numbers, and hence the original message by evaluating in the first grid points. In case of a faulty transmission errors at only a few points can be safely reconstructed with a slightly more complicated approach is still the original message.

The terms appearing in the interpolation containing divisions must therefore be carried out on a body. If the numbers - or symbols - selected the message from the integers, so the calculations are therefore held in the rational numbers. In addition, the extrapolated values ​​can be very large, which may in this transmission channel can not be delivered. To overcome these disadvantages, one introduces the bills through in a finite field. This has a finite number of elements that can be numbered in order to link them with the symbols of the message. The Division - except by zero - is fully feasible, and therefore the interpolation.

Reed-Solomon codes are capable of correcting burst errors in data transmission. Bits appear with burst errors erroneous ( " tilted " ) often referred to as a contiguous string of errors in the data stream. For example, can not be read properly by a scratch on a CD with each turn many consecutive bits.

Definition

Let be a finite field with elements ( is then necessarily a prime power, prim ). There are now pairwise distinct elements chosen and fixed.

The set of codewords of a Reed -Solomon codes of length for messages of length is now given by the tuple of all polynomials with degree less than the selected reference points:

Support sets of places

RS codes to acceptable reference points quantities are linearly isomorphic. The bijective linear mapping that gives the isomorphism results, by Lagrange interpolation with respect to the first grid points and amount of evaluation in the second sampling points amount. This codewords as polynomials of degree less be converted in the first step, so that the second step again results in a codeword.

Is an element of order, or greater, may for example be

Be selected. Each finite field contains a generator of the multiplicative group or primitive element, that is an element of order. Therefore, this particular choice is possible forever.

Are the support points exactly the powers of a member of the order, so the RS code is a cyclic code. Because the codeword polynomial is given by the rotation of the codeword to places to the left. Because of the simpler implementability cyclic codes, this variant is generally preferred.

Encoding of messages

You can leave a message directly transformed into a codeword by the components as coefficients of a polynomial

Using and evaluating this at the support points. This therefore results in a codeword

Length.

This gives a systematic coding, in which the message is contained in the first component in the " plain text ", by a preliminary transformation of the message. The code word for the leading polynomial is obtained here as interpolation of the pairs

According to the formula of the Lagrange interpolation so

Because of results from the codeword

Both versions use the same set of codewords and thus have the same error-correction properties.

Properties

By the definition immediately, the following properties:

  • Codeword length:
  • Dimension of the code:
  • Code rate:

The minimum distance is and thus meets the Singleton bound. Codes with this property are called MDS codes.

675882
de