Samoopravné kódy
Průběh přednášky
(18.2.)
0.Motivace a cíle přednášky. Co znamená a jak lze matematicky modelovat úkol efektivního a bezztrátového přenosu informace prostřednictvým kanálu ze zdroje k příjemci?
(20.2.)
1.Vzdálenost a nosnost blokového kódu. Blokový kód délky n, příklady (paritní a opakovací kódy),
vzdálenost a váha kódu, detekce a oprava chyby [D, 1.2-1.3], nosnost kódu
Velikost koule v prostoru Fn. Hammingova nerovnost a perfektní kódy [D, 4.1].
(25.2.)
Singletonův odhad [K, 1.7.1-2], pojem MDS-kódu. 2.Dualita a linearita.
Generující a kontrolní matice lineárního kódu.
(27.2.)
Permutačně ekvivalentní kódy, standardní tvar generující matice [D, 1.1], výpočet vzdálenosti lineárního kódu pomocí kontrolní matice [D, 1.4, 2.6].
Cvičení: Hammingův [7,4,3]2-kód.
(4.3.) Bodový součin a duální kódy [D, 2.1-2.5].
Cvičení: Binární a q-ární Hammingovy kódy.
(6.3.)
3.MDS-kódy. Charakterizace lineárních MDS-kódů, vztah dimenze, vzdálenosti a velikosti tělesa lineárních MDS kódů [D, 2.8, 4.5-6].
Příklady netriviálních lineárních MDS-kódů.
(11.3.) 4.Samoduální kódy.
Propíchnutí MDS kódu [D, 3.10, 4.7]. Samoortogonální, samoduální a dvojnásobně sudé kódy [D, 2.9-2.14].
(13.3.) Cvičení: Konstrukce samoduálních kódů. Konstrukce cyklických kódů.
(18.3.) 5.RS a BCH kódy.
Zobecněné Reed-Solomonovy kódy. Generující matice Reed-Solomonových kódů [D, část 5].
Cvičení: Existence binárních lineárních cyklických kódů délky 5 a 7 a lineárních cyklických kódů délky 10. Kontrolní matice GRS-kódu.
(20.3.) Cyklické kódy dané nulovými body polynomů a Reed-Solomonovy kódy [K, 6.2].
Reziduální kódy, konstrukce kódů o ,,zaručené" vzdálenosti (designed distance) [D, 5.2, D.1-3].
(25.3.) 6.Úvod do teorie informace. Diskrétní pravděpodobností prostor [Ko, část 1.].
Cvičení: Konstrukce MDS-kódů, příklady RS a BCH kódů.
Určování parametrů BCH kódů.
(27.3.) Diskrétní náhodná veličina a r-ární entropie náhodné veličiny. Združená entropie a nezávislost náhodných veličin [Ko, 3.1-3.4].
(1.4.)
Podmíněná entropie a vzájemná informace [Ko, 3.5-3.8].
Kódování indormačního zdoje, diskrétní informační kanál bez paměti, vzájemná informace vstupu a výstupu a kapacita kanálu.
(3.4.) Kapacita binárního symetrického kanálu a entropická funkce.
7.Kódování zdroje. Prosté a prefixové kódování informačního zdroje, prefixové kódování je nutně prosté.
(8.4.)
Průměrná délka kódování.
Kritérium existence prefixového kódů s danými délkami kódových slov (Kraftova nerovnost).
a Shanonovo-Fanovo kódování.
Cvičení: Konstrukce Shanonova-Fanova kódování a výpočet průměrné délky slov.
Entropie informačníhp zdroje.
(10.4.) Průměrná délka kódování a entropie informačního zdroje.
První Shannonova věta. Existence optimálního kódování.
Cvičení: Kódování zdroje bloky.
(15.4.)
Konstrukce Huffmanova r-árního kódování.
Cvičení: Binární Huffmanova kódování stejného zdroje s různými délkami slov.
Huffmanovo kódování zdroje s rovnoměrným rozdělením.
(17.4.) 8.Přenos informace binárním symetrickým kanálem.
Blokové kódování a jeho nosnost (informační poměr), přenos kódovaného zdroje informačním kanálem,
metoda nejbližšího slova je ML dekódovací schéma. Maximální a uniformní
pravděpodobnost chyby dekódovacího schématu.
[H], [Š], [D, část Teorie informace]
(24.4.) Slabý zákon velkých čísel. Entropická funkce a odhad velikosti binární koule,
Shannonova hlavní věta teorie informace [H], [Š], [D, část Teorie informace]
(29.4.)
Důkaz Shannonovy věty [H], [Š], [D, část Teorie informace].
(6.5.)
Inverzní Shannonova věta. [H], [Š], [D, část Teorie informace].
9. Binární perfektní kódy. Designy, charakterizace symetrických designů [D, 3.4-6].
(13.5.) Existence a jednoznačnost 2-[11,5,2] a 2-[11,6,3]-designů [D, 3.8-9].
Existence a jednoznačnost lineárního dvojnásobně sudého samoduálního [24,12,8]2 kódu a existence
3-perfektního Golayova [23,12,7]2 kódu.
(15.5.)
Jednoznačnost 3-perfektního Golayova kódu délky 23.
10. Reed-Mullerovy kódy. Konstrukce [K, části 7.1 a 7.2], dimenze a vzdálenost Reed-Mullerových kódů [K části 7.3].
(20.5.)
Dualita, kódování a dekódování Reed-Mullerových kódů [K části 7.4] (teorie nebude zkoušena).
Cvičení: Příklady Reed-Mullerových kódů a jejich dekódování.
[D] - skripta A. Drápala,
[H] - text Š.Holuba
[K] - skripta T. Kaisera
[Ko] - text A.Kozlíka
[Š] - text J.Šťovíčka