betaFeedback

WorksComputer Science

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 channel coding sample complexity n∗(W,ε)n^*({\cal W},ε) of a channel W{\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/21/2, which coincides with the cutoff rate as well as with the channel's Sibson capacity of order 1/21/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.

Paper details

vlnc:W_m78w8ttx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-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

ChatGPT-6

View statement
Looking for related papers…