Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
- 31 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (2), 1-48
- https://doi.org/10.1145/3506668
Abstract
We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1-R-ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The alphabet size depends only ε and is nearly optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield. In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice “periodic” structure. To prune this subspace and obtain a good bound on the list size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets that are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspace-evasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e.) sets that leads to excellent list size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs, which were subsequently constructed explicitly and also found further applications in pseudorandomness. To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia–Stichtenoth tower of function fields. Combining this with pruning via h.s.e. sets yields codes list-decodable up to a 1-R-ε error fraction with list size bounded by O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made exp (Õ(1/ε 2)), which is not much worse than the lower bound of exp (Ω (1/ε)). The parameters we achieve are thus quite close to the existential bounds in all three aspects (error-correction radius, alphabet size, and list size) simultaneously. This construction is, however, Monte Carlo and the claimed list-decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O_ε (Nc) for an absolute constant c, where N is the code’s block length. Using subspace designs instead for the pruning, our approach yields the first deterministic construction of an algebraic code family of rate R with efficient list decoding from 1-R-ε fraction of errors over an alphabet of constant size exp (Õ(1/ε 2)). The list-size bound is upper bounded by a very slowly growing function of the block length N; in particular, it is at most O(log (r) N) (the rth iterated logarithm) for any fixed integer r. The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size.Keywords
Funding Information
- NSF (CCF-0963975, CCF-1422045, and CCF-1814603)
- National Science Foundation
- NRFC (12031011)
- National Key Research and Development Project (2021YFE0109900, 2020YFA0712300)
- Sino-Russian Mathematics Center
- SJTU-Huawei Joint Project
This publication has 28 references indexed in Scilit:
- PseudorandomnessFoundations and Trends® in Theoretical Computer Science, 2012
- Cyclotomic function fields, Artin–Frobenius automorphisms, and list error correction with optimal rateAlgebra & Number Theory, 2010
- Algebraic soft-decision decoding of reed-solomon codesIEEE Transactions on Information Theory, 2003
- List decoding from erasures: bounds and code constructionsIEEE Transactions on Information Theory, 2003
- A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov boundIEEE Transactions on Information Theory, 2001
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- On the Asymptotic Behaviour of Some Towers of Function Fields over Finite FieldsJournal of Number Theory, 1996
- A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut boundInventiones Mathematicae, 1995
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rateIEEE Transactions on Information Theory, 1993
- Error-correcting codes for list decodingIEEE Transactions on Information Theory, 1991