Samoopravné kódy
Průběh přednášky
(17.2.) 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], Singletonův odhad [K, 1.7.1-2], definice MDS-kódů,
nosnost kódu.
Cvičení: Velikost koule v prostoru Fn.
(24.2.) Hammingova nerovnost a perfektní kódy [D, 4.1].
Lineární kódy, generující a kontrolní matice, vzdálenost lineárního kódu [D, 1.4, 2.6]
Permutačně ekvivalentní kódy, standardní tvar generující matice [D, 1.1].
Cvičení: Opakování: generující a kontrolní matice cyklického kódu,
příklady 1-perfektních kódů: (cyklický) Hammingův [7,4,3]2-kód [D, kap.1],
dekódování v binárních Hammingových kódech.
(3.3.) 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í: Popis binárních lineárních MDS-kódů, 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].
(10.3.) 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], Samoortogonální, samoduální a dvojnásobně sudé kódy [D, 2.9-2.14],
Cvičení: Cykličnost Reed-Solomonových kódů. Příklady kódů vzdálenosti d, jejichž propíchnutí má vzdálenost větší než d.
(17.3.) Teorie informace, spolehlivost dekódování, formulace Shannonových vět.
Zákon velkých čísel [D, část Teorie informace]. Entropická funkce a odhad velikosti binární koule
[D, část Asymptotické odhady 1.1 - 1.4]. Důkaz ,,přímé" Shannonovy věty
[texty Š.Holuba a
J.Šťovíčka]
(24.3.) Inverzní Shannonova věta, [texty Š.Holuba a
J.Šťovíčka], [D, část Teorie informace] nebo [K, kapitola 11].
Gilbert-Varšamonova nerovnost, asymptotický Gilbert-Varšamonův odhad, asymptotický Hammingův odhoad
[D, 7.4 a část Asymtotické odhady 1.6 - 1.8].
(31.3.) Designy. Fanova rovina, nutné podmínky pro parametry 2-(n,k,l)-designů [D, 3.1-3],
matice incidence.
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 a projektivními prostory. Popis 2-(n,3,1)-designů.
(7.4.) Charakterizace symetrických designů, cykly na pěti prvcích [D, 3.4-6].Existence a jednoznačnost
2-[11,5,2] a 2-[11,6,3] designů [D, 3.7-9]. Existence lineárního samoduálního [24,12,8]2 kódu [D, 3.11].
Cvičení: Kombinatorické vlastnosti pěticyklů, konstrukce 2-[11,5,2] a 2-[11,6,3] designů.
(14.4.) Existence a jednoznačnost [24,12,8]2 a perfektního Golayova [23,12,7]2 kódů [D, 3.12, 4.2-4].
(21.4.) Hadamardovy matice, jejich konstrukce a souvislost s designy. Hadamardovy kódy,
Plotkinův odhad [D, část 7], [K, část 10.3].
Cvičení: Paleyovy matice a paleyova konstrukce Hadamardových matic. Konstrukce perfektního Golayova [11,6,5]3 kódu.
(28.4.) Reed-Mullerovy kódy [K, části 7.1 a 7.2]. Dimenze a vzdálenost Reed-Mullerových kódů, dualita,
kódování a dekódování [K části 7.3 a 7.4].
Cvičení: Konstrukce a vlastnosti Reed-Mullerova kódu R(3,1) a R(3,2).
(5.5.) Reziduální kódy. Konstrukce BCH - kódů o ,, zaručené" vzdálenosti (designed distance) [D, 5.2, D.1-3].
Cvičení: Příklady reziduálních kódů. Konstrukce BCH - kódů, jejich dimenze.
(12.5.) Kvadratická rezidua, q.r.- kódy a rozšířené q.r.- kódy [D, část D]. Vzdálenost q.r.- kódů [D, část D, K část 9.5].
Cvičení: Příklady q.r.- kódů: Hammingův [7,4,3]2-kód, Golayův [23,12,7]2-kód.
[D] - skripta A. Drápala,
[K] - skripta T. Kaisera