Luby transform (LT) code[1]

Description

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.

Decoding

Sum-product algorithm, often called a peeling decoder [2][3], similar to belief propagation [4].

Parent

  • 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.

Zoo code information

Internal code ID: luby_transform

Your contribution is welcome!

on github.com (edit & pull request)

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. https://errorcorrectionzoo.org/c/luby_transform
BibTeX:
@incollection{eczoo_luby_transform, title={Luby transform (LT) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/luby_transform} }
Permanent link:
https://errorcorrectionzoo.org/c/luby_transform

References

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

Cite as:

“Luby transform (LT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/luby_transform

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/luby_transform.yml.