Abstract
This paper provides a precise mathematical characterization of erasure and list decoding performance in the finite blocklength regime. While classical information theory focuses on asymptotic capacity, practical systems operate at finite lengths where error probabilities are non-zero. We derive second-order asymptotic expansions for the achievable rates of these decoding strategies. Our results demonstrate that allowing for erasures or list outputs can significantly enhance the expected transmission rate at moderate blocklengths, providing a rigorous mathematical framework for optimizing modern communication protocols like ARQ.
1. Introduction
In real-world communication, messages are transmitted over finite time intervals, or blocklengths ($n$). In this regime, the maximum achievable rate $R$ is not just the capacity $C$, but is influenced by the channel dispersion $V$ and the allowed error probability $\epsilon$. This paper extends the second-order analysis—characterized by terms of order $1/\sqrt{n}$—to two common practical strategies: erasure decoding and list decoding.
2. Decoding Strategies
Erasure decoding allows the receiver to output a special "erasure" symbol when the received signal is ambiguous, often triggering a retransmission in systems like Automatic Repeat Request (ARQ). List decoding allows the receiver to output a list of $L$ candidate messages; a success is recorded if the true message is within this list. Both strategies aim to improve reliability and throughput in non-asymptotic scenarios.
3. Theoretical Contributions
The authors employ probabilistic tools, including the Berry-Esseen theorem and hypothesis testing converses, to derive new bounds. A key insight is that for erasure decoding, the second-order capacity is governed by the total error probability (the sum of undetected errors and erasures). For list decoding, the research shows how the second-order rate scales linearly with the logarithm of the list size when the list size grows moderately with blocklength ($L \approx \exp(\sqrt{n}l)$).
4. Numerical Analysis and Discussion
To visualize these theoretical gains, the authors modeled a Binary Symmetric Channel (BSC) with crossover probability $q=0.11$. As shown in the figure below, the "Expected Rate" ($E[R_e^{(n)}]$), which accounts for successful transmissions after erasures, can exceed the standard channel coding rate ($R_c^{(n)}$) that does not allow erasures.
This gain is most pronounced at moderate blocklengths (e.g., $n=2,000$) and diminishes as $n$ increases toward the asymptotic limit, where both rates converge to capacity. At $n=2,000$, the expected rate peaks significantly higher than the standard rate when the erasure probability is approximately $10^{-2}$.
5. Conclusion
This research provides a granular look at the trade-offs between reliability, latency, and throughput. By quantifying the benefits of the "option to fail" or "option to list," it offers valuable insights for the design of short-latency communication systems. Future work will focus on closing the remaining third-order gaps in list decoding bounds for general channels.
Summary updated