New List Decoding Algorithms for Reed–Solomon and BCH Codes

DOI10.1109/TIT.2008.926355zbMATH Open1329.94103arXivcs/0703105OpenAlexW2066795426MaRDI QIDQ3604748FDOQ3604748

Authors: Yingquan Wu 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and BCH codes. The proposed list decoding algorithms exhibit the following significant properties. 1 The algorithm corrects up to $n(1-sqrt1-D)$ errors for a (generalized) $(n,k,d=n-k+1)$ Reed-Solomon code, which matches the Johnson bound, where $Deqdeffracdn$ denotes the normalized minimum distance. In comparison with the Guruswami-Sudan algorithm, which exhibits the same list correction capability, the former requires multiplicity, which dictates the algorithmic complexity, $O(n(1-sqrt1-D))$, whereas the latter requires multiplicity $O(n^2(1-D))$. With the up-to-date most efficient implementation, the former has complexity $O(n^6(1-sqrt1-D{)}^{7/2})$, whereas the latter has complexity $O(n^{10}(1-D{)}^4)$. 2. With the multiplicity set to one, the derivative list correction capability precisely sits in between the conventional hard-decision decoding and the optimal list decoding. Moreover, the number of candidate codewords is upper bounded by a constant for a fixed code rate and thus, the derivative algorithm exhibits quadratic complexity $O(n^2)$. 3. By utilizing the unique properties of the Berlekamp algorithm, the algorithm corrects up to $fracn2(1-sqrt1-2D)$ errors for a narrow-sense $(n,k,d)$ binary BCH code, which matches the Johnson bound for binary codes. The algorithmic complexity is $O(n^6(1-sqrt1-2D{)}^7)$.

Full work available at URL: https://arxiv.org/abs/cs/0703105

Recommendations

• Improved decoding of Reed-Solomon and algebraic-geometry codes
• List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
• Efficient decoding of Reed-Solomon codes beyond half the minimum distance
• Decoding of Reed Solomon codes beyond the error-correction bound
• List decoding of algebraic-geometric codes

Mathematics Subject Classification ID

Combinatorial codes (94B25) Bounds on codes (94B65) Decoding (94B35)

Cited In (17)

• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• A module minimization approach to Gabidulin decoding via interpolation
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• Minimal Gröbner bases and the predictable leading monomial property
• The performance of concatenated schemes based on non-binary multithreshold decoders
• A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes
• Title not available (Why is that?)
• A weight-based characterization of the set of correctable error patterns under list-of-2 decoding
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• Improvements on the Johnson bound for Reed-Solomon codes
• List Decoding for Binary Goppa Codes
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• List decoding of matrix-product codes from nested codes: an application to quasi-cyclic codes
• Improved power decoding of interleaved one-point Hermitian codes
• Power decoding Reed-Solomon codes up to the Johnson radius
• An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

This page was built for publication: New List Decoding Algorithms for Reed–Solomon and BCH Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604748)