Reed–Solomon (RS) codes are among the most widely deployed error-correcting codes, yet their practical decoders mostly ignore the reliability (soft) information available from the channel. The Koetter–Vardy (2003) algebraic soft-decision decoder converts soft information into interpolation multiplicities and provably outperforms hard-decision decoding by large margins (2–3 dB and more), but its computational cost — dominated by bivariate interpolation and factorization at high multiplicities — has prevented adoption. A long-standing open problem is realizing, and characterizing, soft-decision decoding of RS codes whose error performance approaches maximum-likelihood (ML) decoding — with Koetter–Vardy decoding, using the multiplicity-assignment rule of Koetter and Vardy (2003) at the largest total interpolation multiplicity whose cost stays within the complexity yardstick stated below, as a computable comparison baseline, though strictly below ML at high rates — while its complexity, memory, and throughput remain comparable to hard-decision algebraic decoding. Despite two decades of partial progress along this performance–complexity frontier, no decoder has been shown to close the gap.

Background

A Reed–Solomon (RS) code is a classic algebraic error-correcting code: its codewords are evaluations of polynomials of bounded degree over a finite field, and it is ubiquitous in storage, deep-space, and modern post-quantum systems such as the Hamming Quasi-Cyclic (HQC) key-encapsulation cryptosystem — selected by NIST for standardization in 2025, with decryption that relies on RS decoding — because it corrects burst errors and has an efficient algebraic decoder. A hard-decision decoder sees only each received symbol's most likely value; a soft-decision decoder additionally uses reliability information, e.g. probabilities or log-likelihood ratios for every candidate symbol, and can therefore substantially outperform hard-decision decoding on noisy channels. Maximum-likelihood (ML) decoding — exhaustive selection of the most probable codeword — is the information-theoretic optimum but computationally infeasible for general linear codes of nontrivial length. Classic soft-aided schemes such as generalized minimum distance (GMD) decoding erase the least reliable symbols and run hard decoding erasures-aware. The Guruswami–Sudan (1999) list decoder enlarged the hard-decision correction radius: it interpolates a nonzero bivariate polynomial Q(x,y)Q(x,y) through the received points and factors it to recover all message polynomials consistent with the received word beyond half the minimum distance. Koetter and Vardy (2003) made this soft: channel reliabilities are converted into nonnegative multiplicities on interpolation points, so reliable positions constrain QQ more strongly than unreliable ones; the resulting algebraic soft-decision (ASD) decoder significantly outperforms both Guruswami–Sudan and GMD decoding while remaining polynomial-time. However, the cost of the interpolation step grows rapidly with the total multiplicity (roughly a high power of the maximum multiplicity), so the large-coding-gain regime is computationally impractical, and the multiplicity assignment itself is a difficult integer optimization trading performance against interpolation cost. Gross, Kschischang, Koetter, and Gulak (2006) framed the engineering question explicitly — how to manage the extra complexity of soft decoding at the systems level — reporting 2–3 dB of soft-decision gain for the high-rate RS(255,239) code on Rayleigh fading channels (a standard statistical model of random wireless signal attenuation; up to about 9 dB at low rates) and proposing complexity-saving redecoding. Subsequent work attacked separate cost components: cheaper multiplicity assignment (Parvaresh–Vardy 2003; El-Khamy–McEliece 2005, 2006), iterative belief-propagation/KV hybrids (El-Khamy–McEliece 2006), bit-level soft information with closed-form decoding radii and lower per-decode cost (Vardy–Be'ery 1991; Jiang–Narayanan 2008), progressive decoding that spends interpolation effort only as needed (Chen–Tang–Ma 2013; Xing–Chen–Bossert 2019), hardware architectures for long codes (Zhang–Zhu 2010), and graph-based soft-decision schemes (Lee–Wu–Wang–Ueng 2023). On the theoretical side, Duggan and Barg (2008) derived the ASD decoding region for additive-noise channels and showed the soft radius exceeds the Guruswami–Sudan radius only for a subset of low and medium rates, bounding where soft gains are available. Despite two decades of partial results, no decoder is known that combines near-ML error performance — or even error performance approaching Koetter–Vardy decoding, the paradigm's computable reference point — with hard-decision-like complexity for long, high-rate RS codes, the setting of most practical interest.

