Luby transform code


In computer science, Luby transform codes are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT codes depend on sparse bipartite graphs to trade reception overhead for encoding and decoding speed. The distinguishing characteristic of LT codes is in employing a particularly simple algorithm based on the exclusive or operation to encode and decode the message.
LT codes are rateless because the encoding algorithm can in principle produce an infinite number of message packets. They are erasure correcting codes because they can be used to transmit digital data reliably on an erasure channel.
The next generation beyond LT codes are Raptor codes, which have linear time encoding and decoding. Raptor codes use two encoding stages for encoding, where the second stage is an LT encoding.
Information about availability of an efficient software implementation of the RaptorQ code specified in IETF RFC 6330, can be found at the
.

Why use an LT code?

The traditional scheme for transferring data across an erasure channel depends on continuous two-way communication.
Certain networks, such as ones used for cellular wireless broadcasting, do not have a feedback channel. Applications on these networks still require reliability. Fountain codes in general, and LT codes in particular, get around this problem by adopting an essentially one-way communication protocol.
The encoding process begins by dividing the uncoded message into n blocks of roughly equal length. Encoded packets are then produced with the help of a pseudorandom number generator.
This process continues until the receiver signals that the message has been received and successfully decoded.

LT decoding

The decoding process uses the "exclusive or" operation to retrieve the encoded message.
This decoding procedure works because A A = 0 for any bit string A. After d − 1 distinct blocks have been exclusive-ored into a packet of degree d, the original unencoded content of the unmatched block is all that remains. In symbols we have

Variations

Several variations of the encoding and decoding processes described above are possible. For instance, instead of prefixing each packet with a list of the actual message block indices, the encoder might simply send a short "key" which served as the seed for the pseudorandom number generator or index table used to construct the list of indices. Since the receiver equipped with the same RNG or index table can reliably recreate the "random" list of indices from this seed, the decoding process can be completed successfully. Alternatively, by combining a simple LT code of low average degree with a robust error-correcting code, a raptor code can be constructed that will outperform an optimized LT code in practice.

Optimization of LT codes

There is only one parameter that can be used to optimize a straight LT code: the degree distribution function. In practice the other "random" numbers, where n is the number of blocks into which the message has been divided.
Luby himself discussed the "ideal soliton distribution" defined by
This degree distribution theoretically minimizes the expected number of redundant code words that will be sent before the decoding process can be completed. However the ideal soliton distribution does not work well in practice because any fluctuation around the expected behavior makes it likely that at some step in the decoding process there will be no available packet of degree 1 so decoding will fail. Furthermore, some of the original blocks will not be xor-ed into any of the transmission packets. Therefore, in practice, a modified distribution, the "robust soliton distribution", is substituted for the ideal distribution. The effect of the modification is, generally, to produce more packets of very small degree and fewer packets of degree greater than 1, except for a spike of packets at a fairly large quantity chosen to ensure that all original blocks will be included in some packet.