Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Projection Algebra Analysis of Error Correcting Codes

Erik Sudderth
SSG Doctoral Student

Error correcting codes are designed to allow efficient, reliable transmission of information over noisy communication channels. Recent advances in the coding community have produced a powerful set of design tools for cases where the number of bits to be transmitted (block length) is very large. For practical block lengths, however, code design is as much intuition as science.

In this talk, I will discuss a new "projection algebra" method for evaluating the performance of error correcting codes. Using this method, one can exactly analyze the dynamics of the belief propagation decoding algorithm as applied to an arbitrary parity-check code on the binary erasure channel. The projection algebra iterations improve upon the standard density evolution method by exactly accounting for the statistical dependencies that exist between belief propagation messages. Although the exact projection algebra technique is computationally intractable for codes of large blocklength, it can be efficiently approximated to give rigorous upper and lower bounds on the bit or block error rates.

Problems with this site should be emailed to