New List Decoding Algorithms for Reed–Solomon and BCH Codes

DOI10.1109/TIT.2008.926355MaRDI QIDQ3604748zbMATH OpenOpenAlexFDO

Authors Yingquan Wu

Publication date 24 February 2009

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

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

Mathematics Subject Classification ID

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

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)$.

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

Cited in

(17)

• List decoding of matrix-product codes from nested codes: an application to quasi-cyclic codes
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Improved power decoding of interleaved one-point Hermitian codes
• A weight-based characterization of the set of correctable error patterns under list-of-2 decoding
• A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes
• Improvements on the Johnson bound for Reed-Solomon codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• List Decoding for Binary Goppa Codes
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Minimal Gröbner bases and the predictable leading monomial property
• scientific article; zbMATH DE number 149700 (Why is no real title available?)
• A module minimization approach to Gabidulin decoding via interpolation
• 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
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• The performance of concatenated schemes based on non-binary multithreshold decoders

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)