Luby transform code

<h2 id="why-use-an-lt-code">Why use an LT code?</h2>
The traditional scheme for transferring data across an erasure channel depends on continuous two-way communication.

<ul><li>The sender encodes and sends a packet of information.</li>
<li>The receiver attempts to decode the received packet. If it can be decoded, the receiver sends an acknowledgment back to the transmitter. Otherwise, the receiver asks the transmitter to send the packet again.</li>
<li>This two-way process continues until all the packets in the message have been transferred successfully.</li></ul>
Certain networks, such as ones used for cellular wireless broadcasting, do not have a feedback channel. Applications on these networks still require reliability. <a href="/facts/Fountain_code/st95SSf8">Fountain codes</a> in general, and LT codes in particular, get around this problem by adopting an essentially one-way communication protocol.

<ul><li>The sender encodes and sends packet after packet of information.</li>
<li>The receiver evaluates each packet as it is received. If there is an error, the erroneous packet is discarded. Otherwise the packet is saved as a piece of the message.</li>
<li>Eventually the receiver has enough valid packets to reconstruct the entire message. When the entire message has been received successfully the receiver signals that transmission is complete.</li></ul>
As mentioned above, the RaptorQ code specified in IETF RFC 6330 outperforms an LT code in practice. 

<h2 id="lt-encoding">LT encoding</h2>
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 <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">pseudorandom number generator</a>.

<ul><li>The degree d, 1 ≤ d ≤ n, of the next packet is chosen at random.</li>
<li>Exactly d blocks from the message are randomly chosen.</li>
<li>If Mi is the i-th block of the message, the data portion of the next packet is computed as</li></ul>

M
          
            
              i
              
                1
              
            
          
        
        ⊕
        
          M
          
            
              i
              
                2
              
            
          
        
        ⊕
        ⋯
        ⊕
        
          M
          
            
              i
              
                d
              
            
          
        
        
      
    
    {\displaystyle M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,}

where {i1, i2, ..., id} are the randomly chosen indices for the d blocks included in this packet.
<ul><li>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 {i1, i2, ..., id}.</li>
<li>Finally, some form of error-detecting code (perhaps as simple as a <a href="/facts/Cyclic_redundancy_check/u2exo4sv">cyclic redundancy check</a>) is applied to the packet, and the packet is transmitted.</li></ul>
This process continues until the receiver signals that the message has been received and successfully decoded.

<h2 id="lt-decoding">LT decoding</h2>
The decoding process uses the "<a href="/facts/Exclusive_or/FHyr7hGQ">exclusive or</a>" operation to retrieve the encoded message.

<ul><li>If the current packet isn't clean, or if it replicates a packet that has already been processed, the current packet is discarded.</li>
<li>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.</li>
<li>When a new, clean packet of degree d = 1 (block Mi) 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 Mi, the degree of that matching packet is decremented, and the list of indices for that packet is adjusted to reflect the application of Mi.</li>
<li>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.</li>
<li>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.</li></ul>
This decoding procedure works because A 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 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

(
                
                  M
                  
                    
                      i
                      
                        1
                      
                    
                  
                
                ⊕
                ⋯
                ⊕
                
                  M
                  
                    
                      i
                      
                        d
                      
                    
                  
                
                )
                ⊕
                (
                
                  M
                  
                    
                      i
                      
                        1
                      
                    
                  
                
                ⊕
                ⋯
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        −
                        1
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        +
                        1
                      
                    
                  
                
                ⊕
                ⋯
                ⊕
                
                  M
                  
                    
                      i
                      
                        d
                      
                    
                  
                
                )
              
            
            
              
              
                
                =
                
                  M
                  
                    
                      i
                      
                        1
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        1
                      
                    
                  
                
                ⊕
                ⋯
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        −
                        1
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        −
                        1
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        +
                        1
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                        +
                        1
                      
                    
                  
                
                ⊕
                ⋯
                ⊕
                
                  M
                  
                    
                      i
                      
                        d
                      
                    
                  
                
                ⊕
                
                  M
                  
                    
                      i
                      
                        d
                      
                    
                  
                
              
            
            
              
              
                
                =
                0
                ⊕
                ⋯
                ⊕
                0
                ⊕
                
                  M
                  
                    
                      i
                      
                        k
                      
                    
                  
                
                ⊕
                0
                ⊕
                ⋯
                ⊕
                0
              
            
            
              
              
                
                =
                
                  M
                  
                    
                      i
                      
                        k
                      
                    
                  
                
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}&{}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}}

