A posterior matching scheme for finite-state channels with feedback

For a memoryless channel, although feedback cannot increase capacity, it can reduce the complexity and/or improve the error performance of a communication system. Recently, Shayevitz and Feder proposed the posterior matching scheme (PMS) which is a simple recursive transmission scheme that achieves the capacity of memoryless channels with feedback. Furthermore, Coleman provided a Lyapunov function approach to prove capacity achievability of the PMS. In this paper, we investigate a capacity-achieving PMS for the case of finite-state channels (FSCs). We first derive a single-letter expression for the capacity of the FSC with delayed output and state feedback by formulating the problem in a stochastic control framework. The resulting capacity expression can be evaluated using dynamic programming. We then propose a simple recursive PMS-like transmission scheme. To prove capacity achievability of the proposed PMS, we identify an appropriate Markov chain induced by the PMS.