The problem
A binary symmetric channel flips each bit independently, say about one bit in ten. A sender can add redundant bits so that the receiver usually recovers the message. The question is how rapidly the smallest achievable chance of a mistake decreases when longer blocks are allowed.[1]
A binary symmetric channel independently flips each transmitted bit with probability . Adding redundancy can reduce mistakes, but at a fixed message rate the best possible speed of that reduction is still unknown across the full positive-rate range. Let minimize the worst-message decoding error over all length- encoders with at least messages and all decoders, without feedback. For and , the target is . The limsup is part of the definition; replacing it by an ordinary limit would require justification.[1]
Scope
For a fixed memoryless BSC with crossover probability p in (0,1/2), determine the optimal fixed-blocklength, no-feedback reliability exponent E_p(R)=limsup as n→∞ of −log₂ P*max(n,R,p)/n for every positive rate R<1−h₂(p). P*max is minimized over unrestricted length-n codes with at least ceil(2^(nR)) messages and decoders, using the worst message error probability.
What remains open
The sphere-packing converse and random-coding achievability coincide above the critical rate and below capacity. At lower rates, expurgation strengthens an achievable lower bound without closing the entire gap to upper bounds. The known zero-rate endpoint does not cover all positive rates. General noncomputability when a channel is supplied as input also does not settle the exact function for this specified binary symmetric family.[1] [2]
Why it matters
Two coding methods can both work below capacity yet need very different block lengths to achieve a tiny error probability. The reliability function describes the fundamental tradeoff between rate and protection, before imposing practical limits on decoding effort.[1]
An achievable exponent describes protection a code construction can provide; a converse limits how much any construction could improve it. Together they quantify the asymptotic transmission length needed for reliable messages at a fixed rate. A result for an average over a random-code ensemble addresses a chosen way of selecting codes. The channel optimum instead ranges over every code and decoder, separating a construction’s limitations from limitations imposed by the noise itself.[1]
Definitions
2 terms
rate
The base-two logarithm of the number of messages divided by the transmitted block length. Lower rate allows more redundancy per message; the reliability question fixes a positive rate as block lengths grow.[1]
limsup
The limiting upper envelope of a sequence. It defines an asymptotic exponent without assuming the whole sequence has an ordinary limit; the selected source explicitly retains this distinction.[1]
Sources
- Computability of the Channel Reliability Function and Related Bounds
Notes on Computability of the Channel Reliability Function and Related Bounds
Revised author manuscript of May 18, 2024: Introduction and Section 2 define optimal error, the limsup exponent and the known high-rate interval. Its noncomputability result over input channels is not a solution for a fixed BSC.
- The Asymptotic Generalized Poor-Verdú Bound Achieves the BSC Error Exponent at Zero Rate
Notes on The Asymptotic Generalized Poor-Verdú Bound Achieves the BSC Error Exponent at Zero Rate
Primary BSC block-code analysis establishes zero-rate exponential tightness and explicitly distinguishes this endpoint result from the open low-rate characterization.