Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Dissertation
Author	Aji, Srinivas Mandayam
Author's Email Address	mas AT systems.caltech.edu
URN	etd-04112003-162805
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-04112003-162805
Title	Graphical models and iterative decoding
Degree	PhD
Option	Electrical Engineering
Advisory Committee	Advisor Name Title Robert J. McEliece Committee Member
Keywords	iterative decoding graphical models
Date of Defense	2000-05-12
Availability	unrestricted
Abstract 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    gmit.pdf 699.82 Kb 00:03:14 00:01:39 00:01:27 00:00:43 00:00:03   gmit.ps 844.19 Kb 00:03:54 00:02:00 00:01:45 00:00:52 00:00:04