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 [7] 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
Non-Caltech Author Email:aamod (AT)
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:21 Dec 2019 04:21

Thesis Files

PDF (thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page