home/Research Interests/LT-codes

Luby transform (LT) codes

Fountain codes are an interesting class of erasure codes, where the idea is, in layman's terms, that the source first splits a message to n blocks and then starts sending practically unique encoded packets. As soon as the recipient has received n+ε of them, she can decode the original message. The name fountain stems from the analogy of fountain spraying water drops and a recipient collecting them to a bucket until the bucket is full. In both cases, it is irrelevant to a succesful completion which particular packets or water drops one has obtained. Luby transform (LT) codes [1,2] are a novel example of a code fulfilling the fountain coding principle.

LT Encoding

For simplicity of explanation, suppose that a message M comprises n equally long blocks, M=(B1,...,Bn). A new packet is obtained by first drawing a random degree D from the so-called degree distribution having support 1,...,n, and then taking the exclusive-OR of D randomly chosen blocks, k1,...,kD,

E = Bk1 ⊕ ... ⊕ BkD.

LT Decoding

Decoding is possible when n linearly independent packets have been received. However, in order to keep the complexity minimal, it has been chosen that the decoder operates only with degree-1 packets, i.e., packets which correspond to a single block in the original message. In particular, whenever a new degree-1 packet is available, it is subtracted from those packets including it, thus reducing their degree by one. This is repeated iteratively as long as new degree-1 packets are discovered. Eventually, one obtains the original message by concatenating the n degree-1 packets.

Our work (Joint work with Dr. T. Tirronen and Prof. J. Virtamo)

The performance of LT code depends greatly on the degree distribution. A good distribution produces packets with a very small degree (in order to keep the decoding process running) and also with a high degree (in order to "fill the holes"). Authors of the code propose Soliton distribution to this end, which indeed has a good overall performance. However, it is not optimal. In [3], we suppose that the criterion is the mean number of packets needed to decode the message, and derive the optimal degree distribution for (very) short message lengths n. In order to get a bit further, we also consider an alternative objective function of maximizing the decoding probability after receiving exactly n encoded packets. In order to evaluate a degree distribution for a longer message lengths n, one has to resort to simulations. Thus, optimizing a degree distribution can be a tedious task. In [4], we propose an importance sampling approach to this end. The idea is to adjust the degree distribution based on simulation results in recursive fashion. The proposed approach has strong similarities with the importance sampling technique.

References:

  1. M. Luby, LT Codes, in The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 271-282. (pdf)
  2. D. J. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge University Press, 2004.
  3. E. Hyytiä, T. Tirronen and J. Virtamo, Optimal Degree Distribution for LT Codes with Small Message Length, in IEEE INFOCOM, pp. 2576-2580, 2007, Anchorage, Alaska, USA. (pdf)
  4. E. Hyytiä, T. Tirronen and J. Virtamo, Optimizing the Degree Distribution of LT codes with an Importance Sampling Approach, in RESIM 2006, Bamberg, Germany. (pdf)