Research Article
BibTex RIS Cite

Year 2018, Volume: 5 Issue: 1, 29 - 43, 15.01.2018

Anna-Lena Horlemann-trautmann Margreta Kuijper

https://doi.org/10.13069/jacodesmath.369863

Abstract

References

  • [1] S. Abramov, M. Bronstein, Linear algebra for skew–polynomial matrices, Technical Report INRIA, RR–4420, 2002.
  • [2] W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, volume 3 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1994.
  • [3] M. Ali, M. Kuijper, A parametric approach to list decoding of Reed–Solomon codes using interpolation, IEEE Trans. Inform. Theory 57(10) (2011) 6718–6728.
  • [4] B. Beckermann, H. Cheng, G. Labahn, Fraction–free row reduction of matrices of Ore polynomials, J. Symbolic Comput. 41(5) (2006) 513–543.
  • [5] D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics, Springer, New York, second edition, 2005.
  • [6] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A 25(3) (1978) 226–241.
  • [7] P. Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory 41(5) (1995) 1290–1302. [8] G. D. Forney, Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control 13(3) (1975) 493–520.
  • [9] E. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21(1) (1985) 3–16.
  • [10] E. M. Gabidulin, A fast matrix decoding algorithm for rank–error–correcting codes, In Algebraic coding (Paris, 1991), Lecture Notes in Computer Science, 573 (1992) 126–133.
  • [11] A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
  • [12] R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
  • [13] M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
  • [14] M. Kuijper, A.–L. Trautmann, Iterative list–decoding of Gabidulin codes via Gröbner based interpolation, In IEEE Information Theory Workshop (ITW 2014), Hobart, TAS, 2014, 581–585.
  • [15] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge, London, 1997.
  • [16] P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In Coding and cryptography, Lecture Notes in Computer Science 3969 (2006) 36–45.
  • [17] O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
  • [18] N. Raviv, A. Wachter–Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory 62(4) (2016) 1605–1615.
  • [19] G. Richter, S. Plass, Fast decoding of rank–codes with rank errors and column erasures, IEEE International Symposium on Information Theory (ISIT) proceedings (2004) 398–398.
  • [20] N. Silberstein, A. S. Rawat, S. Vishwanath, Error resilience in distributed storage via rank–metric codes, In Fiftieth Annual Allerton conference, UIUC, Illinois, USA, (2012) 1150–1157.
  • [21] D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
  • [22] D. Silva, F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory 55(12) (2009) 5479–5490.
  • [23] D. Silva, F. R. Kschischang, R. Koetter, A rank–metric approach to error control in random network coding, IEEE Trans. Inform. Theory 54(9) (2008) 3951 –3967.
  • [24] A. Wachter–Zeh, Bounds on list decoding of rank–metric codes, IEEE Trans. Inform. Theory 59(11) (2013) 7268–7277.
  • [25] A. Wachter–Zeh, V. Afanassiev, V. Sidorenko, Fast decoding of Gabidulin codes, Des. Codes Cryptogr. 66(1–3) (2013) 57–73.
  • [26] Y.Wu, New list decoding algorithms for Reed–Solomon and BCH codes, IEEE Trans. Inform. Theory 54(8) (2008) 3611–3630.
  • [27] H. Xie, Z. Yan, B. W. Suter, General linearized polynomial interpolation and its applications, International Symposium on Network Coding (NetCod) proceedings (2011) 1–4.

A module minimization approach to Gabidulin decoding via interpolation

Year 2018, Volume: 5 Issue: 1, 29 - 43, 15.01.2018

Anna-Lena Horlemann-trautmann Margreta Kuijper

https://doi.org/10.13069/jacodesmath.369863

Abstract

We focus on iterative interpolation-based decoding of Gabidulin codes and present an algorithm that computes a minimal basis for an interpolation module.
We extend existing results for Reed-Solomon codes in showing that this minimal basis gives rise to a parametrization of elements in the module that lead to all Gabidulin decoding solutions that are at a fixed distance from the received word. Our module-theoretic approach strengthens the link between Gabidulin decoding and Reed-Solomon decoding, thus providing a basis for further work into Gabidulin list decoding.

Keywords

Gabidulin codes Linearized polynomials Interpolation Minimal basis Parametrization Polynomial modules Rank metric Iterative algorithm

