Since the 1950s, hidden Markov models (HMMS) have seen widespread use in electrical engineering. Foremost has been their use in speech processing, pattern recognition, artificial intelligence, queuing theory, and communications theory. However, recent years have witnessed a renaissance in the application of HMMs to the analysis and simulation of digital communication systems. Typical applications have included signal estimation, frequency tracking, equalization, burst error characterization, and transmit power control. Of special significance to this thesis, however, has been the use of HMMs to model fading channels typical of wireless communications. This variegated use of HMMs is fueled by their ability to model time-varying systems with memory, their ability to yield closed form solutions to otherwise intractable analytic problems, and their ability to help facilitate simple hardware and/or software based implementations of simulation test-beds. The aim of this thesis is to employ and exploit hidden Markov fading models within an iterative (turbo) decoding framework. Of particular importance is the problem of channel estimation, which is vital for realizing the large coding gains inherent in turbo coded schemes. This thesis shows that a Markov fading channel (MFC) can be conceptualized as a trellis, and that the transmission of a sequence over a MFC can be viewed as a trellis encoding process much like convolutional encoding. The thesis demonstrates that either maximum likelihood sequence estimation (MLSE) algorithms or maximum <I> a posteriori</I> (MAP) algorithms operating over the trellis defined by the MFC can be used for channel estimation. Furthermore, the thesis illustrates sequential and decision-directed techniques for using the aforementioned trellis based channel estimators <I>en masse</I> with an iterative decoder. / Master of Science

Two standard graph representations for linear codes are the Tanner graph and the tailbiting trellis. Such graph representations allow the decoding problem for a code to be phrased as a computational problem on the corresponding graph and yield graph theoretic criteria for good codes. When a Tanner graph for a code is used for communication across a binary erasure channel (BEC) and decoding is performed using the standard iterative decoding algorithm, the maximum number of correctable erasures is determined by the stopping distance of the Tanner graph. Hence the computational problem of determining the stopping distance of a Tanner graph is of interest. In this thesis it is shown that computing stopping distance of a Tanner graph is NP hard. It is also shown that there can be no (1 + є ) approximation algorithm for the problem for any є > 0 unless P = NP and that approximation ratio of 2(log n)1- є for any є > 0 is impossible unless NPCDTIME(npoly(log n)). One way to construct Tanner graphs of large stopping distance is to ensure that the graph has large girth. It is known that stopping distance increases exponentially with the girth of the Tanner graph. A new elementary combinatorial construction algorithm for an almost regular LDPC code family with provable Ώ(log n) girth and O(n2) construction complexity is presented. The bound on the girth is close within a factor of two to the best known upper bound on girth. The problem of linear time exact maximum likelihood decoding of tailbiting trellis has remained open for several years. An O(n) complexity approximate maximum likelihood decoding algorithm for tail-biting trellises is presented and analyzed. Experiments indicate that the algorithm performs close to the ideal maximum likelihood decoder.