Problem Statement

Construct, and characterize the limits of, practical algebraic soft-decision decoding of Reed–Solomon (RS) codes. Concretely: (1) Design a soft-decision decoding algorithm for RS codes of length nn and dimension kk over Fq\mathbb{F}_q that, given symbol reliabilities from the channel, targets, as the field's long-standing aspiration, frame-error-rate performance approaching that of maximum-likelihood (ML) decoding on standard soft channels, including for long, high-rate codes such as RS(255,239), while its computational complexity, memory, and decoding throughput remain comparable to hard-decision algebraic decoding — within a small order-of-magnitude factor of Berlekamp–Massey decoding (the standard hard-decision RS decoder) and no worse than Guruswami–Sudan list decoding, thereby closing the performance–complexity gap identified in the Koetter–Vardy line of work. Koetter–Vardy decoding with the multiplicity-assignment rule of Koetter and Vardy (2003), evaluated at the largest total interpolation multiplicity whose cost stays within the complexity yardstick of goal (1), serves as the computable comparison baseline for the frame-error rate target of goal (1); however, ASD decoding-region analyses (Duggan–Barg; Jiang–Narayanan) show that it can be strictly below ML at high rates, so approaching it does not by itself establish near-ML performance. For long, high-rate codes such as RS(255,239), where ML decoding is not computable, and throughout a stated signal-to-noise-ratio range on the stated channel, the decoder sought in goal (1) has a frame-error rate strictly below that of the Koetter–Vardy baseline defined above, with its own complexity, memory, and throughput within the same complexity yardstick, whether or not it uses interpolation multiplicities; where ML decoding is computable, its frame-error rate is also compared with the exact ML frame-error rate. (2) As an accompanying objective, characterize the optimal trade-off: for a given complexity budget (e.g., a bound on total interpolation multiplicity or on operation count), determine the best achievable error performance of algebraic soft-decision decoding, so that the residual gap to ML can be attributed either to the scheme or to a proven limitation. For fixed code parameters, channel model, and baseline decoders together with a stated complexity budget, such a characterization consists of an achievability result (an explicit decoder or bound attaining a stated frame-error rate within that budget) and a matching converse (a proof that no algebraic soft-decision decoder — any decoder that takes symbol reliabilities as input, forms a bivariate interpolation polynomial with bounded total multiplicity, and factors it to a candidate list, in the manner of Guruswami–Sudan (1999) and Koetter–Vardy (2003) — achieves a lower frame-error rate within the same budget). Goals (1) and (2) are jointly posed: the design question and the accompanying characterization of the complexity–performance trade-off. Throughout, the code parameters, channel model, and baseline decoders are those stated above; 'practical complexity' is understood in the field's conventional sense — an order-of-magnitude cost comparable to hard-decision decoding, feasible for real-time and very-large-scale-integration (VLSI) hardware implementation.

