Arvutiteaduse instituut
  1. Kursused
  2. 2022/23 sügis
  3. Sissejuhatus kodeerimisteooriasse (MTAT.05.082)
EN
Logi sisse

Sissejuhatus kodeerimisteooriasse 2022/23 sügis

  • Home page
  • Lectures and tutorials
  • Problem solving sessions
  • Homework assignments

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 an 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 5 slides.
 Presentation
Lecture 6 Cyclic codes.
 Lecture 6 slides.
 Presentation
Lecture 7 BCH codes; Reed-Solomon codes; Vandermonde matrix.
 Lecture 7 slides.
 Presentation
Lecture 8 Bounds on the parameters of the code: Singleton bound; sphere-packing bound; Gilbert-Varshamov bound.
 Lecture 8 slides.
 Presentation
Lecture 9 Decoding of BCH and RS codes; Peterson-Gorenstein-Zierler algorithm;
 Berlekamp-Massey algorithm.
 Lecture 9 slides.
 Presentation
Lecture 10Solving key equation by using extended Euclid's algorithm; finding error
 values by using Forney's algorithm; summary of decoding of RS codes; example.
 Lecture 10 slides.
 Presentation
Lecture 11Long codes from short codes: product codes; concatenated codes; "turbo principle".
 Lecture 11 slides.
 Presentation
Lecture 12Graph-based codes. Trellis representations
 Lecture 12 slides.
 Presentation
Lecture 13Convolutional codes and their terminations. Zero-tail terminated (ZT) and tail-biting (TB) convolutional codes.
 Lecture 13 slides.
 Presentation
Lecture 14LDPC codes and their generalizations.
 Lecture 14 slides.
 Presentation
Lecture 15Applications of Coding Theory.
 Lecture 15 slides.

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
  • Fall semester 2018 , solutions.
Final exam January 24th, 2018:
  • Fall semester 2017 , solutions.
Final exam December 28th, 2016:
  • Fall semester 2016 , solutions.
Final exam June 8th, 2015:
  • Spring semester 2015, solutions.
Final exam June 10th, 2014:
  • Spring semester 2014, solutions.

Last year

You might also be interested in the oldest course edition course page.

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo