Algorithms for computing the capacity of Markov channels with side information

Consider a finite state, irreducible Markov channel {S_k}. At time k the channel output Y _k depends only on the channel input X_k and the channel state S_k. Let U_k and V_k be the CSIT (channel state information at transmitter) and the CSIR (CSI at receiver) respectively. In this paper we provide algorithms to compute the capacity of the Markov channel under various assumptions on CSIT and CSIR where the assumption P(S _k = s|U₁^k) = P(S_k|U_k) is not necessarily satisfied. Our algorithms are based on the extension of ideas developed for channels with feedback.