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 (SPA), 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.
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
Page edit log
- Victor V. Albert (2022-05-26) — most recent
- Thomas Wrona (2022-05-02)
- Noah Berthusen (2022-04-21)
Cite as:
“Luby transform (LT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/luby_transform