A module minimization approach to Gabidulin decoding via interpolation
Keywords:
Gabidulin codes, Linearized polynomials, Interpolation, Minimal basis, Parametrization, Polynomial modules, Rank metric, Iterative algorithmAbstract
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.
Downloads
References
S. Abramov and M. Bronstein, Linear algebra for skew–polynomial matrices, Research Report INRIA, RR-4420, 2002.
W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, Providence, RI, 1994.
M. Ali and M. Kuijper, A parametric approach to list decoding of Reed–Solomon codes using interpolation, IEEE Trans. Inform. Theory 57(10) (2011) 6718–6728.
B. Beckermann, H. Cheng, and G. Labahn, Fraction–free row reduction of matrices of Ore polynomials, J. Symbolic Comput. 41(5) (2006) 513–543.
D. A. Cox, J. Little, and D. O’Shea, Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185, 2nd ed., Springer, New York, 2005.
P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A 25(3) (1978) 226–241.
P. Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory 41(5) (1995) 1290–1302.
G. D. Forney Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control 13(3) (1975) 493–520.
E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm. 21(1) (1985) 1–12.
E. M. Gabidulin, A fast matrix decoding algorithm for rank–error–correcting codes, In: G. Cohen et al. (Eds.), Algebraic Coding, Lecture Notes in Comput. Sci., vol. 573, Springer, Berlin, Heidelberg (1992) 126–133.
A. Kandri–Rody and V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
M. Kuijper and K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
M. Kuijper and A.–L. Trautmann, Iterative list–decoding of Gabidulin codes via Gröbner based interpolation, In: 2014 IEEE Information Theory Workshop (ITW 2014), Hobart, TAS, Australia (2014) 581–585.
R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20, 2nd ed., Cambridge University Press, Cambridge, 1997.
P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In: N. Sendrier (Ed.), Coding and Cryptography, Lecture Notes in Comput. Sci., vol. 3969, Springer, Berlin, Heidelberg (2006) 36–45.
O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
N. Raviv and A. Wachter–Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory 62(4) (2016) 1605–1615.
G. Richter and S. Plass, Fast decoding of rank–codes with rank errors and column erasures, In: Proc. 2004 IEEE International Symposium on Information Theory (ISIT), Chicago, IL (2004) 398.
N. Silberstein, A. S. Rawat, and S. Vishwanath, Error resilience in distributed storage via rank–metric codes, In: 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL (2012) 1150–1157.
D. Silva and F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, In: 2009 IEEE International Symposium on Information Theory (ISIT), Seoul, Korea (2009) 2858–2862.
D. Silva and F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory 55(12) (2009) 5479–5490.
D. Silva, F. R. Kschischang, and R. Koetter, A rank–metric approach to error control in random network coding, IEEE Trans. Inform. Theory 54(9) (2008) 3951–3967.
A. Wachter–Zeh, Bounds on list decoding of rank–metric codes, IEEE Trans. Inform. Theory 59(11) (2013) 7268–7277.
A. Wachter–Zeh, V. Afanassiev, and V. Sidorenko, Fast decoding of Gabidulin codes, Des. Codes Cryptogr. 66(1–3) (2013) 57–73.
Y. Wu, New list decoding algorithms for Reed–Solomon and BCH codes, IEEE Trans. Inform. Theory 54(8) (2008) 3611–3630.
H. Xie, Z. Yan, and B. W. Suter, General linearized polynomial interpolation and its applications, In: 2011 International Symposium on Network Coding (NetCod), Beijing, China (2011) 1–4.
