Second- and Higher-Order Asymptotics For Erasure and List Decoding

Vincent Y. F. Tan, Pierre Moulin

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.

Comparison of channel coding rates and expected rates for blocklengths n=2,000 and n=100,000. The gain from erasure decoding is particularly prominent at smaller blocklengths.

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

Abstract

We derive the optimum second-order coding rates, known as second-order capacities, for erasure and list decoding. For erasure decoding for discrete memoryless channels, we show that second-order capacity is $\sqrt{V}\Phi^{-1}(\epsilon_t)$ where $V$ is the channel dispersion and $\epsilon_t$ is the total error probability, i.e., the sum of the erasure and undetected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. We also show that the analogous result also holds for lossless source coding with decoder side information, i.e., Slepian-Wolf coding. For list decoding, we consider list codes of deterministic size that scales as $\exp(\sqrt{n}l)$ and show that the second-order capacity is $l+\sqrt{V}\Phi^{-1}(\epsilon)$ where $\epsilon$ is the permissible error probability. We also consider lists of polynomial size $n^\alpha$ and derive bounds on the third-order coding rate in terms of the order of the polynomial $\alpha$. These bounds are tight for symmetric and singular channels. The direct parts of the coding theorems leverage on the simple threshold decoder and converses are proved using variants of the hypothesis testing converse.
BibTeX
@misc{tan2014second,
  author = {Vincent Y. F. Tan and Pierre Moulin},
  title = {{Second- and Higher-Order Asymptotics For Erasure and List Decoding}},
  year = {2014},
  eprint = {1402.4881},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.4881},
}
Figure