Syndrome decoding for Hermite codes with a Sugiyama-type algorithm

Previous Article
An algebraic approach for decoding spread codes
AMC Home
This Issue
Next Article
$\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity

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

Abstract
Related Papers

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.
[2]	D. Cox, J. Little and D. O'Shea, "Using Algebraic Geometry,'' Springer, 1998.
[3]	I. M. Duursma, Algebraic geometry codes: general theory, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.
[4]	D. Ehrhard, "Über das Dekodieren algebraisch-geometrischer Codes,'' Dissertation, Universität Düsseldorf, 1991.
[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.
[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.
[7]	V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR, 259 (1981), 1289-1290.
[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.
[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.
[10]	T. Høholdt, J. H. van Lint and R. Pellikaan, Algebraic geometry codes, in "Handbook of Coding Theory,'' 1 (1998), 871-961.
[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.
[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.
[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.
[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.
[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.
[16]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland Mathematical Library, 1988.
[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.
[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.
[19]	R. M. Roth, "Introduction to Coding Theory,'' Cambridge University Press, 2006.
[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.
[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.
[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.
[23]	H. Stichenoth, "Algebraic Function Fields and Codes,'' 2^nd edition, Springer-Verlag, 2009.
[24]	M. A. Tsfasman and S. G. Vlăduţ, "Algebraic-Geometric Codes,'' Kluwer Academic Publishers Group, 1991.
[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.
[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.

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.
[2]	D. Cox, J. Little and D. O'Shea, "Using Algebraic Geometry,'' Springer, 1998.
[3]	I. M. Duursma, Algebraic geometry codes: general theory, in "Advances in Algebraic Geometry Codes, Ser. Coding Theory Cryptol.,'' 5 (2008), 99-152.
[4]	D. Ehrhard, "Über das Dekodieren algebraisch-geometrischer Codes,'' Dissertation, Universität Düsseldorf, 1991.
[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.
[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.
[7]	V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR, 259 (1981), 1289-1290.
[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.
[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.
[10]	T. Høholdt, J. H. van Lint and R. Pellikaan, Algebraic geometry codes, in "Handbook of Coding Theory,'' 1 (1998), 871-961.
[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.
[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.
[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.
[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.
[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.
[16]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland Mathematical Library, 1988.
[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.
[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.
[19]	R. M. Roth, "Introduction to Coding Theory,'' Cambridge University Press, 2006.
[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.
[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.
[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.
[23]	H. Stichenoth, "Algebraic Function Fields and Codes,'' 2^nd edition, Springer-Verlag, 2009.
[24]	M. A. Tsfasman and S. G. Vlăduţ, "Algebraic-Geometric Codes,'' Kluwer Academic Publishers Group, 1991.
[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.
[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.

[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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Irene I. Bouw Sabine Kampf
on Google Scholar
Irene I. Bouw Sabine Kampf

[Back to Top]