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

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 <mackay@mrao.cam.ac.uk>
Last modified: Mon Sep 27 15:05:59 1999