Asymptotic Weight Analysis of Low-Density Parity Check (LDPC) Code Ensembles

Citation

Sweatlock, Sarah Lynne (2008) Asymptotic Weight Analysis of Low-Density Parity Check (LDPC) Code Ensembles. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/86BY-MA30. https://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.

Thesis Files