A Caltech Library Service

Graph-Based Codes and Iterative Decoding


Khandekar, Aamod Dinkar (2003) Graph-Based Codes and Iterative Decoding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Q06G-MW38.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:binary adder channel; consistency condition; erasure channel; gaussian approximation; IRA codes; irregular LDPC codes; irregular repeat-accumulate codes; iterative decoding; stability condition; typical set bound
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Hassibi, Babak
  • Bruck, Jehoshua
  • Preskill, John P.
  • Vaidyanathan, P. P.
Defense Date:10 June 2002
Record Number:CaltechETD:etd-06202002-170522
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2652
Deposited By: Imported from ETD-db
Deposited On:21 Jun 2002
Last Modified:12 Nov 2021 19:13

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page