Introduction to Reed-Solomon Codes

Reed-Solomon codes is a linear systematic block code based on finite field theory. The systematic format, the efficient encoding and decoding algorithm, and the powerful error correction capability of the code make it one of the most widely used error correction codes in the industry.

1. Format of Reed-Solomon Codes

The basic building block of Reed-Solomon codes is a symbol composed of m binary bits, where m can be any natural number greater than 2. For a given m, the length of all the Reed-Solomon codes composed of m-bit symbols is 2^m - 1. For example, for 8-bit symbols, the length of the Reed-Solomon codes is 2⁸ - 1 = 255.

A complete Reed-Solomon code consists of two parts: the data part and the parity part. For a Reed-Solomon code of n symbols, the first k symbols is the data part, which is the information to be protected against corruption, and the following (n-k) symbols is the parity part, which is calculated based on the data part. Such a Reed-Solomon code is referred to as an (n, k) Reed-Solomon code, or RS(n,k) code. The number of parity symbols is (n-k), usually an even number represented as 2t. A Reed-Solomon code with 2t parity symbols has the capability of correcting up to t error symbols.

When the length of a Reed-Solomon code needs to be less than 2^m - 1, zero padding is used to make the length of the code 2^m - 1. After encoding, the padded zeros is removed to form a so called shortened Reed-Solomon code. For example, for an 8-bit Reed-Solomon code, we have 100 data bytes to be protected against up to 8 errors. Then, we will need 16 parity bytes. The total length of the code will be 116 bytes, which is less than 255. To calculate the 16 parity bytes, we need to pad 139 zeros to the data bytes and then encode the 239 total bytes. After encoding, the padded zeros will be removed and only the original data bytes and the calculated parity bytes will be transmitted or stored. When decoding the code, the removed padding zeros will be added to the code first and then do the decoding.

2. Encoding of Reed-Solomon Codes

A Reed-Solomon code is defined by its generator polynomial. For a t error correcting Reed-Solomon code, its generator polynomial is

g(X) = (X + a^m₀)(X + a^m₀+1)(X + a^m₀+2)…(X + a^m₀+2t-1) = g₀ + g₁X + g₂X² + … + g_2t-1X^2t-1 + X^2t,

where a, an m-bit binary symbol, is the primitive element of the finite field GF(2^m), and m₀ is a pre-set number, usually 0 or 1. To encode a message sequence, the message polynomial is first constructed as

u(X) = u₀ + u₁X + u₂X² + … + u_k-1X^k-1,

where k = n – 2t. The parity polynomial is calculated as the remainder of X^2t.a(X)/g(X), which is represented as

v(X) = v₀ + v₁X + v₂X² + … + v_2t-1X^2t-1.

The parity sequence is the coefficients of the parity polynomial. The code is constructed as the data sequence followed by the parity sequence. The final code polynomial is

t(X) = X^2t u(X) + v(X).

Figure 1 shows the block diagram of the Reed-Solomon code encoder.



3. Decoding of Reed-Solomon Codes

Assume the transmitted code vector is

t(X) = t₀ + t₁X + t₂X² + … + t_n-1X^n-1,

and the received vector is

r(X) = r₀ + r₁X + r₂X² + … + r_n-1X^n-1.

The first step in decoding a Reed-Solomon code is to calculate the 2t syndrome components as:

S₀ = r(a⁰) = r₀ + r₁ + r₂ + … + r_n-1

S₁ = r(a¹) = r₀ + r₁(a) + r₂(a)²+ … + r_n-1(a)^n-1

S₂ = r(a²) = r₀ + r₁(a²) + r₂(a²)² + … + r_n-1(a²)^n-1

.

.

.

S_2t-1 = r(a^2t-1) = r₀ + r₁(a^2t-1) + r₂(a^2t-1)² + … + r_n-1(a^2t-1)^n-1.

The syndrome polynomial is

S(X) = S₀ + S₁X + S₂X² + … + S_2t-1X^2t-1.

The block diagram to calculate a syndrome element is shown in Figure 2.



The second step in decoding a Reed-Solomon code is to find the error location polynomial L(X) and the error evaluation polynomial W(X). The error location polynomial is

L(X) = 1 + L₁X + L₂X² + … + L_eX^e,

and the error evaluation polynomial is

W(X) = W₀ + W₁X + W₂X² + … + W_e-1X^e-1,

where e is the number of errors. The error location polynomial and the error evaluation polynomial are related to the syndrome polynomial through the key equation

L(X)S(X) = W(X) mod X^2t.

The popular iterative Berlekamp-Macey algorithm is used to solve for L(X) and W(X).

The last step in decoding a Reed-Solomon code is to find the error location and the error value. The error location is obtained using Chan’s searching algorithm. Basically X is substituted with aⁿ in L(X) for all possible n in a code to find the root of L(X). The inverse of the root of the error location polynomial is the error position. After an error location is found, the error value is calculated via Forney’s error evaluation algorithm. Once the error value is found, it is added to the corrupted symbol to correct the error.

4. Applications of Reed-Solomon Codes

Reed-Solomon codes are widely used in digital communication systems and digital information storage systems. Digital communication systems that use Reed-Solomon codes for error protection include wireless communication systems, broad band communication systems, digital video broadcasting systems, and space and deep space communication systems. Digital information storage systems that use Reed-Solomon codes for error protection include compact disc (CD) storage systems, digital versatile disc (DVD) storage systems, and hard disc storage systems. One recent development is that Reed-Solomon codes start to find its use in dynamic memory protection applications.

5.Reed-Solomon Codes Products