Title

Verification decoding is a technique introduced by Luby and Mitzenmacher for decoding LDPC codes on the q-ary symmetric channel for large q. In this talk we will adapt this technique to the setting of Raptor codes, and will derive a series of decoding algorithms for such codes on the q-ary symmetric channel for large q. We will analyze the algorithms, and derive optimal codes (in certain cases). We will also show that capacity-achieving Raptor codes on the BEC will lead to capacity-approaching codes on the q-ary symmetric channel in the limiting case of the considered algorithms. This is joint work with R. Karp and M. Luby.

Full presentation