Improved syndrome decoding of lifted L -interleaved Gabidulin codes

A syndrome decoding algorithm for lifted interleaved Gabidulin codes of order L is proposed. The algorithm corrects L times more deviations (packet insertions) than known syndrome decoding methods with probability at least 1 - 8 q ^{- n} , where n is the length of the (interleaved) Gabidulin code. For n< L, the proposed scheme has L times less computational complexity than known interpolation-factorization based decoders which attain the same decoding region. Upper bounds on the decoding failure probability are derived. Up to our knowledge this is the first syndrome-based scheme for interleaved subspace codes that can correct deviations beyond the unique decoding radius.