betaFeedback

WorksComputer Science

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

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 ε>0\varepsilon>0, we construct a family of random binary codes CmC_m whose rates approach ε2\varepsilon^2 and satisfy Pr⁡[δ(Cm)≥12−ln⁡22(ε+ε32)]≥1−2−cε4Nm, \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 mm, where NmN_m is the block length and c>0c>0 is independent of ε\varepsilon and mm. 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.

Introduction

The GV bound for concatenated codes

The Gilbert–Varshamov (GV) bound gives a classical lower bound on the best relative minimum distance attainable by binary codes at a given rate [10, 19]. Its distance function is δGV(R)=h2−1(1−R)\delta_{\mathrm{GV}}(R)=h_2^{-1}(1-R), where h2(x):=−xlog⁡2x−(1−x)log⁡2(1−x)h_2(x):=-x\log_2 x-(1-x)\log_2(1-x) is the binary entropy function (with 0log⁡20:=00\log_2 0:=0), and h2−1:[0,1]→[0,1/2]h_2^{-1}:[0,1]\to[0,1/2] is the inverse of the restriction h2∣[0,1/2]h_2|_{[0,1/2]}. A central problem in coding theory is to approach this bound with codes that admit efficient encoding and decoding.

Code concatenation is a classical approach to this problem. In a binary concatenated code [7], each symbol of an outer code over a larger finite field is encoded as a word of a binary inner code. The classical analysis based on the product of the inner and outer minimum distances gives the Zyablov bound [20]. Thommesen showed that a Reed–Solomon outer code concatenated with independently chosen random binary inner maps, one per outer coordinate, can attain the GV bound [17]. Against this background, Doron, Mosheiff, and Wootters [6] expressed high moments of the bias of concatenated codewords in terms of the dual of the outer code. When both constituent codes are random linear codes of rate ε\varepsilon and the outer alphabet is sufficiently large, they obtain relative minimum distance at least 1/2−O(ε)1/2 - O(\varepsilon) at binary rate ε2\varepsilon^2 with high probability [6 Theorem 3]. Their existence proof, however, leaves open how to construct such outer codes explicitly. With this goal in mind, they asked what conditions on a fixed outer code would suffice to ensure that, with high probability, its concatenation with a single random binary linear inner code approaches the GV bound at low rates [6 Question 1].

We address this question by extending their moment analysis to random subcodes of a prescribed linear code after coordinate scaling. The paper has two principal contributions.

  1. We bound the probability of small minimum distance by two terms. The first depends on the bias moments of the inner code. The second arises from restricting the outer code to a scaled copy of the prescribed code AA. Averaging over the scalings expresses this term through the weight distribution of A⊥A^\perp. A lower bound on the dual distance then suffices to control it.

  1. For algebraic geometry (AG) codes on the Garcia–Stichtenoth (GS) tower [9], the Riemann–Roch bound on dual distance makes the additional term exponentially small. We fix one inner encoding map throughout the tower at each target rate. The resulting distance lower bound holds with failure probability exponentially small in the block length. Its coefficient of R\sqrt{R} agrees with that in the low-rate GV expansion

δGV(R)=12−ln⁡22R+O(R3/2)(R→0).\delta_{\mathrm{GV}}(R) = \frac{1}{2} - \sqrt{\frac{\ln2}{2}}\sqrt{R} + O(R^{3/2}) \qquad(R \to0).

For each fixed target rate, the AG encoder and decoder also give polynomial-time encoding and unique decoding up to the designed radius.

Main results

The codes considered in this paper. We study concatenated codes whose outer code is a random subcode of a scaled copy of a prescribed linear code and whose inner encoding map is the same at every coordinate. Let Q=2k0Q = 2^{k_0}, fix a binary [n0,k0][n_0,k_0] linear code CinC_{\mathrm{in}}, and fix an F2\mathbb{F}_2-linear isomorphism ϕ:FQ→Cin\phi: \mathbb{F}_Q \to C_{\mathrm{in}}. Let A≤FQKA \le\mathbb{F}_Q^K be a prescribed KK-dimensional linear code, called the base code, and fix an FQ\mathbb{F}_Q-linear encoding isomorphism EA:FQK→AE_A : \mathbb{F}_Q^K \to A. We select a kk-dimensional subcode, where 1≤k≤K1 \le k \le K.

