Samoopravné kódy

Průběh přednášky

   (21.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? 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]. Velikost koule v prostoru Fⁿ.

   (28.2.) Hammingova nerovnost a perfektní kódy [D, 4.1], Singletonův odhad [K, 1.7.1-2]. Nosnost kódu, pojem MDS-kódu. (Cyklický) Hammingův [7,4,3]₂-kód [D, kap.1]. Permutačně ekvivalentní kódy. 2.Lineárrní kódy. Lineární kódy, generující a kontrolní matice, výpočet vzdálenosti lineárního kódu pomocí kontrolní matice [D, 1.4, 2.6], standardní tvar generující matice [D, 1.1]

   (7.3.) 3.MDS-kódy a dualita. Bodový součin a duální kódy [D, 2.1-2.5], Charakterizace MDS-kódů, Odhady dimenze a vzdálenosti MDS kódů [D, 2.8, 4.5-6].
Cvičení: Binární Hammingovy kódy. Obecné q-ární Hammingovy kódy.

   (14.3.) Příklady netriviálních lineárních MDS-kódů. 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]. 4.RS a BCH kódy. Zobecněné Reed-Solomonovy kódy. Generující matice Reed-Solomonových kódů [D, část 5]. Cyklické kódy dané nulovými body polynomů a Reed-Solomonovy kódy [K, 6.2].
Cvičení: Konstrukce kontrolní matice GRS kódu s danou generující maticí.

   (21.3.) Reziduální kódy, konstrukce BCH - kódů o ,, zaručené" vzdálenosti (designed distance) [D, 5.2, D.1-3].
Cvičení: Konstrukce MDS-kódů, příklady RS a BCH kódů. Určování parametrů BCH kódů.

   (28.3.) 5.Úvod do teorie informace. Diskrétní pravděpodobností prostor, r-ární entropie náhodné veličiny. Združená entropie a nezávislost náhodných veličin. Prosté a prefixové kódování informačního zdroje, příklady, prefixové kódování je nutně prosté.

   (4.4.) Kritérium existence prefixového kódů s danými délkami kódových slov (Kraftova nerovnost) a Shanonovo-Fanovo kódování. Průměrná délka slova a entropie informačního zdroje. První Shannonova věta. Optimální kódování a Huffmanovo kódování.
Cvičení: Konstrukce prefixových kódování a průměrné délky slov.

   (11.4.) Huffmanovo kódování. Podmíněná entropie, entropie informačního kanálu. Vzájemná informace a kapacita kanálu. Binární symetrický kanál.
Cvičení: Konstrukce Shanonova-Fanovo a Huffmanova kódování. Výpočet proměrné délky kódování.

   (18.4.) Entropická funkce a odhad velikosti binární koule, spolehlivost dekódování, [D, část Teorie informace]. Zákon velkých čísel, Shannonova hlavní věta teorie informace [H], [Š], [D, část Teorie informace]

   (25.4.) Důkaz hlavní věta teorie informace. Informační poměr a kódování neuniformního zdroje. Inverzní Shannonova věta. [ text Š.Holuba].

   (2.5.) Asymtotické odhady Gilbert-Varšamova nerovnost, asymptotický Gilbert-Varšamův odhad, asymptotický Singletonův odhad [D, 7.4 a část Asymtotické odhady]. 6.Designy. Nutné podmínky pro parametry 2-(n,k,l)-designů, Fanova rovina matice incidence [D, 3.1-3],
Cvičení: 2-(2^l-1,3,1)-designy indukované binárními Hammingovými kódy, designy indukované perfektními binárními kódy, designy indukované projektivními rovinami.

   (9.5.) Charakterizace symetrických designů [D, 3.4-6]. Kombinatorické vlastnosti pěticyklů a konstrukce 2-[11,5,2] designu [D, 3.7]. Korespondence a jednoznačnost 2-[11,5,2] a 2-[11,6,3]-designů [D, 3.8-9], Jednoznačnost binárního Golayova kódu [ 4.2-4]. 7.Binární perfektní kódy. Existence a jednoznačnost lineárního samoduálního [24,12,8]₂ kódu a 3-perfektní Golayův [23,12,7]₂ kód jako jeho propíchnutí [D, 3.11-12].

   (16.5.) 8. 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]. Dualita, kódování a dekódování Reed-Mullerových kódů [K části 7.4].

[D] - skripta A. Drápala,
[K] - skripta T. Kaisera
[H] - text Š.Holuba
[Š] - text J.Šťovíčka