A Caltech Library Service

Graphical Models and Iterative Decoding


Aji, Srinivas Mandayam (2000) Graphical Models and Iterative Decoding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/79XC-5C54.


Since the invention of turbo codes, there has been a lot of interest in iterative decoding schemes.It is also known that the turbo decoding algorithm and several other previously known iterative algorithms are instances of Pearl's belief propagation algorithm applied to a graph with cycles, while the algorithm is known to work only for graphs without cycles. We describe a marginalization algorithm which works on junction trees, which is based on some newer developments in Bayesian networks. This is sufficiently general that Pearl's belief propagation and decoding on Tanner graphs may be regarded as special cases. An attempt to compute the discrete Fourier transform as a marginalization problem in this framework gives the fast Fourier transform algorithm, thus showing that this framework has applications apart from probabilistic computations. Junction graphs with cycles lead to an iterative algorithm. The case of junction graphs with a single cycle is analyzed, with specific results in the case of the sum-product algorithm. We also have some experimental results for small turbo code-like junction graphs. On a different topic, we consider the typical set decoder, which can be used to obtain bounds on the noise threshold for asymptotically error free decoding, for given code ensembles. Some choices of the typical set for AWGN channel are considered and the resulting bounds on the threshold obtained.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:graphical models; iterative decoding
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Minor Option:Mathematics
Awards:Charles and Ellen Wilts Prize, 2001
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:12 May 2000
Non-Caltech Author Email:mas (AT)
Record Number:CaltechETD:etd-04112003-162805
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1340
Deposited By: Imported from ETD-db
Deposited On:05 May 2003
Last Modified:20 Dec 2019 19:58

Thesis Files

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

Postscript ( - Final Version
See Usage Policy.


Repository Staff Only: item control page