arXiv preprint ·
Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Two-Stage Secret Sharing
Nonexistence of a quasi-symmetric $2$-$(33,15,35)$ design
Toward the Minimal Set of Information Inequalities in Regenerating Codes: An Algebraic Approach
SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders
Wireless Node Ranking via Fourier-Driven Maximum-Likelihood Estimation (extended version)
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.