Capacity of a POST channel with and without feedback

Himanshu Asnani, Haim H. Permuter, Tsachy Weissman

Abstract

This paper investigates the capacity of Previous Output is the STate (POST) channels, a class of channels with memory where the current state is determined by the previous channel output. While feedback typically increases the capacity of channels with memory, the authors prove a counter-intuitive result: for binary POST channels, feedback provides no capacity gain. This equivalence is established through a rigorous framework of directed information and convex optimization. The study further reveals that this property is sensitive to alphabet size, as feedback does increase capacity when the number of symbols grows.

Introduction

In information theory, calculating the capacity—the maximum rate of reliable data transmission—is well-understood for memoryless channels. However, channels with memory, where the current behavior depends on past events, present significant challenges. A common heuristic in the field is that providing feedback (telling the sender what the receiver actually got) increases the capacity of channels with memory, as seen in the "trapdoor" or "Ising" channels. This paper examines the POST channel to test the limits of this heuristic, specifically focusing on whether the sender gains an advantage by knowing the previous output in real-time.

The POST($\alpha$) Channel Model

The primary model studied is the POST($\alpha$) channel. In this model, the channel's "state" is simply the very last bit that was successfully received ($y_{i-1}$). The channel's behavior flips based on this state: if the last output was 0, it acts as a Z-channel (where a 1 can be received as a 0, but a 0 is always received as a 0). Conversely, if the last output was 1, it acts as an S-channel, which is the mirror image of the Z-channel.

Figure 1: Transition diagrams for the POST(α) channel, showing the Z-channel behavior for y_{i-1}=0 and S-channel behavior for y_{i-1}=1.

Methodology and Theoretical Framework

The authors employ a rigorous mathematical framework centered on Directed Information and Causal Conditioning. They treat the capacity calculation as a convex optimization problem and apply Karush-Kuhn-Tucker (KKT) conditions to establish a necessary and sufficient condition: if the output distribution produced by the optimal feedback-driven input can be mimicked by an input distribution that does not use feedback, then feedback provides no gain.

Figure 2: General communication system model over a channel with state S_i, where the encoder (En) produces X_i and the decoder (De) produces the estimate M_hat.

Through recursive analysis, the authors derive the exact input distributions required to achieve capacity. They prove that for the binary case, a non-feedback distribution always exists that matches the feedback-optimized output, effectively "exhausting" the channel's memory through its own structure.

Key Insights and Results

Capacity Equivalence in Binary Channels

The most significant finding is that for the POST($\alpha$) channel, the capacity with and without feedback is exactly the same. Furthermore, this capacity is identical to that of a standard memoryless Z-channel with parameter $\alpha$. This result generalizes to the binary POST($a, b$) channel, covering all possible transition probabilities for binary inputs and outputs.

The Role of Alphabet Size

Interestingly, the "no-gain from feedback" result is strictly tied to the binary nature of the inputs. The authors demonstrate that as the alphabet size $m$ (the number of possible symbols) increases, feedback eventually begins to increase capacity. For instance, in a constructed POST channel with $m=2^{10}$, the feedback capacity was found to be approximately 3.38 bits, significantly higher than the non-feedback upper bound of 2.77 bits.

Infinite Memory Inputs

To achieve capacity without feedback in the binary case, the required input distribution must be stationary but is not a simple Markov process. It effectively requires "infinite memory" of past inputs to match the performance of a system that has access to real-time feedback.

Conclusion

The study of POST channels provides a surprising exception to the general rule that feedback helps in channels with memory. While the mathematical proof using KKT conditions is robust, the authors note that a direct physical or intuitive explanation for why feedback is redundant in the binary case remains an open question. Future work may involve exploring higher-order memory models where the state depends on a longer window of previous outputs, as well as the development of practical coding schemes to achieve these theoretical limits.

Summary updated

Abstract

We consider finite state channels where the state of the channel is its previous output. We refer to such channels as POST (Previous Output is the STate) channels. Our focus is on a simple binary POST channel, with binary inputs and outputs where the state determines if the channel behaves as a Z or an S channel (of equal capacities). We show that the non feedback capacity equals the feedback capacity, despite the memory in the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that is ignorant of the feedback. Indeed, we show that this is a necessary and sufficient condition for the feedback capacity to equal the non feedback capacity for any finite state channel.
BibTeX
@inproceedings{asnani2013capacity,
  author = {Himanshu Asnani and Haim H. Permuter and Tsachy Weissman},
  title = {{Capacity of a POST channel with and without feedback}},
  booktitle = {ISIT},
  year = {2013},
  url = {https://openreview.net/forum?id=xJiEFbZ1eM},
}
Figure