Research Article
BibTex RIS Cite

Year 2018, , 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, , 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 Articles
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

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 (January 2018), 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.