LT Codes and Raptor Codes

The combination of computational and error-correction performance of iterative decoding algorithms has made them the prime choice for practical error correcting systems that operate at rates extremely close to the capacity of the underlying channel. The first such algorithm is due to Gallager who  invented a simple message passing algorithm for LDPC codes using  a version of the majority-logic algorithm.   

Fountain codes are a new class of codes, originally designed for transmission of information over binary erasure channels with unknown erasure probabilities. Sub-classes of such codes, such as LT-codes and Raptor codes have very efficient decoding algorithms, and can perform arbitrarily close to the capacity of the  channel.

In this work we investigated the performance of Raptor Codes using Gallager's majority decoding algorithm on the binary symmetric channels. We obtain equations which relate the error probability to the output node degree distribution and then we design good degree distributions using the Differential Evolution method.