References

  • [1] S. Abramov, M. Bronstein, Linear algebra for skew–polynomial matrices, Technical Report INRIA, RR–4420, 2002.
  • [2] W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, volume 3 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1994.
  • [3] M. Ali, M. Kuijper, A parametric approach to list decoding of Reed–Solomon codes using interpolation, IEEE Trans. Inform. Theory 57(10) (2011) 6718–6728.
  • [4] B. Beckermann, H. Cheng, G. Labahn, Fraction–free row reduction of matrices of Ore polynomials, J. Symbolic Comput. 41(5) (2006) 513–543.
  • [5] D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics, Springer, New York, second edition, 2005.
  • [6] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A 25(3) (1978) 226–241.
  • [7] P. Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory 41(5) (1995) 1290–1302. [8] G. D. Forney, Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control 13(3) (1975) 493–520.
  • [9] E. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21(1) (1985) 3–16.
  • [10] E. M. Gabidulin, A fast matrix decoding algorithm for rank–error–correcting codes, In Algebraic coding (Paris, 1991), Lecture Notes in Computer Science, 573 (1992) 126–133.
  • [11] A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
  • [12] R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
  • [13] M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
  • [14] M. Kuijper, A.–L. Trautmann, Iterative list–decoding of Gabidulin codes via Gröbner based interpolation, In IEEE Information Theory Workshop (ITW 2014), Hobart, TAS, 2014, 581–585.
  • [15] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge, London, 1997.
  • [16] P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In Coding and cryptography, Lecture Notes in Computer Science 3969 (2006) 36–45.
  • [17] O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
  • [18] N. Raviv, A. Wachter–Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory 62(4) (2016) 1605–1615.
  • [19] G. Richter, S. Plass, Fast decoding of rank–codes with rank errors and column erasures, IEEE International Symposium on Information Theory (ISIT) proceedings (2004) 398–398.
  • [20] N. Silberstein, A. S. Rawat, S. Vishwanath, Error resilience in distributed storage via rank–metric codes, In Fiftieth Annual Allerton conference, UIUC, Illinois, USA, (2012) 1150–1157.
  • [21] D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
  • [22] D. Silva, F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory 55(12) (2009) 5479–5490.
  • [23] D. Silva, F. R. Kschischang, R. Koetter, A rank–metric approach to error control in random network coding, IEEE Trans. Inform. Theory 54(9) (2008) 3951 –3967.
  • [24] A. Wachter–Zeh, Bounds on list decoding of rank–metric codes, IEEE Trans. Inform. Theory 59(11) (2013) 7268–7277.
  • [25] A. Wachter–Zeh, V. Afanassiev, V. Sidorenko, Fast decoding of Gabidulin codes, Des. Codes Cryptogr. 66(1–3) (2013) 57–73.
  • [26] Y.Wu, New list decoding algorithms for Reed–Solomon and BCH codes, IEEE Trans. Inform. Theory 54(8) (2008) 3611–3630.
  • [27] H. Xie, Z. Yan, B. W. Suter, General linearized polynomial interpolation and its applications, International Symposium on Network Coding (NetCod) proceedings (2011) 1–4.
There are 26 citations in total.

Details

Subjects Engineering
Journal Section Research Article
Authors

Anna-Lena Horlemann-trautmann This is me 0000-0003-2685-2343

Margreta Kuijper This is me 0000-0001-9223-9550

Publication Date January 15, 2018
Published in Issue Year 2018 Volume: 5 Issue: 1

Cite

APA Horlemann-trautmann, A.-L., & Kuijper, M. (2018). A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications, 5(1), 29-43. https://doi.org/10.13069/jacodesmath.369863
AMA Horlemann-trautmann AL, Kuijper M. A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications. January 2018;5(1):29-43. doi:10.13069/jacodesmath.369863
Chicago Horlemann-trautmann, Anna-Lena, and Margreta Kuijper. “A Module Minimization Approach to Gabidulin Decoding via Interpolation”. Journal of Algebra Combinatorics Discrete Structures and Applications 5, no. 1 (January 2018): 29-43. https://doi.org/10.13069/jacodesmath.369863.
EndNote Horlemann-trautmann A-L, Kuijper M (January 1, 2018) A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications 5 1 29–43.
IEEE A.-L. Horlemann-trautmann and M. Kuijper, “A module minimization approach to Gabidulin decoding via interpolation”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 5, no. 1, pp. 29–43, 2018, doi: 10.13069/jacodesmath.369863.
ISNAD Horlemann-trautmann, Anna-Lena - Kuijper, Margreta. “A Module Minimization Approach to Gabidulin Decoding via Interpolation”. Journal of Algebra Combinatorics Discrete Structures and Applications 5/1 (January2018), 29-43. https://doi.org/10.13069/jacodesmath.369863.
JAMA Horlemann-trautmann A-L, Kuijper M. A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018;5:29–43.
MLA Horlemann-trautmann, Anna-Lena and Margreta Kuijper. “A Module Minimization Approach to Gabidulin Decoding via Interpolation”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 5, no. 1, 2018, pp. 29-43, doi:10.13069/jacodesmath.369863.
Vancouver Horlemann-trautmann A-L, Kuijper M. A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018;5(1):29-43.