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
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 +
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 +
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 +
and the received vector is
r(X) = r0 + r1X + r2X2 +
The first step in decoding a Reed-Solomon code is to calculate the 2t syndrome components as:
S0 = r(a0) = r0 + r1 + r2 +
S1 = r(a1) = r0 + r1(a) + r2(a)2+
S2 = r(a2) = r0 + r1(a2) + r2(a2)2 +
S2t-1 = r(a2t-1) = r0 + r1(a2t-1) + r2(a2t-1)2 +
The syndrome polynomial is
S(X) = S0 + S1X + S2X2 +
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 +
and the error evaluation polynomial is
W(X) = W0 + W1X + W2X2 +
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 Chans 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 Forneys 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
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
page for mode information.
 Reed, I. S. and Solomon, G., "Polynomial Codes Over Certain Finite Fields," SIAM Journal of
Applied Math., vol. 8, 1960, pp. 300-304.
 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.
 Shu Lin, Daniel J. Costello, Jr., "Error Control Coding: Fundamentals and Applications",
Printice-Hall, Eaglewood, NJ, 1983.
 Wicker, S. B. and Bhargava, V. K., "Reed-Solomon Codes and Their Applications", IEEE Press,
Piscataway, NJ, 1983.
 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.
 Blahut, R. E., "Theory and Practice of Error Control Codes", Addison-Wesley, Reading, MA, 1983.