Part III Physics projects

Dr. David J.C. MacKay, Astrophysics group

Room 961 Rutherford building, x39852,


Meet to discuss at 2pm on Tuesday October 17th

1. Reliable Communication over Insertion/Deletion Channels (T/C)

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.

2. Solving combinatorial problems by message-passing (C)

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
[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.

David MacKay <>
Last modified: Thu Aug 23 23:23:17 2001