Low density parity check codes

Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering Abstract: An ensemble of parity check codes of arbitrary length, n is considered in which each digit of each code is checked by a small fixed number, j, of parity check equations, and each parity check set contains a small, fixed number, k, of digits. The typical minimum distance of codes in such an ensemble increases linearly with n for constant j and k if j>=3. The probability of decoding error for this ensemble of codes on a memoryless symmetric channel with binary input alphabet is analyzed. Using maximum likelihood decoding on a sufficientlyquiet channel, the probability of error is shown to be exponentially decreasing with n; this exponent is relatively close to the theoretical optimum exponent. A simple decoding scheme that directly uses the channel a posteriori probabilities is described in which the decoding computation per digit appears to be constant, or at most, logarithmically increasing block length when this non-optimum decoding scheme is used on a Binary Symmetric channel of sufficiently high capacity. Although no tight bounds have been found for the probability of decoding error using this simple decoding scheme, both some experimental results and the form of the weak bound indicate the potentiality of the decoding scheme.