Two-letter capacity formula for channels with memory and feedback

摘要

For a class of channels with unit memory on previous channels outputs, we identify necessary and sufficient conditions, to test whether the capacity achieving channel input distributions with feedback are time-invariant, and whether feedback capacity is characterized by a two-letter expression, similar to that of memoryless channels. The method is based on showing that a certain dynamic programming equation, which in general, is a nested optimization problem over the sequence of channel input distributions, reduces to a non-nested optimization problem. We then apply these conditions to derive a two-letter expression for the feedback capacity of the Binary State Symmetric Channel, which is evaluated explicitly. Further, we derive computationally efficient upper bounds on the probability of maximum likelihood decoding error in the finite-blocklength regime.