| Recent advances in coding theory have uncovered the previously unattainable power of two types of long block codes---turbo and low-density parity-check (LDPC) codes. Both types of codes rely on an iterative decoding algorithm which does not compute the exact maximum likelihood (ML) decoding rule. This suboptimal decoding behavior introduces non-codeword error events, called trapping sets (TS), into the decoder output. Since the error behavior of most long LDPC codes is determined by these TS and not true codewords, the traditional bounding techniques must be altered to include these new error events. It is also very difficult to locate all of these error events: a brute force search over an impractically large space of possibilities is the only known way to enumerate all of them for a general code.; At higher SNR on the Gaussian channel, only the error events associated with minimum distance codewords and TS are a significant contributor to error performance. A technique called Importance Sampling (IS) can improve upon standard MC when measuring the error contribution of single dominant error events. If it were possible to enumerate a complete set of dominant error events, both codeword and TS, then IS could be used to evaluate high-SNR performance. This work describes a method which can efficiently find these dominant error events in a fairly general class of codes with block length up to about 10,000 bits. By using this efficient technique to gain knowledge of a code's high-SNR performance characteristics, a code designer can construct codes and alter the decoder to allow a significant lowering of LDPC code error floors. In summary, the work presented in this dissertation offers the coding community the first comprehensive source for methods to efficiently analyze, design, and decode LDPC codes in the very low bit error rate regime. |
