Capacity, mutual information, and coding for finite-state Markov channels

The Finite-State Markov Channel (FSMC) is a discrete-time varying channel whose variation is determined by a finite-state Markov process. We obtain the FSCM capacity as a function of the channel state probability conditioned on all past inputs and outputs, and the channel state probability conditioned on all past outputs alone. We also show that when the channel inputs are i.i.d., both conditional probabilities converge in distribution. In this case, the maximum mutual information of the FSMC, I_iid, is determined from these limit distributions. A class of channels for which I_iid equals Shannon capacity is also defined. Next, we consider coding techniques for these channels. We propose a decision-feedback decoding algorithm that uses the channel's Markovian structure to determine the maximum likelihood input sequence. We show that, for a particular class of FSMCs, this decoding scheme preserves the inherent channel capacity. We also present numerical results for the capacity and cutoff rate of a two-state variable noise channel with 4-PSK modulation using the decision-feedback decoder.