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

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 γ insertions and δ deletions up to γ + Lδ ≤ L(nt − k), where nt is the dimension of the transmitted subspace and k is the number of data symbols from the field Fqm. Further, a complementary decoding approach is presented which corrects γ insertions and δ deletions up to Lγ +δ ≤ L(nt −k). Both schemes use properties of minimal Gr¨obner 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¨obner basis using the general K¨otter 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 O(L2n2 r) operations in F qm where nr 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.