Luby transform (LT) code[1] 


Erasure codes based on fountain codes. They improve on random linear fountain codes by having a much more efficient encoding and decoding algorithm.

LT codes can be constructed as follows. First, randomly choose a degree \(d_n\) from a degree distribution depending on total size \(K\). Then, randomly choose \(d_n\) distinct source packets and let the packet to be transmitted \(\hat{p}_n\) be the bitwise sum of the chosen input packets. This forms a graph connecting encoded packets to source packets.


Sum-Product Algorithm (SPA), often called a peeling decoder [2,3], similar to belief propagation [4].


  • Raptor (RAPid TORnado) code — Raptor codes using a trivial pre-code are LT codes. Typically, Raptor codes have constant-sized more overhead but are faster to decode.


M. Luby, “LT codes”, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. DOI
T. Richardson and R. Urbanke, Modern Coding Theory (Cambridge University Press, 2008) DOI
David J. C. MacKay. 2002. Information Theory, Inference & Learning Algorithms. Cambridge University Press, USA
J. Pearl, “Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach”, Probabilistic and Causal Inference 129 (2022) DOI
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: luby_transform

Cite as:
“Luby transform (LT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
@incollection{eczoo_luby_transform, title={Luby transform (LT) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Luby transform (LT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.