Luby Transform Code - LT Decoding

LT Decoding

The decoding process uses the "exclusive or" operation to retrieve the encoded message.

• If the current packet isn't clean, or if it replicates a packet that has already been processed, the current packet is discarded.
• If the current cleanly received packet is of degree d > 1, it is first processed against all the fully decoded blocks in the message queuing area (as described more fully in the next step), then stored in a buffer area if its reduced degree is greater than 1.
• When a new, clean packet of degree d = 1 (block M_i) is received (or the degree of the current packet is reduced to 1 by the preceding step), it is moved to the message queueing area, and then matched against all the packets of degree d > 1 residing in the buffer. It is exclusive-ored into the data portion of any buffered packet that was encoded using M_i, the degree of that matching packet is decremented, and the list of indices for that packet is adjusted to reflect the application of M_i.
• When this process unlocks a block of degree d = 2 in the buffer, that block is reduced to degree 1 and is in its turn moved to the message queueing area, and then processed against the packets remaining in the buffer.
• When all n blocks of the message have been moved to the message queueing area, the receiver signals the transmitter that the message has been successfully decoded.

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