Abstract
Communication over unpredictable, time-varying channels typically requires either worst-case assumptions or high-bandwidth feedback for adaptation. This paper demonstrates that "zero-rate" feedback—where the feedback overhead becomes negligible as the message length grows—is sufficient to achieve the empirical capacity of an unknown channel. By employing a randomized rateless coding strategy with periodic channel estimation, the proposed method adapts to the actual sequence of channel states encountered without requiring a high-speed return link.
Introduction
In information theory, communication channels are often modeled with fixed, known statistics. However, real-world channels like Wi-Fi or cellular networks are dynamic and unpredictable. Traditional approaches like the Arbitrarily Varying Channel (AVC) model often assume a worst-case scenario, which can lead to inefficient use of the channel. A more practical goal is to achieve the empirical capacity: the maximum rate possible given the specific sequence of states that actually occurred during transmission.
While prior research established that achieving empirical capacity is possible with full output feedback, this paper investigates the minimum amount of feedback required. The authors prove that a "zero-rate" feedback link is sufficient.
System Model and Methodology
The authors propose a system architecture that utilizes common randomness and a limited feedback link, as illustrated in Figure 1.
The core of the methodology is a randomized rateless coding strategy. The transmission process is structured hierarchically to facilitate adaptation:
- Rounds and Chunks: The total transmission time $N$ is divided into rounds, each intended to deliver a fixed number of bits. Each round is further partitioned into smaller units called chunks.
- Randomized Training: Within each chunk, "pilot" or training symbols are inserted at positions determined by a shared random seed (common randomness). These symbols allow the decoder to estimate the current channel quality.
- Minimal Feedback Triggers: Instead of streaming back the channel state, the decoder provides "zero-rate" feedback at the end of each chunk. It sends one of three signals: "DECODED" (success), "BAD NOISE" (abort and retry), or "KEEP GOING" (continue transmission).
This hierarchical structure is detailed in Figure 2.
Key Insights
The effectiveness of this approach stems from several key ideas:
- Feedback as a Trigger: High-bandwidth feedback is unnecessary if the return link is used only to signal critical state changes or successful decoding.
- The Power of Common Randomness: By sharing a random seed, the encoder and decoder can coordinate training positions and codebook selections without using up precious communication bandwidth.
- Efficiency relative to Prior Work: This work achieves results similar to established individual sequence models (e.g., Shayevitz and Feder [3]) but reduces the feedback requirement from full output feedback to a zero-rate link.
Results and Conclusion
The primary theoretical result, Theorem 1, proves that for any desired gap $\rho > 0$, there exists a coding strategy with a vanishing feedback rate that achieves a transmission rate within $\rho$ of the empirical mutual information. As the blocklength $N$ approaches infinity, the feedback rate $R_{fb}$ goes to zero while the communication rate remains optimal for the realized channel sequence.
While the current scheme uses a fixed input distribution $P$, future work could explore adapting $P$ over time to reach the true empirical capacity. Additionally, reducing the requirements for common randomness and developing "horizon-free" versions for indefinite streaming remain open challenges.
Summary updated