Parallel Welch–Berlekamp Algorithm
- 19 February 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3473-3488
Abstract
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$ (where e is the number of errors and t is 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.Keywords
Funding Information
- China National Key Research and Development Program (2021YFA1000500)
This publication has 17 references indexed in Scilit:
- On the Equivalence between the Welch–Berlekamp Algorithm and the Modular Approach Algorithm2023
- An Early-Termination Method for the Welch-Berlekamp Algorithm2023
- Fast Encoding and Decoding Algorithms for Arbitrary $(n,k)$ Reed-Solomon Codes Over $\mathbb{F}_{2^m}$IEEE Communications Letters, 2020
- Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes2014
- Error Correction Coding2005
- Algebraic Codes for Data Transmission2003
- High-speed architectures for Reed-Solomon decodersIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- On the minimal interpolation problem and decoding RS codesIEEE Transactions on Information Theory, 2000
- Fast parallel algorithms for decoding Reed-Solomon codes based on remainder polynomialsIEEE Transactions on Information Theory, 1995
- Why systolic architectures?Computer, 1982