The effect of memory order on the capacity of finite-state Markov and flat-fading channels

In this paper, we study the effect of memory order on the capacity of finite-state Markov channels (FSMC). We analytically compare the capacity of an originally high-order FSMC model with the capacity of its reduced memory order version. We show that the capacity difference is caused by two factors: 1) the channel entropy difference, and 2) the channel observability difference between the two models. While the first factor, alone, results in underestimation of the original FSMC capacity by the reduced-order FSMC model, due to the existence of the second factor, capacity overestimation can also occur. Explicit examples of FSMC models are provided, where the reduced-order FSMC model overestimates the capacity of the original high-order channel. To show the practical significance of the analysis, we model time-varying flat-fading (FF) channels with FSMC models. It is observed that the first-order FSMC models can provide both higher and lower estimates of the FF channel capacity, compared to higher order FSMC models