Coding Theory
Lectures and Tutorials: Irina Bocharova
Language of instruction: English
Schedule
| Lectures: | Thr 16.15-17.45 |
| Practice: | Fri 14.15-15.45 |
Additional office hours: Tuesday, 14.00-16.00
About the course
In our information age, we are used to operating with huge volumes of information: multimedia files, software, databases, etc. Is not it amazing that a multi-gigabyte movie, downloaded from the Internet to a mobile phone or a picture from Mars,sent by Curiosity does not contain errors, despite the inevitable noise in the information storage medium or in the communication channel?
In fact, there were errors and there were a lot of them, but they were all corrected by error correcting codes constructed using elegant mathematical methods. Coding theory has achieved impressive results, applying algebra, finite geometries, graph theory, combinatorics, probability theory, etc. At the first glance, it sounds dangerously complicated but in our course, we will come close to understanding the most modern codes, without requiring the student to have any special mathematical background.
Error correcting codes (ECC) came to the world as a part of communication systems and nowadays are intensively used in modern communication standards such as the 5G, WiFi, DVB-S2, ATSC, and many more standards. However, communication systems are far from exhausting all applications of ECC. Moreover, a variety of new applications of ECC appear due to the development of computer networks and the Internet. For example, the most promising candidates for post-quantum cryptography systems are code-based cryptosystems. In this course, we discuss some of the modern applications of coding theory.
Final exam
The final exam will be written. The exam consists of five questions and contains 50 points.
Prerequisites
- Linear algebra or equivalent course would be helpful
- Interest in the application of mathematics to computer science and engineering
The course is suitable for all levels: Bachelor, Master and Ph.D. Basic knowledge of linear algebra is assumed (linear transformations, vector spaces, solving systems of linear equations). Beyond that, all necessary mathematical background will be explained in the course. However, knowledge of basics in probability theory, discrete mathematics, and finite fields can be helpful.
Preliminary syllabus
| Lecture 1 | Problem statement; communications model; channel models: BSC and BEC; code and its parameters. |
| Lecture 1 slides. | |
| Addition: Measuring information of discrete ensembles | |
| Lecture 2 | Capacity of BSC and BEC; Shannon's theorems; decoding rules: ML and MAP decoding. |
| Lecture 2 slides. | |
| Presentation | |
| Lecture 3 | Correction and detection of errors; correction of erasures; linear codes; generator matrix; parity-check matrix. |
| Lecture 3 slides. | |
| Presentation | |
| Lecture 4 | Computing minimum distance; code examples; Hamming code; |
| extended Hamming code; syndrome decoding; information set decoding. | |
| Lecture 4 slides. | |
| Presentation | |
| Lecture 5 | Construction of finite fields; extension fields. |
| Lecture 6 | Cyclic codes; BCH codes; Reed-Solomon codes; Vandermonde matrix. |
| Lecture 7 | Bounds on the parameters of the code: Singleton bound; sphere-packing bound; Gilbert-Varshamov bound. |
| Lecture 8 | Decoding of BCH and RS codes; key equation; Peterson-Gorenstein-Zierler |
| algorithm; Berlekamp-Massey algorithm for solving the key equation. | |
| Lecture 9 | Solving key equation by using extended Euclid's algorithm; finding error |
| values by using Forney's algorithm; summary of decoding of GRS codes; example. | |
| Lecture 10 | Long codes from short codes: product codes; concatenated codes; "turbo principle". |
| Lecture 11 | Graph-based codes. Trellis representations |
| Lecture 12 | Decoding of zero-tail terminated (ZT) and tail-bitting (TB) convolutional codes. |
| Lecture 13 | LDPC codes and their generalizations. |
| Lecture 14 | Applications of Coding Theory. |
Literature
- R.M. Roth, Introduction to Coding Theory, Cambridge University Press, 2008 (the course mainly follows parts of this book; available in UT library)
- F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, 1977 (a newly published copy is available in UT library)
- J.H. van Lint, Introduction to Coding Theory, Springer 1999
- Lecture notes of old course editions Lecture notes
Final grade structure
- Homework assignments: 50%
- Final exam: 50%
Final exam will be open-book, i.e. any printed or written materials allowed but no electronic devices.
Previous exams
Final exam December 14th, 2018
Final exam January 24th, 2018:
Final exam December 28th, 2016:
Final exam June 8th, 2015:
Final exam June 10th, 2014:
Last year
You might also be interested in the oldest course edition course page.