Introduction

Instructor: Dan Spielman
Where: room 1-115.
When: Tuesday and Thursday from 2:30 to 4:00.
Dan's Office Hours: to be determined

The field of Error-Correcting Codes has been revolutionized in the last decade by the emergence of iterative decoding techniques. Surprisingly, these techniques are elementary and rely little on the more sophisticated tools developed in the field in recent decades. While the results that sparked this revolution were purely experimental, analytical techniques have been developed that partially explain, and more importantly predict, the behavior of iterative decoding algorithms. This course will introduce students to iterative decoding algorithms and the codes to which they are applied, including Turbo Codes, Low-Density Parity-Check Codes, and Serially-Concatenated Codes. The course will begin with an introduction to the fundamental problems of Coding Theory and their mathematical formulations. This will be followed by a study of Belief Propagation--the probabilistic heuristic which underlies iterative decoding algorithms. Belief Propagation will then be applied to the decoding of Turbo, LDPC, and Serially-Concatenated codes. The technical portion of the course will conclude with a study of tools for explaining and predicting the behavior of iterative decoding algorithms, including EXIT charts and Density Evolution. We will see how these predictive tools can be used to aid code design.

While students are working on finishing their final projects, lectures will focus on presentation techniques while covering material of interest that is not required for the final projects.

All work in the class will be project-based. These projects will involve computer experiments. Students may use any computing environment they like, but are recommended to work in C, Java or Matlab as these are the languages with which the instructor is most familiar. As some of these projects will involve experiments that will run for hours or days, students are advised to start early or buy large supercomputers.


Dan Spielman
Last modified: Wed Jan 28 17:10:37 EST 2004