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

Sissejuhatus kodeerimisteooriasse 2016/17 sügis

  • Home page
  • Lectures and tutorials
  • Homeworks

Introduction to Coding Theory

Lectures: Vitaly Skachek (office hours: Monday 15:30-17:30, Paabel 224)
Practice: Yauhen Yakimenka
Language of instruction: English

Schedule

Lectures:Wed 10.15-12.00Ülikooli 17 - 219 (Paabel)
Practice:Wed 12.15-14.00Ülikooli 17 - 219 (Paabel)


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 1communications model; BSC and BEC channels; code and its parameters.
Lecture 2ML and nearest-neighbour decoding; examples of simple codes; Shannon theorems.
Lecture 3correction and detection of errors; correction of erasures.
Lecture 4linear codes; generator matrix; parity-check matrix.
Lecture 5construction of finite fields; primitive elements.
Lecture 6parity-check matrix; dual code; Hamming code.
Lecture 7extended Hamming code; concatenated code; syndrome decoding.
Lecture 8Singleton bound; sphere-packing bound; Gilbert-Varshamov bound.
Lecture 9asymptotic bounds; Reed-Solomon codes; Vandermonde matrix.
Lecture 10generalized Reed-Solomon codes; GRS codes as cyclic codes.
Lecture 11decoding of GRS codes; key equation; Peterson-Gorenstein-Zierler decoding algorithm.
Lecture 12solving key equation by using extended Euclid's algorithm.
Lecture 13finding error values by using Forney's algorithm; summary of decoding of GRS codes; example.
Lecture 14NP-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

  • Homeworks: 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 Dec 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 last year 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