Year 2018, Volume 5 , Issue 1, Pages 29 - 43 2018-01-15

A module minimization approach to Gabidulin decoding via interpolation

Anna-Lena Horlemann-Trautmann [1] , Margreta Kuijper [2]


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.
Gabidulin codes, Linearized polynomials, Interpolation, Minimal basis, Parametrization, Polynomial modules, Rank metric, Iterative algorithm
  • [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.
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0003-2685-2343
Author: Anna-Lena Horlemann-Trautmann

Orcid: 0000-0001-9223-9550
Author: Margreta Kuijper (Primary Author)

Dates

Publication Date : January 15, 2018

Bibtex @research article { jacodesmath369863, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2018}, volume = {5}, pages = {29 - 43}, doi = {10.13069/jacodesmath.369863}, title = {A module minimization approach to Gabidulin decoding via interpolation}, key = {cite}, author = {Horlemann-trautmann, Anna-Lena and Kuijper, Margreta} }
APA Horlemann-trautmann, A , Kuijper, M . (2018). A module minimization approach to Gabidulin decoding via interpolation . Journal of Algebra Combinatorics Discrete Structures and Applications , 5 (1) , 29-43 . DOI: 10.13069/jacodesmath.369863
MLA Horlemann-trautmann, A , Kuijper, M . "A module minimization approach to Gabidulin decoding via interpolation" . Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018 ): 29-43 <https://dergipark.org.tr/en/pub/jacodesmath/issue/33304/369863>
Chicago Horlemann-trautmann, A , Kuijper, M . "A module minimization approach to Gabidulin decoding via interpolation". Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018 ): 29-43
RIS TY - JOUR T1 - A module minimization approach to Gabidulin decoding via interpolation AU - Anna-Lena Horlemann-trautmann , Margreta Kuijper Y1 - 2018 PY - 2018 N1 - doi: 10.13069/jacodesmath.369863 DO - 10.13069/jacodesmath.369863 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 29 EP - 43 VL - 5 IS - 1 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.369863 UR - https://doi.org/10.13069/jacodesmath.369863 Y2 - 2017 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications A module minimization approach to Gabidulin decoding via interpolation %A Anna-Lena Horlemann-trautmann , Margreta Kuijper %T A module minimization approach to Gabidulin decoding via interpolation %D 2018 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 5 %N 1 %R doi: 10.13069/jacodesmath.369863 %U 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
AMA Horlemann-trautmann A , Kuijper M . A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018; 5(1): 29-43.
Vancouver Horlemann-trautmann A , Kuijper M . A module minimization approach to Gabidulin decoding via interpolation. Journal of Algebra Combinatorics Discrete Structures and Applications. 2018; 5(1): 29-43.

Authors of the Article
Anna-Lena Horlemann-Trautmann [1]
Margreta Kuijper [2]