A module minimization approach to Gabidulin decoding via interpolation
Keywords:
Gabidulin codes, Linearized polynomials, Interpolation, Minimal basis, Parametrization, Polynomial modules, Rank metric, Iterative algorithm
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.
References
S. Abramov, M. Bronstein, Linear algebra for skew–polynomial matrices, Technical Report INRIA, RR–4420, 2002.
W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, volume 3 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1994.
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.
B. Beckermann, H. Cheng, G. Labahn, Fraction–free row reduction of matrices of Ore polynomials, J. Symbolic Comput. 41(5) (2006) 513–543.
D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics, Springer, New York, second edition, 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, Problemy Peredachi Informatsii, 21(1) (1985) 3–16.
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.
A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
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.
R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge, London, 1997.
P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In Coding and cryptography, Lecture Notes in Computer Science 3969 (2006) 36–45.
O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
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.
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.
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.
D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
D. Silva, 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, 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, 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, B. W. Suter, General linearized polynomial interpolation and its applications, International Symposium on Network Coding (NetCod) proceedings (2011) 1–4.
W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, volume 3 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1994.
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.
B. Beckermann, H. Cheng, G. Labahn, Fraction–free row reduction of matrices of Ore polynomials, J. Symbolic Comput. 41(5) (2006) 513–543.
D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics, Springer, New York, second edition, 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, Problemy Peredachi Informatsii, 21(1) (1985) 3–16.
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.
A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9(1) (1990) 1–26.
R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54(8) (2008) 3579–3591.
M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property, Linear Algebra Appl. 434(1) (2011) 104–116.
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.
R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge, London, 1997.
P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In Coding and cryptography, Lecture Notes in Computer Science 3969 (2006) 36–45.
O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
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.
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.
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.
D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
D. Silva, 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, 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, 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, B. W. Suter, General linearized polynomial interpolation and its applications, International Symposium on Network Coding (NetCod) proceedings (2011) 1–4.
