List-decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound

被引:0
作者
Mahdavifar, Hessam [1 ]
Vardy, Alexander [1 ]
机构
[1] Univ Calif San Diego, La Jolla, CA 92093 USA
来源
2012 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT) | 2012年
关键词
REED-SOLOMON;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Subspace codes and rank-metric codes can be used to correct errors and erasures in network, with linear network coding. Both types of codes have been extensively studied in the past five years. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks where topology is unknown (the non-coherent case). In this model, the codewords are vector subspaces of a fixed ambient space; thus codes for this model are collections of such subspaces. In a previous work, we have developed a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. Using these codes, we achieved a better decoding radius than Koetter-Kschischang codes at low rates. Herein, we introduce a new family of subspace codes based upon a different approach which leads to a linear-algebraic list-decoding algorithm. The resulting error-correction radius can be expressed as follows: for any integer s, our list-decoder using s + 1-variate interpolation polynomials guarantees successful recovery of the message subspace provided the normalized dimension of errors is at most s(1 - sR). The same list-decoding algorithm can be used to correct erasures as well as errors. The size of output list is at most Q(s-1), where Q is the size of the field that message symbols are chosen from. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank-distance of a code. In this paper, we introduce a folded version of Gabidulin codes analogous to the folded Reed-Solomon codes of Guruswami and Rudra along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to recover the message provided that the normalized rank of error is at most 1 - R - epsilon, for any epsilon > 0. Notably this achieves the information theoretic bound on the decoding radius of a rank-metric code.
引用
收藏
页数:5
相关论文
共 16 条
  • [1] [Anonymous], IEEE INT C IM PROC I
  • [2] Gabidulin E. M., 1985, Problems of Information Transmission, V21, P1
  • [3] Improved decoding of Reed-Solomon and algebraic-geometry codes
    Guruswami, V
    Sudan, M
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) : 1757 - 1767
  • [4] Guruswami V., 2008, IEEE T INFORM THEORY, V54
  • [5] Linear-algebraic list decoding of folded Reed-Solomon codes
    Guruswami, Venkatesan
    [J]. 2011 IEEE 26TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2011, : 77 - 85
  • [6] Ho T, 2003, 2003 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, P442
  • [7] Coding for errors and erasures in random network coding
    Koetter, Ralf
    Kschischang, Frank R.
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (08) : 3579 - 3591
  • [8] Mahdavifar Hessam, 2011, 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), P1430
  • [9] Mahdavifar H., LIST DECODING SUBSPA
  • [10] Mahdavifar H., IEEE T INFO IN PRESS