Chapter 7Alternate Decoding Algorithms for Reed–Solomon Codes
7.1 Introduction: Workload for Reed–Solomon Decoding
In this chapter, we present two alternatives to the decoding algorithms presented in Chapter 6. The first is based upon a new key equation and is called remainder decoding. The second method is a list decoder capable of decoding beyond the design distance of the code.
A primary motivation behind the remainder decoder is that implementations of it may have lower decode complexity. The decode complexity for a conventional decoding algorithm for an 
code having redundancy 
is summarized by the following steps:
- Compute the syndromes.
syndromes must be computed, each with a computational cost of 
, for a total cost of 
. Furthermore, all syndromes must be computed, regardless of the number of errors. - Find the error‐locator polynomial and the error evaluator. This has a computation cost (depending on the approach).
- Find the roots of the error‐locator polynomial. This has a computation ...
Get Error Correction Coding, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
