Talk abstract:

Capacity Achieving Low-Density Erasure Codes

Amin Shokrollahi
Bell Labs

We give an overview of the work of Luby, Mitzenmacher, Shokrollahi, Spielman, and Stemann (1997) dealing with the construction of capacity achieving sequences of low-density erasure codes that have linear time encoders and decoders. We remark that the erasure channel is the only known channel for which we know explicit sequences of irregular degree distributions whose codes achieve capacity. The explicit sequences of Luby {\it et al.} and a new class of sequences discovered recently by the author are the only known sequences that provably approach capacity on an erasure channel.

Slides used during the talk

Back to Codes, Systems and Graphical Models