Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets

Authors: Venkatesan Guruswami and Anindya C. Patthak
Journal: Math. Comp. 77 (2008), 447-473
MSC (2000): Primary 94B27, 12Y05, 14Q05, 14H05
Published electronically: September 13, 2007
MathSciNet review: 2353961
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (nonobvious) generalization of the approach in the recent breakthrough work of Parvaresh and Vardy (2005).

Our work shows that the PV framework applies to fairly general settings by elucidating the key algebraic concepts underlying it. Also, more importantly, AG codes of arbitrary block length exist over fixed alphabets $ \Sigma$, thus enabling us to establish new trade-offs between the list decoding radius and rate over a bounded alphabet size.

The work of Parvaresh and Vardy (2005) was extended in Guruswami and Rudra (2006) to give explicit codes that achieve the list decoding capacity (optimal trade-off between rate and fraction of errors corrected) over large alphabets. A similar extension of this work along the lines of Guruswami and Rudra could have substantial impact. Indeed, it could give better trade-offs than currently known over a fixed alphabet (say, $ {\rm GF}(2^{12})$), which in turn, upon concatenation with a fixed, well-understood binary code, could take us closer to the list decoding capacity for binary codes. This may also be a promising way to address the significant complexity drawback of the result of Guruswami and Rudra, and to enable approaching capacity with bounded list size independent of the block length (the list size and decoding complexity in their work are both $ n^{\Omega(1/\varepsilon)}$ where $ \varepsilon$ is the distance to capacity).

Similar to algorithms for AG codes from Guruswami and Sudan (1999) and (2001), our encoding/decoding algorithms run in polynomial time assuming a natural polynomial-size representation of the code. For codes based on a specific ``optimal'' algebraic curve, we also present an expected polynomial time algorithm to construct the requisite representation. This in turn fills an important void in the literature by presenting an efficient construction of the representation often assumed in the list decoding algorithms for AG codes.

References [Enhancements On Off] (What's this?)

  • 1. Arnaldo Garcia and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound, Inventiones Mathematicae 121 (1995), 211-222. MR 1345289 (96d:11074)
  • 2. -, On the asymptotic behavior of some towers of function fields over finite fields, Journal of Number Theory 61 (1996), no. 2, 248-273. MR 1423052 (97i:11067)
  • 3. Venkatesan Guruswami and Piotr Indyk, Expander-based constructions of efficiently decodable codes, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 658-667. MR 1948755
  • 4. Venkatesan Guruswami and Atri Rudra, Explicit capacity-achieving list-decodable codes, Proceedings of the 38th ACM Symposium on Theory of Computing, May 2006, pp. 1-10. MR 2277125
  • 5. Venkatesan Guruswami, Amit Sahai, and Madhu Sudan, Soft-decision decoding of Chinese Remainder codes, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), 2000, pp. 159-168. MR 1931814
  • 6. Venkatesan Guruswami and Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, IEEE Transactions on Information Theory 45 (1999), 1757-1767. MR 1720630 (2000j:94033)
  • 7. Venkatesan Guruswami and Madhu Sudan, On representations of algebraic-geometric codes, IEEE Transactions on Information Theory 47 (May 2001), no. 4, 1610-1613. MR 1830110 (2002b:94046)
  • 8. Ralf Koetter and Alexander Vardy, Soft decoding of Reed Solomon codes and optimal weight assignments, ITG Fachtagung (Berlin, Germany), January 2002.
  • 9. -, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory 49 (2003), no. 11, 2809-2825. MR 2027561 (2004k:94093)
  • 10. Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, MA, 1986. MR 860948 (88c:11073)
  • 11. Farzad Parvaresh and Alexander Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 285-294.
  • 12. Kenneth Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar, A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound, IEEE Transactions on Information Theory 47 (2001), no. 6, 2225-2241. MR 1873198 (2003e:94110)
  • 13. Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961 (94k:14016)
  • 14. Madhu Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, Journal of Complexity 13 (1997), no. 1, 180-193. MR 1449766 (98f:94024)
  • 15. Michael A. Tsfasman, Serge G. Vladut, and Thomas Zink, Modular curves, Shimura curves, and codes better than the Varshamov-Gilbert bound, Math. Nachrichten 109 (1982), 21-28. MR 705893 (85i:11108)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 94B27, 12Y05, 14Q05, 14H05

Retrieve articles in all journals with MSC (2000): 94B27, 12Y05, 14Q05, 14H05

Additional Information

Venkatesan Guruswami
Affiliation: Department of Computer Science & Engineering, University of Washington, Seattle, Washington 98195

Anindya C. Patthak
Affiliation: Department of Computer Science, University of Texas at Austin, Austin, Texas 78712

Received by editor(s): July 26, 2006
Received by editor(s) in revised form: November 14, 2006
Published electronically: September 13, 2007
Additional Notes: An extended abstract describing some of these results was presented at the 47th Annual Symposium on Foundations of Computer Science (FOCS), 2006. This is an expanded version of the paper, containing the proofs and algorithms in full
The first author was supported by NSF Career Award CCF-0343672, an Alfred P. Sloan Research Fellowship, and a David and Lucile Packard Foundation Fellowship
The second author was supported in part by NSF Grant CCR-0310960
Article copyright: © Copyright 2007 Venkatesan Guruswami and Anindya C. Patthak

American Mathematical Society