Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY 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> BIB001 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY 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> BIB002 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> This tutorial provides an overview of the basic theory of hidden Markov models (HMMs) as originated by L.E. Baum and T. Petrie (1966) and gives practical details on methods of implementation of the theory along with a description of selected applications of the theory to distinct problems in speech recognition. Results from a number of original sources are combined to provide a single source of acquiring the background required to pursue further this area of research. The author first reviews the theory of discrete Markov chains and shows how the concept of hidden states, where the observation is a probabilistic function of the state, can be used effectively. The theory is illustrated with two simple examples, namely coin-tossing, and the classic balls-in-urns system. Three fundamental problems of HMMs are noted and several practical techniques for solving these problems are given. The various types of HMMs that have been studied, including ergodic as well as left-right models, are described. > <s> BIB003 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> Preface to the Second Edition. Preface to the First Edition. Acknowledgments for the Second Edition. Acknowledgments for the First Edition. 1. Introduction and Preview. 1.1 Preview of the Book. 2. Entropy, Relative Entropy, and Mutual Information. 2.1 Entropy. 2.2 Joint Entropy and Conditional Entropy. 2.3 Relative Entropy and Mutual Information. 2.4 Relationship Between Entropy and Mutual Information. 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information. 2.6 Jensen's Inequality and Its Consequences. 2.7 Log Sum Inequality and Its Applications. 2.8 Data-Processing Inequality. 2.9 Sufficient Statistics. 2.10 Fano's Inequality. Summary. Problems. Historical Notes. 3. Asymptotic Equipartition Property. 3.1 Asymptotic Equipartition Property Theorem. 3.2 Consequences of the AEP: Data Compression. 3.3 High-Probability Sets and the Typical Set. Summary. Problems. Historical Notes. 4. Entropy Rates of a Stochastic Process. 4.1 Markov Chains. 4.2 Entropy Rate. 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph. 4.4 Second Law of Thermodynamics. 4.5 Functions of Markov Chains. Summary. Problems. Historical Notes. 5. Data Compression. 5.1 Examples of Codes. 5.2 Kraft Inequality. 5.3 Optimal Codes. 5.4 Bounds on the Optimal Code Length. 5.5 Kraft Inequality for Uniquely Decodable Codes. 5.6 Huffman Codes. 5.7 Some Comments on Huffman Codes. 5.8 Optimality of Huffman Codes. 5.9 Shannon-Fano-Elias Coding. 5.10 Competitive Optimality of the Shannon Code. 5.11 Generation of Discrete Distributions from Fair Coins. Summary. Problems. Historical Notes. 6. Gambling and Data Compression. 6.1 The Horse Race. 6.2 Gambling and Side Information. 6.3 Dependent Horse Races and Entropy Rate. 6.4 The Entropy of English. 6.5 Data Compression and Gambling. 6.6 Gambling Estimate of the Entropy of English. Summary. Problems. Historical Notes. 7. Channel Capacity. 7.1 Examples of Channel Capacity. 7.2 Symmetric Channels. 7.3 Properties of Channel Capacity. 7.4 Preview of the Channel Coding Theorem. 7.5 Definitions. 7.6 Jointly Typical Sequences. 7.7 Channel Coding Theorem. 7.8 Zero-Error Codes. 7.9 Fano's Inequality and the Converse to the Coding Theorem. 7.10 Equality in the Converse to the Channel Coding Theorem. 7.11 Hamming Codes. 7.12 Feedback Capacity. 7.13 Source-Channel Separation Theorem. Summary. Problems. Historical Notes. 8. Differential Entropy. 8.1 Definitions. 8.2 AEP for Continuous Random Variables. 8.3 Relation of Differential Entropy to Discrete Entropy. 8.4 Joint and Conditional Differential Entropy. 8.5 Relative Entropy and Mutual Information. 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information. Summary. Problems. Historical Notes. 9. Gaussian Channel. 9.1 Gaussian Channel: Definitions. 9.2 Converse to the Coding Theorem for Gaussian Channels. 9.3 Bandlimited Channels. 9.4 Parallel Gaussian Channels. 9.5 Channels with Colored Gaussian Noise. 9.6 Gaussian Channels with Feedback. Summary. Problems. Historical Notes. 10. Rate Distortion Theory. 10.1 Quantization. 10.2 Definitions. 10.3 Calculation of the Rate Distortion Function. 10.4 Converse to the Rate Distortion Theorem. 10.5 Achievability of the Rate Distortion Function. 10.6 Strongly Typical Sequences and Rate Distortion. 10.7 Characterization of the Rate Distortion Function. 10.8 Computation of Channel Capacity and the Rate Distortion Function. Summary. Problems. Historical Notes. 11. Information Theory and Statistics. 11.1 Method of Types. 11.2 Law of Large Numbers. 11.3 Universal Source Coding. 11.4 Large Deviation Theory. 11.5 Examples of Sanov's Theorem. 11.6 Conditional Limit Theorem. 11.7 Hypothesis Testing. 11.8 Chernoff-Stein Lemma. 11.9 Chernoff Information. 11.10 Fisher Information and the Cram-er-Rao Inequality. Summary. Problems. Historical Notes. 12. Maximum Entropy. 12.1 Maximum Entropy Distributions. 12.2 Examples. 12.3 Anomalous Maximum Entropy Problem. 12.4 Spectrum Estimation. 12.5 Entropy Rates of a Gaussian Process. 12.6 Burg's Maximum Entropy Theorem. Summary. Problems. Historical Notes. 13. Universal Source Coding. 13.1 Universal Codes and Channel Capacity. 13.2 Universal Coding for Binary Sequences. 13.3 Arithmetic Coding. 13.4 Lempel-Ziv Coding. 13.5 Optimality of Lempel-Ziv Algorithms. Compression. Summary. Problems. Historical Notes. 14. Kolmogorov Complexity. 14.1 Models of Computation. 14.2 Kolmogorov Complexity: Definitions and Examples. 14.3 Kolmogorov Complexity and Entropy. 14.4 Kolmogorov Complexity of Integers. 14.5 Algorithmically Random and Incompressible Sequences. 14.6 Universal Probability. 14.7 Kolmogorov complexity. 14.9 Universal Gambling. 14.10 Occam's Razor. 14.11 Kolmogorov Complexity and Universal Probability. 14.12 Kolmogorov Sufficient Statistic. 14.13 Minimum Description Length Principle. Summary. Problems. Historical Notes. 15. Network Information Theory. 15.1 Gaussian Multiple-User Channels. 15.2 Jointly Typical Sequences. 15.3 Multiple-Access Channel. 15.4 Encoding of Correlated Sources. 15.5 Duality Between Slepian-Wolf Encoding and Multiple-Access Channels. 15.6 Broadcast Channel. 15.7 Relay Channel. 15.8 Source Coding with Side Information. 15.9 Rate Distortion with Side Information. 15.10 General Multiterminal Networks. Summary. Problems. Historical Notes. 16. Information Theory and Portfolio Theory. 16.1 The Stock Market: Some Definitions. 16.2 Kuhn-Tucker Characterization of the Log-Optimal Portfolio. 16.3 Asymptotic Optimality of the Log-Optimal Portfolio. 16.4 Side Information and the Growth Rate. 16.5 Investment in Stationary Markets. 16.6 Competitive Optimality of the Log-Optimal Portfolio. 16.7 Universal Portfolios. 16.8 Shannon-McMillan-Breiman Theorem (General AEP). Summary. Problems. Historical Notes. 17. Inequalities in Information Theory. 17.1 Basic Inequalities of Information Theory. 17.2 Differential Entropy. 17.3 Bounds on Entropy and Relative Entropy. 17.4 Inequalities for Types. 17.5 Combinatorial Bounds on Entropy. 17.6 Entropy Rates of Subsets. 17.7 Entropy and Fisher Information. 17.8 Entropy Power Inequality and Brunn-Minkowski Inequality. 17.9 Inequalities for Determinants. 17.10 Inequalities for Ratios of Determinants. Summary. Problems. Historical Notes. Bibliography. List of Symbols. Index. <s> BIB004 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <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> BIB005 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> While feedback does not increase the capacity of memoryless channels, the capacity of time-varying channels with feedback can be increased by exploiting the structure in the channel variations. Feedback information from the receiver is usually available at the transmitter only after some time delay. The capacity increase due to feedback depends on the feedback delay relative to the channel decorrelation time. We model time-varying channels as finite-state Markov channels and determine their capacity as a function of the feedback delay assuming perfect channel state information at the receiver. We apply the result to derive power control strategies to maximize the capacity for finite-state additive Gaussian noise channels and log-normal shadow fading channels. <s> BIB006 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> This paper addresses the design and performance evaluation with respect to capacity of M-PSK turbo-coded systems operating in frequency-flat time-selective Rayleigh fading. The receiver jointly performs channel estimation and turbo decoding, allowing the two processes to benefit from each other. To this end, we introduce a suitable Markov model with a finite number of states, designed to approximate both the values and the statistical properties of the correlated flat fading channel phase, which poses a more severe challenge to PSK transmission than amplitude hiding. Then, the forward-backward algorithm determines both the maximum a posteriori probability (MAP) value for each symbol in the data sequence and the MAP channel phase in each iteration. Simulations show good performance in standard correlated Rayleigh fading channels. A sequence of progressively tighter upper bounds to the capacity of a simplified Markov-phase channel is derived, and performance of a turbo code with joint iterative channel estimation and decoding is demonstrated to approach these capacity bounds. <s> BIB007 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> In this paper, we present two simple Monte Carlo methods for estimating the achievable information rates of general finite state channels. Both methods require only the ability to simulate the channel with an a posteriori probability (APP) detector matched to the channel. The first method estimates the mutual information rate between the input random process and the output random process, provided that both processes are stationary and ergodic. When the inputs are iid equiprobable, this rate is known as the Symmetric Information Rate (SIR). The second method estimates the achievable information rate of an explicit coding system which interleaves m independent codes onto the channel and employs multistage decoding. For practical values of m, numerical results show that this system nearly achieves the SIR. Both methods are applied to the class of partial response channels commonly used in magnetic recording. <s> BIB008 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> We propose a decision-feedback decoder for coded signals transmitted over finite-state Markov channels. The decoder achieves maximum-likelihood sequence detection (in the absence of feedback errors) with very low complexity by exploiting previous bit decisions and the Markov structure of the channel. We also propose a similar decoder, the output-feedback decoder, that does not use previous bit decisions and therefore does not suffer from error propagation. The decoder performance is determined using a new sliding window analysis technique as well as by simulation. Both decoders exhibit excellent bit error rate performance with a relatively low complexity that is independent of the channel decorrelation time. <s> BIB009 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> Magnetic recording channels are generally modeled as finite-state linear intersymbol interference (ISI) channels with additive white Gaussian noise and a binary input constraint. Lower bounds on the channel capacity have been computed by using this technique to estimate the information rates of optimized, order-r Markov input processes. RLL-constrained binary symmetric channel (BSC) and for two-dimensional finite-state ISI channels is proved in this paper <s> BIB010 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> In this paper, time-varying flat-fading channels are modeled as first-order finite-state Markov channels (FSMC). The effect of this modeling on the channel information capacity is addressed. The approximation accuracy of the first-order memory assumption in the Markov model is validated by comparing the FSMC capacity with the channel capacity assuming perfect state information at the receiver side. The results indicate that the first-order Markovian assumption is accurate for normalized Doppler frequencies f/sub d/T /spl lsim/ 0.01, in amplitude-only quantization of the channel gain for noncoherent binary signaling. In phase-only and joint phase and amplitude quantization of the channel gain for coherent binary signaling, the first-order Markovian assumption is accurate for f/sub d/T /spl lsim/ 0.001. Furthermore, the effect of channel quantization thresholds on the FSMC capacity is studied. In high signal-to-noise ratio (SNR) conditions, nonuniform two-level amplitude quantization scheme outperforms equiprobable quantization method by 0.8-1.5 dB. <s> BIB011 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> We consider a finite-state machine channel with a finite memory length (e.g., finite length intersymbol interference channels with finite input alphabets-also known as partial response channels). For such a finite-state machine channel, we show that feedback-dependent Markov sources achieve the feedback capacity, and that the required memory length of the Markov process matches the memory length of the channel. Further, we show that the whole history of feedback is summarized by the causal posterior channel state distribution, which is computed by the sum-product forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) (Baum-Welch, discrete-time Wonham filtering) algorithm. These results drastically reduce the space over which the optimal feedback-dependent source distribution needs to be sought. Further, the feedback capacity computation may then be formulated as an average-reward-per-stage stochastic control problem, which is solved by dynamic programming. With the knowledge of the capacity-achieving source distribution, the value of the capacity is easily estimated using Markov chain Monte Carlo methods. When the feedback is delayed, we show that the feedback capacity can be computed by similar procedures. We also show that the delayed feedback capacity is a tight upper bound on the feedforward capacity by comparing it to tight existing lower bounds. We demonstrate the applicability of the method by computing the feedback capacity of partial response channels and the feedback capacity of run-length-limited (RLL) sequences over binary symmetric channels (BSCs). <s> BIB012 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <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> BIB013 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> This paper shows the existence of the optimal training, in terms of achievable mutual information rate, for an output feedback implicit estimator for finite-state Markov communication channels. A proper quantification of source redundancy information, implicitly used for channel estimation, is performed. This enables an optimal training rate to be determined as a tradeoff between input signal entropy rate reduction (source redundancy) and channel process entropy rate reduction (channel estimation). The maximal mutual information rate, assuming the optimal implicit training and the presence of channel noise, is shown to be strictly below the ergodic channel information capacity. It is also shown that this capacity penalty, caused by noisy time-varying channel process estimation, vanishes only if the channel process is known or memoryless (channel estimation cannot improve system performance). <s> BIB014 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> The finite-state Markov channel (FSMC) is a time-varying channel having states that are characterized by a finite-state Markov chain. These channels have infinite memory, which complicates their capacity analysis. We develop a new method to characterize the capacity of these channels based on Lyapunov exponents. Specifically, we show that the input, output, and conditional entropies for this channel are equivalent to the largest Lyapunov exponents for a particular class of random matrix products. We then show that the Lyapunov exponents can be expressed as expectations with respect to the stationary distributions of a class of continuous-state space Markov chains. This class of Markov chains, which is closely related to the prediction filter in hidden Markov models, is shown to be nonirreducible. Hence, much of the standard theory for continuous state-space Markov chains cannot be applied to establish the existence and uniqueness of stationary distributions, nor do we have direct access to a central limit theorem (CLT). In order to address these shortcomings, we utilize several results from the theory of random matrix products and Lyapunov exponents. The stationary distributions for this class of Markov chains are shown to be unique and continuous functions of the input symbol probabilities, provided that the input sequence has finite memory. These properties allow us to express mutual information and channel capacity in terms of Lyapunov exponents. We then leverage this connection between entropy and Lyapunov exponents to develop a rigorous theory for computing or approximating entropy and mutual information for finite-state channels with dependent inputs. We develop a method for directly computing entropy of finite-state channels that does not rely on simulation and establish its convergence. We also obtain a new asymptotically tight lower bound for entropy based on norms of random matrix products. In addition, we prove a new functional CLT for sample entropy and apply this theorem to characterize the error in simulated estimates of entropy. Finally, we present numerical examples of mutual information computation for intersymbol interference (ISI) channels and observe the capacity benefits of adding memory to the input sequence for such channels <s> BIB015 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e. C = limNrarrinfin/1N max I(XN rarr YN), where the maximization is over the causal conditioning probability Q(xN||kN-) defined in this paper <s> BIB016 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> INFORMATION THEORY OF FSMC MODELS <s> The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs. <s> BIB017
The capacity of the GEC for the very special case of error-free good state (P G = 0) was given in closed form by Gilbert in 1960 BIB001 . However, the method heavily relied on the fact that errors can only occur in the bad state and could not be extended to any other GEC with nonzero error probability in the good state P G > 0. In 1968, Gallager proved general theorems for capacity and coding for FSMC [7, pp. 97-111, 176-187] . However, computation of the FSMC capacity remained a challenge for more than 20 years. To appreciate the difficulty in evaluating and analyzing the FSMC capacity, examine the capacity of an indecomposable FSMC that can be written as BIB002  where I(X N 1 ; Y N 1 ) denotes mutual information between sequences of channel input and output of length N. The maximization is over all possible input distributions. Even if we are only interested in obtaining FSMC information rates and not the optimal input distribution, direct computation of I(X N 1 ; Y N 1 ) is problematic for large N. Note that the information rate for a fixed sequence length N is expanded as If the input and output alphabet sizes are P and Q, there are P N × Q N different probabilities that need to be calculated in the mutual information rate above. For many FSMC models of practical interest, a very large N is needed for the information rate I N to converge to its asymptotic value and the computation of (33) becomes unfeasible. In 1989, Mushkin and Bar-David proposed a new recursive technique for computing the GEC capacity for general error probabilities in the good and bad states  . This work was later extended in BIB005 to recursive capacity computations for FSMC models with an arbitrary number of states. The main result in BIB005 is that the FSMC information rate can be computed as expectation with respect to the steady-state distribution of the following channel predictors: which can be recursively computed. For an FSMC model with K states, the quantities π N (k) and ρ N (k) take values in the Kdimensional real field R (K−1) . The proposed approach in  and BIB005 for feasible computation of π N (k) and ρ N (k) is to finely quantize the field R (K−1) into B (K−1) bins. As a result, practical computation of π N (k) and ρ N (k) is possible for small number of FSMC states (K ≤ 4 BIB007 ). It is also noted that the methods proposed in  and BIB005 are applicable to i.i.d input distributions and for data-independent FSMC models, which excludes ISIinduced FSMC models. In 2001, three groups of researchers  - BIB008 , independently proposed a numerical stochastic method for computing FSMC information rates, which relies on the Shannon-McMillan-Breiman theorem BIB004 . The Shannon-McMillan-Breiman theorem states that for stationary and ergodic processes, a time sample of entropy converges with probability one to the expected entropy rate over the ensemble. In other words, , with probability one. The complexity of computing log(Pr(y n )) on the left hand side is greatly simplified by the use of the recursive Forward-Backward or BCJR algorithm for HMMs [64, p. 519] , BIB003 and is linear in the sample length N. As a result, one can compute an estimate of (33), by generating a long sample of channel input and output and by computing 1/N log(Pr(y N |x N )/Pr(y N )). More details and examples of this technique can be found in BIB013 . Reference BIB013 also discusses an algorithm for obtaining upper and lower bounds for very general (nonfinite-state) channels with memory based on auxiliary FSMC models. The capacity-achieving input distribution for general FSMCs is generally unknown. A result is due to BIB005 , where it is shown that the capacity of data-independent FSMCs with a symmetric discrete memoryless channel in each state is achieved by i.u.d inputs. As a reminder, according to BIB014 , for this class of FSMC models, channel state estimation in the output-feedback decoder of BIB009 is only possible with non-i.u.d. input distributions, or in other words, at rates below channel capacity. The numerical computation method for FSMC information rates in  - BIB008 was later utilized in BIB017 to propose a stochastic expectation-maximization (EM) algorithm for optimizing the input distribution of FSMC models. The channel input is assumed to be a Markov chain, whose state transition probabilities are optimized to increase the FSMC information rate. This method can be thought of as a nontrivial extension of the classical Blahut-Arimoto (see the references in BIB017 ) algorithm for the iterative optimization of the input distribution to achieve the capacity of DMCs. However, whether the proposed algorithm in BIB017 globally converges to the FSMC capacity-achieving input distribution is an open problem. Compared to the choice of i.u.d input distribution, optimizing state transition probabilities of Markov sources over FSMC models results in noticeable achievable information rate improvements. In fact, BIB010 showed that Markov inputs can asymptotically achieve the capacity of data-dependent FSMC models induced by ISI. Recently, the authors in BIB015 shed light onto potential (but mainly theoretical) limitations of the numerical technique for the FSMC information rate computation. These potential limitations are mainly related to the lack of confidence intervals or error bounds on the estimated mutual information, which precludes determination of the necessary sample lengths for x N 1 and y N 1 for a reliable estimate. From an engineering/practical viewpoint, however, the these limitations are not major issues and it is likely that the information rate estimate is very close to the correct answer, where the order of difference is 10 −3 (see [57, Figure 2] ). The generated sample length can be determined by a few initial trials and then based on experience. Generally, sample lengths N ≈ 10 6 to N ≈ 10 7 are good starting points. The authors in BIB015 then prove the central limit theorem, confidence intervals, and bounds on initialization bias for the numerical estimate of information rates. The latter can be used to provide (rather conservative) upper bounds on the sample length to reach steady state. Finally, BIB015 expressed the FSMC mutual information and capacity in terms of Lyapunov exponents and developed a theory for computing or approximating entropy and mutual information with dependent (non-i.i.d) inputs, which does not rely on numerical techniques. In  , BIB005 , and  - BIB015 , the FSMC capacity has been studied mainly as a mathematical model. However, a main issue is whether the FSMC model is applicable to analyze the information rates through more complicated channels such as the TV-FFC that may neither be Markov nor finite state. The applicability of FSMC models for the TV-FFC has been analyzed in BIB011 from an information-theoretic viewpoint and the effect of channel parameters, such as the normalized fading rate f D T s , SNR, Markov memory order M, and the number of states on the resulting information rates is investigated. Both TV-FFC amplitude and phase are mapped into FSMC models and the resulting information rates or information rate bounds are analyzed. It is concluded that for binary signalling [such as BPSK or binary frequency shift keying (BFSK)] the capacity is rapidly saturated beyond D = 16 fading amplitude or phase partition regions in the FSMC model. This gives an indication on the number of required FSMC states for the FSMC-based decoding at the receiver, which was discussed as application types two and three in the previous section. In other words, the optimum number of FSMC states for joint channel estimation and decoding is where the information rate stops to increase noticeably by increasing the number of FSMC states. We conclude this section by a brief discussion on the capacity and/or capacity-achieving input distribution in FSMCs with feedback from the receiver to the transmitter. The author in BIB006 studied the FSMC capacity with perfect channel state information (CSI) at the receiver and delayed, but noiseless CSI feedback to the transmitter. The analysis verified the intuitive expectation that the advantage of having access to CSI at the transmitter vanishes as the feedback delay increases. The authors in BIB012 - BIB016 studied the case where the delayed channel observations y (not CSI) are fed back to the transmitter. Their treatment is based on the directed (causal) mutual information. In BIB012 , converse and direct coding theorems for the FSMC capacity with feedback are proven. In  , it is shown that the capacity of data-dependent FSMC models with feedback and memory order M is achieved by Markov sources of the same memory order. In BIB016 , the achievable rate and a capacity upper bound are given for FSMC models with feedback, where the feedback is a deterministic function of the channel output. For indecomposable and data-independent FSMC models with no ISI (such as TV-FFCs), the achievable rate and the capacity upper bound coincide and hence, are equal to the channel capacity.