Title

LT codes are the first class of universal Fountain codes. They are well-suited for fault-tolerant transmission of information over the Internet, modeled as a binary erasure channel. We briefly describe these codes and their decoding algorithms, introduce the concept of a state in which a decoder can be at any given instance during decoding, and describe a recursion for the state-generating function of the LT decoder derived by Karp, Luby and Shokrollahi. Starting from this recursion, we will extend the analysis of Karp, Luby, and Shokrollahi to find explicit formulas for the variance of the main state parameters of the decoder. These formulas describe an explicit “corridor” within which the decoding state parameters can move, and lead to explicit good upper bounds on the decoding error. They can also be used to compute good finite length designs for LT-codes. [Joint work with Amin Shokrollahi]