\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Efficient list decoding of a class of algebraic-geometry codes

Abstract Related Papers Cited by
  • We consider the problem of list decoding algebraic-geometry codes. We define a general class of one-point algebraic-geometry codes encompassing, among others, Reed-Solomon codes, Hermitian codes and norm-trace codes. We show how for such codes the interpolation constraints in the Guruswami-Sudan list-decoder, can be rephrased using a module formulation. We then generalize an algorithm by Alekhnovich [2], and show how this can be used to efficiently solve the interpolation problem in this module reformulation. The family of codes we consider has a number of well-known members, for which the interpolation part of the Guruswami-Sudan list decoder has been studied previously. For such codes the complexity of the interpolation algorithm we propose, compares favorably to the complexity of known algorithms.
    Mathematics Subject Classification: Primary: 14G50, 94B35; Secondary: 94B27, 11T71.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]
    [2]

    M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 51 (2005), 2257-2265.doi: 10.1109/TIT.2005.850097.

    [3]

    M. F. Atiyah and I. G. MacDonald, "Introduction to Commutative Algebra,'' 1rt edition, Addison-Wesley, 1969.

    [4]

    D. Augot and L. Pecquet, A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes, IEEE Transactions on Information Theory, 46 (2000), 2605-2614.doi: 10.1109/18.887868.

    [5]

    D. Augot and A. Zeh, On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm, in "Information Theory, 2008. ISIT 2008. IEEE International Symposium,'' (2008), 2620-2624.

    [6]

    P. Beelen and K. Brander, Key-equations for list decoding of Reed-Solomon codes and how to solve them, Journal of Symbolic Computation, 45 (2010), 773-786.doi: 10.1016/j.jsc.2010.03.010.

    [7]

    P. Beelen and R. Pellikaan, The Newton polygon of plane curves with many rational points, Designs, Codes and Cryptography, 21 (2000), 41-67.doi: 10.1023/A.1008323208670.

    [8]

    W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. the user language, Journal of Symbolic Computation, 3-4 (1997), 235-265.doi: 10.1006/jsco.1996.0125.

    [9]

    P. Fitzpatrick, On the key equation, IEEE Transactions onInformation Theory, 41 (1995), 1290-1302.

    [10]

    S. H. Gao and M. A. Shokrollahi, Computing roots of polynomials over function fields of curves, in "Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory'' (ed. D. Joyner), Springer-Verlag, (2000), 214-228.

    [11]

    J. von zur Gathen and J. Gerhard, "Modern Computer Algebra,'' 2nd edition edition, Cambridge University Press, 2003.

    [12]

    O. Geil, On codes from norm-trace curves, Finite Fields and Their Applications, 9 (2003), 351-371.doi: 10.1016/S1071-5797(03)00010-8.

    [13]

    D. M. Goldschmidt, "Algebraic Functions and Projective Curves,'' Springer, 2002.

    [14]

    V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, IEEE Transactions On Information Theory, 45 (1999), 1757-1767.doi: 10.1109/18.782097.

    [15]

    T. Høholdt and R. R. Nielsen, Decoding Hermitian codes with Sudan's algorithm, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. M. Fossorier, H. Imai, S. Lin and A. Poli), Springer-Verlag, (1999), 260-270.doi: 10.1007/3-540-46796-3_26.

    [16]

    P. V. Kumar and K. Yang, On the true minimum distance of Hermitian codes, Springer, (1992), 99-107.

    [17]

    K. Lee and M. E. O’Sullivan, List decoding of Hermitian codes using Gröbner bases, Journal of Symbolic Computation, in Press, 2008.

    [18]

    K. Lee and M. E. O’Sullivan, List decoding of Reed-Solomon codes from a Gröbner basis perspective, Journal of Symbolic Computation, 43 (2008), 645-658.doi: 10.1016/j.jsc.2008.01.002.

    [19]

    S. Miura and N. Kamiya, Geometric-Goppa codes on some maximal curves and their minimum distance, in "Proceedings of 1993 IEEE Information Theory Workshop,'' Shizuoka, Japan, (1993), 85-86.

    [20]

    H. O’Keeffe and P. Fitzpatrick, Gröbner basis solutions of constrained interpolation problems, Journal of Linear Algebra and Applications, 351/352 (2002), 533-551.doi: 10.1016/S0024-3795(01)00509-2.

    [21]

    H. O’Keeffe and P. Fitzpatrick, Gröbner basis approach to list decoding of algebraic geometry codes, Applicable Algebra in Engineering, Communication and Computing, 18 (2007), 445-466.doi: 10.1007/s00200-007-0048-7.

    [22]

    V. Olshevsky and M. A. Shokrollahi, A displacement approach to efficient decoding of algebraic-geometric codes, in "STOC'99: Proceedings of the thirty-first annual ACM symposium on Theory of computing,'' New York, USA, (1999), 235-244.

    [23]

    V. S. Pless and W. C. Huffman (eds.), "Handbook of Coding Theory,'' North-Holland, 1 (1998).

    [24]

    S. Sakata, Finding a minimal polynomial vector set of a vector of nD arrays, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes,'' 1991.

    [25]

    S. Sakata, On fast interpolation method for Guruswami-Sudan list decoding of one-point algebraic-geometry codes, in "AAECC,'' (2001), 172-181.

    [26]

    M. Sala, T. Mora, L. Perret, S. Sakata and C. Traverso (eds.), "Gröbner Bases, Coding, and Cryptography,'' Springer, 2009.

    [27]

    M. A. Shokrollahi and H. Wasserman, Decoding algebraic-geometric codes beyond the error-correction bound, in "Proceedings of the thirtieth annual ACM symposium on Theory of computing,'' (1998), 241-248.

    [28]

    J. H. Silverman, "The Arithmetic of Elliptic Curves,'' Springer, 1986.

    [29]

    H. Stichtenoth, "Algebraic Function Fields and Codes,'' Springer, 1993.

    [30]

    M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, Journal of Complexity, 13 (1997), 180-193.doi: 10.1006/jcom.1997.0439.

    [31]

    X.-W. Wu and P. H. Siegel, Efficient root-finding algorithm with application to list decoding of algebraic-geometric codes, IEEE Transactions On Information Theory, 47 (2001), 2579-2587.doi: 10.1109/18.945273.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(266) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return