Efficient list decoding of a class of algebraic-geometry codes

Previous Article
Some applications of lattice based root finding techniques
AMC Home
This Issue
Next Article
On the generic construction of identity-based signatures with additional properties

November 2010, 4(4): 485-518. doi: 10.3934/amc.2010.4.485

Efficient list decoding of a class of algebraic-geometry codes

Peter Beelen ^1, and Kristian Brander ^1,

1.	DTU-Mathematics, Technical University of Denmark, Matematiktorvet 303S, 2800 Kgs. Lyngby, Denmark, Denmark

Received November 2009 Revised May 2010 Published November 2010

Abstract
Related Papers

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.

Keywords: Alekhnovich’s algorithm., List-decoding, algebraic geometry codes.

Mathematics Subject Classification: Primary: 14G50, 94B35; Secondary: 94B27, 11T7.

Citation: Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

References:

[1]	, Overview of Magma v2.9 features,, \url{http://magma.maths.usyd.edu.au/magma/Features/node93.html}., ().
[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,'' 1^rt 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,'' 2^nd 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.

show all references

References:

[1]	, Overview of Magma v2.9 features,, \url{http://magma.maths.usyd.edu.au/magma/Features/node93.html}., ().
[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,'' 1^rt 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,'' 2^nd 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.

[1]	Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
[2]	Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311
[3]	Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[4]	Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[5]	Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.
[6]	Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419
[7]	Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021031
[8]	Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002
[9]	Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[10]	Alex L Castro, Wyatt Howard, Corey Shanbrom. Bridges between subriemannian geometry and algebraic geometry: Now and then. Conference Publications, 2015, 2015 (special) : 239-247. doi: 10.3934/proc.2015.0239
[11]	Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[12]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[13]	Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021
[14]	Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009
[15]	Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331
[16]	Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[17]	François Lalonde, Yasha Savelyev. On the injectivity radius in Hofer's geometry. Electronic Research Announcements, 2014, 21: 177-185. doi: 10.3934/era.2014.21.177
[18]	Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046
[19]	Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
[20]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Peter Beelen Kristian Brander
on Google Scholar
Peter Beelen Kristian Brander

[Back to Top]