Abstract
Given an algebraic geometry code \({C_{\mathcal L}(D, \alpha P)}\), the Guruswami–Sudan algorithm produces a list of all codewords in \({C_{\mathcal L}(D, \alpha P)}\) within a specified distance of a received word. The initialization step in the algorithm involves parameter choices that bound the degree of the interpolating polynomial and hence the length of the list of codewords generated. In this paper, we use simple properties of discriminants of polynomials over finite fields to provide improved parameter choices for the Guruswami–Sudan list decoding algorithm for algebraic geometry codes. As a consequence, we obtain a better bound on the list size as well as a lower degree interpolating polynomial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Garcia A., Stichtenoth H.: A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vlădut bound. Invent. Math. 121, 211–222 (1995)
Gao S., Shokrollahi M.: Computing roots of polynomials over function fields of curves. In: Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory. Springer, Berlin, pp. 214–228 (2000).
Goppa V.D.: Algebraico-geometric codes. Math. USSR-Izv. 21, 75–91 (1983)
Goppa V.D.: Geometry and Codes. Kluwer, Dordrecht (1988)
Guruswami V., Rudra A.: Limits to list decoding Reed–Solomon codes, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 602–609, ACM, New York (2005).
Guruswami V., Sudan M.: On representations of algebraic-geometry codes. IEEE Trans. Inform. Theory 47(4), 1610–1613 (2001)
Guruswami V., Sudan M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Trans. Inform. Theory 45(6), 1757–1767 (1999)
Høholdt T., van Lint J.H., Pellikaan R.: Algebraic Geometry Codes. In: Pless, V., Huffman, W.C., Brualdi, R.A. (eds) Handbook of Coding Theory 1, pp. 871–961. Elsevier, Amsterdam (1998)
Shokrollahi M.A., Wasserman H.: List decoding of algebraic-geometric codes. IEEE Trans. Inform. Theory 45, 432–437 (1999)
Stichtenoth H.: Algebraic Function Fields and Codes. Springer-Verlag, Heidelberg (1993)
Sudan M.: Decoding of Reed-Solomon codes beyond the error correction bound. J. Compl. 13, 180–193 (1997)
Tsfasman M.A., Vlădut S.G., Zink T.: Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound. Math. Nach. 109, 21–28 (1982)
Wang M.: Parameter choices on Guruswami–Sudan algorithm for polynomial reconstruction. Finite Fields Appl. 13, 877–886 (2007)
Yang K., Kumar P.V.: On the true minimum distance of Hermitian codes, coding theory and algebraic geometry, Proceedings, Luminy, 1991. Lecture Notes in Mathematics vol. 1518, pp. 99–107. Springer-Verlag, Heidelberg (1992).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Gabor Korchmaros.
This project was supported by NSF DMS-0201286 and NSA H-98230-06-1-0008.
Rights and permissions
About this article
Cite this article
Drake, N., Matthews, G.L. Parameter choices and a better bound on the list size in the Guruswami–Sudan algorithm for algebraic geometry codes. Des. Codes Cryptogr. 54, 181–187 (2010). https://doi.org/10.1007/s10623-009-9317-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-009-9317-8