Choose a random kk-dimensional subspace U≤FQKU \le\mathbb{F}_Q^K and, independently, choose α\alpha uniformly from (FQ×)n(\mathbb{F}_Q^\times)^n. Let diag⁡(α)\operatorname{diag}(\alpha) denote the diagonal matrix with entries α1,…,αn\alpha_1,\ldots,\alpha_n. We call Aα:=diag⁡(α)AA_\alpha:= \operatorname{diag}(\alpha)A the scaled base code and define

Cout(α,U):=diag⁡(α)EA(U)⊆Aα,C(α,U):=Cout(α,U)∘ϕCin;C_{\mathrm{out}}(\alpha,U) := \operatorname{diag}(\alpha)E_A(U) \subseteq A_\alpha,\qquad C(\alpha,U) := C_{\mathrm{out}}(\alpha,U) \circ_\phi C_{\mathrm{in}};

see § 3.1 for the precise definition of the concatenated codes. Thus C(α,U)C(\alpha,U) has block length N=nn0N = nn_0 and binary dimension kk0kk_0. We choose the distribution of UU so that

Pr⁡U[ℓ∣U=0]≤Q−k\Pr_U[\ell|_U = 0] \le Q^{-k}

for every nonzero FQ\mathbb{F}_Q-linear functional ℓ:FQK→FQ\ell: \mathbb{F}_Q^K \to\mathbb{F}_Q. (1.1)

The uniform distribution on kk-dimensional subspaces satisfies (1.1). § 4.1 gives further examples using graphs of linear maps. In the moment expansion below, condition (1.1) makes the average contribution from vectors outside Aα⊥A_\alpha^\perp nonpositive. Averaging over the coordinate scalings expresses the contribution from nonzero vectors in Aα⊥A_\alpha^\perp in terms of the weight distribution of A⊥A^\perp (Remark 3.7). These two steps are explained in § 3.3 and § 4.3.1. Moreover, the inclusion Cout(α,U)⊆AαC_{\mathrm{out}}(\alpha,U) \subseteq A_\alpha allows us to use the decoding algorithms available for AA (§ 6.3).

A general bound on the probability of small minimum distance. Write Tr⁡:=Tr⁡FQ/F2\operatorname{Tr}:=\operatorname{Tr}_{\mathbb{F}_Q/\mathbb{F}_2} and let ωj∈FQ\omega_j\in\mathbb{F}_Q be the unique element such that

ϕ(a)j=Tr⁡(ωja)(a∈FQ, 1≤j≤n0).\phi(a)_j=\operatorname{Tr}(\omega_j a)\qquad(a\in\mathbb{F}_Q,\ 1\le j\le n_0).

For an integer r≥1r\ge1, choose an ordered tuple V=((i1,j1),…,(ir,jr))V=((i_1,j_1),\ldots,(i_r,j_r)) uniformly from Vr:=({1,…,n}×{1,…,n0})r\mathcal{V}_r:=\left(\{1,\ldots,n\}\times\{1,\ldots,n_0\}\right)^r, independently of α\alpha. Associate to VV the vector gV∈FQng_V\in\mathbb{F}_Q^n given by

(gV)i:=∑ℓ:iℓ=iωjℓ(1≤i≤n).(g_V)_i:=\sum_{\ell:i_\ell=i}\omega_{j_\ell}\qquad(1\le i\le n).

For 0<β<10<\beta<1 and an even integer r≥2r\ge2, define

