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 2m - 1. For example, for 8-bit symbols, the length of the Reed-Solomon codes is 28 - 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 2m - 1, zero padding is used to make the length of the code 2m - 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 + am0)(X + am0+1)(X + am0+2)(X + am0+2t-1) = g0 + g1X + g2X2 +  + g2t-1X2t-1 + X2t,

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

u(X) = u0 + u1X + u2X2 +  + uk-1Xk-1,

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

v(X) = v0 + v1X + v2X2 +  + v2t-1X2t-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) = X2t 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) = t0 + t1X + t2X2 +  + tn-1Xn-1,

r(X) = r0 + r1X + r2X2 +  + rn-1Xn-1.

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

S0 = r(a0) = r0 + r1 + r2 +  + rn-1

S1 = r(a1) = r0 + r1(a) + r2(a)2+  + rn-1(a)n-1

S2 = r(a2) = r0 + r1(a2) + r2(a2)2 +  + rn-1(a2)n-1

.

.

.

S2t-1 = r(a2t-1) = r0 + r1(a2t-1) + r2(a2t-1)2 +  + rn-1(a2t-1)n-1.

The syndrome polynomial is

S(X) = S0 + S1X + S2X2 +  + S2t-1X2t-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 + L1X + L2X2 +  + LeXe,

and the error evaluation polynomial is

W(X) = W0 + W1X + W2X2 +  + We-1Xe-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 X2t.

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 an 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

Through extensive research Highland Communications Technologies has developed a series of Reed-Solomon codes for different applications. Our implementation is characterized by high throughput, compact size and low latency. We also custom design Reed-Solomon codes based on your specification. Please go to our Products page for mode information.

6.References

[1] Reed, I. S. and Solomon, G., "Polynomial Codes Over Certain Finite Fields," SIAM Journal of Applied Math., vol. 8, 1960, pp. 300-304.
[2] Berlekamp, E. R., Peile, R. E., and Pope, S. P.,"The Application of Error Control to Communications," IEEE Communications Magazine, vol. 25, no. 4, April 1987, pp. 44-57.
[3] Shu Lin, Daniel J. Costello, Jr., "Error Control Coding: Fundamentals and Applications", Printice-Hall, Eaglewood, NJ, 1983.
[4] Wicker, S. B. and Bhargava, V. K., "Reed-Solomon Codes and Their Applications", IEEE Press, Piscataway, NJ, 1983.
[5] Hagenauer, J., and Lutz, E., "Forward Error Correction Coding for Fading Compensation in Mobile Satellite Channels," IEEE JSAC, vol. SAC-5, no. 2, February 1987, pp. 215-225.
[6] Blahut, R. E., "Theory and Practice of Error Control Codes", Addison-Wesley, Reading, MA, 1983.