CS Paper Radar

One-Shot Information Theory via the Pairwise Error Probability: Lossy, Joint Source-Channel, Erasure, and Multiuser Coding

Nir Elkayam, Meir Feder

cs.IT ·submitted 2026-08-15 11:12 UTC · v1

Abstract

This paper extends a one-shot (finite-blocklength) information-theoretic framework built on a single primitive: the pairwise error probability (PEP) of a randomized, dither-broken decoding rule, and the error spectrum it induces. A companion paper developed the framework for point-to-point channel coding -- uniformity of the PEP, the error-spectrum representation of achievability and converse, and the linear-programming form of the prior-optimized minimax meta-converse. Here we show that the same primitive, read on an enlarged candidate space, governs four further settings: lossy source coding under average distortion, joint source-channel coding with list decoding, channel coding with an erasure/undetected-error option, and the two-user multiple-access channel. In each case a single spectrum yields a random-coding achievability bound and exact fixed-code identities, and we indicate how the convex -- indeed linear-programming -- prior optimization of the channel-coding case extends under matched decoding. The development recovers the one-shot lossy bound of Matsuta-Uyematsu and the joint source-channel bounds in the Csiszar tradition, complements the lossy bounds of Kostina-Verdu, and connects the multiuser case to the comparable achievability/converse pair through three pairwise error events.

Closest papers

Nearest neighbours by meaning across the whole index.

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.74
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

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.69
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

Universal Decoding via the Pairwise Error Probability

cs.IT ·2026-08-20 ·Nir Elkayam, Meir Feder
theory similarity 0.67
Abstract

We develop a theory of universal decoding built on the pairwise error probability (PEP) primitive of a companion paper. The PEP and its error spectrum are defined for an arbitrary decoding metric, and while raw metric values across a family share no common scale, the PEP supplies one. Universal decoding -- decoding well simultaneously against a whole family of metrics or channels -- becomes the problem of merging the per-metric spectra into a single rule, which we construct from a clipped inverse-PEP statistic. The construction rests on a Kraft-type inequality for decoding, valid for any input prior: per output, every metric canonicalizes into a conditional probability assignment on the codewords, and the merge is the normalized-maximum-likelihood envelope of the induced family. We prove the rule is random-coding universal (it loses only a vanishing rate relative to the best metric in the family, against every channel), show it is an asymptotic minimax/equalizer rule, and derandomize it: over a subexponential channel family a single deterministic code inherits the guarantee. For discrete memoryless channels the construction reduces to types and recovers the maximum-mutual-information decoder, its tilted variant for non-uniform memoryless input, and finite-state universal decoders. It extends to decoding with an erasure option (deterministically, uniformly over erasure margins) and, via a discretization of separable metric families, to continuous alphabets: for AWGN with deterministic interference it attains the matched-ML exponent up to an explicit typical-set cap, and for ISI channels the best exponent in a family of equalize-and-decode rules, under explicit assumptions on the equalizers and the channel spectrum and the same cap. Throughout, universality is a corollary of the PEP analysis rather than a separate theory.

0.26

The Sample Complexity of Channel Coding

cs.IT math.ST ·2026-11-16 ·Terence Viaud, Ioannis Kontoyiannis
similarity 0.65
Abstract · 31 pages, 3 figures

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.

0.16

Multi-Stream Spatiotemporal Channel Coding for MIMO Systems: Transmission Scheme Design and Achievable Rate Optimization

eess.SP ·2026-09-09 ·Liang Jin, Xiaodong Xu, Shujun Han, Xiaoyu Chi, Ping Zhang +1 more
top venuebenchmark similarity 0.65
Abstract

Spatiotemporal channel coding (STCC) can improve the achievable rate over traditional temporal channel coding (TCC) by leveraging spatial degrees of freedom to extend the codeword length. Although several information-theoretic foundations on STCC have been established, the investigation of transmission schemes from a communication-theoretic perspective remains in its early stages. This paper proposes a multi-stream over multi-subchannel STCC (STCC-MSC) under full channel state information assumption and optimizes its achievable rate in the finite blocklength regime. We first formulate the transmission architecture of STCC-MSC in a point-to-point MIMO system, which introduces a stream-subchannel matching mechanism. We then maximize the achievable rate of STCC-MSC by jointly optimizing the subchannel assignment and power allocation strategies, which is formulated as a mixed-integer-nonlinear-programming problem. Next, a penalized alternating convex approximation (PACA) algorithm is proposed to solve this problem. Subsequently, we extend the point-to-point STCC-MSC designs to the more general multi-user MIMO systems, including both uplink and downlink scenarios. Finally, simulation results indicate that the PACA algorithm achieves a 9.85% rate improvement over the benchmark algorithm within the STCC-MSC scheme. Furthermore, the joint STCC-MSC-PACA scheme improves the achievable rate by 28.68% over TCC scheme.

0.33

MacKay-Neal Codes Achieve Capacity under MAP Decoding

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

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.64
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.51

Universal Decoding for Unequal Error Protection

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

We study universal unequal error protection of a single special message over discrete memoryless channels. We construct a sequence of codes with a decoding rule that does not depend on the channel transition law. We derive an achievable error exponent for the special message while ensuring reliable decoding of the ordinary messages. The resulting exponent strictly improves on the natural equal-error-protection random-coding baseline and remains positive as the rate approaches capacity. For symmetric channels, it converges to the optimal red-alert exponent at capacity.

0.17