A module minimization approach to Gabidulin decoding via interpolation

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. [1] S. Abramov, M. Bronstein, Linear algebra for skew–polynomial matrices, Technical Report INRIA, RR–4420, 2002.
2. [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. [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. [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. [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. [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. [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.
8. [9] E. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21(1) (1985) 3–16.

9. [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.
10. [11] A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
11. [12] R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
12. [13] M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
13. [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.
14. [15] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge, London, 1997.
15. [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.
16. [17] O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
17. [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.
18. [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.
19. [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.
20. [21] D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
21. [22] D. Silva, F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory 55(12) (2009) 5479–5490.
22. [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.
23. [24] A. Wachter–Zeh, Bounds on list decoding of rank–metric codes, IEEE Trans. Inform. Theory 59(11) (2013) 7268–7277.
24. [25] A. Wachter–Zeh, V. Afanassiev, V. Sidorenko, Fast decoding of Gabidulin codes, Des. Codes Cryptogr. 66(1–3) (2013) 57–73.
25. [26] Y.Wu, New list decoding algorithms for Reed–Solomon and BCH codes, IEEE Trans. Inform. Theory 54(8) (2008) 3611–3630.
26. [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.