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 | 2020/1 |
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:
- On-line resources that you work through at your own pace (e.g. videos, web resources, e-books, quizzes),
- On-line interactive sessions to work with other students and staff (e.g. discussions, live streaming of presentations, live-coding, group meetings)
- Face to face small group sessions (e.g. tutorials, exercise classes, feedback sessions)
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.
Essential Reading and Resource List
An interactive version of this reading list is available at https://whelf-cardiff.alma.exlibrisgroup.com/leganto/public/44WHELF_CAR/lists/7713425420002420?auth=SAML