[Department project server / Index]

Part III Physics projects (2005)

Prof. David J.C. MacKay, Astrophysics group

Room 961 Rutherford building, x39852, http://www.inference.org.uk/mackay/

E-mail: mackay@mrao.cam.ac.uk

A project for a student with exceptionally good theoretical and computational skills. Send email to discuss.

1. Fountain Codes

Fountain codes are record-breaking sparse-graph codes for channels with erasures -- such as the internet, where files are transmitted in multiple small packets, each of which is either received without error or not received.

Standard file-transfer protocols simply chop a file up into K packet-sized pieces, then repeatedly transmit each packet until it is successfully received. A back-channel is required for the transmitter to find out which packets need retransmitting. In contrast, fountain codes make packets that are random functions of the whole file. The transmitter sprays packets at the receiver without any knowledge of which packets are received. Once the receiver has received any N packets, where N is just slightly greater than the original file-size K, he can recover the whole file.

In this project you will study the question: `how to make optimal fountain codes?'

Information Theory, Inference, and Learning Algorithms Information Theory, Inference, and Learning Algorithms
by David MacKay

Further reading:
[1] Fountain Codes (review paper by David MacKay)
[2] Chapter 50 in Information Theory, Inference, and Learning Algorithms
[3] Papers by Amin Shokrollahi at http://algo.epfl.ch/

URL: http://www.inference.org.uk/teaching/projects/p.html

David MacKay
1999 | 2000 | 2001 | 2004 Last modified: Thu Oct 13 14:20:18 2005