Luby Transform Code - LT Encoding

LT Encoding

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.

• The degree d, 1 ≤ d ≤ n, of the next packet is chosen at random.
• Exactly d blocks from the message are randomly chosen.
• If M_i is the ith block of the message, the data portion of the next packet is computed as

where {i₁, i₂, …, i_d} are the randomly chosen indices for the d blocks included in this packet.

• A prefix is appended to the encoded packet, defining how many blocks n are in the message, how many blocks d have been exclusive-ored into the data portion of this packet, and the list of indices {i₁, i₂, …, i_d}.
• Finally, some form of error-detecting code (perhaps as simple as a cyclic redundancy check) is applied to the packet, and the packet is transmitted.

This process continues until the receiver signals that the message has been received and successfully decoded.