Graphical Models and Iterative Decoding

Citation

Aji, Srinivas Mandayam (2000) Graphical Models and Iterative Decoding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/79XC-5C54. https://resolver.caltech.edu/CaltechETD:etd-04112003-162805

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.

Thesis Files