T0:=Qk(βN)r#{V∈Vr:gV=0},T_0:=\frac{Q^k}{(\beta N)^r}\#\{V\in\mathcal{V}_r:g_V=0\},
TA:=Qk(βN)rEα#{V∈Vr:0≠gV∈Aα⊥}.(1)T_A:=\frac{Q^k}{(\beta N)^r}\mathbb{E}_{\alpha}\#\{V\in\mathcal{V}_r:0\ne g_V\in A_\alpha^\perp\}. \tag*{(1)}

We first prove the following bound.

Theorem 1.1 (General probability bound). For the construction above, suppose that the distribution of UU satisfies (1.1). For every 0<β<10<\beta<1 and every even integer r≥2r\ge2,

Pr⁡α,U[δ(C(α,U))<1−β2]≤T0+TA.(2)\Pr_{\alpha,U}\left[\delta(C(\alpha,U))<\frac{1-\beta}{2}\right]\le T_0+T_A. \tag*{(2)}

A binary linear code C≤F2NC\le\mathbb{F}_2^N is called β\beta-balanced if every nonzero x∈Cx\in C satisfies ∣wt⁡(x)/N−1/2∣≤β/2\left|\operatorname{wt}(x)/N-1/2\right|\le\beta/2, where wt⁡(x)\operatorname{wt}(x) is its Hamming weight. We will prove the following stronger estimate under the assumptions of Theorem 1.1:

Pr⁡α,U[C(α,U) is not β-balanced]≤T0+TA.(3)\Pr_{\alpha,U}[C(\alpha,U)\text{ is not }\beta\text{-balanced}]\le T_0+T_A. \tag*{(3)}

When A=FQnA=\mathbb{F}_Q^n and UU is a uniformly random kk-dimensional subspace, coordinate scaling preserves this distribution and A⊥={0}A^\perp=\{0\}. Thus TA=0T_A=0 and only the tuples with gV=0g_V=0 enter the upper bound, as in the random outer code argument of Doron, Mosheiff, and Wootters [6 Section 1.2]. With both constituent rates equal to ε\varepsilon and log⁡2Q=Ω(ε−3)\log_2 Q=\Omega(\varepsilon^{-3}), this specialization recovers the 1/2−O(ε)1/2-O(\varepsilon) lower bound on relative distance at binary rate ε2\varepsilon^2 in their Theorem 3 (see § 7.1). For a proper base code, Theorem 1.1 allows any subspace distribution satisfying (1.1), and the nonzero vectors in Aα⊥A_\alpha^\perp contribute the additional term TAT_A.

The moment identity and the proof are given in § 3.2 and § 3.3. In § 4, we construct distributions satisfying (1.1) and derive sufficient conditions for both terms to decay exponentially.

Choice of parameters. To obtain a useful distance guarantee, we choose the inner code and the base code so that both terms are small. The first term, T0T_0, is independent of AA and of the choice of the inner encoding map. We choose an inner code satisfying the τ\tau-nice condition in Definition 3.3, and choose its rate and block length so that the bias of a uniformly random inner codeword has a sufficiently small moment generating function. The estimates in Section 3.2 then make T0T_0 decay exponentially.

Our main technical contribution is an estimate for TAT_A, which arises from the restriction of the outer code to the scaled base code AαA_\alpha. In § 4.3.1, we bound this additional term using the weight distribution of A⊥A^\perp, and in particular its minimum distance:

TA≤Qkβr(Q−1)1−d(A⊥)(A⊥≠{0}).T_A\le\frac{Q^k}{\beta^r}(Q-1)^{1-d(A^\perp)}\qquad(A^\perp\ne\{0\}).

Thus, we choose AA with sufficiently large dual distance to make TAT_A decay exponentially as well. The resulting conditions are stated in Corollary 3.9.

A construction from AG codes. Let A=CL(D,G)A=C_L(D,G) be an AG code on a curve of genus gg; see § 5.2 for the definition. The Riemann–Roch theorem gives d(A⊥)≥deg⁡G−2g+2d(A^\perp)\ge\deg G-2g+2. On the GS tower, we can choose deg⁡G\deg G so that this lower bound meets the requirement for TAT_A, while AA has dimension large enough to contain the desired subcode. Together with the choice of the inner code described above, this gives a concrete family to which Theorem 1.1 applies. The precise construction is given in § 5.1 and § 5.3 and yields the following result.

