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
- Michael Luby. LT Codes. FOCS 2002, sections 1.1-1.2, 2-3. DOI: 10.1109/SFCS.2002.1181950.
- Amin Shokrollahi. Raptor Codes. IEEE TIT 52(6), 2551-2567 (2006), sections III-IV. DOI: 10.1109/TIT.2006.874390.
- RFC 6330 (2011): RaptorQ, sections 5.3.1, 5.8 and 6.
- Hesela: exact synthetic XOR equation, rank and peeling observations
Further reading
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.