Home

Luby Transform Fountain Code

This project is a way to get the Luby Transform Code work. you can easily apply this algorithm in your project or work, but it does not means the encoding and decoding process is easy to understand and keep in mind. There comes the wiki, here i will give a brief understanding of this algorithm existing in the code implementation. If you do not know clearly how this algorithm generally work, you may need to refer to paper. Here I just come to the main idea.

Encoding Process

   1. open the transform file and save it in a byte buffer.

   2. split the source bytes into K equal length blocks, if 
      without enough bytes, fill b'0' at end.

   3. each time get a random degree from CDF array, d , and 
      then select d blocks randomly.

   4. make ^ operate within the d blocks and send the seed 
      number of d, block size, total file size out.

   5. loop step 3 and 4 until the decoder decode the source
      file out.

The encoder's work flow is nothing special and easy to understand, there should be something you should get it out: how to calculate the CDF array? you may refer to the paper for details.

Decoding Process

The decoding process may not easy as the the encoding process to understand. The confusing part is the several data structure use in decoding process, which really confuse people.

   1. waiting until the package which just contain one source block, if not, 
      just save the package information and continue waiting.

   2. try to eliminate the source graph with certain source block:
      1) if all the source block can be decode, exist
      2) if without enough source package, just receive, use the source 
         block do ^ operation with the coming and existing data package, 
         remove the check between source package and source block.

this usually is not enough to make the decode process clear. I will just use the actual data structure in the python implementation to get you out of the confusion.

    eliminated: {}
    checks: {}
    
    use the dictionary structure to save the source block, why use this data structure? 
    because the source block may come and decode without source file block order, here 
    you need to save the block index and the block data.

    what does the checks dictionary save?
    there the author define a class to hold the check between data package and data block:

                 _____ check(how the package comes from, may be s1, s2, s8 do ^ operation)
                |
    CheckNode : |
                |_____ data package(one block length)

    
    when there comes a package consist of one source block, it will be added to eliminated
    dictionary, and remove all the checks connected to this source block.

    if comes a package consist of several package, use the eliminated dictionary to remove
    some checks, then check if some source block can be eliminated, if it does, add the 
    source block to the eliminated dictionary, if not, just add construct the checkNode with
    checks and data package and add the checkNode to each node contained in this data package 

    with enough data package and the source can be decoded out.