CS Paper Radar

Threshold Saturation from a Bounded Region in Multidimensional Spatially Coupled Codes over the BEC

Kenta Kasai

cs.IT ·submitted 2026-09-21 13:34 UTC · v1
theory

Abstract

We prove that a bounded shortened region initiates decoding throughout multidimensional spatially coupled regular LDPC and MacKay--Neal (MN) codes over the binary erasure channel (BEC). In every fixed finite dimension, uniform hypercube coupling permits the coupling width and shortened region to be chosen independently of the total number $V$ of spatial positions. At fixed widths and dimension $d>1$, replacing a shortened slab by a bounded hypercube reduces the shortening fraction from order $V^{-1/d}$ to order $V^{-1}$, with the same improvement in the shortening term of the check-count rate bound. Regular LDPC codes decode below their uncoupled potential threshold. MN codes achieve capacity for every integer degree choice $\ell>r\geq2$, $g\geq2$: their actual transmitted rates tend to $r/\ell$ and their average bit-erasure probabilities under sum-product decoding vanish below $1-r/\ell$. The proof combines an endpoint-potential identity, removal of an auxiliary constraint, finite-time estimates uniform in direction, and a curvature comparison that transfers flat-boundary progress to expanding balls. For MN codes, elementary inequalities establish fixed-point positivity for all these degrees. Two-dimensional density-evolution examples illustrate the dependence on the initial shortened region; the general sufficient constants are not evaluated numerically.

Comment
26 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Spatially Coupled MacKay-Neal Codes Achieve Capacity on BMS Channels at Fixed Degrees

cs.IT ·2026-09-14 ·Kenta Kasai
code/data similarity 0.72
Abstract · 43 pages; expanded preliminaries, proof explanations, BEC comparison, and historical context; exact certificates and verification software: …

We establish two degree-dependent results for spatially coupled MacKay-Neal codes on binary-input memoryless symmetric channels. The ensembles use uniform random smoothing and shorten both variable types outside the active chain. For $r=g=3$, every integer $\ell\geq4$, and each channel of capacity greater than $R=r/\ell$, there is a sequence of code realizations whose actual transmitted rate tends to $R$ and whose average sum-product bit error tends to zero. For $r=g=2$ and each $\ell\in\{3,4,5\}$, an interval of binary symmetric channels has capacity greater than $R$ but retains positive transmitted-bit error under terminated density evolution as chain length grows relative to coupling width. Both results follow from the signs of the same density-valued potential at uncoupled fixed points. The degree-three proof combines analytic bounds for $\ell\geq33$ with exact interval certificates for $4\leq\ell\leq32$, followed by threshold saturation and a projection argument for the actual rate. The degree-two proof analytically constructs a fixed point with negative potential and controls both boundary contributions. We relate the potential and the degree-two bifurcation condition to earlier statistical-mechanical predictions. The finite certificates and verification software are available in a versioned supplement.

0.59

Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes

cs.IT ·2026-10-04 ·Jianshen Zhu
similarity 0.71
Abstract

We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.

0.11

Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels

cs.IT ·2026-09-22 ·Kenta Kasai
theory similarity 0.69
Abstract · 15 pages

We prove a capacity criterion for fixed-degree spatially coupled MacKay--Neal codes on additive symmetric Markov noise. The noise bit flips with probability $p$, so the channel has one parameter and capacity $1-h_2(p)$. For every integer $\ell\geq4$ with $3/\ell<1-h_2(p)$, matched finite-window BCJR and sum-product decoding admit code sequences, possibly depending on $p$, with actual rate tending to $3/\ell$ and vanishing average information-bit error. The proof parallels the GEC-to-BEC argument: a conditional-entropy correction transfers BMS fixed-point positivity to the channel with memory. The correction also covers a capacity deficit of the effective BMS channel. A two-state posterior contraction supplies the additional derivative bound needed for threshold saturation. The result uses the cited BMS positivity theorem, with an analytic proof for $\ell\geq33$ and exact interval certificates for $4\leq\ell\leq32$.

0.17

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.67
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.42

Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure Channels

cs.IT ·2026-11-10 ·Henry D. Pfister, Oscar Sprumont, Gilles Zémor
similarity 0.64
Abstract

We show that on the classical erasure channel, the tensor product of two capacity-achieving code families is itself capacity-achieving under mild conditions. We also prove that duals of tensor products of independent uniform random binary linear codes achieve erasure capacity. Using these local codes, for every erasure probability $ρ\in(0,1/2)$ and every rate gap $\varepsilon>0$, we obtain a family of binary quantum Tanner codes of rate at least $1-2ρ-\varepsilon$. For fixed $ρ$ and $\varepsilon$, these codes have bounded check weights, minimum distance growing linearly with the blocklength, and a linear-time erasure decoder whose decoding error decays exponentially with the blocklength.

0.21

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

cs.IT ·2026-11-12 ·Yota Maeda, Ruho Kondo
theory similarity 0.64
Abstract · 25 pages

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.

0.18

An Upper Bound to the Undetected Error Exponent with Erasure Decoding at Positive Rates

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Marco Dalai, Albert Guillén i Fàbregas
theory similarity 0.64
Abstract

We study the undetected-error exponent of discrete memoryless channels with erasure decoding. Assuming that the undetected-error and erasure probabilities vanish, we derive an upper bound on the undetected-error exponent at positive rates. The bound uses Somekh-Baruch's genie-aided argument where an auxiliary output provides the decoder with a list of codewords. It recovers Telatar's tight rate-zero converse and is at least as tight as the straight-line bound. A numerical example shows that the improvement over the straight-line bound can be strict.

0.16

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
highly cited similarity 0.63
Abstract

We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.44