Talk abstract:

Markov Chains, Error Control, and the Advent of Turbo Coding

Stephen B. Wicker
School of Electrical Engineering
Cornell University
wicker@ee.cornell.edu

This talk is, first and foremost, a tutorial on turbo coding. Turbo coding allows for the operation of communication systems at extremely low signal to noise ratios, providing performance that is a hair's breadth from that promised by Shannon's Noisy Channel Coding Theorem. Turbo coding consists of two key elements: parallel concatenated codes and iterative decoding. In describing how these elements interrelate, it is necessary to indulge in a bit of intellectual history. With the benefit of hindsight, it can be shown that turbo coding has evolved through the interaction of the field of error control coding with the analysis of hidden Markov models. One of the key results in the latter area was the development by Baum and Welch of a recursive algorithm for estimating the parameters of a hidden Markov model. This avenue of research reached a recent peak in the work of Pearl, who generalized the Markov property through the concepts of U- and D-Separation in graphs, and developed a series of recursive belief propagation algorithms that exploit separation of subgraphs.

The recognition that convolutional and block codes can be described using the language of Markov chains led to the application of statistical analysis techniques originally developed for hidden Markov models, and to what is now called the BCJR algorithm. Turbo decoding is shown to be an iterative application of the BCJR algorithm that carefully isolates different information sources, allowing for the development of independent estimates of a posteriori distributions on transmitted data. Over the course of multiple iterations these estimates (sometimes) converge. The connection between iterative decoding and belief propagation was made quite recently, and continues to spur research into the relationship between turbo decoding and graph theory.

Material used during the talk

Back to Codes, Systems and Graphical Models

1998-1999 Mathematics in Biology