American Institute of Mathematical Sciences

Advanced
November  2012, 6(4): 419-442. doi: 10.3934/amc.2012.6.419

Syndrome decoding for Hermite codes with a Sugiyama-type algorithm

Irene I. Bouw 1, and  Sabine Kampf 2,

1. 

Institute of Pure Mathematics, Ulm University, Ulm, Germany
2. 

Institute of Communications Engineering, Ulm University, Ulm, Germany

Received  July 2011 Revised  May 2012 Published  November 2012

This paper gives a new approach to decoding Hermite codes using the key equation, avoiding the use of majority voting. Our approach corrects up to $(d_{\min}-1)/2$ errors, and works up to some extent also beyond. We present an efficient implementation of our algorithm based on a Sugiyama-type iterative procedure for computing solutions of a key equation.
Keywords: Hermite codes, Groebner bases., algebraic decoding.
Mathematics Subject Classification: Primary: 14G50; Secondary: 11T7.
Citation: 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
References:
[1]

P. Beelen and T. Høholdt, The decoding of algebraic geometry codes, in "Advances in algebraic geometry codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[2]

D. Cox, J. Little and D. O'Shea, "Using Algebraic Geometry,'' Springer, 1998.  Google Scholar

[3]

I. M. Duursma, Algebraic geometry codes: general theory, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[4]

D. Ehrhard, "Über das Dekodieren algebraisch-geometrischer Codes,'' Dissertation, Universität Düsseldorf, 1991. Google Scholar

[5]

J. I. Farrán, Decoding algebraic geometry codes by the key equation, Finite Field Appl., 6 (2000), 207-217. doi: 10.1006/ffta.1999.0274.  Google Scholar

[6]

G. L. Feng and T. R. N. Rao, Decoding algebraic-geometric codes up to the designed distance, IEEE Trans. Inform. Theory, 39 (1993), 37-45. doi: 10.1109/18.179340.  Google Scholar

[7]

V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR, 259 (1981), 1289-1290.  Google Scholar

[8]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, in "39th Annual Symposium on Foundations of Computer Science,'' 1998.  Google Scholar

[9]

T. Høholdt, J. H. van Lint and R. Pellikaan, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, 41 (1995), 1589-1614. doi: 10.1109/18.476214.  Google Scholar

[10]

T. Høholdt, J. H. van Lint and R. Pellikaan, Algebraic geometry codes, in "Handbook of Coding Theory,'' 1 (1998), 871-961.  Google Scholar

[11]

J. Justesen, K. Larsen, H. Jensen and T. Høholdt, Fast decoding of codes from algebraic plane curves, IEEE Trans. Inform. Theory, 38 (1992), 111-119. doi: 10.1109/18.108255.  Google Scholar

[12]

S. Kampf, Bounds on collaborative decoding of interleaved Hermitian codes with a division algorithm and virtual extension, 3ICMCTA Special Issue of Designs, Codes and Cryptography, accepted, 2012. Google Scholar

[13]

S. Kampf, M. Bossert and S. Bezzateev, Some results on list decoding of interleaved Reed-Solomon codes with the extended euclidean elgorithm, in "Proc. Coding Theory Days in St. Petersburg 2008,'' (2008), 31-36. Google Scholar

[14]

S. Kampf, M. Bossert and I. I. Bouw, Solving the key equation for Hermitian codes with a division algorithm, in "IEEE International Symposium on Information Theory,'' St. Petersburg, (2011), 1008-1012. Google Scholar

[15]

D. A. Leonard, A generalized Forney formula for algebraic-geometric codes, IEEE Trans. Inform. Theory, 42 (1996), 1263-1268. doi: 10.1109/18.508855.  Google Scholar

[16]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland Mathematical Library, 1988. Google Scholar

[17]

M. O'Sullivan and M. Bras-Amorós, The key equation for one-point codes, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[18]

S. C. Porter, B.-Z. Shen and R. Pellikaan, Decoding geometric Goppa codes using an extra place, IEEE Trans. Inform. Theory, 38 (1992), 1663-1676. doi: 10.1109/18.165441.  Google Scholar

[19]

R. M. Roth, "Introduction to Coding Theory,'' Cambridge University Press, 2006. Google Scholar

[20]

S. Sakata, J. Justesen, Y. Madelung, H. Elbrønd and T. Høholdt, Fast decoding of algebraic-geometric codes up to the designed minimum distance, IEEE Trans. Inform. Theory, 41 (1995), 1672-1677. doi: 10.1109/18.476240.  Google Scholar

[21]

B.-Z. Shen, Solving a congruence on a graded algebra by a subresultant sequence and its application, J. Symbolic Comput., 14 (1992), 505-522. doi: 10.1016/0747-7171(92)90020-5.  Google Scholar

[22]

A. Skorobogatov and S. G. Vlăduţ, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, IT-36 (1990), 1051-1060. doi: 10.1109/18.57204.  Google Scholar

[23]

H. Stichenoth, "Algebraic Function Fields and Codes,'' 2nd edition, Springer-Verlag, 2009.  Google Scholar

[24]

M. A. Tsfasman and S. G. Vlăduţ, "Algebraic-Geometric Codes,'' Kluwer Academic Publishers Group, 1991.  Google Scholar

[25]

M. A. Tsfasman and S. G. Vlăduţ and T. Zink, Modular curves, Shimura curves and Goppa codes better than the Varshmov-Gilbert bound, Math. Nachr., 109 (1982), 21-28. doi: 10.1002/mana.19821090103.  Google Scholar

[26]

