MC347 Coding Theory

Next: MC361 Generalized Linear Models Up: Year 3 Previous: MC346 Communicating Mathematics

MC347 Coding Theory

Credits: 20

Convenor: Dr. J. C. Ault

Semester: 1

Prerequisites:	essential: MC241, MC144, MC145, MC147	desirable: MC242, MC344
Assessment:	Course Work: 10%	Three hour exam: 90%

Lectures:	36	Classes:	10
Tutorials:	none	Private Study:	104
Labs:	none	Seminars:	none
Project:	none	Other:	none
Total:	150

Explanation of Pre-requisites

Much use is made of concepts from Linear Algebra (MC147 and MC241) such as linear independence; basis of a linear space; dimension of a linear space; solution space of a set of linear equations; matrix algebra; row and column operations. MC242 is useful for the analogy between concepts and results introduced here and those of Group Theory.

Course Description

The general aim of the course is to introduce the idea of error-correcting codes and to develop some of the standard techniques for constructing codes with specified desirable properties. The theory and techniques make heavy use of many concepts and theorems from abstract algebra and this topic may be thought of as the culmination in the form of a practical application of ideas learnt elsewhere. Consequently, some reliance will be placed on previous knowledge - particularly from Linear Algebra - but not without a brief resume of the relevant results. Other topics will be covered here, especially for those who have not seen them before, but not with the same thoroughness as would be the case in a dedicated course of Abstract Algebra.

Aims

To understand some of the mathematical theory necessary for the efficient and accurate transmission of information and to show that abstract pure mathematics can have important practical applications. The problems set are intended not only to give practice with the work in the course but also to give an opportunity for improvement in the presentation of Mathematics in writing.

Objectives

At the end of the course you should have a good understanding of the basic concepts of error-correcting codes, the three main parameters associated with a code - its length, its minimum distance and the number of codewords - and how these are related by the sphere-packing bound. You should also have some knowledge of how to construct linear codes and cyclic codes and how to use them in practice. The application of syndrome decoding is particularly important in this respect. You should also have learnt (or reinforced your previous learning) about finite fields, polynomials and linear algebra.

Transferable Skills

The abstraction of a practical problem and the application of known mathematical techniques to its solution.

Syllabus

Minimum distance and error correction abilities of codes, general equivalence of codes, perfect codes. Finite fields. Linear codes, generator matrices, equivalence of linear codes, decoding and encoding, dual codes, orthogonality, parity check matrices and syndrome decoding, the Hamming codes. Ideals in the ring of polynomials, cyclic codes, generator and check polynomials for a cyclic code, the ternary 2-error correcting Golay code.

Reading list

Background:

N. L. Biggs, Discrete Mathematics, Oxford University Press.

Details of Assessment

Assessment is by a combination of coursework (10%) and 3 hour examination (90%) in January. The coursework mark is based on weekly problem sheets, the better marks of each two weeks being averaged to give the overall mark. (The second of each pair of problem sheets will contain questions similar to those on the first.) The examination is based on the material given in the lectures, and tests knowledge of the Mathematics used as well as an understanding of the concepts of error-correcting codes.

Next: MC361 Generalized Linear Models Up: Year 3 Previous: MC346 Communicating Mathematics

S. J. Ambler
11/20/1999