|
LT Codes
Michael Luby,
Digital Fountain:
Thursday November 7, 2002 2:30 pm, Princeton University, Friend 101:
LT 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.
|
 |
