Samoopravné kódy LS 2019/20
Rozvrh
Po, 17:20 – 18:55, K1 (nejdřív přednáška, pak 5 minut pauza, pak cvičení)
St, 10:40 – 12:10, K11
Podmínky pro zápočet
Zápočet je za vyřešení aspoň poloviny domácích úkolů. Na každý úkol
budete mít řádný pokus a dva opravné pokusy. Na každý opravný pokus je
týden času navíc.
Domácí úkoly
- Dú 1 termín odevzdání 2. 3. 2020
- Dú 2 termín odevzdání 9. 3. 2020
- Dú 3 termín odevzdání 16. 3. 2020
- Dú 4 termín odevzdání 23. 3. 2020
- Dú 5 termín odevzdání 30. 3. 2020
- Dú 6 termín odevzdání 6. 4. 2020
- Dú 7 termín odevzdání 13. 4. 2020
- Dú 8 termín odevzdání 20. 4. 2020
- Dú 9 termín odevzdání 27. 4. 2020
- Dú 10 termín odevzdání 4. 5. 2020
- Dú 11 termín odevzdání 11. 5. 2020
Zápočet budete potřebovat k přihlášení se na zkoušku
Konzultace
Konzultace po dohodě e-mailem na kazda@karlin.mff.cuni.cz.
Program přednášek (změna programu vyhrazena)
- 17.2.2020: Úvod, co je to kanál a kód, opakovací kód, Hammingův kód
- 19.2.2020: Hammingova vzdálenost, velikost, délka a počet chyb a minimální
vzdálenost kódu
- 24.2.2020: Triviální kódy, funkce A(n,d)
- 26.2.2020: Singletonův odhad, lineární kódy. Systematické
kódy
- 2.3.2020: Dokončení systematických kódů, kódovaní a
dekódování lineárních kódů
- 4.3.2020: Hammingovy kódy, dekódování Hammingových kódů,
Hammingův odhad
- 9.3.2020: Perfektní kódy, Tietäväinenova-van Lintova věta o
perfektních kódech
- 11.3.2020: Binární a ternární Golayovy kódy, MDS (maximum
distance separable) kódy (sekce 4.2, 4.4 a 6.1 učebnice)
- 16.3.2020: Pár slov o G24, věty o MDS kódech (sekce 6.1
učebnice)
- 18.3.2020: Reed-Solomonovy kódy, Reed-Mullerovy kódy
(binární) (sekce 6.2, 6.3, 7.1 a 7.3)
- 23.3.2020: Majoritní dekódování (sekce 7.4)
- 25.3.2020: Cyklické kódy, počítání v okruhu F[x]/(x^n-1)
- 30.3.2020: Generující a paritní
matice cyklických kódů
- 1.4.2020: Cyklotomické polynomy, BCH kódy
- 6.4.2020: Quadratic residue (QR) kódy
- 8.4.2020: Designy, Golayovy kódy jsou jedinečné
13.4.2020: Velikonoční pondělí
- 15.4.2020: Asymptotické odhady
- 20.4.2020: Entropie, Huffmanovo kódování I
- 22.4.2020: Huffmanovo kódování II, entropie jako dolní odhad
očekávané délky kódu, entropie a objem koule
- 27.4.2020: Dokončení důkazu, že entropie je horní odhad
objemu koule; binární symetrický kanál, kapacita kanálu
- 29.4.2020: Kapacita kanálu, Shannonova věta
- 4.5.2020: Dokončení Shannonovy věty, její důsledky
- 6.5.2020: Inverzní Shannonova věta
- 11.5.2020: Velké opakování
- 13.5.2020: Konzultační hodina
Program cvičení
- 17.2.2020: Detekce chyb v
ISBN-10, Hammingův versus opakovací kód, kódování a dekódování s Hammingovými kódy
- 24.2.2020: Parametry kódů, funkce A(n,d)
- 2.3.2020: Lineární kódy, dekódování lineárních kódů
- 9.3.2020: Perfektní kódy, Hammingův odhad
- 16.3.2020: Golayovy kódy, MDS kódy opravené úlohy
- 23.3.2020: Reed-Solomonovy a Reed-Mullerovy kódy úlohy
- 30.3.2020: Cyklické kódy úlohy
- 6.4.2020: BCH, QR kódy
13.4.2020: Velikonoční pondělí
- 20.4.2020: Odhady entropie úlohy
- 27.4.2020: Kódování, kanály, entropie úlohy
- 4.5.2020: Kódy pro k=100, p=0,01 úlohy
- 11.5.2020: Velké opakování
Literatura