# American Institute of Mathematical Sciences

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

 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.

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:

show all references

##### References:
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$
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$
Simulation results and upper bounds on $P_f$ of the probabilistic-unique decoder with parameters $m = {{n}_{t}} = 6, k = 2, L = 2$
Multiplications vs. the number of insertions for $L = 4$
Number of multiplications for root-finding step for different interleaving orders L. The complexity of the recursive GE is independent of $\gamma$
Memory requirements of the root-finding step for ${{n}_{t}} = 80, k = 60$
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$
 $\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$
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)$
 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] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] Heide Gluesing-Luerssen, Carolyn Troha. Construction of subspace codes through linkage. Advances in Mathematics of Communications, 2016, 10 (3) : 525-540. doi: 10.3934/amc.2016023 [19] Kamil Otal, Ferruh Özbudak, Wolfgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042 [20] Umberto Martínez-Peñas. Rank equivalent and rank degenerate skew cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 267-282. doi: 10.3934/amc.2017018

2018 Impact Factor: 0.879