Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

DOI10.1109/TIT.2014.2314468MaRDI QIDQ2986260zbMATHOpenAlexFDO

Authors Yang Ding, Lingfei Jin, Chaoping Xing

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2716

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Abstract: Erasure list decoding was introduced to correct a larger number of erasures with output of a list of possible candidates. In the present paper, we consider both random linear codes and algebraic geometry codes for list decoding erasure errors. The contributions of this paper are two-fold. Firstly, we show that, for arbitrary $0<R<1$ and $epsilon>0$ ($R$ and $epsilon$ are independent), with high probability a random linear code is an erasure list decodable code with constant list size $2^{O(1/epsilon)}$ that can correct a fraction $1-R-epsilon$ of erasures, i.e., a random linear code achieves the information-theoretic optimal trade-off between information rate and fraction of erasure errors. Secondly, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, for any $0<R<1$ and $epsilon>0$, a $q$-ary algebraic geometry code of rate $R$ from the Garcia-Stichtenoth tower can correct $1-R-frac1sqrtq-1+frac1q-epsilon$ fraction of erasure errors with list size $O(1/epsilon)$. This improves the Johnson bound applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time.

Cited in

(2)

• Minimum Distance Decoding of General Algebraic Geometry Codes via Lists
• Pauli manipulation detection codes and applications to quantum communication over adversarial channels

This page was built for publication: Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986260)