| Lecturer: | Prof Norman Biggs |
| Room: | B306 (3rd floor, Columbia House) |
| Email: | N.L.Biggs@lse.ac.uk |
| Office hours: | Please see the office hours page |
Lectures: (Michaelmas Term) Tuesday 10.00 - 12.00 (room D703).
Classes: There will be one class each week 10.00 - 11.00 on Thursdays in room V303, starting in the second week of the Michaelmas Term.
There will be some revision lectures or classes in the Summer Term.Course
materials
The course will based on the following text
N. L. Biggs, Codes: An Introduction to Information, Communication and Cryptography, Springer 2008.
Not all the material in the book will be covered in the course, and a key to the examinable material will be distributed.
Weekly exercises will be set, selected from the exercises in the course text. Work should be handed in, and will be discussed in the class.
Notes on the exercises will be distributed in due course. (Some exercises may require the use of Maple, and a separate information sheet about them will be distributed).
Books
In addition to the course text, the following may be useful.
G. A. Jones and J. M. Jones: Information and Coding Theory Q360 J71
C. M. Goldie and R. G. E. Pinch: Communication Theory TK5101 G61
D. J. A. Welsh: Codes and Cryptography Z103 W46
The following book contains much more material
than can be
covered in the course, but it may be useful for background reading and
ideas for
dissertations:
D. J. C.
MacKay: Information Theory,
Inference, and Learning Algorithms.
Assessment
There
will be a formal 2-hour examination in the Summer
term, counting for 90% of the final mark.
This course provides
an
introduction, for students with a mathematical background, to
information
theory, coding theory, cryptography, and related areas. These areas
have been
the subject of significant advances during the last 50 years, beginning
with the
fundamental work of Shannon. He
provided good definitions of such things as ‘information content’ and
‘channel capacity’, leading to the formulation of precise mathematical
statements. Nowadays these ideas
provide a framework for serious discussion of practical aspects of
communication, such as data compression, coding, and cryptography.
In coding theory, the aim is to construct systems that will overcome random errors produced by ‘noise’ in the system. On the other hand, in cryptography we seek to transform a message into a form that can only be understood by the intended recipient. Not surprisingly, absolute security is unobtainable in practice, and so we are led to introduce the notion of complexity. The intention is that it will be relatively easy for the intended recipient to understand the message, but very hard for anyone else to do so.
Prerequisite
Students
must attend the course MA407
Algorithms and Computation.
Course
Content
The course will cover
mathematical
aspects of the following topics.
Noiseless coding, the
Kraft-McMillan criterion, optimal coding, entropy, Shannon's first
theorem.
Noisy channels, capacity,
system entropy, outline proof of Shannon's fundamental theorem.
Error-correcting codes,
decoding rules, bounds, construction and properties of linear and
cyclic codes.
Structure of
natural languages, redundancy, the frequency table, making and breaking
cryptosystems, historical examples.
Public-key cryptography, complexity issues, the RSA system, authenticity and signatures, elliptic curve cryptography.
Office
Hours
Please note: students are advised not to rely too heavily on past exam papers when revising for their exams, as they can only offer a limited indication of what might be covered in a future exam. For further information, please see the guidance here: http://www.maths.lse.ac.uk/examinations_in_mathematics.html#past_papers
MA410 Exam paper
of 2006
MA410
Solutions to the 2006 exam
MA410 Exam paper
of 2007
MA410
Solutions to the 2007 exam
MA410 Exam paper
of 2008
MA410
Solutions to the 2008 exam
MA410 Exam paper of 2009
MA410
Solutions to the 2009 exam