×

Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. (English) Zbl 1402.94120

Summary: An interpolation-based decoding scheme for \(L\)-interleaved subspace codes is presented. The scheme can be used as a (not necessarily polynomial-time) list decoder as well as a polynomial-time probabilistic unique decoder. Both interpretations allow to decode interleaved subspace codes beyond half the minimum subspace distance. Both schemes can decode \(\gamma\) insertions and \(\delta\) deletions up to \(\gamma +L\delta \leq L(n_{t}-k)\), where \(n_{t}\) is the dimension of the transmitted subspace and \(k\) is the number of data symbols from the field \(\mathbb{F}_{q^{m}}\). Further, a complementary decoding approach is presented which corrects \(\gamma\) insertions and \(\delta\) deletions up to \(L\gamma +\delta \leq L(n_{t}-k)\). Both schemes use properties of minimal Gröebner bases for the interpolation module that allow predicting the worst-case list size right after the interpolation step. An efficient procedure for constructing the required minimal Gröebner basis using the general Kötter interpolation is presented. A computationally- and memory-efficient root-finding algorithm for the probabilistic unique decoder is proposed. The overall complexity of the decoding algorithm is at most \(\mathcal{O}(L^{2}n_{r}^{2})\) operations in \(\mathbb{F}_{q^{m}}\) where \(n_{r}\) is the dimension of the received subspace and \(L\) is the interleaving order. The analysis as well as the efficient algorithms can also be applied for accelerating the decoding of interleaved Gabidulin codes.

MSC:

