Tight limits found for variable-length feedback communication codes
A Tight Second-Order Converse Bound for Variable-Length Feedback Codes
Information Theory
Summary
The paper looks at ways to send messages over a communication channel where the time it takes to decode can vary. The authors refine mathematical limits that describe how large the message set can be for a given average decoding time and error chance. They close a previous gap in understanding the second-order terms of this relationship, meaning they can predict these limits more precisely. The work also explains what the best coding strategies must look like and gives exact results for a specific communication channel called the binary erasure channel.
What this means in practice
- •For communication system engineers: Optimize message length and feedback timing in systems with variable decoding times to improve transmission efficiency under specific error constraints.
- •For data transmission protocol designers: Design protocols that achieve the fundamental limits of reliability and delay trade-offs in noisy communication channels using variable-length codes with feedback.
A theory result. No direct application yet.
Authors
Recep Can Yavas
Abstract
We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.