Introduction to Coding Theory
Lectures: Vitaly Skachek
Practice: Javier G. Vidal
Language of instruction: English
Schedule
| Lectures: | Thr 16.15-17.45 | online |
| Practice: | Fri 14.15-15.45 | online |
Final exam
The students will receive the exam forms by email at 16:15 on May 27th. Please return your solutions by 18:15. The exam contains a declaration that you work independently - please sign it or type a confirmation. The exam consists of three questions and contains 120 points (i.e. 20 points are bonus).
You can print out the exam forms, to write your solutions on the paper, and then to scan the solutions and send back to us. If you use this option, please make sure that your solutions are easily visible. Alternatively, you can also type your solutions in a separate DOC, Latex file, or to send us a PDF.
In parallel, we will run a Helpline in Zoom, where one of us will be present during the whole exam. If you have any questions or problems -- the Helpline is the place to contact us. We invite you to join the Helpline before the beginning of the exam. We have sent the Zoom link to the Helpline room by email -- please let us know if you did not receive it.
Announcements
- There are no classes on Friday, April 2nd, due to Good Friday holiday. The practice session will not take place on that day.
- Due to COVID-19 pandemic, the classes will take place in Zoom. The first lecture will take place on Thursday 11th, 2021, at 16:15. If you did not receive a link to the meeting by email, please contact Vitaly.
About the course
- How is a compact disc protected from scratches?
- How polynomials can help to keep a secret?
- How to send more bits over the network link that link can carry?
We will answer these and other questions. The course is dealing with mathematical methods and algorithms for reliable transmission and storage of information. The main object under consideration is an error-correcting code, which is typically a set of vectors equipped with certain properties. The discussed methods make use of linear algebra and finite fields. Only knowledge of linear algebra (introductory course into linear algebra) is assumed. All necessary mathematics will be explained in the course.
Prerequisites
- Linear algebra or equivalent course
- Interest in application of mathematics to computer science and engineering
The course is suitable for all levels: Bachelor, Master and Ph.D. The basic knowledge of linear algebra is assumed (linear transformations, vectors 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 | communications model; BSC and BEC channels; code and its parameters. |
| Lecture 2 | ML and nearest-neighbour decoding; examples of simple codes; Shannon theorems. |
| Lecture 3 | correction and detection of errors; correction of erasures. |
| Lecture 4 | linear codes; generator matrix; parity-check matrix. |
| Lecture 5 | construction of finite fields; primitive elements. |
| Lecture 6 | parity-check matrix; dual code; Hamming code. |
| Lecture 7 | extended Hamming code; concatenated code; syndrome decoding. |
| Lecture 8 | Singleton bound; sphere-packing bound; Gilbert-Varshamov bound. |
| Lecture 9 | asymptotic bounds; Reed-Solomon codes; Vandermonde matrix. |
| Lecture 10 | generalized Reed-Solomon codes; GRS codes as cyclic codes. |
| Lecture 11 | decoding of GRS codes; key equation; Peterson-Gorenstein-Zierler decoding algorithm. |
| Lecture 12 | solving key equation by using extended Euclid's algorithm. |
| Lecture 13 | finding error values by using Forney's algorithm; summary of decoding of GRS codes; example. |
| Lecture 14 | NP-hardness of nearest-neighbour decoding; LDPC codes. |
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 (newly published copy is available in UT library)
- J.H. van Lint, Introduction to Coding Theory, Springer 1999
Final grade structure
- Homework assignments: 60%
- Final exam: 40%
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.