K. Yang and P. V. Kumar, On the true minimal distance of Hermitian codes, in "Coding Theory and Algebraic Geometry (Luminy, 1991),'' Springer, Berlin, (1992), 99-107. doi: 10.1007/BFb0087995.  Google Scholar

show all references

References:
[1]

P. Beelen and T. Høholdt, The decoding of algebraic geometry codes, in "Advances in algebraic geometry codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[2]

D. Cox, J. Little and D. O'Shea, "Using Algebraic Geometry,'' Springer, 1998.  Google Scholar

[3]

I. M. Duursma, Algebraic geometry codes: general theory, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[4]

D. Ehrhard, "Über das Dekodieren algebraisch-geometrischer Codes,'' Dissertation, Universität Düsseldorf, 1991. Google Scholar

[5]

J. I. Farrán, Decoding algebraic geometry codes by the key equation, Finite Field Appl., 6 (2000), 207-217. doi: 10.1006/ffta.1999.0274.  Google Scholar

[6]

G. L. Feng and T. R. N. Rao, Decoding algebraic-geometric codes up to the designed distance, IEEE Trans. Inform. Theory, 39 (1993), 37-45. doi: 10.1109/18.179340.  Google Scholar

[7]

V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR, 259 (1981), 1289-1290.  Google Scholar

[8]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, in "39th Annual Symposium on Foundations of Computer Science,'' 1998.  Google Scholar

[9]

T. Høholdt, J. H. van Lint and R. Pellikaan, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, 41 (1995), 1589-1614. doi: 10.1109/18.476214.  Google Scholar

[10]

T. Høholdt, J. H. van Lint and R. Pellikaan, Algebraic geometry codes, in "Handbook of Coding Theory,'' 1 (1998), 871-961.  Google Scholar

[11]

J. Justesen, K. Larsen, H. Jensen and T. Høholdt, Fast decoding of codes from algebraic plane curves, IEEE Trans. Inform. Theory, 38 (1992), 111-119. doi: 10.1109/18.108255.  Google Scholar

[12]

S. Kampf, Bounds on collaborative decoding of interleaved Hermitian codes with a division algorithm and virtual extension, 3ICMCTA Special Issue of Designs, Codes and Cryptography, accepted, 2012. Google Scholar

[13]

S. Kampf, M. Bossert and S. Bezzateev, Some results on list decoding of interleaved Reed-Solomon codes with the extended euclidean elgorithm, in "Proc. Coding Theory Days in St. Petersburg 2008,'' (2008), 31-36. Google Scholar

[14]

S. Kampf, M. Bossert and I. I. Bouw, Solving the key equation for Hermitian codes with a division algorithm, in "IEEE International Symposium on Information Theory,'' St. Petersburg, (2011), 1008-1012. Google Scholar

[15]

D. A. Leonard, A generalized Forney formula for algebraic-geometric codes, IEEE Trans. Inform. Theory, 42 (1996), 1263-1268. doi: 10.1109/18.508855.  Google Scholar

[16]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland Mathematical Library, 1988. Google Scholar

[17]

M. O'Sullivan and M. Bras-Amorós, The key equation for one-point codes, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.  Google Scholar

[18]

S. C. Porter, B.-Z. Shen and R. Pellikaan, Decoding geometric Goppa codes using an extra place, IEEE Trans. Inform. Theory, 38 (1992), 1663-1676. doi: 10.1109/18.165441.  Google Scholar

[19]

R. M. Roth, "Introduction to Coding Theory,'' Cambridge University Press, 2006. Google Scholar

[20]

S. Sakata, J. Justesen, Y. Madelung, H. Elbrønd and T. Høholdt, Fast decoding of algebraic-geometric codes up to the designed minimum distance, IEEE Trans. Inform. Theory, 41 (1995), 1672-1677. doi: 10.1109/18.476240.  Google Scholar

[21]

B.-Z. Shen, Solving a congruence on a graded algebra by a subresultant sequence and its application, J. Symbolic Comput., 14 (1992), 505-522. doi: 10.1016/0747-7171(92)90020-5.  Google Scholar

[22]

A. Skorobogatov and S. G. Vlăduţ, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, IT-36 (1990), 1051-1060. doi: 10.1109/18.57204.  Google Scholar

[23]

H. Stichenoth, "Algebraic Function Fields and Codes,'' 2nd edition, Springer-Verlag, 2009.  Google Scholar

[24]

M. A. Tsfasman and S. G. Vlăduţ, "Algebraic-Geometric Codes,'' Kluwer Academic Publishers Group, 1991.  Google Scholar

[25]

M. A. Tsfasman and S. G. Vlăduţ and T. Zink, Modular curves, Shimura curves and Goppa codes better than the Varshmov-Gilbert bound, Math. Nachr., 109 (1982), 21-28. doi: 10.1002/mana.19821090103.  Google Scholar

[26]

K. Yang and P. V. Kumar, On the true minimal distance of Hermitian codes, in "Coding Theory and Algebraic Geometry (Luminy, 1991),'' Springer, Berlin, (1992), 99-107. doi: 10.1007/BFb0087995.  Google Scholar

[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]

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
[3]

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
[4]

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
[5]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[6]

Piotr Pokora, Tomasz Szemberg. Minkowski bases on algebraic surfaces with rational polyhedral pseudo-effective cone. Electronic Research Announcements, 2014, 21: 126-131. doi: 10.3934/era.2014.21.126
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1
[14]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49
[15]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
[16]

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
[17]

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
[18]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[19]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2020, 14 (2) : 265-278. doi: 10.3934/amc.2020019
[20]

Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (91)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences