The Feedback Capacity of Discrete Memoryless Channels with Input Constraints

We consider the input-constrained feedback capacity of discrete memoryless channels. While we focus specifically on channels in which the inputs are binary sequences in which consecutive 1s are disallowed, the techniques apply more generally to any memoryless channel with finite input and output alphabets, and input sequences satisfying a constraint with finite memory. It is known that the feedback capacity computation for such channels can be formulated as an average-reward dynamic program (DP). In the case of the binary erasure channel with a no-consecutive-1s input constraint, we obtain an exact expression for the capacity by explicitly solving the Bellman equation associated with the DP formulation. Furthermore, the optimal policy of the DP leads to a simple and elegant zero-error coding scheme that achieves capacity. For a general binary-input, binary-output channel, we are able to obtain an explicit expression for feedback capacity under the no-consecutive-1s input constraint by solving the associated Bellman equation. The optimal policy for the DP suggests a capacity-achieving coding scheme based on posterior matching. 

 This is joint work with Oron Sabag and Haim Permuter (Ben-Gurion University, Israel).