MA6053 - Error Correcting Codes (2019/20)
| Module specification | Module approved to run in 2019/20 | ||||||||||||
| Module title | Error Correcting Codes | ||||||||||||
| Module level | Honours (06) | ||||||||||||
| Credit rating for module | 15 | ||||||||||||
| School | School of Computing and Digital Media | ||||||||||||
| Total study hours | 150 | ||||||||||||
|
|||||||||||||
| Assessment components |
|
||||||||||||
| Running in 2019/20(Please note that module timeslots are subject to change) |
|
Module summary
The module is an introduction to modern ideas in error correcting codes. It provides the background to the essential techniques and algorithms in widespread use today, as well as the essentials of number theory and finite field theory underlying them.
Error correcting codes are an important part of the data communications theory and allow a message to be recovered even if errors have been introduced during transmission. The elegant mathematics of finite field theory is introduced to develop multiple error correcting codes with a wide range of communications applications.
Prior learning requirements
Students are expected to be familiar with concepts in matrices and linear algebra such as would be acquired by taking a level 4 module such as MA4010 – Calculus and Linear Algebra. Knowledge of algebraic structures such as groups is desirable but not essential to take the module.
Syllabus
Theory of fields:
Rings, Integral Domains & Fields, examples and their axioms; construction of finite fields; polynomials over fields and the Euclidean Algorithm; calculation of inverses; factorisation and the construction of minimum polynomials. LO1,LO3
Error correcting codes: Linear codes, Hamming and other perfect codes, check and generator matrices, encoding and decoding strategies using matrices and coset leader/syndrome tables. LO2
Multiple error correcting codes:
BCH codes and the construction of a check matrix; generator and check polynomials; error locator polynomial; Reed Solomon codes and the error evaluator polynomial. LO4
Balance of independent study and scheduled teaching activity
Students’ learning is directed via face-to-face learning activities centred on lectures and seminars. There is full provision of documents related to the module in electronic format that can be accessed by students all the time. The documents include lecture notes, slides, guidance to further reading and relevant mathematical packages, and exercises and tests.
Learning outcomes
On successful completion of this module, students should be able to:
LO1 Appreciate proofs of theorems in Field Theory and their application to coding theory
LO2 Use appropriate error detecting and error correcting algorithms for a given code;
LO3 Construct and perform arithmetic, including finding inverses, in finite fields GF(p^n);
LO4 Use finite field arithmetic to construct efficient multiple error correcting codes including those applicable to a ‘burst error’ scenario.
Assessment strategy
There will be a series of mini tests every 2-3 weeks lasting c15-20minutes, allowing students an early opportunity to demonstrate their understanding of basic topics and techniques [from LO1, LO2 ,LO3, LO4] and to receive feedback on them. The marks for these are aggregated to form a mark for component sequence 001. Students who fail this component of assessment on aggregate will be reassessed by a one hour test covering all topics.
Additionally a 1.5 hour test will take place at the end of the module where students will be tested across the whole of the material studied with longer questions covering both theory and practice in number theory and cryptography [LO1, LO2, LO3, LO4].
Students are permitted to bring two sides of handwritten notes to each assignment to aid the consolidation of learning.
Bibliography
Core Text:
On-line lecture notes
Recommended Reading:
J. Holt, J. Jones (2002); Discovering Number Theory; W.H. Freeman and Company.
Pretzel, O (2002); Error Correcting Codes; Oxford University Press.