n late 1950s and early 1960s, Gilbert and Elliott at Bell Labs were modeling burst-noise telephone circuits with a very simple two-state channel model with memory. This simple model allowed them to evaluate channel capacity and error rate performance through bursty wireline telephone circuits. However, it took another 30 years for the so-called Gilbert-Elliott channel (GEC) and its generalized finite-state Markov channel (FSMC) to be applied in the design of second-generation (2G) wireless communication systems. Since the mid 1990s, the GEC and FSMC models have been widely used for modeling wireless flat-fading channels in a variety of applications, ranging from modeling channel error bursts to decoding at the receiver. FSMC models are versatile, and with suitable choices of model parameters, can capture the essence of time-varying fading channels. This article's goal is to provide an in-depth understanding of the principles of FSMC modeling of fading channels with its applications in wireless communication systems. Digital Object Identifier 10.1109/MSP.2008 [ Parastoo Sadeghi, Rodney A. Kennedy, Predrag B. Rapajic, and Ramtin Shams ] While the emphasis is on frequency nonselective or flat-fading channels, this understanding will be useful for future generalizations of FSMC models for frequency-selective fading channels. The target audience of this article include both theory-and practice-oriented researchers who would like to design accurate channel models for evaluating the performance of wireless communication systems in the physical or media access control layers, or those who would like to develop more efficient and reliable transceivers that take advantage of the inherent memory in fading channels. Both FSMC models and flat-fading channels will be formally introduced. However, a background in time-varying fading communication channels is beneficial. We consider the FSMC modeling of fading channels from five distinct viewpoints. First, we provide a brief history of FSMC models and the FSMC modeling of flat-fading channels. Second, we define the parameters of FSMC models and discuss how these parameters can be derived from flat-fading channel statistics. We point out the trade-offs between model accuracy and complexity. Third, we categorize applications of FSMC models for fading channels into four categories and discuss the FSMC model applicability and accuracy in each application. We pay special attention to the effect of FSMC memory order on the model accuracy. Fourth, we consider the information-theoretical aspects of FSMC models and the FSMC modeling of fading channels. Finally, we present open questions and directions for future research. For easier access to the technical contents, the reader can refer to the "List of Acronyms" and "Notational Conventions." THE HISTORY OF FSMC The study of finite-state communication channels with memory dates back to the work by Shannon in 1957 [1]. In [1], 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. [2] 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 [3] . One main distinction between Gilbert's model and Blackwell's model [2] 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 [3] , Elliott used this model to evaluate and compare the error rate performance of error correcting and error detecting codes over burst-noise channels [4] . 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 Fritchman [6] 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 [7] , 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 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. From 1969 to the mid 1970s, research activity on applications of FSMCs was limited to modeling error bursts in digital wireline telephone circuits and HF tropospheric/ionospheric wireless links between fixed stations. The proposed models were mainly variations of earlier ones developed up to 1968, such as the Fritchman model [6] . While earlier works mainly focused on first-order characterization of channels with memory, higher-order Markov models were proposed in 1973 by Blank and Trafton [8], where the probability of transition to a state depended on M > 1 previous states. For a detailed survey of the modeling and applications of channels with memory up to 1978, see [9] . From 1978 to 1989, research activity for finding new applications of FSMCs in digital communications was more or less dormant. During this period, theory and techniques for mobile radio communications were in early stages of development and cellular digital telephone networks did not emerge (were not commercially available) until the early 1990s. This explains why research activity on applications of FSMC for digital mobile communication systems did not receive impetus until the early to mid 1990s. 1989-PRESENT: FSMC MODELING OF MOBILE RADIO FADING CHANNELS Fading channels with memory are common in mobile radio communications [64] . With the advent and commercial success of digital cellular networks in the early 1990s, there was an immediate need for accurate modeling of fading channels with memory. The channel models helped system designers analyze and improve system performance measures, such as the error correcting capability of channel codes or the packet throughput. But more importantly, the use of channel models with memory for decoding at the receiver would potentially result in higher information rates than those achieved by assuming a memoryless channel [27] . It was the work by Wang and Moayeri in 1995 [14] that is widely viewed to have revived FSMC modeling of fading channels in mobile radio communications. One of the novelties of their work was to explicitly establish the link between the statistical Clarke's model for fading channels [66] and the FSMC states. In particular, each FSMC state in their model represented a range of received signal-to-noise ratio (SNR), which in turn determined the error probability in that state. Based on this assumption, Wang and Moayeri provided analytical expressions for states, state transition probabilities, and error probabilities in each state. The original FSMC modeling of fading channels as proposed in [14] or its variations are still widely used in the literature. Almost concurrently with Wang and Moayeri, Goldsmith and Varaiya proposed a new iterative method for computing the information rates and capacity of data-independent FSMC models with independent and identically distributed (i.i.d) inputs. They also introduced a maximum-likelihood (ML) decisionfeedback decoding technique for the receiver that took the inherent channel memory into account [27] . Their work was a generalization of an earlier study by Mushkin and Bar-David in [10] on the capacity and coding for the GEC. Traditionally, FSMCs have been used to model error bursts in fading channels during the design stages of wireless communication systems. This helps system designers analyze and improve performance measures in the physical or media access control layers. Since 1997, FSMC models have enabled closed-form or simulation-based analysis of system-level performance measures, such as packet throughput [20] , [21] , packet error distribution (PED) [18] , and packet error rate (PER) [17] through bursty wireless channels. The bit error rate (BER) in more sophisticated communications systems that include receiver diversity has been studied using FSMC models in [23] and [24] . The potential benefits of incorporating FSMC memory into decoding algorithms at the receiver to achieve higher information rates has been known as early as 1989 [10] . Since the late 1990s, an active area of research has been to develop practical decoding techniques at the receiver using FSMC models for fading channels. FSMC models enable implementation of mathematically tractable channel estimation and data decoding algorithms for time-varying fading channels [35] and it is shown that information rates higher than the memoryless channel capacity become possible. More recently, successive decoding is proposed for fading channels modeled by FSMCs that takes channel memory into account [33] . In a later section on FSMC applications, we will provide a more in-depth categorization of the FSMC applications for fading channels. Since 1995 [14] , first-order FSMC models for fading channels have been the models of choice due to their computational simplicity and the ease with which model parameters can be determined. A first-order Markovian assumption in the FSMC model means that given the previous fading channel state, the current state is statistically independent of all other past and future fading channel states. Ever since, the accuracy of first-order FSMC models for fading channels, compared with higher-order FSMC models, has been the subject of research. One main research aim has been to find channel fading rates over which low-order FSMC models are a sufficiently good match with other widely accepted statistical fading models, such as the Clarke's model [66] . While it is generally accepted that first-order FSMC models are more accurate for slow fading channels than for medium-rate or fast-fading channels, still today, there is no consensus about exact fading rates over which first-order FSMC models are accurately applicable for fading channels. In a later section on FSMC applications, we will provide a detailed examination of the literature on the accuracy of first-order and higher-order FSMC models for fading channels. This study will take into account the FSMC application and the criterion used for accuracy analysis. A summary of the history of FSMC and its applications is shown in Table 1 . We study two important aspects of flat-fading channels in wireless communications. First, we review the channel observation equation, which relates channel input to channel output. Second, we study the time-varying nature of the fading channel, which is a key factor in its FSMC modeling. The decision to focus on flat-fading channels is made because FSMC models have been mainly used for modeling such channels in the literature. While the emphasis is on flat-fading channels, this under-
We refer to REF for a survey of the development and applications of FSMC models.
Finite-state Markov modeling of fading channels - a survey of principles and applications
IEEE Signal Processing Magazine
IEEE Signal Processing Magazine
Computer Science