A Caltech Library Service

Iterative decoding and pseudo-codewords


Horn, Gavin B. (1999) Iterative decoding and pseudo-codewords. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/RS6G-C640.


In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance.

Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.

Item Type:Thesis (Dissertation (Ph.D.))
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)
  • Divsalar, Dariush
  • Vaidyanathan, P. P.
Defense Date:12 May 1999
Record Number:CaltechETD:etd-02062008-130016
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:531
Deposited By: Imported from ETD-db
Deposited On:07 Mar 2008
Last Modified:21 Dec 2019 02:31

Thesis Files

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


Repository Staff Only: item control page