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.
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.
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