Rateless coding with partial information - 10/24/2008

Ari Trachtenberg

Classical error-correcting codes have a fixed rate, meaning that their redudancy is pre-determined according to the error-correction capability desired. Rateless codes, on the other hand, have no specified redundancy - encoded packets can be produced without end until the recipient has correctly decoded the desired message. As such, rateless coding provides an excellent method for distributing information to multiple recipients in uncertain environments.

In this talk we will describe the basics of rateless coding, including Luby-Transform and Raptor codes. We will then describe a new variant known as shifted LT codes, designed for the case where the recipient already has some (undetermined) portion of the transmitted data. This is joint work with Sachin Agarwal and Andrew Hagedorn.