A framework is introduced for examining and evaluating the fundamental limits of channel coding, that emphasizes genuinely non-asymptotic results. The sample complexity of a channel is defined as the smallest blocklength at which it is possible to transmit a source through the channel above a specified code size and below a specified decoding error probability. This formulation mirrors an existing framework in lossless data compression inspired by corresponding developments in statistics and computer science. For discrete memoryless channels, it is shown that the sample complexity is characterized not by the channel capacity, but by the Augustin–Csiszár capacity of order 1/2. Nonasymptotic bounds on the sample complexity are obtained, with explicit constants. Finally, an extension to the additive white gaussian noise channel is established and discussed.
