Introduction to Coding Theory
Instructor: Vitaly Skachek
Lecture: Tue. 10:15-12:00, J. Liivi 2-206
Practice: Fri. 12:15-14:00, J. Liivi 2-206
Office hours: Fri. 10:15-11:15, J. Liivi 2-216, or by appointment
Contact: Vitaly Skachek
The final exam will take place on Tuesday, June 10th, in room 511. The starting time is 15:00. The length of the exam is three hours.
It is allowed to use any printed or hand-written material during the exam. No electronic devices (computers, tablets, mobile phones) are allowed during the exam.
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.
- 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.
- Lecture 1: communications model; BSC and BEC channels; code and its parameters.
- Lecture 2: ML and nearest-neighbor 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-neighbor decoding; LDPC codes.
R.M. Roth, Introduction to Coding Theory, Cambridge University Press, 2008
F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, 1977
J.H. van Lint, Introduction to Coding Theory, Springer 1999
Final grade structure
- Homeworks: 60%
- Final exam: 40%