lt-code · research · also Luby transform code, LT codes

LT code

An LT code is a rateless erasure code that forms each output symbol by XORing a randomly selected subset of source symbols according to a degree distribution.

The encoder samples a degree d, then d distinct source neighbors. A receiver needs the same neighbor information, whether transmitted explicitly or reconstructed from agreed identifiers and parameters. Peeling recovers an input from an equation with one remaining unknown, substitutes it into neighboring equations and repeats. The choice of degree distribution is essential to keeping this process progressing. [1]

Do not equate a stalled peeling decoder with insufficient information. In the linked example, the equations a XOR b, a XOR c and a XOR b XOR c determine all three inputs, but none initially has degree one. Adding a alone permits peeling to recover the other two. This illustrates a decoder limitation with fixed equations, not the failure probability of a designed LT code. [4]

The LT paper's ripple is the set of released input symbols awaiting processing; Shokrollahi also defines an output ripple of degree-one equations. Counts for these two definitions need not coincide when several equations expose the same input. [1] [2]

Relations

related
Fountain code, Erasure coding, Raptor code, RaptorQ

Limitations

  • The original LT construction is not systematic. Systematic RaptorQ is a separate construction, not another name for plain LT coding. [1, 3]

Citations

  1. Michael Luby. LT Codes. FOCS 2002, sections 1.1-1.2, 2-3. DOI: 10.1109/SFCS.2002.1181950. (accessed 2026-11-21)
  2. Amin Shokrollahi. Raptor Codes. IEEE TIT 52(6), 2551-2567 (2006), sections III-IV. DOI: 10.1109/TIT.2006.874390. (accessed 2026-11-21)
  3. RFC 6330 (2011): RaptorQ, sections 5.3.1, 5.8 and 6. (accessed 2026-11-21)
  4. Hesela: exact synthetic XOR equation, rank and peeling observations (accessed 2026-11-21)

Further reading

  1. Hesela: worked decoding example and reproduction instructions (accessed 2026-11-21)
Sources & caveats
  • Source review covers the encoder, recovery rule and ripple definitions rather than relying on the abstracts. No throughput or recovery-rate replication is claimed.

JSON: /data/terms/lt-code.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. LT code. Hesela. 2026-11-21. https://hesela.dev/terms/lt-code/