94B35 Decoding
94B05 Linear codes (general theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, 3, American Mathematical Soc., 1994. · Zbl 0803.13015
[2] C. Bachoc; F. Vallentin; A. Passuello, Bounds for Projective Codes from Semidefinite Programming, Adv. Math. Commun., 7, 127-145 (2013) · Zbl 1317.94164 · doi:10.3934/amc.2013.7.127
[3] H. Bartz, Algebraic Decoding of Subspace and Rank-Metric Codes, PhD thesis, Technical University of Munich, 2017.
[4] H. Bartz, M. Meier and V. Sidorenko, Improved Syndrome Decoding of Interleaved Subspace Codes, in 11th International ITG Conference on Systems, Communications and Coding 2017 (SCC), Hamburg, Germany, 2017.
[5] H. Bartz and V. Sidorenko, List and probabilistic unique decoding of folded subspace codes in IEEE International Symposium on Information Theory (ISIT), 2015.
[6] H. Bartz and V. Sidorenko, On list-decoding schemes for punctured reed-solomon, Gabidulin and subspace codes in XV International Symposium “Problems of Redundancy in Information and Control Systems”, 2016.
[7] H. Bartz and A. Wachter-Zeh, Efficient interpolation-based decoding of interleaved subspace and Gabidulin codes, in 52nd Annual Allerton Conference on Communication, Control, and Computing, 2014, 1349-1356.
[8] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, vol. 3, Springer, 1992.
[9] P. Delsarte, Bilinear forms over a finite field with applications to coding theory, J. Combin. Theory, 25, 226-241 (1978) · Zbl 0397.94012 · doi:10.1016/0097-3165(78)90015-8
[10] T. Etzion; N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inf. Theory, 55, 2909-2919 (2009) · Zbl 1367.94414 · doi:10.1109/TIT.2009.2021376
[11] T. Etzion; A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inf. Theory, 57, 1165-1173 (2011) · Zbl 1366.94589 · doi:10.1109/TIT.2010.2095232
[12] T. Etzion; E. Gorla; A. Ravagnani; A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 62, 1616-1630 (2016) · Zbl 1359.94794 · doi:10.1109/TIT.2016.2522971
[13] E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21, 3-16 (1985) · Zbl 0585.94013
[14] M. Gadouleau; Z. Yan, Constant-rank codes and their connection to constant-dimension codes, IEEE Trans. Inf. Theory, 56, 3207-3216 (2010) · Zbl 1366.94591 · doi:10.1109/TIT.2010.2048447
[15] V. Guruswami and C. Xing, List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound, STOC’13??Proceedings of the 2013 ACM Symposium on Theory of Computing, 843-852, ACM, New York, 2013. · Zbl 1293.94110
[16] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013. · Zbl 1267.15001
[17] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, vol. 5393 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008, 31-42. · Zbl 1178.94239
[18] R. Kötter; F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inf. Theory, 54, 3579-3591 (2008) · Zbl 1318.94111 · doi:10.1109/TIT.2008.926449
[19] M. Kuijper and A. Trautmann, Gröbner bases for linearized polynomials, URL <a href=http://arXiv.org/abs/1406.4600“ target=”_blank”>http://arXiv.org/abs/1406.4600.
[20] W. Li; V. Sidorenko; D. Silva, On transform-domain error and erasure correction by Gabidulin codes, Des. Codes Cryptogr., 73, 571-586 (2014) · Zbl 1335.94097 · doi:10.1007/s10623-014-9954-4
[21] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1997.
[22] P. Loidreau and R. Overbeck, Decoding rank errors beyond the error correcting capability, in Int. Workshop Alg. Combin. Coding Theory (ACCT), 2006,186-190.
[23] H. Mahdavifar and A. Vardy, Algebraic list-decoding on the operator channel, in IEEE Int. Symp. Inf. Theory (ISIT), 2010, 1193-1197.
[24] H. Mahdavifar and A. Vardy, List-Decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound, in IEEE Int. Symp. Inf. Theory (ISIT), 2012, 1488-1492.
[25] J. N. Nielsen, List Decoding of Algebraic Codes, PhD thesis, 2013.
[26] ∅. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35, 559-584 (1933) · JFM 59.0163.02 · doi:10.1090/S0002-9947-1933-1501703-0
[27] S. Puchinger, J. S. R. Nielsen, W. Li and V. Sidorenko, Row reduction applied to decoding of rank metric and subspace codes, Designs, Codes and Cryptography, 82 (2017), 389-409, URL http://arXiv.org/abs/1510.04728v2. · Zbl 1402.94092
[28] N. Raviv; A. Wachter-Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory, 62, 1605-1615 (2016) · Zbl 1359.94867 · doi:10.1109/TIT.2016.2532343
[29] R. M. Roth, Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inf. Theory, 37, 328-336 (1991) · Zbl 0721.94012 · doi:10.1109/18.75248
[30] V. R. Sidorenko and M. Bossert, Decoding interleaved Gabidulin codes and multisequence linearized shift-register synthesis, in IEEE Int. Symp. Inf. Theory (ISIT), 2010, 1148-1152.
[31] V. R. Sidorenko; L. Jiang; M. Bossert, Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes, IEEE Trans. Inf. Theory, 57, 621-632 (2011) · Zbl 1366.94681 · doi:10.1109/TIT.2010.2096032
[32] D. Silva, Error Control for Network Coding, PhD thesis, University of Toronto, Toronto, Canada, 2009.
[33] D. Silva; F. R. Kschischang; R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inf. Theory, 54, 3951-3967 (2008) · Zbl 1318.94119 · doi:10.1109/TIT.2008.928291
[34] V. Skachek, Recursive code construction for random networks, IEEE Trans. Inf. Theory, 56, 1378-1382 (2010) · Zbl 1366.94750 · doi:10.1109/TIT.2009.2039163
[35] A. L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - A new concept in the area of network coding in IEEE Information Theory Workshop 2019 (ITW 2012), 2010.
[36] A.-L. Trautmann and M. Kuijper, Gabidulin decoding via minimal bases of linearized polynomial modules, preprint, arXiv: 1408.2303.
[37] A.-L. Trautmann, N. Silberstein and J. Rosenthal, List decoding of lifted Gabidulin codes via the Plücker embedding, in Int. Workshop Coding Cryptogr. (WCC), 2013.
[38] A. Wachter-Zeh, Bounds on list decoding of rank-metric codes, IEEE Trans. Inf. Theory, 59, 7268-7277 (2013) · Zbl 1364.94731 · doi:10.1109/TIT.2013.2274653
[39] A. Wachter-Zeh; A. Zeh, List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques, Des. Codes Cryptogr., 73, 547-570 (2014) · Zbl 1335.94104 · doi:10.1007/s10623-014-9953-5
[40] B. Wang, R. J. McEliece and K. Watanabe, Kötter interpolation over free modules, in Proc. 43rd Annu. Allerton Conf. Comm., Control, and Comp., 2005.
[41] S. Xia; F. Fu, Johnson type bounds on constant dimension codes, Des. Codes Cryptogr., 50, 163-172 (2009) · Zbl 1237.94151 · doi:10.1007/s10623-008-9221-7
[42] H. Xie, Z. Yan and B. W. Suter, General linearized polynomial interpolation and its applications, in IEEE Int. Symp. Network Coding (Netcod), 2011, 1-4.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.