A BP/ML hybrid decoding algorithm for LT codes

In order to eliminate the performance gap between the belief propagation (BP) decoding and the maximum-likelihood (ML) decoding for LT codes with small message length, the paper presents a BP/ML hybrid decoding algorithm to obtain a performance-complexity tradeoff for LT codes over the binary erasure channel (BEC). When BP decoding fails, the algorithm only uses the ML decoding to determine a few guessing bits for completely recovering the message. The simulation results show that, compared with the BP decoding, the BP/ML hybrid decoding has less than a 50% increase in decoding time, which is still much smaller than that of the ML decoding. On the other hand, the proposed BP/ML hybrid decoding significantly decreases the probability of decoding failure, and its decoding performance is similar to the ML decoding when the overhead is larger than 10%.