Introduction to ReedSolomon Codes

ReedSolomon 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 ReedSolomon Codes
The basic building block of ReedSolomon 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 ReedSolomon codes composed of mbit symbols is 2^{m}  1. For example,
for 8bit symbols, the length of the ReedSolomon codes is 2^{8}  1 = 255.
A complete ReedSolomon code consists of two parts: the data part and the parity part.
For a ReedSolomon code of n symbols, the first k symbols is the data part,
which is the information to be protected against corruption, and the following
(nk) symbols is the parity part, which is calculated based on the data part. Such a
ReedSolomon code is referred to as an (n, k) ReedSolomon code, or RS(n,k) code.
The number of parity symbols is (nk), usually an even number represented as 2t.
A ReedSolomon code with 2t parity symbols has the capability of correcting up to t
error symbols.
When the length of a ReedSolomon 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 ReedSolomon
code. For example, for an 8bit ReedSolomon 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 ReedSolomon Codes
A ReedSolomon code is defined by its generator polynomial. For a t error correcting
ReedSolomon code, its generator polynomial is
g(X) = (X + a^{m0})(X + a^{m0+1})(X + a^{m0+2})
(X + a^{m0+2t1})
= g_{0} + g_{1}X + g_{2}X^{2} +
+ g_{2t1}X^{2t1} + X^{2t},
where a, an mbit binary symbol, is the primitive element of the finite field GF(2^{m}), and
m_{0} is a preset number, usually 0 or 1. To encode a message sequence, the message polynomial
is first constructed as
u(X) = u_{0} + u_{1}X + u_{2}X^{2} +
+ u_{k1}X^{k1},
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_{0} + v_{1}X + v_{2}X^{2} +
+ v_{2t1}X^{2t1}.
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 ReedSolomon code encoder.
3. Decoding of ReedSolomon Codes
Assume the transmitted code vector is
t(X) = t_{0} + t_{1}X + t_{2}X^{2} +
+ t_{n1}X^{n1},
and the received vector is
r(X) = r_{0} + r_{1}X + r_{2}X^{2} +
+ r_{n1}X^{n1}.
The first step in decoding a ReedSolomon code is to calculate the 2t syndrome components as:
S_{0} = r(a^{0}) = r_{0} + r_{1} + r_{2} +
+ r_{n1}
S_{1} = r(a^{1}) = r_{0} + r_{1}(a) + r_{2}(a)^{2}+
+ r_{n1}(a)^{n1}
S_{2} = r(a^{2}) = r_{0} + r_{1}(a^{2}) + r_{2}(a^{2})^{2} +
+ r_{n1}(a^{2})^{n1}
.
.
.
S_{2t1} = r(a^{2t1}) = r_{0} + r_{1}(a^{2t1}) + r_{2}(a^{2t1})^{2} +
+ r_{n1}(a^{2t1})^{n1}.
The syndrome polynomial is
S(X) = S_{0} + S_{1}X + S_{2}X^{2} +
+ S_{2t1}X^{2t1}.
The block diagram to calculate a syndrome element is shown in Figure 2.
The second step in decoding a ReedSolomon 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_{1}X + L_{2}X^{2} +
+ L_{e}X^{e},
and the error evaluation polynomial is
W(X) = W_{0} + W_{1}X + W_{2}X^{2} +
+ W_{e1}X^{e1},
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 BerlekampMacey algorithm is used to solve for L(X) and W(X).
The last step in decoding a ReedSolomon code is to find the error location and the error value.
The error location is obtained using Chans searching algorithm. Basically X is substituted with
a^{n} 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 Forneys error evaluation algorithm.
Once the error value is found, it is added to the corrupted symbol to correct the error.
4. Applications of ReedSolomon Codes
ReedSolomon codes are widely used in digital communication systems and digital information storage systems.
Digital communication systems that use ReedSolomon 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 ReedSolomon 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 ReedSolomon codes start to find its use in dynamic memory protection
applications.
5.ReedSolomon Codes Products
Through extensive research Highland Communications Technologies has developed a series
of ReedSolomon codes for different applications. Our implementation is characterized by
high throughput, compact size and low latency. We also custom design ReedSolomon 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. 300304.
[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. 4457.
[3] Shu Lin, Daniel J. Costello, Jr., "Error Control Coding: Fundamentals and Applications",
PrinticeHall, Eaglewood, NJ, 1983.
[4] Wicker, S. B. and Bhargava, V. K., "ReedSolomon 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. SAC5, no. 2, February 1987, pp. 215225.
[6] Blahut, R. E., "Theory and Practice of Error Control Codes", AddisonWesley, Reading, MA, 1983.
