CaltechTHESIS
  A Caltech Library Service

Asymptotic weight analysis of low-density parity check (LDPC) code ensembles

Citation

Sweatlock, Sarah L. (2008) Asymptotic weight analysis of low-density parity check (LDPC) code ensembles. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-05202008-094714

Abstract

With the invention of turbo codes in 1993 came increased interest in codes and iterative decoding schemes. Gallager's Regular codes were rediscovered, and irregular codes were introduced. Protograph codes were introduced and analyzed by NASA's Jet Propulsion Laboratory in the early years of this century. Part of this thesis continues that work, investigating the decoding of specific protograph codes and extending existing tools for analyzing codes to protograph codes.

The rest of this work focuses on a previously unknown relationship between the binary entropy function and the asymptotic ensemble average weight enumerator, which we call the spectral shape of the ensemble. This result can be seen as an extension of the Pless power-moment identities based on the discovery that the convex hull of the spectral shape is the Legendre transform of a function closely related to the moment-generating function of a codeword's weight.

In order to fully investigate this new relationship, tools needed to be designed to calculate the derivatives of the spectral shape as the equation describing an ensemble's spectral shape is rarely straightforward. For Gallager's regular ensembles, a formula for calculating derivatives of functions defined parametrically was required. For repeat-accumulate (RA) codes, a formula was needed for functions defined implicitly through a second function. Both formulas are similar to Faa di Bruno's formula for derivatives of compositions of functions.With the invention of turbo codes in 1993 came increased interest in codes and iterative decoding schemes. Gallager's Regular codes were rediscovered, and irregular codes were introduced. Protograph codes were introduced and analyzed by NASA's Jet Propulsion Laboratory in the early years of this century. Part of this thesis continues that work, investigating the decoding of specific protograph codes and extending existing tools for analyzing codes to protograph codes.

The rest of this work focuses on a previously unknown relationship between the binary entropy function and the asymptotic ensemble average weight enumerator, which we call the spectral shape of the ensemble. This result can be seen as an extension of the Pless power-moment identities based on the discovery that the convex hull of the spectral shape is the Legendre transform of a function closely related to the moment-generating function of a codeword's weight.

In order to fully investigate this new relationship, tools needed to be designed to calculate the derivatives of the spectral shape as the equation describing an ensemble's spectral shape is rarely straightforward. For Gallager's regular ensembles, a formula for calculating derivatives of functions defined parametrically was required. For repeat-accumulate (RA) codes, a formula was needed for functions defined implicitly through a second function. Both formulas are similar to Faa di Bruno's formula for derivatives of compositions of functions.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:LDPC codes; weight enumerator
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Meiron, Daniel I.
  • Candes, Emmanuel J.
  • Tropp, Joel A.
Defense Date:29 April 2008
Author Email:sarah (AT) acm.caltech.edu
Record Number:CaltechETD:etd-05202008-094714
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-05202008-094714
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1898
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:30 May 2008
Last Modified:06 Mar 2013 20:17

Thesis Files

[img]
Preview
PDF (Sarah_Sweatlock_thesis.pdf) - Final Version
See Usage Policy.

1190Kb

Repository Staff Only: item control page