Algebraic List-Decoding of Subspace Codes

Subspace codes are collections of subspaces of a certain ambient vector space over a finite field. Koetter and Kschischang introduced subspace codes in order to correct errors and erasures in noncoherent (random) linear network coding. They have also studied a remarkable family of subspace codes obtained by evaluating certain linearized polynomials. The Koetter-Kschischang subspace codes are widely regarded as the counterpart of Reed-Solomon codes in the domain of network error-correction. Koetter and Kschischang have furthermore devised an algebraic decoding algorithm for these codes, analogous to the Berlekamp-Welch decoding algorithm for Reed-Solomon codes. In this paper, we develop list-decoding algorithms for subspace codes, thereby providing, for certain code parameters, a better tradeoff between rate and error-correction capability than that of the Koetter-Kschischang codes. In a sense, we are able to achieve for these codes what Sudan was able to achieve for Reed-Solomon codes. In order to do so, we have to modify and generalize the original Koetter-Kschischang construction in many important respects. The end result is this: for any integer, our list-L decoder guarantees successful recovery of the message subspace provided that the normalized dimension of the error satisfies τ ≤ L - L(L + 1)/2 R* where R* is the packet rate, which is a new parameter introduced in this paper. As in the case of Sudan´s list-decoding algorithm, this exceeds the previously best-known error-correction radius 1 - R*, established by Koetter and Kschischang, only for low rates R*.