Digital Fountain Codes
Aims: Understand and implement a randomised protocol called a Digital Fountain Code – for sending a file over a channel, without the receiver having to ever ask for any part of the message to be re-sent.
Background: Digital fountain codes (or Luby codes) are an elegant solution to a natural problem. Suppose you have to send a large file over a network, so that you have to split it into a sequence of small packets. Suppose that some packets can get lost, and suppose that it is either expensive or impossible for the receiver to ask you to re-send any lost packets, and you do not know which packets did not arrive. How can you send the file so that the receiver can reconstruct it? One’s first idea is to send a stream of packets, each containing a random part of the file: eventually the receiver will get all parts of the file, but the total amount of packets that the receiver has to get will be many times the size of the original file. Remarkably, using a digital fountain code, it is possible to construct randomised packets so that the receiver can reconstruct the file after receiving only about 5% more data than was in the original file. Although the basic idea is quite simple, there are numerous issues in constructing an efficient implementation, and the optimal ‘degree distribution’ of the packets may still be unknown.
Early Deliverables
A basic implementation for sending sequences of characters. The ‘droplets’ may be object instances with appropriate fields. The implementation should consist of two programs: an encoder that reads in a text file and writes out a sequence of ‘droplets’, and a decoder that reads in a sequence of droplets and which outputs a text file, which should be identical to the original text file.
A description of how the basic encoding and decoding algorithms work, with pseudocode and a running example. It should also include a discussion of the ‘degree distribution’, and of how to sample random values from a discrete distribution.
Final Deliverables
An efficient program for encoding and decoding.
A sequence of well designed and analysed experiments investigating the program’s efficiency and behaviour.
The report will contain a discussion of erasure channels, contrast with feedback channels. When are erasure channels needed? What other solutions are there?
The report will contain a description of Digital Fountain Codes: basic encoding and decoding, with a running example. Role of degree distribution. Behaviour with special cases of degree distribution. Luby’s degree distributions. Time and space efficiency of variants of decoding algorithm.
The report will contain 3. Design and implementation: What is overall structure of program? What are design issues? How were these design issues resolved?
The report will contain complete testing schedule: What is evidence program is correct (test cases)
The report will contain an analysis of the time and space efficiency of algorithm(s)
The report will contain, for each experiment: aim, method, tables/graphs of results, questions raised
Suggested Extensions
Implementation should be efficient: different optimisations lead to time and space efficiency. Many small extensions to algorithm are possible. You could design and carry out experiments to assess the efficiency of your algorithm.
It is possible to design experiments to check the efficiency of the packet degree distribution, and you could try to optimise the degree distribution in the light of your experiments.
Reading
Start with Wikipedia on ‘Luby Transform Code’, and the
