Title: LT Codes
Speaker: Michael Luby, Digital Fountain
Date: Thursday November 7, 2002 2:30 pm
Location: Princeton University, Friend 101, Princeton, NJ
Abstract:
T codes are the first realization of a class of erasure codes that we call universal erasure codes. LT codes are rateless, i.e., the number of encoding symbols that can be generated from the data is potentially limitless. Furthermore, encoding symbols can be generated on the fly, as few or as many as needed. Also, the decoder can recover an exact copy of the data from any set of the generated encoding symbols that in aggregate are only slightly longer in length than the data. Thus, no matter what the loss model is on the erasure channel, encoding symbols can be generated as needed and sent over the erasure channel until a sufficient number have arrived at the decoder in order to recover the data. Since the decoder can recover the data from nearly the minimal number of encoding symbols possible, this implies that LT codes are near optimal with respect to any erasure channel. Furthermore, the encoding and decoding times are asymptotically very efficient as a function of the data length. Thus, LT codes are universal in the sense that they are simultaneously near optimal for every erasure channel and they are very efficient as the data length grows. LT codes have a number of applications, including providing reliability for state of the art data transport protocols that are fast, predictable and massively scalable.
Seminar Sponsored by DIMACS Special Focus on Computational Information Theory and Coding.