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 poly-nomial-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(n _t − k), where n _t is the dimension of the transmitted subspace and k is the number of data symbols from the field F _q ^m . Further, a complementary decoding approach is presented which corrects γ insertions and δ deletions up to Lγ + δ ≤ L(n _t − k). Both schemes use properties of minimal Gröbner 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öbner 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 O(L ² n ² _r ) operations in 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.