Finite-state Markov modeling of fading channels - a survey of principles and applications <s> FORMAL DEFINITION: THREE TYPES OF STOCHASTIC PROCESSES <s> In this paper we will develop certain extensions and refinements of coding theory for noisy communication channels. First, a refinement of the argument based on “random” coding will be used to obtain an upper bound on the probability of error for an optimal code in the memoryless finite discrete channel. Next, an equation is obtained for the capacity of a finite state channel when the state can be calculated at both transmitting and receiving terminals. An analysis is also made of the more complex case where the state is calculable at the transmitting point but not necessarily at the receiving point. <s> BIB001 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> FORMAL DEFINITION: THREE TYPES OF STOCHASTIC PROCESSES <s> Communication Systems and Information Theory. A Measure of Information. Coding for Discrete Sources. Discrete Memoryless Channels and Capacity. The Noisy-Channel Coding Theorem. Techniques for Coding and Decoding. Memoryless Channels with Discrete Time. Waveform Channels. Source Coding with a Fidelity Criterion. Index. <s> BIB002 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> FORMAL DEFINITION: THREE TYPES OF STOCHASTIC PROCESSES <s> 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. <s> BIB003 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> FORMAL DEFINITION: THREE TYPES OF STOCHASTIC PROCESSES <s> The information rate of finite-state source/channel models can be accurately estimated by sampling both a long channel input sequence and the corresponding channel output sequence, followed by a forward sum-product recursion on the joint source/channel trellis. This method is extended to compute upper and lower bounds on the information rate of very general channels with memory by means of finite-state approximations. Further upper and lower bounds can be computed by reduced-state methods <s> BIB004
The block diagram of the FSMC model is shown in Figure 6 at discrete time index . Three types of stochastic processes in FSMC models will be described next. The first stochastic component of the FSMC model is the channel input x , which can be either a memoryless or a correlated random process. The FSMC input is often discrete valued with P possible symbols. Historically, the study of discrete-valued channel inputs in FSMC models dates back to the early works of Shannon BIB001 , Blackwell et al.  , and Gallager BIB002 , as well as more recent ones, such as Goldsmith et al. BIB003 . From [7, p. 97] , it seems that the decision not to consider continuousvalued inputs was made for the ease of analysis. According to a recent study in BIB004 , this assumption is not essential and with some modifications continuous-valued channel inputs may also be considered. So far, continuous-valued channel inputs in FSMC models have received far less attention in the literature. The second stochastic component of the FSMC model is the channel state s . The number of FSMC states is finite and equal to K. As highlighted in Figure 6 , we have assumed that at time index , the state of the channel is equal to an arbitrary state s = m, m ∈ {0, . . . , K − 1}. The channel state is the output of a Markov chain. The state transition probability is the probability of moving from state k to state m and is denoted by Therefore, the channel state transition probability matrix P is a K × K matrix as follows: . . . . . . Often, the Markov state process is stationary and hence, the state transition probability is independent of time index . This is a reasonable assumption in many practical communication scenarios, where channel statistics do not change rapidly over time. In this article, we consider only indecomposable FSMC  Markovian Genie models, where roughly speaking, the influence of the initial channel state fades out with time. Let us denote the stationary probability of being in state k by π k = Pr(S = k). For stationary Markov models, the stationary state probability vector T is the solution to the eigenvalue equation where superscript T denotes matrix or vector transpose. The third type of stochastic process in the FSMC model is the one that probabilistically maps the channel input x to the channel output y at each channel state s . In other words, for each FSMC state, there is a corresponding memoryless channel, which determines the channel's input-output relationship. This probabilistic relationship is often referred to as the channel observation law, or simply as the channel law, and is denoted by Pr(y |x , s ). The channel output y is often discrete valued. However, a continuous channel output is also allowed. The channel observation law is independent of time index , due to stationarity. For practical communication purposes, it is often useful to introduce the FSMC error or noise z , which is a function of the current channel input and output such as z = f(x , y ). The corresponding error probability is given by Pr(z |x , s ), which is shown in the lower part of Figure  6 . The FSMC error probability often depends on the type of modulation at the transmitter, the physical law that governs the channel input-output relationship, and the type of detection at the receiver. It is important to note that the presence of the stochastic channel input, unknown to the receiver, makes an FSMC model distinct from a classical hidden Markov model. In a hidden Markov model, there are only two types of stochastic processes: hidden Markov state s which is observed in stochastic noise process z . Similarly, the presence of the stochastic channel state, unknown to the receiver, makes an FSMC model distinct from a memoryless channel. In a memoryless channel, there are only two types of stochastic processes: channel input x and memoryless noise z .