Improved Syndrome Decoding of Lifted L-Interleaved Gabidulin Codes

Abstract

A syndrome decoding algorithm for lifted interleaved Gabidulin codes of order L is proposed. The algorithm corrects L times more packet insertions than known syndrome decoding methods with probability at least 1−8q−n. For n < L, where n is the dimension of the code words (subsapces), 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 insertions beyond the unique decoding radius.