Limited Randomness LT Codes

appeared in Proceedings of the 41st Annual Allerton Conference on Communication, Control, and Computing, 2003.
ps (336kB), ps.gz (156kB) or pdf (224kB).
with Chris Harrelson and Wei Wang.

LT codes are asymptotically optimal rateless erasure codes with highly efficient encoding and decoding algorithms. In the original analysis of these codes, it was assumed that for each encoding symbol, the neighbors used to generate that encoding symbol are chosen uniformly at random.

Practical implementations of LT codes cannot afford this amount of randomness, because all random bits must be communicated to the decoding party. Instead, they use a linear congruential generator to reduce the randomness used per encoding symbol to a seed consisting of two random numbers. We show that such limited randomness LT codes perform almost as well as the fully random version. Thus even limited randomness LT codes are asymptotically optimal.

Last modified November 25, 2003