American Institute of Mathematical Sciences

Advanced
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.  Google Scholar

[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.  Google Scholar

[3]

H. Bartz, Algebraic Decoding of Subspace and Rank-Metric Codes, PhD thesis, Technical University of Munich, 2017. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 3-16.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

M. Kuijper and A. Trautmann, Gröbner bases for linearized polynomials, URL http://arXiv.org/abs/1406.4600. Google Scholar

[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.  Google Scholar

[21]

R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1997.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[25]

J. N. Nielsen, List Decoding of Algebraic Codes, PhD thesis, 2013. Google Scholar

[26]

∅. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35 (1933), 559-584.  doi: 10.1090/S0002-9947-1933-1501703-0.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

D. Silva, Error Control for Network Coding, PhD thesis, University of Toronto, Toronto, Canada, 2009. Google Scholar

[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.  Google Scholar

[34]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inf. Theory, 56 (2010), 1378-1382.  doi: 10.1109/TIT.2009.2039163.  Google Scholar

[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.  Google Scholar

[36]

A.-L. Trautmann and M. Kuijper, Gabidulin decoding via minimal bases of linearized polynomial modules, preprint, arXiv: 1408.2303. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

H. Bartz, Algebraic Decoding of Subspace and Rank-Metric Codes, PhD thesis, Technical University of Munich, 2017. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 3-16.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

M. Kuijper and A. Trautmann, Gröbner bases for linearized polynomials, URL http://arXiv.org/abs/1406.4600. Google Scholar

[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.  Google Scholar

[21]

R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1997.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[25]

J. N. Nielsen, List Decoding of Algebraic Codes, PhD thesis, 2013. Google Scholar

[26]

∅. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35 (1933), 559-584.  doi: 10.1090/S0002-9947-1933-1501703-0.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

D. Silva, Error Control for Network Coding, PhD thesis, University of Toronto, Toronto, Canada, 2009. Google Scholar

[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.  Google Scholar

[34]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inf. Theory, 56 (2010), 1378-1382.  doi: 10.1109/TIT.2009.2039163.  Google Scholar

[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.  Google Scholar

[36]

A.-L. Trautmann and M. Kuijper, Gabidulin decoding via minimal bases of linearized polynomial modules, preprint, arXiv: 1408.2303. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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 $TransmissionsObserved dec. failuresSimulated $P_{f}$
880 $1.2\cdot10^{6}$18749 $1.56\cdot10^{-2}$
61 $4.0\cdot10^{5}$6202 $1.55\cdot10^{-2}$
770 $4.4\cdot10^{6}$1025 $2.33\cdot10^{-4}$
51 $6.0\cdot10^{5}$144 $2.40\cdot10^{-4}$
660 $9.0\cdot10^{6}$21 $2.33\cdot10^{-6}$
41 $3.4\cdot10^{6}$17 $5.00\cdot10^{-6}$
550 $3.2\cdot10^{6}$750 $2.33\cdot10^{-4}$
31 $8.0\cdot10^{5}$184 $2.30\cdot10^{-4}$
440 $4.4\cdot10^{6}$21 $4.77\cdot10^{-6}$
21 $1.6\cdot10^{6}$0 $0$
Table Options

Download as excel

$\gamma + L\delta $ $\gamma $ $\delta $TransmissionsObserved dec. failuresSimulated $P_{f}$
880 $1.2\cdot10^{6}$18749 $1.56\cdot10^{-2}$
61 $4.0\cdot10^{5}$6202 $1.55\cdot10^{-2}$
770 $4.4\cdot10^{6}$1025 $2.33\cdot10^{-4}$
51 $6.0\cdot10^{5}$144 $2.40\cdot10^{-4}$
660 $9.0\cdot10^{6}$21 $2.33\cdot10^{-6}$
41 $3.4\cdot10^{6}$17 $5.00\cdot10^{-6}$
550 $3.2\cdot10^{6}$750 $2.33\cdot10^{-4}$
31 $8.0\cdot10^{5}$184 $2.30\cdot10^{-4}$
440 $4.4\cdot10^{6}$21 $4.77\cdot10^{-6}$
21 $1.6\cdot10^{6}$0 $0$
Table 2.  Comparison of different decoding schemes for interleaved KK subspace codes
Decoding schemeDecoding regionOp. 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 schemeDecoding regionOp. 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]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[2]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[3]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[4]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[5]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322
[6]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[7]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020  doi: 10.3934/fods.2020017
[8]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[9]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071
[10]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[11]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[12]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[13]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (176)
  • HTML views (332)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences