LT codes
From Wikipedia, the free encyclopedia
LT codes are a class of near optimal rateless erasure correcting codes introduced by Michael Luby.
Like some other similar codes, notably Tornado codes, Online codes and Raptor codes, LT codes depend on sparse bipartite graphs to trade reception overhead for encoding and decoding speed. All of these codings transmit random linear combinations of message symbols where the number of message symbols packet into each sent symbol is chosen at random from a carefully crafted probability distribution. The sole decoding operation is to find a node on the right that has only one edge. Since that node will be a direct copy of a node on the left, it can be used for decoding that symbol and for reducing the dependency of the symbol from other encoded symbols.
In LT codes, the process of decoding is viewed as a process of throwing balls into bins where the left nodes in the graph represent symbols of the sent message or bins and the single edge nodes on the right represent balls thrown at random. The set of all the single edge nodes on the right is known as the ripple. In every step of the decoding, one node from the ripple is processed, decoding a node on the left and possibly adding more symbols to the ripple. Since the target bin for a ball is fixed when a node on the right is added to the ripple, but the bin is not removed until the symbol connected to it is decoded it follows that the ripple should be kept small to avoid collisions, and thus reception overhead. However, should the ripple disappear, the decoding process will fail.
