Samoopravné kódy
Průběh přednášky
(23.2.) 1.Vzdálenost a nosnost kódu. Blokový kód délky n, příklady (paritní a opakovací kódy),
vzdálenost kódu, detekce a oprava chyby [D, 1.2-1.3], Hammingova nerovnost a perfektní kódy [D, 4.1], Singletonův odhad [K, 1.7.1-2], definice MDS-kódů.
Nosnost kódu.
Cvičení: Velikost koule v prostoru Fn.
(1.3.) 2.Vzdálenost, dualita a linearita.
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]
Permutačně ekvivalentní kódy, standardní tvar generující matice [D, 1.1], (cyklický) Hammingův [7,4,3]2-kód [D, kap.1].
Cvičení: Binární 1-perfektní Hammingovy kódy.
(8.3.) Bodový součin a duální kódy [D, 2.1-2.5],
3.MDS-kódy. Charakterizace MDS-kódů, Odhady dimenze a vzdálenosti MDS kódů [D, 2.8, 4.5-6].
Cvičení: Dekódování v binárních Hammingových kódech. Obecné q-ární Hammingovy kódy.
(15.3.) Příklady netriviálních lineárních MDS-kódů:
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].
Propíchnutí MDS kódu [D, 3.10, 4.7],
Cvičení:
Příklady kódů vzdálenosti d, jejichž propíchnutí má vzdálenost větší než d.
Konstrukce lineárních MDS-kódů.
(22.3.) Samoortogonální, samoduální a dvojnásobně sudé kódy [D, 2.9-2.14],
4.Úvod do teorie informace. Entropie a entropická funkce, spolehlivost dekódování, formulace Shannonových vět [D, část Teorie informace].
Cvičení: Počet lineárních kódů dané délky.
(29.3.)
Zákon velkých čísel, entropická funkce a odhad velikosti binární koule
[D, část Asymptotické odhady 1.1 - 1.4]. Důkaz Shannonových vět [H], [Š], [D, část Teorie informace] nebo [K, kapitola 11].
(5.4.)
Gilbert-Varšamonova nerovnost, asymptotický Gilbert-Varšamonův odhad, asymptotický Hammingův odhad
[D, 7.4 a část Asymtotické odhady 1.6 - 1.8].
5.Designy. Fanova rovina, nutné podmínky pro parametry 2-(n,k,l)-designů [D, 3.1-3],
Cvičení: 2-(2l-1,3,1)-designy indukované binárními Hammingovými kódy, designy indukované
perfektními binárními kódy.
(12.4.) Matice incidence, charakterizace symetrických designů [D, 3.4-6].
Kombinatorické vlastnosti pěticyklů a konstrukce 2-[11,5,2] designu [D, 3.7].
Cvičení: Designy indukované perfektními binárními kódy, designy indukované projektivními rovinami, nutné podmínky
pro parametry 2-(n,k,l)-designů. Permutace na S5 a neoprientované grafy na pěti vrcholech.
(19.4.)
Korespondence a jednoznačnost 2-[11,5,2] a 2-[11,6,3]-designů [D, 3.8-9].
6.Binární perfektní kódy.
Existence a jednoznačnost lineárního samoduálního [24,12,8]2 kódu
a 3-perfektní Golayův [23,12,7]2 kód jako jeho propíchnutí [D, 3.11-12].
(26.4.) Jednoznačnost binárního Golayova kódu [ 4.2-4]. 7.Hadamardovy matice a kódy. Hadamardovy matice,
jejich konstrukce a souvislost s designy. Hadamardovy kódy, Plotkinův odhad [D, část 7], [K, část 10.3].
Cvičení: Hadamardovy matice odvozené z 2-(11,5,2)-designu, vlastnosti Paleyových matic.
(3.5.) 8. Kódy založené na kvadratických reziduích . Kvadratické zbytky, q.r.- kódy a rozšířené q.r.- kódy [D, část D].
Cvičení: Paleyova konstrukce Hadamardových matic. Konstrukce perfektního Golayova [11,6,5]3 kódu.
(10.5.) Vzdálenost q.r.- kódů [D, část D, K část 9.5].
9. 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].
Cvičení: Příklady q.r.- kódů: Hammingův [7,4,3]2-kód, Golayův [23,12,7]2-kód.
(17.5.) Dualita, kódování a dekódování Reed-Mullerových kódů [K části 7.4]. 10. Reziduální kódy. Koncept reziduální kódů. Konstrukce BCH - kódů o ,, zaručené" vzdálenosti (designed distance) [D, 5.2, D.1-3].
Cvičení: Konstrukce a vlastnosti Reed-Mullerova kódu R(3,1). Příklady reziduálních kódů. Konstrukce BCH - kódů, jejich dimenze.
[D] - skripta A. Drápala,
[K] - skripta T. Kaisera
[H] - text Š.Holuba
[Š] - text J.Šťovíčka