MA3007: Coding Theory
| School | Cardiff School of Mathematics |
| Department Code | MATHS |
| Module Code | MA3007 |
| External Subject Code | 100405 |
| Number of Credits | 10 |
| Level | L6 |
| Language of Delivery | English |
| Module Leader | PROFESSOR Iskander Aliev |
| Semester | Spring Semester |
| Academic Year | 2022/3 |
Outline Description of Module
A lecture-based module introducing the fundamentals of the mathematical theory of error-correcting codes. Error-correcting codes are used to correct errors when messages (typically blocks of binary digits) are transmitted using a noisy communication channel (e.g. satellite link). Constructing such codes is based on nice geometric and algebraic ideas.
On completion of the module a student should be able to
- understand how error-correcting codes can be used to reduce the probability of a message being misread.
- do simple calculations in finite-field arithmetic.
- classify an error-correcting code and describe its properties.
- describe some standard examples of error-correcting codes.
- demonstrate an understanding of the theoretical constraints on possible error-correcting codes.
How the module will be delivered
Modules will be delivered through blended learning. You will be guided through learning activities appropriate to your module, which may include:
- Weekly face to face classes (e.g. labs, lectures, exercise classes)
- Electronic resources that you work through at your own pace (e.g. videos, exercise sheets, lecture notes, e-books, quizzes)
Students are also expected to undertake self-guided study throughout the duration of the module.
Skills that will be practised and developed
Skills:
Deciding what level of error-correction is appropriate in a situation. Choosing or constructing an appropriate code. Devising algorithms for error-correction using a given code.
Transferable Skills:
Reasoning logically. Recognising patterns. Calculating in finite-field arithmetic.
Assessment Breakdown
| Type | % | Title | Duration(hrs) |
|---|---|---|---|
| Exam - Spring Semester | 100 | Coding Theory | 2 |
Syllabus content
Introduction; Errors: Basic definitions. Assumptions on the “noise” that causes errors.
Codes: Simple examples, error analysis. Equivalent codes, symmetries.
Distances: Hamming distance, the triangle inequality. Why you choose the “nearest neighbour” codeword. The minimum distance in a code.
Parameters of codes: The (n,M,d)q classification. Transmission efficiency of information. The “sphere-packing” bound for M in terms of d.
Finite fields: The finite field Fp of p elements (or unit digits to base p). The vector space over Fp as a field Fq of q = pn elements.
Plotkin’s bounds: Plotkin’s bounds for M.
New codes from old: Puncturing and shortening codes. Plotkin’s addition of codes.
Linear codes: The generator matrix, decoding by standard error vector cosets.
Dual codes and check matrices: The dual code; its generator matrix is the check matrix. Decoding by syndrome vectors. How to spot the minimum distance.
Perfect codes: The Hamming distance 3 codes and Golay’s codes.