**Description**.
In general, error correcting codes aim to ensure that errors occurring during the writing, reading or transmission of information, can be removed, or at least detected.
At one end of the spectrum of employed methods are simple codes that add a parity bit (which only allows validation, whether a single error has occurred),
at the other end there are the Reed-Solomon codes, which allow the recovery of the original information even when a constant fraction of the codewords is corrupted.
As errors in transmissions are ever-present, correction codes are widely used, from file storage systems through barcodes, video data recording and cellular network transmission.
In this lecture, classical (and sometimes a little more modern) results on correction codes will be presented:
- Upper and Lower bounds: combinatorial results that impose bounds on the possible parameters of the codes, and unconstructive methods that allow getting arbitrarily close to these bounds.
- Reed-Solomon codes, arguably the best known and most widely used error correction codes, which allow correction of a fixed fraction of errors. Their decoding algorithms are highly non-trivial (Berlekamp-Welch algorithm, Berlekamp-Massey and derivatives).
- Reed-Muller codes and their decoding (binary and general case).
- BCH codes: depending on the viewpoint: generalisation or special case of Reed-Solomon codes.
- Concatenated codes: which allow combining constructive and unconstructive methods in a single code. The decoding algorithm is one of the first non-trivial results concerning derandomisation in computer science.
- List decoding: a generalisation of classical decoding, in which instead of a single word we get a list of possible words. A tool widely used today in computational complexity.
- Local correction codes: a weakened version of correction codes in which all decisions are made based on a fixed number of message bits.
- Shannon model and the polar codes: most of the codes described above work in the pessimistic scenario. In Shannon model we assume that the errors occur randomly and we want to recover the original message with high probability. Polar codes are a simple, modern construction, which achieves optimal upper bounds.
**Lecture plan.**
1. Theory of error correction.
2. Linear codes.
3. Lower and upper bounds.
4. Reed-Solomon codes and their decoding.
5. Reed-Muller codes and their decoding.
6. BCH codes.
7. Cyclic codes.
8. Concatenated codes.
9. List decoding: bounds and algorithms.
10. Locally correctable codes.
11. Error correction codes for erasures.
12. Shannon model and polar codes.
**Audience**.
The course is mainly aimed at a wider audience of final year undergraduate or postgraduate students.
**Requirements**.
Students are expected to have previously passed *Algebra* and *Algorithms and Data Structures*.
More advanced topics in algebra (field extensions, minimal polynomials, Fourier transform for arbitrarily fields, …) will be introduced and explained during the lecture, but algebraic skills are required.
**Opis**
W ogólnym zarysie, kodowanie korekcyjne ma zagwarantować możliwość usunięcia, a przynajmniej wykrycia, błędów powstałych w czasie zapisu, odczytu czy przesyłania informacji.
Na jednym końcu skali używanych metod znajdują się proste kody dodające bit parzystości (które umożliwiają jedynie sprawdzenie poprawności),
na drugim są kody Reeda-Solomona, umożliwiające odzyskanie oryginalnej informacji nawet w przypadku przekłamań stałej frakcji słów kodowych.
Jako że przekłamania transmisji są normą, kody korekcyjne są powszechnie stosowane, od
systemów przechowywania plików przechodząc przez kody kreskowe, zapis danych wideo a kończąc na transmisji sieci komórkowych.
W czasie wykładu w przedstawione zostaną klasyczne (i czasami trochę nowsze) wyniki dotyczące kodów korekcyjnych:
- Ograniczenie górne i dolne: wyniki kombinatoryczne, które nakładają ograniczenia na możliwe parametry kodów oraz niekonstrukcyjne metody pozwalające dowolnie blisko zbliżyć się do tych granic.
- Kody Reeda-Solomona, przypuszczalnie najbardziej znane i najczęściej stosowane kody korekcyjne, pozwalające na korekcję stałej frakcji błędów. Ich algorytmy dekodowanie są wysoce nietrywialne (algorytm Berlekamp–Welch, Berlekamp-Massey i pochodne).
- Kody Reeda-Mullera i ich dekodowanie (przypadek binarny i ogólny).
- Kody BCH: w zależności od punktu widzenia: uogólnienie lub przypadek szczególny kodów Reeda-Solomona.
- Kody skonkatenowane: które pozwalają na połączenie wyników konstrukcyjnych i niekonstrukcyjnych w jednym kodzie. Algorytm dekodujący jest jednym z pierwszych nietrywialnych wyników dotyczących derandomizacji w informatyce.
- Dekodowanie do list: uogólnienie klasycznego dekodowania, w którym zamiast jednego słowa otrzymujemy listę możliwych słów. Narzędzie powszechnie wykorzystywane obecnie w złożoności obliczeniowej.
- Lokalne kody korekcyjne: osłabiona wersja kodów korekcyjnych, w których wszelkie decyzje podejmowane są na podstawie stałej liczby bitów wiadomości.
- Model Shannona i kody polarne (polaryzujące): większość opisanych powyżej kodów działa w modelu pesymistycznym. W modelu Shannona zakładamy, że błędy pojawiają się losowo i chcemy odzyskać oryginalną wiadomość z dużym prawdopodobieństwem. Kody polarne to prosta, współczesna konstrukcja, która osiąga optymalne ograniczenia górne.
**Plan wykładu.**
1. Kodowanie i korekcja błędów: teoria.
2. Kody liniowe.
3. Granice dolne i górne kodowania.
4. Kody Reeda-Solomona i ich dekodowanie.
5. Kody Reeda-Mullera i ich dekodowanie.
6. Kody BCH.
7. Kody cykliczne.
8. Kody skonkatenowane.
9. Dekodowanie do list: ograniczenia i algorytmy.
10. Lokalne kody korekcyjne.
11. Kody korekcyjne z utratą bitów.
12. Model Shannona i kody polarne.
**Słuchacze**
Przedmiot kierowany jest głównie do szerszego grona słuchaczy ostatniego roku studiów I stopnia lub studiów II stopnia.
**Wymagania**
Od słuchaczy oczekuję wcześniejszego zaliczenia *Algebry* oraz *Algorytmów i struktur danych*.
Bardziej zaawansowane zagadnienia algebraiczne (rozszerzenia ciał, wielomiany minimalne, transformata Fouriera dla dowolnych ciał, …) będą wprowadzone i wyjaśnione podczas wykładu, ale wymagane jest obycie algebraiczne.
