Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases

Hannes Bartz; Antonia Wachter-Zeh

doi:10.3934/amc.2018046

Previous Article
On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients
AMC Home
This Issue
Next Article
Higher weights and near-MDR codes over chain rings

November 2018, 12(4): 773-804. doi: 10.3934/amc.2018046

Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases

Hannes Bartz ^1, and Antonia Wachter-Zeh ^2,

1.	Institute of Communications and Navigation, German Aerospace Center (DLR), D-82234 Oberpfaffenhofen, Germany
2.	Institute for Communications Engineering, Technical University of Munich (TUM), D-80290 Munich, Germany

Received February 2018 Published September 2018

Fund Project: A. Wachter-Zeh's work was supported by the Technical University of Munich|Institute for Advanced Study, funded by the German Excellence Initiative and European Union Seventh Framework Programme under Grant Agreement No. 291763 and the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) unter Grant No. WA3907/1-1.

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}\left( {{L}^{2}}n_{r}^{2} \right)$ 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.

Keywords: Subspace codes, rank-metric codes, interleaved Gabidulin codes, probabilistic unique decoding, interpolation-based decoding.

Mathematics Subject Classification: Primary: 94B35, 94B05.

Citation: Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

References:

[1]	W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, 3, American Mathematical Soc., 1994. doi: 10.1090/gsm/003.
[2]	C. Bachoc, F. Vallentin and A. Passuello, Bounds for Projective Codes from Semidefinite Programming, Adv. Math. Commun., 7 (2013), 127-145. 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. doi: 10.1109/ISIT.2015.7282407.
[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. doi: 10.1109/RED.2016.7779321.
[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. doi: 10.1109/ALLERTON.2014.7028612.
[8]	D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms, vol. 3, Springer, 1992. doi: 10.1007/978-1-4757-2181-2.
[9]	P. Delsarte, Bilinear forms over a finite field with applications to coding theory, J. Combin. Theory, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.
[10]	T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inf. Theory, 55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376.
[11]	T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inf. Theory, 57 (2011), 1165-1173. doi: 10.1109/TIT.2010.2095232.
[12]	T. Etzion, E. Gorla, A. Ravagnani and A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 62 (2016), 1616-1630. doi: 10.1109/TIT.2016.2522971.
[13]	E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 3-16.
[14]	M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes, IEEE Trans. Inf. Theory, 56 (2010), 3207-3216. 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. doi: 10.1145/2488608.2488715.
[16]	R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.
[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. doi: 10.1007/978-3-540-89994-5_4.
[18]	R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inf. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.
[19]	M. Kuijper and A. Trautmann, Gröbner bases for linearized polynomials, URL http://arXiv.org/abs/1406.4600.
[20]	W. Li, V. Sidorenko and D. Silva, On transform-domain error and erasure correction by Gabidulin codes, Des. Codes Cryptogr., 73 (2014), 571-586. 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. doi: 10.1109/ISIT.2010.5513656.
[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 (1933), 559-584. 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. doi: 10.1007/s10623-016-0257-9.
[28]	N. Raviv and A. Wachter-Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory, 62 (2016), 1605-1615. 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 (1991), 328-336. 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. doi: 10.1109/ISIT.2010.5513676.
[31]	V. R. Sidorenko, L. Jiang and M. Bossert, Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes, IEEE Trans. Inf. Theory, 57 (2011), 621-632. 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 and R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inf. Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.
[34]	V. Skachek, Recursive code construction for random networks, IEEE Trans. Inf. Theory, 56 (2010), 1378-1382. 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. doi: 10.1109/CIG.2010.5592788.
[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 (2013), 7268-7277. doi: 10.1109/TIT.2013.2274653.
[39]	A. Wachter-Zeh and A. Zeh, List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques, Des. Codes Cryptogr., 73 (2014), 547-570. 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 and F. Fu, Johnson type bounds on constant dimension codes, Des. Codes Cryptogr., 50 (2009), 163-172. 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. doi: 10.1109/ISNETCOD.2011.5978942.

show all references

References:

[1]	W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, 3, American Mathematical Soc., 1994. doi: 10.1090/gsm/003.
[2]	C. Bachoc, F. Vallentin and A. Passuello, Bounds for Projective Codes from Semidefinite Programming, Adv. Math. Commun., 7 (2013), 127-145. 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. doi: 10.1109/ISIT.2015.7282407.
[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. doi: 10.1109/RED.2016.7779321.
[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. doi: 10.1109/ALLERTON.2014.7028612.
[8]	D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms, vol. 3, Springer, 1992. doi: 10.1007/978-1-4757-2181-2.
[9]	P. Delsarte, Bilinear forms over a finite field with applications to coding theory, J. Combin. Theory, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.
[10]	T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inf. Theory, 55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376.
[11]	T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inf. Theory, 57 (2011), 1165-1173. doi: 10.1109/TIT.2010.2095232.
[12]	T. Etzion, E. Gorla, A. Ravagnani and A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 62 (2016), 1616-1630. doi: 10.1109/TIT.2016.2522971.
[13]	E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 3-16.
[14]	M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes, IEEE Trans. Inf. Theory, 56 (2010), 3207-3216. 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. doi: 10.1145/2488608.2488715.
[16]	R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.
[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. doi: 10.1007/978-3-540-89994-5_4.
[18]	R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inf. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.
[19]	M. Kuijper and A. Trautmann, Gröbner bases for linearized polynomials, URL http://arXiv.org/abs/1406.4600.
[20]	W. Li, V. Sidorenko and D. Silva, On transform-domain error and erasure correction by Gabidulin codes, Des. Codes Cryptogr., 73 (2014), 571-586. 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. doi: 10.1109/ISIT.2010.5513656.
[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 (1933), 559-584. 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. doi: 10.1007/s10623-016-0257-9.
[28]	N. Raviv and A. Wachter-Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius, IEEE Trans. Inform. Theory, 62 (2016), 1605-1615. 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 (1991), 328-336. 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. doi: 10.1109/ISIT.2010.5513676.
[31]	V. R. Sidorenko, L. Jiang and M. Bossert, Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes, IEEE Trans. Inf. Theory, 57 (2011), 621-632. 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 and R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inf. Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.
[34]	V. Skachek, Recursive code construction for random networks, IEEE Trans. Inf. Theory, 56 (2010), 1378-1382. 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. doi: 10.1109/CIG.2010.5592788.
[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 (2013), 7268-7277. doi: 10.1109/TIT.2013.2274653.
[39]	A. Wachter-Zeh and A. Zeh, List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques, Des. Codes Cryptogr., 73 (2014), 547-570. 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 and F. Fu, Johnson type bounds on constant dimension codes, Des. Codes Cryptogr., 50 (2009), 163-172. 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. doi: 10.1109/ISNETCOD.2011.5978942.

Figure 1. Decoding region for the Kötter-Kschischang [18] decoder $(L = 1)$ and for list decoding a homogeneous interleaved KK subspace code with $(L = 4)$. Both codes have minimum subspace distance ${{d}_{s}} = 8$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. Decoding region for Kötter-Kschischang [18] codes $(L = 1)$ and for probabilistic unique decoding of $(L = 4)$-interleaved KK subspace codes. Both codes have minimum subspace distance ${{d}_{s}} = 8$. The decoding region for insertions increases with the interleaving order $L$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3. Simulation results and upper bounds on $P_f$ of the probabilistic-unique decoder with parameters $m = {{n}_{t}} = 6, k = 2, L = 2$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4. Multiplications vs. the number of insertions for $L = 4$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Number of multiplications for root-finding step for different interleaving orders L. The complexity of the recursive GE is independent of $\gamma $

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6. Memory requirements of the root-finding step for ${{n}_{t}} = 80, k = 60$

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. Simulation results of the probabilistic-unique decoder with parameters $m = {{n}_{t}} = 6, k = 2$ and $L = 2$

$\gamma + L\delta $	$\gamma $	$\delta $	Transmissions	Observed dec. failures	Simulated $P_{f}$
8	8	0	$1.2\cdot10^{6}$	18749	$1.56\cdot10^{-2}$
	6	1	$4.0\cdot10^{5}$	6202	$1.55\cdot10^{-2}$
7	7	0	$4.4\cdot10^{6}$	1025	$2.33\cdot10^{-4}$
	5	1	$6.0\cdot10^{5}$	144	$2.40\cdot10^{-4}$
6	6	0	$9.0\cdot10^{6}$	21	$2.33\cdot10^{-6}$
	4	1	$3.4\cdot10^{6}$	17	$5.00\cdot10^{-6}$
5	5	0	$3.2\cdot10^{6}$	750	$2.33\cdot10^{-4}$
	3	1	$8.0\cdot10^{5}$	184	$2.30\cdot10^{-4}$
4	4	0	$4.4\cdot10^{6}$	21	$4.77\cdot10^{-6}$
	2	1	$1.6\cdot10^{6}$	0	$0$

Table Options

Download as excel

$\gamma + L\delta $	$\gamma $	$\delta $	Transmissions	Observed dec. failures	Simulated $P_{f}$
8	8	0	$1.2\cdot10^{6}$	18749	$1.56\cdot10^{-2}$
	6	1	$4.0\cdot10^{5}$	6202	$1.55\cdot10^{-2}$
7	7	0	$4.4\cdot10^{6}$	1025	$2.33\cdot10^{-4}$
	5	1	$6.0\cdot10^{5}$	144	$2.40\cdot10^{-4}$
6	6	0	$9.0\cdot10^{6}$	21	$2.33\cdot10^{-6}$
	4	1	$3.4\cdot10^{6}$	17	$5.00\cdot10^{-6}$
5	5	0	$3.2\cdot10^{6}$	750	$2.33\cdot10^{-4}$
	3	1	$8.0\cdot10^{5}$	184	$2.30\cdot10^{-4}$
4	4	0	$4.4\cdot10^{6}$	21	$4.77\cdot10^{-6}$
	2	1	$1.6\cdot10^{6}$	0	$0$

Table 2. Comparison of different decoding schemes for interleaved KK subspace codes

Decoding scheme	Decoding region	Op. in ${{\mathbb{F}}_{{{q}^{m}}}}$
Li-Sidorenko-Silva [20,31]	$(L+1)t+L\varkappa+L\rho\leq L({{n}_{t}}-k)$	$ \mathcal{O}\left( Ln_{t}^{2} \right) \phantom{{}^{2}}$
Wachter-Zeh-Zeh [39]	$(L+1)t+L\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{3}}n_{t}^{2} \right)$
Guruswami-Xing [15]	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{6}}n_{t}^{2} \right)$
Bartz-Meier-Sidorenko [4]	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{3}}n_{t}^{3} \right)$
This contribution	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{4}}n_{t}^{2} \right)$

Table Options

Download as excel

Decoding scheme	Decoding region	Op. in ${{\mathbb{F}}_{{{q}^{m}}}}$
Li-Sidorenko-Silva [20,31]	$(L+1)t+L\varkappa+L\rho\leq L({{n}_{t}}-k)$	$ \mathcal{O}\left( Ln_{t}^{2} \right) \phantom{{}^{2}}$
Wachter-Zeh-Zeh [39]	$(L+1)t+L\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{3}}n_{t}^{2} \right)$
Guruswami-Xing [15]	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{6}}n_{t}^{2} \right)$
Bartz-Meier-Sidorenko [4]	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{3}}n_{t}^{3} \right)$
This contribution	$(L+1)t+\phantom{L}\varkappa+L\rho\leq L({{n}_{t}}-k)$	$\mathcal{O}\left( {{L}^{4}}n_{t}^{2} \right)$

[1]	Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[2]	Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[3]	Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147
[4]	Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
[5]	Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[6]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[7]	Rakhi Pratihar, Tovohery Hajatiana Randrianarisoa. Constructions of optimal rank-metric codes from automorphisms of rational function fields. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022034
[8]	Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[9]	Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[10]	Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[11]	Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
[12]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[13]	Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419
[14]	Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1
[15]	Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49
[16]	Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[17]	Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
[18]	Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021031
[19]	Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021007
[20]	Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028

2021 Impact Factor: 1.015

Tools

Metrics

Tools

Article outline

Figures and Tables

2021 Impact Factor: 1.015

Tools

Figures and Tables

2021 Impact Factor: 1.015

American Institute of Mathematical Sciences

Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors