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

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}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/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

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