-
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
Efficient list decoding of a class of algebraic-geometry codes
1. | DTU-Mathematics, Technical University of Denmark, Matematiktorvet 303S, 2800 Kgs. Lyngby, Denmark, Denmark |
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,'' 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. |
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,'' 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. |
[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
[Back to Top]