2012/02/02 by Hessam Mahdavifar, Mahdavifar, Hessam, Alexander Vardy +1
Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Technologies #Coding theory and cryptography #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1202.0338
arxiv created 2012/02/02 · openalex publication_date 2012/02/02 · arxiv updated 2012/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Subspace codes were introduced in order to correct errors and erasures for randomized network coding, in the case where network topology is unknown (the noncoherent case). Subspace codes are indeed collections of subspaces of a certain vector space over a finite field. The Koetter-Kschischang construction of subspace codes are similar to Reed-Solomon codes in that codewords are obtained by evaluating certain (linearized) polynomials. In this paper, we consider the problem of list-decoding the Koetter-Kschischang subspace 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 L, our list-L decoder guarantees successful recovery of the message subspace provided that the normalized dimension of the error is at most L - (L(L+1))/(2)R where R is the normalized packet rate. Just as in the case of Sudan's list-decoding algorithm, this exceeds the previously best known error-correction radius 1-R, demonstrated by Koetter and Kschischang, for low rates R.