Iterative data detection: Modified message-passing algorithms and convergence

Since Turbo codes were introduced, numerous works have focused on iterative decoding (ID), a technique in which soft information (also known as extrinsic information) is exchanged among Soft Input Soft Output (SISO) modules. A SISO module can be viewed as the probabilistic inverse of a constituent FSM at the encoder. It has been shown that the application of such ID techniques to a system consisting of a network of FSMs achieves very good iteration gain. The extrinsic information is refined at each iteration, becoming more reliable.; The modifications needed to the ID algorithm change with application. For example, in the unknown channel case, ID has to be made adaptive, for implementation, the complexity has to be reduced. In this work, several modified ID algorithms are introduced and their performance and complexity are considered. For systems with time-varying channels, several ways to add the adaptivity to the SISO module are presented. A simple stopping criteria is also presented to reduce the average complexity of iterative decoding.; In the recent past, an analytical tool was developed to explain the superior performance of these ID algorithms. This development was based on the message passing algorithms and the corresponding graphical representations (e.g., Bayesian networks, Factor graphs, Tanner graphs, etc.) of the codes (e.g., Turbo codes, Low Density Parity Check (LDPC) codes etc.). This tool, known as the Density Evolution (DE), gives the asymptotic capacity of ID and explains many characteristics of ID, including convergence of performance and preferred structures for the constituent codes.; In this work, several variations of the density evolution concept, which were independently developed in the literature, are used to analyze common code structures. It is shown that those ideas yield results that agree well with simulation results. In particular, the performance gain due to scaling of the extrinsic information is analyzed by these density evolution techniques. The expected scaling gain by density evolution matches well with the achievable scaling gain from simulation results.; Finally, in an attempt to optimally decode codes with cycles, a conceptual cycle cutting problem is introduced. This cycle cutting problem is a generalization of the optimal decoder of a single cycle tail-biting convolutional code, and can be realized by imposing constraints on a single or multiple nodes in the graphical representation of codes. This modified message passing algorithm, referred to Constrained Iterative Decoding (CID), is applied to the Serially concatenated Convolutional Code (SCCC) and the LDPC code.