Sparse graph codes are codes whose constraints are defined by sparse random graphs. The best known decoding method for these codes is the sum-product algorithm. Sparse graph codes include Gallager's low- density parity-check codes, turbo codes and repeat--accumulate codes. I will review old theoretical results for Gallager codes, and new empirical work.

Gallager codes are record-breaking codes for low signal-to-noise applications with large blocklength and low rate (e.g., N 10,000 - 40,000 and R 0.25 - 0.5). Are they also competitive for high rate, small blocklength problems? We have studied the empirical performance of high rate binary and non-binary Gallager codes on three channels: the binary input Gaussian channel, the binary symmetric channel, and the 16-ary symmetric channel. We find that Gallager codes with rate R=8/9 and block length N=1998 bits outperform comparable BCH and Reed-Solomon codes (decoded by a hard input decoder) by more than a decibel on the Gaussian channel. Even on the 16-ary symmetric channel, Gallager codes have outstanding performance.

Slides used during the talk