A first course in linear algebra, such as G11LMA,
and an understanding of mathematical proof techniques, as in G11ACF;
some further experience of pure mathematics (especially algebra) would
be an advantage, and some familiarity with basic probability, as in
G1APRB, would also be helpful.
Outline of the Module
The tools used in this module are elementary probability theory,
linear algebra, and (for G13CCR only) some simple number theory.
The first few lectures define the concepts of information
and uncertainty, and so provide a brief introduction to information theory.
The rest of the module is in three parts, describing three different types of
code.
Data compression.
If we have a message to send,
we may want to encode it so that it becomes as short as possible.
Thus the codewords for words that are used most frequently should be shortest.
However, it must be possible to decode the received message unambiguously.
This places limits on the lengths of the codewords.
These limits, and a standard method for encoding, will be described.
Error-correcting codes.
In a "noisy" communication channel,
the received message may differ from that transmitted because of errors.
But if the message is suitably encoded, the receiver may be able to recover
the correct message with a high degree of probability.
For example, the sender could repeat each
symbol so many times that the receiver is almost bound to get it right.
But clearly this slows down the rate of communication.
In general one can do much better than this by skilful coding.
We will investigate various types of good error-correcting code.
(For G13CCR only:)
Cryptography.
Coding is also used to keep messages secret;
this is increasingly important as confidential information is sent through
insecure channels (telex, telephone, the internet, etc.).
Often the general method of encipherment is publicly known,
but involves the use of a number or word called the key,
which is changed regularly and kept secret.
The cryptanalyst's task is to deduce the key used
on a particular occasion by studying intercepted enciphered messages.
The cryptographer's task is to make this too difficult in the time available.
Some classical ciphers will be discussed together with methods for breaking
them, based on simple probability theory.
Some public-key cryptosystems will also be described.
Method and frequency of class
3 hours per week, plus regular coursework assignments.
One lecture each week is devoted to Cryptography and
the other two lectures to Information and Coding theory.
Assessment
One 2½-hour written examination for G13CCR;
one 2-hour written examination for G13CC2.
Reading
The following books are recommended, although Singh is nonmathematical
and is for interest only.
Welsh is by far the best book for the module as a whole (and would be a
useful "buy"), with the other books being relevant to parts of it.
(If you find a book that you think is more useful,
whether or not it is in the library, please tell the lecturer.)
D. Welsh, Codes and Cryptography (Oxford, 1988, QA 269.5).
D. S. Jones, Elementary Information Theory (Oxford, 1979, TK 5102).
R. Hill, A First Course in Coding Theory (Oxford, 1986, QA 269.6).
For G13CCR only:
H. Beker and F. Piper, Cipher Systems (Northwood Books, London, 1982,
QA 269.5).
S. Singh, The Code Book (Fourth Estate, London, 1999, QA 269.5).