This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:20081029 [2016/06/23 11:26]
en:group:seminars:20081029 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +---- dataentry seminar ----
 +date_dt : 2008-10-29
 +title : Recursions for the LT Decoder
 +speaker : Ghid Maatouk
 +affiliation :  ALGO
 +time : 16h15-17h15
 +room : BC129
 +table : seminars
 +==== abstract ====
 +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]