MATH32031 Coding Theory - 2014/15, Semester 1

Thank you for visiting. The purpose of this page is to give a preview of the Coding Theory course, which will begin in September 2014.

About the course

Please make sure that you have read the official course description. Below is some information that complements it.

What is it all about?

Coding theory is not about writing computer code, and is not about cryptography. The purpose of coding theory is to generate mathematical ideas and methods that can be used to transmit information more reliably. The main concept of coding theory is error correcting code.

Why does one need error correction?

When information (message) is passed from a sender to a receiver, there is a chance that some parts of that message are changed or lost. This is often due to random noise - think of atmospheric noise interfering with radio transmision, gamma-ray bursts affecting satellite feed, crosstalk in Ethernet cables, scratches on a DVD, etc. One would like to recover the original message after it has been affected by noise.

How can one possibly correct errors in the transmitted messages?

One wants to design messages in such a way that they are "far" from each other. Then, if a message is changed slightly, it still does not coincide with any other message, and can be recovered.

The precise meaning of "far" can be formalised in terms of Hamming distance, but here is an easy example.

Suppose that we want to transmit one of the two messages: 0 (No) or 1 (Yes). If we send just one bit, 0 or 1, it can arrive corrupted so that No changes to Yes and vice versa - there is no way to know that an error occurred. We will transmit the codeword 00000 for No and the codeword 11111 for Yes. That way, because it is much less likely that more than two bits will change in a transmitted codeword due to noise, the received word 01000 can be fairly safely interpreted to mean No.

We have just seen an example of an error correcting code called repetition code, which is quite inefficient: we had to send five bits instead of one. In the course, we will see how to design much more efficient codes.

What mathematical ideas are used to design codes?

We will use algebra and, to some extent, geometry and logic to do this, and will have to work with vectors, matrices and projective spaces over finite fields, polynomials and the Boolean algebra. We will prove general facts about codes. We will also see some codes which were used by NASA to transmit messages to the deep space missions, and codes used in modern telecommunication networks, alongside more peculiar historical applications of codes in sports betting.

It should be noted that, while the above serves as a background or motivation to the study of codes, all the examinable material in this course is purely mathematical. Students' knowledge of electrical engineering or sports will not be assessed.

Lecture notes

Here are the lecture notes from the 2013/14 academic year. The material is not expected to vary too much, but use at your own risk.

Previous years' exams:

Coding Theory exam papers from years 2008-2014 are here. Model solutions are provided for most papers.

Extra material (optional)

Here you can view Golay's original paper of 1949 where he introduced the Hamming codes and two other perfect codes known as the Golay codes. Amazingly, the paper is only half a page long. (C) IEEE

Here is a newspaper article which attempts to describe, to a lay audience, an example of use of the Distance Theorem for linear codes.

Here is a survey of early Algebraic Coding Theory. You can read about a football pool enthusiast who happened to discover the ternary Golay code more than a year before Golay.

Organisation

There will be three 50-minute sessions per week in weeks 1-5 and 7-12. Two sessions will be designated as lectures, and one as an examples class. There will be example sheets. In an examples class, we will typically be going over the solutions to the questions on the most recent example sheet; sometimes we will do short quizzes in class, which will not be assessed (due to traditionally large class size of MATH32031).

Assessment and e-learning

Percentages indicate the weighting of each mode of assessment in the final mark.
Students will be given access to the Blackboard-based Coding Theory Discussion Forum, where various aspects of the course will be discussed. This forum is a useful venue for asking (and answering!) questions about the course material, assessment, etc.

Arrangements

Timetable:
Wednesday 12pm-12:50pm, Friday 12pm-12:50pm and 1pm-1:50pm, Schuster Rutherford lecture theatre.
Lecturer:
Dr Yuri Bazlov
e-mail:
yuri.bazlov, append AT and manchester.ac.uk
office:
2.220 Alan Turing building
office hours:
TBA. I intend to be available in my office during the office hours, but students may come to see me at other times as well, or make an appointment by email.