Optimization of the Belief Propagation algorithm for Luby Transform decoding over the Binary Erasure Channel.
M.A.G. Alvarez Guede · 2011
Live-streaming media applications over the Internet are characterized by time deadlines and bandwidth constraints. Reliability over the Internet has been provided traditionally by the Transmission Control Protocol (TCP) based on retransmissions. However, resending the missed information leads to a waste in time and bandwidth. Erasure correcting codes can be used as an alternative to TCP. In this thesis, we consider the use of Luby Transform (LT) codes, which are part of the Digital Fountain (DF) codes. LT codes show a low encoding and decoding time as opposite to other erasure codes as Reed-Solomon (RS) and Low-Density Parity-Check (LDPC) codes. They are also the first realization of rateless codes, where the number of encoded symbols is potentially limitless. Therefore, they are suitable for Internet applications, where the channel conditions can change very fast or be unknown. The accepted efficient decoding algorithm for LT codes is the Belief Propagation (BP) algorithm, unfortunaly it shows a rather poor performance when used with small sizes of message symbols. This turns out to be a limitation in live-streaming applications, as they should wait until that number of source symbols have been received for attempting decoding. In our project, we explore optimisations of the BP decoding process for LT codes when the number of information symbols is small. We present two new decoding algorithms that improve the performance of BP while keeping a low complexity. We show simulation results of the new LT decoding algorithms success rate and complexity versus overhead when used with small sizes, proving the gain in performance compare with BP.