Algebraic List-Decoding of Subspace Codes

作者：Mahdavifar Hessam^*; Vardy Alexander

来源：IEEE Transactions on Information Theory, 2013, 59(12): 7814-7828.

DOI：10.1109/TIT.2013.2281718

• Koetter-Kschischang codes
• linearized polynomials
• list-decoding
• network error-correction
• 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
tau <= L - L(L+1)/2R*
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*.

• 出版日期2013-12