Kody korekcyjne 2019

Kody korekcyjne 2019–20

Wykład: środa, 10:15-12:00, sala 103

Ćwiczenia: wtorek, 10:15-12:00, sala 4

Polecane książki i notatki

Wykład jest z grubsza na podstawie następujących książek i notatek:

Venkatesan Guruswami, Atri Rudra i Madhu Sudan Essential Coding Theory
Mary Wootters Algebraic Error Correcting Codes
San Ling, Chaoping Xing Coding theory: a first course
Venkatesan Guruswami Introduction to Coding Theory. Teoretycznie pokryte w pełni przez książkę powyżej.
Michael O'Sullivan Coding Theory Opisany ze szczegółami algorytm Berlekamp-Massey: dekodowanie kodów Reeda-Solomona. Niestety trochę mało przystępne.

Lista może ulec rozszerzeniu w czasie wykładu, w szczególności o pojedyncze artykuły.

Oczywiście są też inne książki, niektóre chyba za proste, inne za trudne, a inne o innym modelu.

Claude Berrou Codes and Turbo Codes (trochę o czym innym — model Shannona).
Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, Sebastien Varrette Foundations of Coding: Compression, Encryption, Error Correction (szerszy zakres, mało o interesujących nas tematach)
Raymond Hill A first Course in Coding Theory (łatwe, ale ma ciekawe przykłady z życia)
D. G. Hoffman, K.T. Phelps, D.A. Leonard, C.A. Rodger, J.R. Wall, Charles C. Lindner, David Hoffman Coding Theory: The essentials (w sumie też by mogło być)
J. H. van Lint Introduction to Coding Theory (trudne, ukierunkowane na matematykę)
Rüdiger Urbanke, Thomas Joseph Richardson Modern Coding Theory (trochę o czym innym — model Shannona)

Egzamin

Termin zerowy: 03.02.2020, 12-16 w sali nr 4. Proszę o kontakt w sprawie dokładnego przydziału terminów. (Jeśli nie będzie mnie w sali, to proszę spróbować w pokoju 342).
Termin w sesji i w czasie sesji poprawkowej proszę ustalać indywidualnie.

Na egzaminie obowiązuje materiał z wykładu oraz ważniejsze fakty pokazane na ćwiczeniach (praktycznie zawsze są one też obecne w notatkach).

Będziemy losować trzy pytania. Każde pytanie składa się z trzech części: podstawowej definicji (np. jak definiujemy kody RM), pytania o ważniejsze własności (np. jaka jest odległość kodów RM) i ideę dowodu (np. jak działa algorytm majority logic decoding dla kodów RM i dlaczego.) Uzyskanie oceny pozytywnej wymaga w miarę poprawnego udzielenia odpowiedzi na podstawowe części na wszystkie pytania. Wyższa ocena zależeć będzie od odpowiedzi na część zaawansowaną. Będę brał poprawkę na trudność pytań. W przypadkach granicznych dolosujemy jedno pytanie.

Pół godziny na przygotowanie (można zadawać pytania), mniej więcej pół godziny na odpowiedź.

Moje notatki

Notatki: pierwsza wersja, dość skrótowe.

Listy zadań

Lista 1.
Lista 2.
Lista 3.
Lista 4.
Lista 5.
Lista 6.
Lista 7.
Lista 8.
Lista 9 (zostało zadanie 1).
Lista 10 (zostały zadanie 5).
Lista 11 (zostały zadania 3 (omówienie detali) i 5 (szczegóły albo nowy pomysł; 4 też zostało, ale tam chyba nie da się nic ciekawego pokazać).
Lista 12 (zrobiona).
Lista 13 (zrobiona).
Lista 14 (zostały zadania 1, 2).

Ogłoszenia:

Egzamin w terminie zerowym: 03.02 (poniedziałek) 12:15-16, sala nr 4.