Name
Abstract | ||
|---|---|---|
Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 0 <; R <; 1 and ϵ > 0 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ) that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TIT.2014.2314468 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
algebraic geometric codes,linear codes,list decoding,information-theoretic optimal tradeoff,erasure codes,polynomial time,erasure list-decodable code,q-ary random linear code,garcia-stichtenoth tower,decoding,generalized hamming weights,algebraic geometry codes,geometry,hamming weight | Journal | 60 |
Issue | ISSN | Citations |
7 | 0018-9448 | 1 |
PageRank | References | Authors |
0.37 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Ding | 1 | 1 | 0.37 |
| Lingfei Jin | 2 | 135 | 15.30 |
| Chaoping Xing | 3 | 916 | 110.47 |