Horn, Gavin B. (1999) Iterative decoding and pseudo-codewords. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-02062008-130016
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)|
|Defense Date:||12 May 1999|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||07 Mar 2008|
|Last Modified:||26 Dec 2012 02:30|
- Final Version
See Usage Policy.
Repository Staff Only: item control page