Graph-Based Codes and Iterative Decoding

Citation

Khandekar, Aamod Dinkar (2003) Graph-Based Codes and Iterative Decoding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Q06G-MW38. https://resolver.caltech.edu/CaltechETD:etd-06202002-170522

Abstract

The field of error correcting codes was revolutionized by the introduction of turbo codes in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes.

This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels.

We also introduce a new class of codes called irregular repeat-accumulate (IRA) codes, which are adapted from the previously known class of repeat-accumulate (RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check (LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity.

We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking.

Thesis Files