Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

DOI10.1109/TIT.2014.2314468zbMATH Open1360.94424arXiv1401.2716OpenAlexW2052485280MaRDI QIDQ2986260FDOQ2986260

Authors: Yang Ding, Lingfei Jin, Chaoping Xing 

Publication date: 16 May 2017

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

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.

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)

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)