Finite-state Markov modeling of fading channels - a survey of principles and applications <s> 1957-1968: DEVELOPMENT OF FSMC MODELS <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> 1957-1968: DEVELOPMENT OF FSMC MODELS <s> A model of a burst-noise binary channel uses a Markov chain with two states G and B. In state G, transmission is error-free. In state B, the channel has only probability h of transmitting a digit correctly. For suitably small values of the probabilities, p, P of the B $rA G and G $rA B transitions, the model simulates burst-noise channels. Probability formulas relate the parameters p, P, h to easily measured statistics and provide run distributions for comparison with experimental measurements. The capacity C of the model channel exceeds the capacity C(sym. bin.) of a memoryless symmetric binary channel with the same error probability. However, the difference is slight for some values of h, p, P; then, time-division encoding schemes may be fairly efficient. <s> BIB002 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> 1957-1968: DEVELOPMENT OF FSMC MODELS <s> The error structure on communication channels used for data transmission may be so complex as to preclude the feasibility of accurately predicting the performance of given codes when employed on these channels. Use of an approximate error rate as an estimate of performance allows the complex statistics of errors to be reduced to a manageable table of parameters and used in an economical evaluation of large collections of error detecting codes. Exemplary evaluations of error detecting codes on the switched telephone network are included in this paper. On channels which may be represented by Gilbert's model of a burst-noise channel, the probabilities of error or of retransmission may be calculated without approximations for both error correcting and error detecting codes <s> BIB003 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> 1957-1968: DEVELOPMENT OF FSMC MODELS <s> The nature of the errors in a regenerative digital transmission system is such that a memoryless channel is a poor model for predicting the error phenomena. In this paper we present a model which provides a reasonable approximation to observed error phenomena. The memory of the channel is represented by a Markov model. This model is similar to the model developed by E. N. Gilbert, but several important modifications greatly simplify the estimation of parameters, and make the model correspond more closely to the physical phenomena involved. Bounds for the channel capacity of the binary regenerative channel are obtained. Error separation, block error, and burst statistics are derived. Error model parameters are derived from available experimental data on the T1 digital transmission line and the switched telephone network. The Markov model is shown to provide a good representation of the observed error phenomena. <s> BIB004 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> 1957-1968: DEVELOPMENT OF FSMC MODELS <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> BIB005
The study of finite-state communication channels with memory dates back to the work by Shannon in 1957 BIB001 . In BIB001 , Shannon proved coding theorems for finite-state channels (FSCs) with discrete channel input and output symbols, where the channel state could be calculated at the transmitter, but not necessarily at the receiver. In 1958, Blackwell et al.  proved that for a practical class of FSCs with memory, reliable transmission is possible at rates below the channel capacity. In 1960, Gilbert introduced a new type of FSC model to determine the information capacity of wireline telephone circuits with burst-noise BIB002 . One main distinction between Gilbert's model and Blackwell's model  was in the way channel output was defined to depend on channel states and inputs. In Blackwell's model, channel output was a deterministic function of the current channel state, which, in turn, stochastically depended on current channel input and previous channel state. Whereas in Gilbert's model, channel output was a probabilistic function of the current channel input and the current channel state. In particular, each channel state in Gilbert's model was associated with a discrete memoryless channel (DMC). Despite its simplicity, Gilbert's model was the first nontrivial example of channel models with memory, where the channel state is statistically independent of channel input symbols and is unknown to the transmitter or the receiver. Soon after the work of Gilbert BIB002 , Elliott used this model to evaluate and compare the error rate performance of error correcting and error detecting codes over burst-noise channels BIB003 . This channel model is known as the GEC, which is shown in Figure 1 . States are determined by the upper two-state Markov chain model and are denoted by good G and bad B. The probability of moving from the good state G to the bad state B is b Pr(G → B ) and the probability of moving from the bad state B to the good state G is g Pr(B → G ). When the channel is in the good state G, channel output is related to the channel input through a DMC, governed by error probability P G Pr(0 → 1|G ). In the original version of the GEC, Gilbert assumed a noise-free good state with zero error probability P G = 0. The zero error probability assumption in the good state allowed Gilbert to calculate capacity in closed form. Elliott later modified the model to accommodate for the error probability in the good state to be nonzero or P G > 0. In the bad state B, the error probability is higher than that in the good state and is defined as P B Pr(0 → 1|B ). Researchers in the late 1960s extended the model proposed by Gilbert and Elliott to improve their representations of channels with memory. In 1968, McCullough BIB004 introduced more channel states in the model, each with a different error rate. State transitions in BIB004 were allowed only immediately following an error in the state. In another work in 1967, Fritchman  proposed a FSC with J error free and K − J error states. However, the model was complicated in terms of deriving channel error statistics, unless there was a single error state or K − J = 1, which effectively made the Fritchman model similar to the GEC model. In 1968, Gallager further developed the information theory of FSMCs BIB005 , making it a classical subject in advanced information theory. Originally, Gallager used the term FSC, where channel states are assumed to be the output of a Markov chain. FSMC is more clarifying and will be used throughout the article. In [7, pp. 97-111, 176-187 ], Gallager provides rigorous definitions, coding theorems, error exponents, and several examples of FSMCs with memory. Gallager also mentions fading channels in wireless radiotelephony as physical channels with memory that can be represented by FSMCs. Gallager's definition of FSMCs is the standard definition used by [FIG1] The GEC model BIB002 , BIB003 was the first nontrivial example of burst-noise channel models with memory. Channel states belong to the set {G, B} are statistically independent of channel input symbols, and are unknown to the transmitter or the receiver. States are determined by the upper two-state Markov chain model. The channel input-output behavior is governed by one of the lower two discrete memoryless channels, selected according to the current channel state. researchers today. This model accommodates for both cases where the channel state transition is driven and controlled by the channel input (such as intersymbol-interference (ISI) channels), as well as the case where the channel state is statistically independent of the channel input (such as fading channels). We will refer to the first case as data-dependent FSMC models and to the second case as data-independent FSMC models, respectively. Since the state of fading channels is independent of the channel input, our focus is naturally on data-independent FSMC models.