Talk abstract:

Error-Correcting Codes and Graph-based Algorithms: Origins, Successes, the Current Quests

R. Michael Tanner
Department of Computer Science
University of California-Santa Cruz
Baskin School of Engineering
tanner@cse.ucsc.edu

Graphs have been used in many forms to describe the structure of codes for achieving in practical application the channel capacity predicted by Shannon. While perhaps the most versatile application has been as the language for finite-state transition-output systems for the encoding mapping of information streams to coded streams and decoding back, graphs recently gained prominence for specifying the sets of constraints governing the codewords of codes. This overview traces the history of the graph-based codes and iterative decoding. In 1962 Gallager introduced low-density parity check codes (LDPC) binary codes for which the parity check matrix is very sparse, having a small, fixed number of parity equations checking each bit, and each parity equation checking the same number of bits. Gallager showed that such codes have good distance properties and that iterative computation of a posteriori probabilities on a decoding tree for each bit (now called the sum-product algorithm) could achieve a probability of bit error decreasing exponentially with block length. In 1981 Tanner formalized the representation of a code by a graph, in which constraints operate on a local set of codeword symbols, and analyzed message-passing algorithms, including the min-sum and sum-product algorithms. Studying the stunning performance of turbocodes of Berrou et al., Wiberg and Loeliger generalized code graphs to include state variables, which allowed message-passing algorithms to subsume, for example, Viterbi decoding. Others strengthened the connection between graphs properties and code performance by constructions of good low- complexity codes using expander graphs. These are characterized by a low ratio of second to first eigenvalues and have properties associated with random sparse graphs. Multiple authors presented alternative models for graph-structured equations and computations. For example, the sum-product algorithm was shown to be version of Pearl'9s mid-80'9s belief propagation. A graph-message passing decoders may be viewed as a complex non-linear dynamical system, typically with codewords as attractors. Recent work on LDPC codes has shown irregular graphs and non-binary codes to be advantageous for decoder convergence, with Richardson et al. demonstrating performance very near the Shannon limit. Both the turbocodes and LDPC schools construct good codes using random graphs, which cannot have terse descriptions or deterministically predictable quality. An outstanding question is whether algebraic descriptions can be given for codes of provable quality and predictable performance with iterative decoding.

Back to Codes, Systems and Graphical Models

1998-1999 Mathematics in Biology