### Princeton-Rutgers Seminar Series in
Communications and Information Theory

#### Chris Rose and Sergio Verdú, Co-Chairs

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.