Preprint version (202KB)
	Get Adobe® Reader®

Abstract:
Our objective in this work is to investigate these two techniques---GMD decoding of Euclidean-space codes and iterative decoding of turbo codes---analytically at practical SNRs. Our analysis provides useful insights into the decoding mechanisms of these algorithms. This, in turn, leads to better design principles for multilevel Euclidean-space codes and for more efficient iterative decoding algorithms.

This dissertation is divided into two major parts. In Chapter 2, generalized minimum-distance decoding of Euclidean-space codes is considered. Chapter 3, we analyze the turbo decoding algorithm using bifurcation theory and the theory of dynamical systems.

In Chapter 2, we present a detailed analysis of GMD decoding algorithms for Euclidean-space codes. In particular, we completely characterize GMD decoding regions in terms of receiver front-end properties. This characterization is used to show that GMD decoding regions have intricate geometry. We prove that although these decoding regions are polyhedral, they are essentially always nonconvex. We furthermore show that conventional performance parameters, such as error-exponent and effective error-coefficient, do not capture the essential geometric features of GMD decoding regions, and thus do not provide meaningful measures of performance. Our geometrical analysis of GMD decoding can also be applied to other list-decoding algorithms, such as the Chase decoding algorithm and decoding algorithms based on ordered statistics. In the analysis of these other algorithms, a similar conclusion is reached---the conventional performance parameters do not capture the essential geometric features of these decoding regions.

As an alternative to the geometrical characterization, probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Furthermore, extensive simulation results are presented for both low-dimensional and high-dimensional Euclidean-space codes. These simulations show that multilevel codes in conjunction with multistage GMD decoding provide significant coding gains at a very low complexity. In both cases, simulated performance is in remarkably close agreement with our probabilistic approximations.

In Chapter 3, we consider the iterative decoding algorithm for turbo codes. The turbo decoding algorithm can be formalized as a dynamical system due to its iterative nature. We focus on classical turbo codes transmitted over an AWGN channel with binary-phase-shift-keying (BPSK) modulation. In this setup, the existence of certain fixed points at asymptotic SNRs is shown. At asymptotically low SNRs, these fixed points correspond to a large number of erroneous decisions on the information bits. Conversely, at asymptotically high SNRs, these fixed points correspond to correct decisions on the information bits.

Extensive simulations are performed to investigate the relationship between phase trajectories of the dynamical system at asymptotic SNRs and phase trajectories at practical SNRs. These simulations reveal that, as the SNR increases, phase trajectories undergo a fundamental transition in the waterfall region. Before the waterfall region, phase trajectories are qualitatively similar to those predicted by the analysis for asymptotically low SNRs. In contrast, after the waterfall region, phase trajectories resemble those predicted for asymptotically high SNRs.

Using the bifurcation theory, we associate the qualitative transition of phase trajectories in the waterfall region to the bifurcation of certain fixed points. This connection explains the dramatic improvement of performance in the waterfall region, and leads to a better understanding of the iterative decoding algorithm. Specifically, we give a simplified stopping criterion based on the characteristics of the phase trajectories.

In the last chapter, we summarize our results, draw conclusions, and present directions for future research.