References

  1. [1]Alexander Barg, Jørn Justesen, and Christian Thommesen. Concatenated codes with fixed inner code and random outer code. IEEE Transactions on Information Theory, 47(1):361–365, 2001.DOI
  2. [2]Avraham Ben-Aroya and Amnon Ta-Shma. Constructing small-bias sets from algebraic-geometric codes. Theory of Computing, 9(5):253–272, 2013.
  3. [3]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, and Zihan Zhang. AG codes achieve list decoding capacity over constant-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 740–751, 2024.
  4. [4]Martijn Brehm, Yuval Ishai, and Nicolas Resch. Fast Bounded-Independence Functions and Their Duals. In Yevgeniy Dodis, editor, 7th Conference on Information-Theoretic Cryptography (ITC 2026), volume 385 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.
  5. [5]Gil Cohen, Dean Doron, Noam Goldgraber, and Tomer Manket. Tracing AG codes: Toward meeting the Gilbert–Varshamov bound. In ICALP 2026, volume 374 of LIPIcs, pages 68:1–68:23, 2026.arxiv.org/abs/2511.08788
  6. [6]Dean Doron, Jonathan Mosheiff, and Mary Wootters. When do low-rate concatenated codes approach the Gilbert–Varshamov bound? In APPROX/RANDOM 2024, volume 317 of LIPIcs, pages 53:1–53:12, 2024.arxiv.org/abs/2405.08584
  7. [7]Jr. G. David Forney. Concatenated Codes. Number 37 in M.I.T. Research Monograph. The MIT Press, Cambridge, MA, 1966.
  8. [8]Jr. G. David Forney. Generalized minimum distance decoding. IEEE Transactions on Information Theory, 12(2):125–131, 1966.DOI
  9. [9]Arnaldo Garcia and Henning Stichtenoth. On the asymptotic behaviour of some towers of function fields over finite fields. Journal of Number Theory, 61(2):248–273, 1996.DOI
  10. [10]Edgar N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31(3):504–522, 1952.DOI
  11. [11]Venkatesan Guruswami. List Decoding of Error-Correcting Codes. PhD thesis, Massachusetts Institute of Technology, 2002. Winning Thesis of the 2002 ACM Doctoral Dissertation Competition.
  12. [12]Venkatesan Guruswami and Piotr Indyk. Efficiently decodable codes meeting Gilbert–Varshamov bound for low rates. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 756–757, 2004. Longer version appeared in Allerton 2003.DOI
  13. [13]Kwankyu Lee, Maria Bras-Amorós, and Michael E. O’Sullivan. Unique decoding of general AG codes. IEEE Transactions on Information Theory, 60(4):2038–2053, 2014.DOI
  14. [14]Florence Jessie MacWilliams and Neil James Alexander Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
  15. [15]Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar. A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert–Varshamov bound. IEEE Transactions on Information Theory, 47(6):2225–2241, 2001.DOI
  16. [16]Henning Stichtenoth. Algebraic Function Fields and Codes. Springer, 2nd edition, 2009.DOI
  17. [17]Christian Thomsen. The existence of binary linear concatenated codes with Reed–Solomon outer codes which asymptotically meet the Gilbert–Varshamov bound. IEEE Transactions on Information Theory, 29(6):850–853, 1983.
  18. [18]Takeshi Umeda, Katsumi Sakakibara, and Masao Kasahara. Notes on the average binary weight enumerator of generalized algebraic-geometric codes. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E79-A(9):1444–1446, 1996.
  19. [19]R. R. Varshamov. Estimate of the number of signals in error correcting codes. Doklady Akademii Nauk SSSR, 117:739–741, 1957.
  20. [20]Victor V. Zyablov. An estimate of the complexity of constructing binary linear cascade codes. Problems of Information Transmission, 7(1):3–10, 1971.

Paper details

vlnc:W_k86fbezt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents