language: en

Capacity, Mutual Information, and Coding for Finite-State Markov Channels

Andrea J. Goldsmith, Member, IEEE and Pravin P. Varaiya, Fellow, IEEE

Abstract The Finite-State Markov Channel (FSMC) is a discrete-time varying channel whose variation is determined by a finite-state Markov process. These channels have memory due to the Markov channel variation. We obtain the FSMC capacity as a function of the conditional channel state probability. We also show that for i.i.d. channel inputs, this conditional probability converges weakly, and the channel's mutual information is then a closed-form continuous function of the input distribution. We next consider coding for FSMCs. In general, the complexity of maximum-likelihood decoding grows exponentially with the channel memory length. Therefore, in practice, interleaving and memoryless channel codes are used. This technique results in some performance loss relative to the inherent capacity of channels with memory. We propose a maximum-likelihood decision-feedback decoder with complexity that is independent of the channel memory. We calculate the capacity and cutoff rate of our technique, and show that it preserves the capacity of certain FSMCs. We also compare the performance of the decision-feedback decoder with that of interleaving and memoryless channel coding on a fading channel with 4PSK modulation.

Index Terms: Finite-State Markov Channels, Capacity, Mutual Information, Decision-Feedback Maximum-Likelihood Decoding.

[Work supported in part by an IBM graduate fellowship, and in part by the PATH program, Institute of Transportation Studies, University of California, Berkeley. A. Goldsmith is with the Department of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125.]

[P. Varaiya is with the Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720.]