Room 961 Rutherford building, x39852, http://wol.ra.phy.cam.ac.uk/mackay/
E-mail: mackay@mrao.cam.ac.uk
Meet to discuss at 2pm on Tuesday October 17th
Some communication channels suffer from loss of synchronization. In a binary channel, for example, the transmission 1001001001001001 might be received (after one insertion and one deletion) as 1001100100100101. We would like to communicate data reliably and fast over such channels.
In the 1960s two papers were written describing the limits to communication if one uses random codes and a decoding method known as sequential decoding [3,4].
In this project you will learn about the theoretical methods used, and compare the results with recent empirical results [1,2], which suggest that the theoretical results could be improved. The aim of this project will be to attempt to so improve those theoretical bounds, or understand why they cannot be further improved.
This project would require considerable background study, and should only be attempted by an independent-minded student.
[1] Matthew C. Davey and David J. C. MacKay,
"Reliable communication over channels with insertions, deletions and substitutions".
[2]
Edward A. Ratzer and David J.C. MacKay,
"Codes for Channels with Insertions, Deletions and Substitutions".
[3] Gallager, R. G.,
"Sequential Decoding for Binary Channels with Noise and Synchronization Errors",
Unpublished Lincoln Lab report 25 G-2, 1961.
[4] Zigangirov, K. Sh.,
"Sequential Decoding for a Binary Channel with Drop-outs and Insertions",
1969.
The maximum independent set problem is a classical problem in combinatorial optimization [1]. A graph consisting of edges and vertices is given, and the problem is to find the maximum size subset of vertices such that no vertices in the subset have edges between them.
In this project you will try applying message-passing methods, which have been found to work very well on other NP-complete problems [2], to this problem, comparing the results with the best known methods [1].
[1] See review papers
provided
in http://wol.ra.phy.cam.ac.uk/teaching/projects/papers/.
[2] D. J. C. MacKay and R. M. Neal,
"Near Shannon Limit Performance of Low Density Parity
Check Codes",
Electronics Letters
33(6):457-458, March 1997.