Locuras

Reed-Solomon Codes
by
Bernard Sklar
Introduction
In 1960, Irving Reed and Gus Solomon published a paper in the Journal of the
Society for Industrial and Applied Mathematics [1]. This paper described a new
class of error-correcting codes that are now called Reed-Solomon (R-S) codes.
These codes have great power and utility, and are today found in many
applications from compact disc playersto deep-space applications. This article is
an attempt to describe the paramount features of R-S codes and the fundamentals
of how they work.
Reed-Solomon codes are nonbinary cyclic codes with symbols made up of m-bit
sequences, where m is any positive integer having a value greater than 2. R-S (n, k)
codes on m-bit symbols exist for all n and k for which
0 < k < n < 2m + 2

(1)

wherek is the number of data symbols being encoded, and n is the total number of
code symbols in the encoded block. For the most conventional R-S (n, k) code,
(n, k) = (2m - 1, 2m - 1 - 2t)

(2)

where t is the symbol-error correcting capability of the code, and n - k = 2t is the
number of parity symbols. An extended R-S code can be made up with n = 2m or
n = 2m + 1, but not any further.Reed-Solomon codes achieve the largest possible code minimum distance for any
linear code with the same encoder input and output block lengths. For nonbinary
codes, the distance between two codewords is defined (analogous to Hamming
distance) as the number of symbols in which the sequences differ. For ReedSolomon codes, the code minimum distance is given by [2]
dmin = n - k + 1

(3)

The codeis capable of correcting any combination of t or fewer errors, where t can
be expressed as [3]


t =  d min
2


n - k 
=  2 




- 1

(4)

where  x  means the largest integer not to exceed x. Equation (4) illustrates that

for the case of R-S codes, correcting t symbol errors requires no more than 2t parity
symbols. Equation (4) lends itself to the followingintuitive reasoning. One can say
that the decoder has n - k redundant symbols to “spend,” which is twice the amount
of correctable errors. For each error, one redundant symbol is used to locate the error,
and another redundant symbol is used to find its correct value.
The erasure-correcting capability, ρ, of the code is
ρ = dmin - 1 = n - k

(5)

Simultaneous error-correction anderasure-correction capability can be expressed
as follows:
2α + γ < dmin < n - k

(6)

where α is the number of symbol-error patterns that can be corrected and γ is the
number of symbol erasure patterns that can be corrected. An advantage of
nonbinary codes such as a Reed-Solomon code can be seen by the following
comparison. Consider a binary (n, k) = (7, 3) code. The entire n-tuple space
contains2n = 27 = 128 n-tuples, of which 2k = 23 = 8 (or 1/16 of the n-tuples) are
codewords. Next, consider a nonbinary (n, k) = (7, 3) code where each symbol is
composed of m = 3 bits. The n-tuple space amounts to 2nm = 221 = 2,097,152
n-tuples, of which 2km = 29 = 512 (or 1/4096 of the n-tuples) are codewords. When
dealing with nonbinary symbols, each made up of m bits, only a small fraction(i.e.,
2km of the large number 2nm) of possible n-tuples are codewords. This fraction
decreases with increasing values of m. The important point here is that when a
small fraction of the n-tuple space is used for codewords, a large dmin can be
created.
Any linear code is capable of correcting n - k symbol erasure patterns if the n - k
erased symbols all happen to lie on the parity symbols.However, R-S codes have
the remarkable property that they are able to correct any set of n - k symbol
erasures within the block. R-S codes can be designed to have any redundancy.
However, the complexity of a high-speed implementation increases with
2

Reed-Solomon Codes

redundancy. Thus, the most attractive R-S codes have high code rates (low
redundancy).

Reed-Solomon Error Probability...