Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm

Alexander Zeh, Wenhui Li2010 · DOI

TL;DR

This paper presents a novel decoding algorithm for Reed-Solomon (RS) codes that can correct errors beyond the traditional half-minimum distance bound, reaching up to the "Sudan radius." The core innovation lies in adapting the Feng-Tzeng Euclidean algorithm to a "virtually extended" interleaved RS code, which reformulates the decoding problem into a more manageable multi-sequence shift-register problem of equal length.

What Problem Does This Paper Address?

Reed-Solomon (RS) codes are fundamental in error correction, widely used in data storage and communication systems. A key limitation of standard RS decoding algorithms, like the Berlekamp-Massey (BM) or the Euclidean algorithm, is their inability to correct more than half of the minimum possible errors. This limit is known as the "error-correction radius." While Sudan's list-decoding algorithm offers a way to correct more errors, it is computationally complex. This paper aims to bridge this gap by developing a more efficient decoding method that can correct errors up to the Sudan radius, leveraging a modified Euclidean algorithm. The challenge is to adapt existing multi-sequence decoding techniques to handle the specific structure of RS codes and achieve this enhanced error-correction capability.

Methods

The paper's primary contribution is the adaptation of the Feng-Tzeng (FT) Euclidean algorithm for decoding Reed-Solomon (RS) codes up to the Sudan radius. This is achieved through a two-step process:

  1. Virtual Extension to an Interleaved RS Code (IRS): The original RS code is conceptually transformed into a "virtually extended" Interleaved Reed-Solomon (IRS) code. This virtual extension allows for a more robust error correction capability, effectively increasing the decoding radius. The paper defines this virtual extension and illustrates its concept with an example.
  2. Reformulation of the Multi-Sequence Problem: The decoding problem for this virtually extended IRS code is then reformulated. Instead of dealing with multi-sequence shift-register problems of varying lengths (which arise from the virtual extension), it's transformed into a multi-sequence problem of equal length. This reformulation is proven mathematically.

The paper also presents an alternative polynomial derivation of the "extended key equation," which is central to the multi-sequence problem. The complexity of the proposed decoding approach is analyzed.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, using mathematical constructs and examples rather than empirical datasets.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully demonstrates a method to decode RS codes beyond the traditional half-minimum distance, reaching the Sudan radius, using a modified Euclidean algorithm. This is significant because it offers a more powerful decoding capability without resorting to the potentially more complex Sudan's list-decoding algorithm.
  • Virtual Extension as a Key Enabler: The concept of "virtual extension" to an IRS code is crucial. It allows the problem to be framed in a way that naturally leads to a multi-sequence decoding problem, which can then be tackled with generalized Euclidean algorithms.
  • Simplifying the Multi-Sequence Problem: Transforming the varying-length multi-sequence problem into an equal-length one is a key simplification. This makes the problem more amenable to existing algorithms and analysis, as demonstrated by the proposed Algorithm 1 and Algorithm 2.
  • Alternative Derivation of the Key Equation: Providing a new polynomial derivation for the extended key equation offers a different perspective and potentially new avenues for understanding and optimizing the algorithm.

Key Results

  • The paper proposes a method to decode RS codes up to the Sudan radius using a modified Feng-Tzeng Euclidean algorithm.
  • A mathematical proof is provided for the reformulation of the multi-sequence problem of varying length into an equal-length problem.
  • The complexity of the proposed decoding approach is analyzed, yielding an approximate complexity of $O(s^2k \cdot (n-k)^2)$, where $s$ is the interleaving factor, $k$ is the code's information length, and $n$ is the code's block length.
  • An example is provided in the appendix demonstrating the algorithm's application to an RS(10,3) code, showing how it can correct errors beyond the standard error-correction radius.

Limitations and Future Work

  • Complexity: While the complexity is analyzed, the derived complexity $O(s^2k \cdot (n-k)^2)$ might still be high for very large codes or high interleaving factors. The paper notes that the complexity of solving the equivalent multi-sequence problem of equal length will be higher than the original problem.
  • Rate Restriction: The paper mentions that the virtual extension scheme is restricted to low-rate Reed-Solomon codes (specifically, $R < 1/3$ for a decoding radius greater than $(n-k)/2$). This limitation might restrict its applicability to certain scenarios.
  • Generalization: The paper focuses on homogeneous IRS codes and a specific type of error (burst errors). Further work could explore its applicability to more general heterogeneous IRS codes or different error patterns.
  • Practical Implementation: While the theoretical framework is presented, the paper doesn't delve into the practical implementation challenges or performance benchmarks of the proposed algorithm in real-world systems.

Future work could involve optimizing the complexity, exploring its application to a wider range of RS codes and error models, and investigating its practical performance through simulations and hardware implementations.

Summary updated

Abstract

We modify the Euclidean algorithm of Feng and Tzeng to decode Reed-Solomon (RS) codes up to the Sudan radius. The basic steps are the virtual extension to an Interleaved RS code and the reformulation of the multi-sequence shift-register problem of varying length to a multi-sequence problem of equal length. We prove the reformulation and analyze the complexity of our new decoding approach. Furthermore, the extended key equation, that describes the multi-sequence problem, is derived in an alternative polynomial way.
BibTeX
@misc{zeh2010decoding,
  author = {Alexander Zeh and Wenhui Li},
  title = {{Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm}},
  year = {2010},
  doi = {10.1109/isita.2010.5649520},
}

Loading related content...

Figure