module specification

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
applications in a wide range of communications applications.

Please note: This module is superseded by MA6030

Prerequisite: MA2036N Further Discrete Maths or MA1040N Linear Algebra or equivalent

This module aims to
• develop students understanding of situations in which error correcting codes are used;
• develop and analyse algorithms for encoding and decoding efficient single error correcting
      codes;
• to use finite fields to develop efficient multiple error correcting codes.

The Graduate Attribute appropriate to this module is A2.

Assumptions for the binary symmetric channel; error detecting versus error detecting; minimum distance; the probability of undetected error.

Linear codes; check and generator matrices; decoding by cosets; Hamming codes and other perfect codes.

The existence of finite fields and the representation of elements; arithmetic in a finite field; Fermat’s little theorem; minimal polynomials; irreducible polynomials.

Vandermonde matrices and the construction of check matrices for BCH codes; an encoding algorithm for BCH codes; codeword checking in BCH codes; a decoding algorithm for BCH(k,t) and the error locator polynomial.

The problem of burst errors; constructing Reed Solomon codes; adapting the BCH decoding algorithm to RS(k,t); the error evaluator polynomial.

The module will be timetabled for four hours per week over 12 weeks and incorporates lectures and problem classes. The lectures will outline the main concepts proving relevant theorems and describing examples. The problem classes will enable students to practice the techniques. There will be approximately 30 hours of lectures and 18 hours of problem classes.
Students will be expected to spend time on unsupervised work, for example, exercises and directed reading (102 Hours).
Printed lecture notes will be available to students in hard copy form and on the web and will form the basis of directed reading for students.

On completing this module students should be able to:

LO1: Find the minimum distance, generator and check matrices for a given code;
LO2 : Specify appropriate error detecting and error correcting strategies for a given code;
LO3 : Construct and use a coset leader/syndrome table to correct errors in received words;
LO4 : Construct finite fields of order pn representing elements as numbers and/or polynomials;
LO5: Perform arithmetic operations and calculate inverses in a finite field;
LO6: Find the minimal polynomial of an element in a finite field;
LO7: Encode a given message in BCH(k,t);
LO8: Determine whether a given received word is or is not a codeword in BCH(k,t);
LO9: Apply a decoding algorithm to identify the locations of up to 3 errors in a received word in
BCH(k,t) or RS(k,t);
LO10: Calculate the error evaluator polynomial for a given received word in RS(k,t) and use it
correct burst errors of reasonably short length.

Assessment is designed to address all the Learning Outcomes of the module. The principal assessment instrument is the end of module examination which tests students’ ability to construct, manipulate and interpret the results of constructions using the various models encountered.

Practice in examination type questions is provided by the formative in class exercises and by test based on previous examination questions.

In order to pass the module, a student must achieve an aggregate mark of 40% or more.

Pretzel, O; Error Correcting Codes; Oxford University Press, (1996)