# Part III Physics projects

Dr. David J.C. MacKay, Astrophysics group
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

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

David MacKay <mackay@mrao.cam.ac.uk>
Last modified: Thu Aug 23 23:23:17 2001