<h2 id="variations">Variations</h2>
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 {i1, i2, ..., id}, the encoder might simply send a short "key" which served as the seed for the <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">pseudorandom number generator</a> (PRNG) 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 <a href="/facts/Raptor_code/4LIez9tx">raptor code</a> can be constructed that will outperform an optimized LT code in practice.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="optimization-of-lt-codes">Optimization of LT codes</h2>
There is only one parameter that can be used to optimize a straight LT code: the degree distribution function (described as a pseudorandom number generator for the degree d in the LT encoding section above). In practice the other "random" numbers (the list of indices { i1, i2, ..., id } ) are invariably taken from a uniform distribution on [0, n), where n is the number of blocks into which the message has been divided.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
Luby himself<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> discussed the "ideal <a href="/facts/Soliton_distribution/RwEXvehb">soliton distribution</a>" defined by

P
                
                {
                d
                =
                1
                }
              
              
                
                =
                
                  
                    1
                    n
                  
                
              
            
            
              
                
                  P
                
                {
                d
                =
                k
                }
              
              
                
                =
                
                  
                    1
                    
                      k
                      (
                      k
                      −
                      1
                      )
                    
                  
                
                
                (
                k
                =
                2
                ,
                3
                ,
                …
                ,
                n
                )
                .
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\}&={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}}

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 (reduced) 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 <a href="/facts/Soliton_distribution/RwEXvehb">soliton distribution</a>", is substituted for the ideal distribution. The effect of the modification is, generally, to produce more packets of very small degree (around 1) 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Online_codes/rWYURD4M">Online codes</a></li>
<li><a href="/facts/Raptor_codes/4LIez9tx">Raptor codes</a></li>
<li><a href="/facts/Tornado_codes/ywLpA7Yd">Tornado codes</a></li></ul>
<h2 id="notes-and-references">Notes and references</h2>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.codeproject.com/Articles/425456/Your-Digital-Fountain">"Implementation of Luby transform Code in C#"</a></li>
<li><a href="https://github.com/suaybarslan/founsure">"Implementation of Fountain Codes for storage in C/C++"</a></li>
<li><a href="https://franpapers.com/en/algorithmic/2018-introduction-to-fountain-codes-lt-codes-with-python/">"Introduction to fountain codes: LT Codes with Python"</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. <a href="https://ieeexplore.ieee.org/document/1181950/;jsessionid=758EBC54886BB9A881D8EDFB3E71FBF4?arnumber=1181950" target="_blank">https://ieeexplore.ieee.org/document/1181950/;jsessionid=758EBC54886BB9A881D8EDFB3E71FBF4?arnumber=1181950</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">The exclusive or (XOR) operation, symbolized by ⊕, has the very useful property that A ⊕ A = 0, where A is an arbitrary string of bits. <a href="/wiki/Bit" target="_blank">/wiki/Bit</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fountain codes, by D.J.C. MacKay, first published in IEEE Proc.-Commun., Vol. 152, No. 6, December 2005. <a href="http://switzernet.com/people/emin-gabrielyan/060112-capillary-references/ref/MacKay05.pdf" target="_blank">http://switzernet.com/people/emin-gabrielyan/060112-capillary-references/ref/MacKay05.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach, by Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo (2006). <a href="http://www.netlab.tkk.fi/tutkimus/abi/publ/lt-resim-2006.pdf" target="_blank">http://www.netlab.tkk.fi/tutkimus/abi/publ/lt-resim-2006.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. <a href="https://ieeexplore.ieee.org/document/1181950/;jsessionid=758EBC54886BB9A881D8EDFB3E71FBF4?arnumber=1181950" target="_blank">https://ieeexplore.ieee.org/document/1181950/;jsessionid=758EBC54886BB9A881D8EDFB3E71FBF4?arnumber=1181950</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach, by Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo (2006). <a href="http://www.netlab.tkk.fi/tutkimus/abi/publ/lt-resim-2006.pdf" target="_blank">http://www.netlab.tkk.fi/tutkimus/abi/publ/lt-resim-2006.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Luby transform code open-in-new

Luby transform code