Capacity of channels with memory and feedback: Encoder properties and dynamic programming

This paper is concerned with capacity formulae for channels with memory and feedback, properties of the capacity achieving encoder, and dynamic programming for designing optimal encoders. The source is general and the techniques discussed include outputs of dynamic systems whose conditional probability distribution depends causally on the channel output and encoder law. First, encoder strategies are identified to maximize directed information, between the source and the channel output. Second, various definitions of information capacity are introduced via directed information, and converse coding theorems are derived. Encoder properties which lead to a tight upper bound on achievable rates are identified. Specifically, it is shown that channel inputs need to be independent of past channel outputs. Third, the form of the capacity achieving encoder is described. The encoder law is a functional of the a posteriori distribution of the source output given a sequence of observable channel outputs. Here a generalization of the Posterior Matching Scheme to channels with memory and feedback is shown to hold. Finally, dynamic programming is discussed, identifying analogies with optimal stochastic control under partial information.