Talk abstract:

Some Simple Codes that are Good in Both Theory and Practice

Robert J. McEliece
Department of Electrical Engineering
California Institute of Technology
rjm@systems.caltech.edu

In an unsuccessful attempt to prove coding theorems for the ensemble of classical turbo codes, we were forced to invent a much simpler ensemble, which we call "repeat-accumulate" (RA) codes. RA codes are an almost degenerate special case of serially concatenated "turbo" codes, but they have just enough structure to allow us to prove coding theorems for them. For example, we can show that maximum-likelihood decoding of RA codes "achieves capacity" on the AWGN channel. The really surprising thing about RA codes, however, is that their performance with a simple practical iterative decoding algorithm (belief propagation on an appropriate Tanner graph) is almost as good as maximum likelihood. Thus in applications where decoder complexity is as important as nearness to the Shannon limit, RA codes may give turbo codes and LDPC codes a run for their money.

[Research in collaboration with Sam Dolinar, Dariush Divsalar, and Hui Jin]

Slides used during the talk

Back to Codes, Systems and Graphical Models