The encyclopedia · Engineering & Operations · Technical decision · 1998-2002
LT codes made erasure correction rateless so a sender never asks what you lost
Luby Transform codes emit an endless stream of coded symbols, so a receiver gets what it needs without the sender learning which packets died.
Digital Fountain
the move
Broadcasting a large file was stuck on a chicken-and-egg problem: you had to pick how much redundant data to add before you knew how much loss the path would deliver.
Luby Transform codes, introduced by Michael Luby in 1998 and formalised in 2002, are the first practical 'fountain' or rateless codes. They generate an unbounded stream of encoded symbols, and the decoder uses the sparse degree distribution to peel the source symbols back out once it has enough.
The trick is that it does not matter which encoded symbols arrive — only how many. So the receiver asks for nothing; it just stops when it has decoded the whole file.
why it works
- A rateless code needs no estimate of the loss rate before transmission begins.
- It needs only a small constant overhead above the source length, not a fixed redundancy.
- Because any subset works, it suits multicast and broadcast where feedback from many receivers is impractical.
what transfers
If you cannot predict a failure rate, design a scheme that adapts as the data arrives instead of committing to a number upfront. Make the receiver smart enough to stop when done.
what came after
LT codes became the basis for fountain-coding research and led to the Raptor codes used in the DVB broadcast, LTE and the delivery of large files over lossy links. The rateless idea moved erasure coding from fixed blocks to a stream a receiver can turn off at will.
references
- A Digital Fountain Approach to Reliable Distribution of Bulk Data (SIGCOMM 1998)
- A Digital Fountain Approach to Reliable Distribution of Bulk Data (review)
spotted an error? The archive wants to know.