References

  1. V. Guruswami and M. Sudan, "Improved decoding of Reed-Solomon and algebraic-geometry codes," IEEE Transactions on Information Theory, vol. 45, no. 6, pp. 1757–1767, 1999. DOI: 10.1109/18.782097, https://doi.org/10.1109/18.782097
  2. R. Koetter and A. Vardy, "Algebraic soft-decision decoding of Reed-Solomon codes," IEEE Transactions on Information Theory, vol. 49, no. 11, pp. 2809–2825, 2003. DOI: 10.1109/TIT.2003.819332, https://doi.org/10.1109/TIT.2003.819332
  3. F. Parvaresh and A. Vardy, "Multiplicity assignments for algebraic soft-decoding of Reed-Solomon codes," IEEE International Symposium on Information Theory (ISIT), 2003. DOI: 10.1109/ISIT.2003.1228219, https://doi.org/10.1109/ISIT.2003.1228219
  4. M. El-Khamy and R. J. McEliece, "Interpolation multiplicity assignment algorithms for algebraic soft-decision decoding of Reed-Solomon codes," in Algebraic Coding Theory and Information Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 68, pp. 99–120, 2005. DOI: 10.1090/dimacs/068/07, https://doi.org/10.1090/dimacs/068/07
  5. M. El-Khamy and R. J. McEliece, "Iterative algebraic soft-decision list decoding of Reed-Solomon codes," IEEE Journal on Selected Areas in Communications, vol. 24, no. 3, pp. 481–490, 2006. DOI: 10.1109/JSAC.2005.862399, https://doi.org/10.1109/JSAC.2005.862399
  6. W. J. Gross, F. R. Kschischang, R. Koetter, and P. G. Gulak, "Applications of algebraic soft-decision decoding of Reed-Solomon codes," IEEE Transactions on Communications, vol. 54, no. 7, pp. 1224–1234, 2006. DOI: 10.1109/TCOMM.2006.877972, https://doi.org/10.1109/TCOMM.2006.877972
  7. A. Vardy and Y. Be'ery, "Bit-level soft-decision decoding of Reed-Solomon codes," IEEE Transactions on Communications, vol. 39, no. 3, pp. 440–444, 1991. DOI: 10.1109/26.79287, https://doi.org/10.1109/26.79287
  8. J. Jiang and K. R. Narayanan, "Algebraic soft-decision decoding of Reed–Solomon codes using bit-level soft information," IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 3907–3928, 2008. DOI: 10.1109/TIT.2008.928238, https://doi.org/10.1109/TIT.2008.928238
  9. A. Duggan and A. Barg, "Performance analysis of algebraic soft-decision decoding of Reed–Solomon codes," IEEE Transactions on Information Theory, vol. 54, no. 11, pp. 5012–5018, 2008. DOI: 10.1109/TIT.2008.929969, https://doi.org/10.1109/TIT.2008.929969
  10. X. Zhang and Y. Zhu, "Algebraic soft-decision decoder architectures for long Reed–Solomon codes," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 57, no. 10, pp. 787–792, 2010. DOI: 10.1109/TCSII.2010.2067812, https://doi.org/10.1109/TCSII.2010.2067812
  11. L. Chen, S. Tang, and X. Ma, "Progressive algebraic soft-decision decoding of Reed-Solomon codes," IEEE Transactions on Communications, vol. 61, no. 2, pp. 433–442, 2013. DOI: 10.1109/TCOMM.2012.100912.110752, https://doi.org/10.1109/TCOMM.2012.100912.110752
  12. J. Xing, L. Chen, and M. Bossert, "Progressive algebraic soft-decision decoding of Reed–Solomon codes using module minimization," IEEE Transactions on Communications, vol. 67, no. 11, pp. 7379–7391, 2019. DOI: 10.1109/TCOMM.2019.2927207, https://doi.org/10.1109/TCOMM.2019.2927207
  13. H.-C. Lee, J.-H. Wu, C.-H. Wang, and Y.-L. Ueng, "A graph-based soft-decision decoding scheme for Reed-Solomon codes," IEEE Journal on Selected Areas in Information Theory, vol. 4, pp. 420–433, 2023. DOI: 10.1109/JSAIT.2023.3315453, https://doi.org/10.1109/JSAIT.2023.3315453
  14. J. Cai and X. Zhang, "HQC post-quantum cryptography decryption with soft-decision Reed-Solomon decoder," IEEE International Symposium on Circuits and Systems (ISCAS), pp. 832–836, 2026. DOI: 10.1109/ISCAS66217.2026.11562887, https://doi.org/10.1109/ISCAS66217.2026.11562887