Introduction
In modern communication systems, the presence of a feedback channel allows the transmitter to adapt its strategy based on the receiver's state. Variable-Length Feedback (VLF) codes leverage this by allowing the transmitter to stop sending data as soon as the receiver can decode the message with sufficient confidence. While the first-order performance limit—the channel capacity $C$—is well-established, characterizing the second-order terms is crucial for understanding performance at finite blocklengths. This paper sharpens the second-order achievability bounds for VLF codes over both known and unknown (universal) channels, demonstrating that higher data rates are achievable with fixed error probabilities than previously estimated.
Problem Formulation
Traditional fixed-length codes operate over a predetermined duration. In contrast, VLF codes utilize a feedback link to determine a stopping time $\tau$. The goal is to maximize the message set size $M$ for a given average transmission time $E[\tau] = N$ and a target error probability $\epsilon$.
Previous research identified a second-order penalty term of approximately $\log N$. However, a gap remained between the best-known achievability bounds and the theoretical converse. This research specifically addresses this gap, aiming to refine the penalty term to $\frac{C}{C_1} \log N$, where $C_1$ represents a measure of the distinguishability of the channel's symbols. Furthermore, the study explores Universal VLF (UVLF) codes, where the channel statistics are unknown to both the transmitter and the receiver.
Methodology
1. Modified Yamamoto–Itoh Scheme
The authors propose a variation of the Yamamoto–Itoh coding scheme. While standard versions typically involve a communication phase followed by a confirmation phase, this modified approach utilizes two communication phases and one confirmation phase. Critically, the scheme allows for random stopping times for each phase. By making the duration of the confirmation phase dependent on the specific noise realization, the system achieves higher efficiency than fixed-length checkpoint schemes.
2. Empirical Mutual Information (EMI) Decoding
To address the universal case where channel parameters (such as the flip probability of a Binary Symmetric Channel) are unknown, the authors employ Empirical Mutual Information (EMI) decoding. Instead of relying on information density—which requires knowledge of the channel—the receiver calculates the statistical correlation between the observed output and potential messages. This allows the system to remain robust across a family of possible channels.
3. Analytical Tools
The proofs rely on nonlinear renewal theory to estimate the distribution of stopping times. Additionally, a refined method of types is used to provide tighter bounds on the probabilities of rare error events, which is essential for sharpening the second-order terms.
Key Results
Improved Achievability for DMCs
For known Discrete Memoryless Channels (DMCs), the authors derived a new lower bound for the codebook size $M^*(N, \epsilon)$: $$\log M^*(N, \epsilon) \ge \frac{NC}{1-\epsilon} - \frac{C}{C_1} \log N - \log \log N + O(1)$$ This result refines the second-order term compared to the landmark 2011 Polyanskiy et al. paper. Since $C_1 \ge C$ (and often $C_1 \gg C$), the penalty for finite-time communication is significantly reduced.
Universal VLF Bounds
The paper provides the first second-order achievability bound for UVLF codes over general DMCs. A significant insight is that universality is relatively "cheap": the same optimal reliability function (the rate at which error probability decays) can be achieved even without prior knowledge of the channel, provided EMI-based metrics are used.
Extension to Gaussian Channels
The results were extended to Additive White Gaussian Noise (AWGN) channels with power constraints. The new bounds improve upon the previous state-of-the-art results from 2017, providing a more optimistic outlook for finite-length performance in satellite and radio communications.
Discussion and Limitations
While this work significantly tightens the achievability bounds, a gap of $O(\log N)$ still exists between these new lower bounds and the known converse (upper bound). Closing this gap remains a primary open challenge in information theory.
Furthermore, the universal results are currently asymptotic. The derivation of non-asymptotic bounds for UVLF codes is hindered by the lack of a non-asymptotic version of the universal stopping time lemma in existing mathematical literature. Finally, while the theoretical bounds are improved, the practical computational complexity of implementing EMI-based decoders for extremely large message sets was not the focus of this study and warrants further investigation.
Summary updated