CS Paper Radar

The Sample Complexity of Channel Coding

Terence Viaud, Ioannis Kontoyiannis

cs.IT math.ST ·submitted 2026-11-16 16:50 UTC · v1

Abstract

We introduce a new framework for the study and evaluation of the fundamental limits of channel coding, emphasizing genuinely nonasymptotic results. The {\em channel coding sample complexity} $n^*({\cal W},ε)$ of a channel ${\cal W}$ is defined as the smallest blocklength at which it is possible to transmit information through that channel with error probability below $ε$ and at a rate at least as high as that given by an appropriate constraint also in terms of $ε$. This formulation follows analogous developments in statistics, computer science and, more recently, in lossless source coding. For any discrete memoryless channel we derive nonasymptotic bounds on the sample complexity, with explicit constants. These bounds show that the sample complexity is characterized not by the usual channel capacity, but by the channel's Augustin--Csiszár capacity of order $1/2$, which coincides with the cutoff rate as well as with the channel's Sibson capacity of order $1/2$. The proof is partly based on a new channel-coding one-shot converse in terms of hypothesis testing. We also examine extensions of the sample complexity framework to general target rates. Moreover, we derive corresponding results for the sample complexity of the additive white Gaussian noise channel with a quadratic power constraint. Their proof relies on new, explicit upper bounds on the best achievable error probability, which may be of independent interest.

Comment
31 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.75
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.72
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.70
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

Functional Information, Optimal Channel Simulation and Lossy Source Coding

cs.IT ·2026-11-15 ·Gergely Flamich, Spencer Hill, Fady Alajaji, Tamás Linder
similarity 0.67
Abstract

We characterize, within a constant number of bits, the minimum achievable rate for several one-shot coding problems, such as channel simulation and lossy source coding. The basis of our work is a new information measure between random variables $X, Y$ that we call the functional information $I_F(X \to Y)$. We show that this quantity characterizes the minimum one-shot rate $R^*(X \to Y)$ of channel simulation, in which a sample $Y \sim P_{Y \mid X}$ is communicated in the presence of common randomness: $I_F(X \to Y) \leq R^*(X \to Y) < I_F(X \to Y) + 1.45$. For the achievability result, we construct an explicit code using the Poisson functional representation. Using these results, we develop new bounds for one-shot variable-rate lossy source coding: given some distortion measure $Δ$, we use $I_F(X \to Y)$ to define the functional rate-distortion function $R_F$. Then, letting $R_O$ denote the one-shot operational rate-distortion function with private encoder randomness and distortion measure $Δ$, we make use of our channel simulation result to show that $R_F(D) \leq R_O(D) < R_F(D) + 2.45$ at every positive distortion level $D$. Finally, we generalize our channel simulation result by introducing the Rényi $α$-functional information $I_{F, α}(X \to Y)$ and show that it characterizes the minimum Arimoto-Rényi conditional entropy for channel simulation, ${R^*_α(X \to Y)}$, associated with the Campbell cost: ${I_{F, α}(X \to Y) \leq R^*_α(X \to Y) \leq I_{F, α}(X \to Y) + O(1/α)}$.

0.22

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

cs.IT ·2026-10-11 ·Yijun Fan, Aaron B. Wagner
similarity 0.67
Abstract

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

0.40

Joint Source-Channel Coding of Gaussian Sources over Block Erasure Channels: Nonasymptotic Bounds and Channel-Uniform Normal Approximations

cs.IT ·2026-09-30 ·Adeel Mahmood
benchmark similarity 0.67
Abstract · Added an SSCC achievability benchmark and expanded numerical results

We study finite-blocklength lossy transmission of a Gaussian memoryless source over memoryless, possibly nonstationary block erasure channels under an excess mean-squared distortion criterion. We derive computable nonasymptotic achievability and converse bounds and establish matching third-order, channel-uniform normal approximations. Our achievability bound exactly evaluates the ensemble-average excess-distortion probability of a specified random coding scheme and improves corresponding specializations of known general one-shot bounds. Our converse conditions on the erasure pattern and source energy and combines spherical-cap and volume bounds, with the spherical-cap term providing the geometric prefactor needed for the matching third-order term. In our channel-uniform normal approximation, we show that for fixed distortion ratio, target excess-distortion probability, and block size, the sufficient and necessary information-balance conditions have the same dispersion and $\frac{1}{2}\log k$ terms, where $k$ is the source blocklength, and differ only by bounded remainders that are uniform over the channel blocklength and erasure-probability profile. Numerical evaluations compare the nonasymptotic JSCC bounds and their common third-order normal approximation with an optimized symmetrized SSCC achievability benchmark.

0.32

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

cs.IT quant-ph ·2026-09-28 ·Tina Shariat, Matt Hoogsteder-Riera, Marco Tomamichel
similarity 0.67
Abstract · 25 pages, 1 figure

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

0.35

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.67
Abstract · A part of this work has been reported in https://arxiv.org/pdf/2601.12640

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. In this paper, we formulate the notion of computation capacity, and derive achievability and converse results for a large class of functions $F$, characterized by the Hamming weight of functions. Different from the classical transmission problem, the performance of the function computation problem is jointly characterized by the computation capacity and the rate function, namely how $m$ scales with $n$ asymptotically. Our results give a complete characterization of the rate function of the computation problem, and provide upper and lower bounds on the computation capacity, where they differ by a factor of at most $2$.

0.52