Reed-Solomon Codes
PrintOverview
National Instruments has partnered with Prentice Hall to bring you large portions of in-depth technical topics from several PTR RF and Communications books, including Digital Communications: Fundamentals and Applications, 2nd Edition. This series of content is designed for a broad range of audiences, from experts who want to review a specific topic to students who need easy-to-understand documentation for their projects.
For the complete list of RF topics, please visit the RF and Communications Resource Main Page.
Table of Contents
8.1 REED–SOLOMON CODES
Reed–Solomon (R–S) 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
where k 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,
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 (R–S) 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
Reed–Solomon codes the code minimum distance is given by [1]
The code is capable of correcting any combination of t or fewer errors, where t
obtained from Equation (6.44), can be expressed as
where 
means the largest integer not to exceed x. Equation (8.4) illustrates that
for the case of R–S codes, correcting t symbol errors requires no more than 2t
parity symbols. Equation (8.4) lends itself to the following intuitive 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
Simultaneous error-correction and erasure-correction capability can be
expressed by the requirement that
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 contains 2n = 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 comprises 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 redundancy.
Thus, the most attractive R–S codes have high code rates (low redundancy).
Relevant NI products
Customers interested in this topic were also interested in the following NI products:
For the complete list of tutorials, return to the NI RF and Communications Fundamentals Main page.
Buy the Book
Purchase Digital Communications from Prentice Hall Professional through this link and receive the following:
- Between 15% and 30% Off
- Free Shipping and Handling
Reader Comments | Submit a comment »
Legal
Excerpt from the book published by Prentice Hall Professional (http://www.phptr.com).
Copyright Prentice Hall Inc., A Pearson Education Company, Upper Saddle River, New Jersey 07458.
This material is protected under the copyright laws of the U.S. and other countries and any uses not in conformity with the copyright laws are prohibited, including but not limited to reproduction, DOWNLOADING, duplication, adaptation and transmission or broadcast by any media, devices or processes.