Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

This paper presents new variants of the Welch-Berlekamp algorithm that are favorable to hardware implementation. First, we derive the parallel Welch-Berlekamp (PWB) algorithm in a constructive manner based on the properties of solutions to the rational interpolation problem. The algorithm features the simultaneously performed discrepancy computation and polynomial update. Second, we explore the early-termination mechanism of the PWB algorithm for decoding of Reed-Solomon (RS) codes. By introducing the concept of incomplete error locator polynomial, we show that if$e \leq t$(whereeis the number of errors andtis the error correction capability), the PWB algorithm can be terminated at latest at the completion of the$(t+ e)$-th iteration. This leads to the early-terminating PWB (EPWB) algorithm. Finally, we develop frequency-domain versions of the PWB and EPWB algorithms, namely, FPWB and FEPWB. The key point toward the two algorithms is to replace the update of polynomial coefficients with the update of polynomial evaluations. It is worth noting that the FEPWB algorithm applies only to shortened RS codes. Furthermore, an efficient systolic architecture for the FPWB algorithm is designed, which is easily adapted for the FEPWB algorithm.

In this paper, we present an efficient decoding algorithm for a class of Reed-Solomon (RS) codes over Fermat field$\mathbb{F}_{2^{r}+1}$. We show that the Fermat number transform can be used to speed up the syndrome computation and the Chien search. The implementation architectures are designed for the two blocks. The key equation is then derived. When using the RS code in practice, there arises the issue that a$(2^{r}+1)$-ary symbol is less efficiently represented by a tuple of$(r+1)$bits. We present a nested coding scheme based on RS code and single parity-check (SPC) code to harness the inefficiency. A modified Wagner algorithm is proposed for decoding the inner (nonlinear) code and is proved to be an ML decoding over the BPSK-modulated AWGN channel. Simulation results show that the proposed RS-SPC nested coding scheme yields a considerable performance gain compared to the stand-alone RS coding scheme.

The Berlekamp-Massey algorithm is a primary algorithm for decoding Reed-Solomon codes. As an inherent property of the algorithm, the early termination can effectively reduce the latency and power of decoding. It has been known that the algorithm can be terminated at the completion of the$(t+e)$-th iteration (where$e$is the number of errors and$t$is the error-correction capability of the code). In this paper, we explore a new mechanism for the early termination. Specifically, assuming$e\leq t$, we present a detection method that can identify the$2e$-th iteration. Since the error locator polynomial will have been found at the completion of the$2e$-th iteration, we can terminate the algorithm at this point based on the proposed method. As an application, a hardware-friendly algorithm variant, dubbed Reformulated Early-Terminating Parallel Inversionless Berlekamp-Massey (RETPIBM) algorithm, is presented, which yields a systolic architecture. The derivative architecture consists of$3t+1$processing elements (PEs) and has the critical path of one multiplier and one adder. To the best of the authors' knowledge, this is literally the first architecture that achieves the early termination for Berlekamp-Massey algorithm.

This paper presents an early-termination method for the Welch-Berlekamp algorithm. Specifically, if e ≤ t (where e is the number of errors and t is the error correction capability), the Welch–Berlekamp algorithm can be terminated at latest at the completion of the (t + e)-th iteration. Based on the early-termination mechanism, a new variant of the Welch–Berlekamp algorithm called eFDMA is presented, and a systolic architecture is designed for the eFDMA algorithm. This provides an efficient implementation for the key equation solver for a new class of Reed–Solomon codes recently proposed by Lin et al. [9].

Decoding algorithms for Reed–Solomon (RS) codes are of great interest for both practical and theoretical reasons. In this paper, an efficient algorithm, called the modular approach (MA), is devised for solving the Welch–Berlekamp (WB) key equation. By taking the MA as the key equation solver, we propose a new decoding algorithm for systematic RS codes. For$(n,k)$RS codes, where$n$is the code length and$k$is the code dimension, the proposed decoding algorithm has both the best asymptotic computational complexity$O(n\log (n-k) + (n-k)\log ^{2}(n-k))$and the smallest constant factor achieved to date. By comparing the number of field operations required, we show that when decoding practical RS codes, the new algorithm is significantly superior to the existing methods in terms of computational complexity. When decoding the (4096, 3584) RS code defined over$\mathbb {F}_{2^{12}}$, the new algorithm is 10 times faster than a conventional syndrome-based method. Furthermore, the new algorithm has a regular architecture and is thus suitable for hardware implementation.