no. 16 · Tuesday 17 November 2026
The Sample Complexity of Channel Coding
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.
- comments
- 31 pages, 3 figures
- fields
- Information Theory, Statistics Theory