Tang and Han (IEEE Transactions on Communications, 2022) proposed the modular approach (MA) and its fast variants FDMA and FMA for solving the Welch–Berlekamp key equation in Reed–Solomon (RS) decoding, attaining the best known asymptotic complexity O(nlog⁡(n−k)+(n−k)log⁡2(n−k))O(n\log(n-k)+(n-k)\log^2(n-k)) with the smallest constant factor to date and a regular, hardware-suitable algorithmic architecture. The paper explicitly leaves open the transfer of these algorithms into concrete circuit designs, a fast list-decoding extension, and use in one-pass Chase decoding. No circuit or FPGA/ASIC realization of any of these quasi-linear FFT-based RS decoders with timing, area, and energy characterization is known in the literature to date. The problem is to design, implement, and characterize in hardware an MA/FDMA/FMA-family decoder for medium-to-long RS codes, determining whether its quasi-linear complexity advantage is preserved at high throughput relative to conventional syndrome-based decoder hardware.

Background

Reed–Solomon (RS) codes are a central family of error-correcting codes: for an (n,k)(n,k) RS code over the finite field F2m\mathbb{F}_{2^m} (block length nn, dimension kk), a codeword is the evaluation of a degree-(k−1)(k-1) polynomial, and the code corrects any pattern of up to t=⌊(n−k)/2⌋t=\lfloor(n-k)/2\rfloor symbol errors. RS codes are ubiquitous in storage systems, deep-space and optical communication, and post-quantum cryptography. Classical hard-decision decoding is syndrome-based: one computes syndromes (evaluations of the received word at the code's evaluation points), solves a key equation — finding an error-locator polynomial from the syndromes — using the Berlekamp–Massey algorithm (an iterative linear-recurrence solver) or the extended Euclidean algorithm (a gcd-style iteration on polynomials), locates errors by finding the roots of the locator via the Chien search (exhaustive evaluation at all field elements), and computes error magnitudes via the Forney formula. This pipeline costs roughly O(n(n−k)+(n−k)2)O(n(n-k)+(n-k)^2) field operations and its serial iteration structure limits parallel hardware performance. The Welch–Berlekamp (WB) formulation instead recasts decoding as a rational interpolation problem, avoiding syndromes. Finite-field fast Fourier transforms (FFTs) — in particular additive FFTs over binary extension fields, built on special polynomial bases and subspace polynomials — enable quasi-linear-time transforms. Using such transforms, Lin, Al-Naffouri, and Han (IEEE Transactions on Information Theory, 2016) obtained an RS decoder with complexity O(nlog⁡(n−k)+(n−k)log⁡2(n−k))O(n\log(n-k)+(n-k)\log^2(n-k)), the best asymptotic complexity to date, but their key-equation solver is based on Half-GCD (a divide-and-conquer version of the extended Euclidean algorithm), which has a large constant factor and an implementation structure that is not regular or highly parallel. Tang and Han (IEEE Transactions on Communications, 2022) closed this gap at the algorithmic level: their modular approach (MA) solves the WB key equation via operations on polynomial moduli; the frequency-domain modular approach (FDMA) performs the polynomial updates on FFT evaluations rather than coefficients, at O((n−k)2)O((n-k)^2) cost for short codes; and the fast modular approach (FMA) processes in divide-and-conquer style at O((n−k)log⁡2(n−k))O((n-k)\log^2(n-k)) cost. The full decoder attains O(nlog⁡(n−k)+(n−k)log⁡2(n−k))O(n\log(n-k)+(n-k)\log^2(n-k)) with the smallest constant factor achieved to date (the paper bounds the FMA key-equation constant below 9.5 versus at least 22.5 for Half-GCD), needs about ten times fewer field operations than a conventional syndrome-based decoder on the (4096,3584)(4096,3584) RS code over F212\mathbb{F}_{2^{12}}, and uses FFT butterfly building blocks, giving a regular architecture that the authors call suitable for hardware implementation. However, all of these are algorithmic and operation-count statements. Deployed hardware RS decoders today (e.g., those based on the RiBM architecture — remainderless inverse Berlekamp–Massey, a standard pipelined syndrome-based design) target short codes, and no complete circuit design, FPGA prototype, or ASIC implementation of the MA/FDMA/FMA decoders — or of any decoder of this quasi-linear family — with timing, area, and energy characterization exists in the published literature as of August 2026. The closest hardware-oriented advance, the parallel Welch–Berlekamp (PWB/FPWB) algorithm with a systolic architecture design (Chen, Han, Tang, Ma, and Bai, IEEE Transactions on Information Theory, 2025; a systolic architecture is a regular array of identical processing elements with nearest-neighbor data flow), remains at the architecture-design level without a complete implementation of a quasi-linear decoder. The gap between the proven algorithmic regularity and an actual working circuit is precisely what the source paper lists as its first item of future work.

Problem Statement

Realize the quasi-linear FFT/modular-approach Reed–Solomon decoders of Tang and Han (2022) — the MA/FDMA/FMA family — in concrete hardware. Specifically: design a complete circuit architecture (register-transfer-level design with explicit pipelining, processing-element structure, and memory organization for the FFT-based transforms and the modular/frequency-domain key-equation updates) for decoding systematic (n,k)(n,k) RS codes over F2m\mathbb{F}_{2^m}, implement it as an FPGA prototype and/or ASIC synthesis, verify functional equivalence with the algorithmic decoder — correct decoding of error patterns up to the correction capability t=⌊(n−k)/2⌋t=\lfloor(n-k)/2\rfloor, with the behavior for error patterns beyond tt explicitly specified — and characterize throughput, latency, area, and energy, comparing that characterization against a conventional syndrome-based (RiBM-class) decoder hardware baseline at the same code configuration. The realization should determine, at minimum for (4096,3584)(4096,3584) over F212\mathbb{F}_{2^{12}} (the setting of the source paper's own algorithm-level comparison with the RiBM syndrome-based decoder), whether and to what extent the quasi-linear complexity and small-constant advantage of the algorithm carries over to hardware relative to conventional syndrome-based decoder hardware.

References

  1. Nianqi Tang, Yunghsiang S. Han, A New Decoding Method for Reed–Solomon Codes Based on FFT and Modular Approach, IEEE Transactions on Communications 70(12):7790–7801, 2022, DOI: 10.1109/TCOMM.2022.3215998 (arXiv:2207.11079), https://arxiv.org/abs/2207.11079
  2. Sian-Jheng Lin, Tareq Y. Al-Naffouri, Yunghsiang S. Han, FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon Codes, IEEE Transactions on Information Theory 62(10):5343–5358, 2016, DOI: 10.1109/TIT.2016.2600417, https://doi.org/10.1109/TIT.2016.2600417
  3. Chao Chen, Yunghsiang S. Han, Nianqi Tang, Xiao Ma, Baoming Bai, Parallel Welch–Berlekamp Algorithm, IEEE Transactions on Information Theory 71(5):3473–3488, 2025, DOI: 10.1109/TIT.2025.3542812, https://doi.org/10.1109/TIT.2025.3542812
  4. Wrya K. Kadir, Hsuan-Yin Lin, Eirik Rosnes, Efficient Interpolation-Based Decoding of Reed-Solomon Codes, 2023 IEEE International Symposium on Information Theory (ISIT), arXiv:2307.00891, https://arxiv.org/abs/2307.00891
  5. Nianqi Tang, Yunghsiang S. Han, Danyang Pei, Chao Chen, A Fast Decoding Algorithm for Generalized Reed-Solomon Codes and Alternant Codes, 2025 International Workshop on Signal Design and Its Applications in Communications (IWSDA), arXiv:2502.02356, https://arxiv.org/abs/2502.02356
  6. Chao Chen, Sian-Jheng Lin, Nianqi Tang, Yunghsiang S. Han, Suihua Cai, Leilei Yu, Zhongwei Li, Baoming Bai, Bo Bai, Two Fast Erasure Decoding Algorithms for Reed–Solomon Codes Based on LCH-FFT, IEEE Transactions on Information Theory 72(6):3784–3798, 2026, DOI: 10.1109/TIT.2026.3685291, https://doi.org/10.1109/TIT.2026.3685291
  7. Nianqi Tang, Yunghsiang S. Han, Chao Chen, Danyang Pei, Generalized Inverse Discrete Fourier Transform With Application to Goppa Codes, IEEE Transactions on Information Theory 72(7):4719–4738, 2026, DOI: 10.1109/TIT.2026.3693655, https://doi.org/10.1109/TIT.2026.3693655
  8. Nianqi Tang, Chao Chen, Yunghsiang S. Han, Fast Error and Erasure Decoding Algorithm for Reed-Solomon Codes, IEEE Communications Letters 28(4):759–762, 2024, DOI: 10.1109/LCOMM.2024.3358055, https://doi.org/10.1109/LCOMM.2024.3358055
  9. Chao Chen, Nianqi Tang, Yunghsiang S. Han, Baoming Bai, On the Equivalence between the Welch–Berlekamp Algorithm and the Modular Approach Algorithm, 2023 IEEE/CIC International Conference on Communications in China (ICCC Workshops), pp. 1–5, 2023, DOI: 10.1109/ICCCWorkshops57813.2023.10233747, https://doi.org/10.1109/ICCCWorkshops57813.2023.10233747
  10. Muxun Zhang, Suwen Song, Liyang Zhou, Low-Complexity Parallel Syndrome Computation and Chien Search Architecture Based on Reed–Muller Transform, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 34(8):2397–2407, 2026, DOI: 10.1109/TVLSI.2026.3689292, https://doi.org/10.1109/TVLSI.2026.3689292
  11. Haobin Xu, Zichuan Qiu, Suwen Song, Zhongfeng Wang, Liyang Zhou, A Low-Latency Hardware Architecture Design for Five-Error-Correcting Reed–Solomon Decoder, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 34(7):2321–2325, 2026, DOI: 10.1109/TVLSI.2026.3689157, https://doi.org/10.1109/TVLSI.2026.3689157