Part III Physics projects

Dr. David J.C. MacKay, Astrophysics group

Room 961 Rutherford building, x39852,


Meet to discuss at 2pm on Tuesday October 19th

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. This project involves theoretical and experimental work on a new system for solving this communication problem.

(0) Work out the reliability of simple-minded communication schemes.
(1) Consider the subproblem of recovering synchronization in the case where the transmission is known, and there are just insertions, deletions and noise. Connect this problem to the results for flux depinning:
T. Hwa and M. Lassig, "Similarity-Detection and Localization," Phys. Rev. Lett. 76, 2591-2594 (1996)
Scaling Laws and Similiarity Detection in Sequence Alignment with Gaps by D. Drasdo, T. Hwa and M. Lassig.
and if possible come up with a predictive theory for the probability of symbol error as a function the in/del probabilities.

2. Empirical models of error-correcting code performance (T/C)

At present, the best codes for communication over noisy channels are Gallager codes. The main method for finding the performance of a particular code is to simulate it. In this project an empirical model of Gallager code performance will be built, based on existing data and new computer experiments. This model will be a useful tool for the error-correcting code community, allowing performance to be predicted without lengthy simulations.

inputs - Eb/No, or raw bit error rate. Block length. Capacity of channel. Distance from capacity. Code rate. Row weight and column weight. Field size (q). Number of constraints.
output - log(p_B/(1-p_B)), or log(p_b/(1-p_b)).

3. Fast Monte Carlo methods for Boltzmann machines. (T/C)

Boltzmann machines are neural networks that can be trained to discovery simple patterns in data. The training involves a rather slow Monte Carlo method. This project will investigate a cheap-and-cheerful Monte Carlo method proposed by Hinton (1999), to establish (a) whether it always converges to the right answer; (b) if not, why not; (c) when it does work, whether it's always faster than the standard method.
David MacKay <>
Last modified: Mon Sep 27 15:05:59 1999