home/Publications/HTV07

E. Hyytiä, T. Tirronen and J. Virtamo, Optimal Degree Distribution for LT Codes with Small Message Length, in IEEE INFOCOM mini-symposium, pp. 2576-2580, 2007, Anchorage, Alaska, USA.

Abstract: Fountain codes introduced by Byers et al. in 1998 provide an efficient way to transfer information over erasure channels. In this paper, we present an exact analysis of the performance of a specific type of fountain codes, called LT codes, for the cases where the message length N is small. Two different approaches are developed. In a Markov chain approach the explosion of the state space, even with reduction of the state space based on permutation isomorphism, however, limits the analysis to very small message lengths, N <= 4. An alternative combinatorial method is developed that allows recursive calculation of the probability of success for decoding after N received packets. The recursion equations can be solved symbolically for values of N up to 10 and numerically up to values of the order of N = 30. Examples of optimization results are presented giving some insight into the nature of the problem. In particular, we argue that few conditions are sufficient to define an almost optimal degree distribution.

Links: DOI (pdf)

(C) 2007 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

BibTeX entry:

@inproceedings{hyytia-infocom-2007,
  author = {Esa Hyyti{\"a} and Tuomas Tirronen and Jorma Virtamo},
  title = {Optimal Degree Distribution for {LT} Codes with Small Message Length},
  booktitle = {{IEEE} {INFOCOM} mini-symposium},
  year = {2007},
  month = {May.},
  address = {Anchorage, Alaska, USA},
  pages = {2576--2580},
  doiopt = {10.1109/INFCOM.2007.324},
}