Samoopravné kódy
Průběh přednášky
(19.2.) Blokový [n,k,d]q-kód, příklady (paritní a opakovací kódy),
vzdálenost kódu, detekce a oprava chyby [D, 1.2-1.3],
(20.2.) Singletonův odhad [K, 1.7.1-2]. Lineární kódy, generující a prověrková matice, Hammingův
[7,4,3]2-kód [D, kap.1].
(26.2.) Standardní tvar generující matice, permutačně ekvivalentní kódy [D, 1.1], Prověrková matice
a vzdálenost kódu [D, 2.6],
(27.2.) Cvičení: Dekódování v binárních Hammingových kódech, obecné Hammingovy kódy,
velikost koule v Fn
(5.3.) Hammingova nerovnost a perfektní kódy [D, 4.1], bodový součin a duální kódy [D, 2.1-2.5],
charakterizace MDS-kódů [D, 2.8, 4.5].
(6.3.) Propíchnutí kódu [D, 3.10], odhady dimenze a vzdálenosti MDS kódů [D, 4.6-7],
(12.3.) Samoortogonální, samoduální a dvojnásobně sudé kódy [D, 2.9-2.14], Příklady designů.
(13.3.) 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.
(19.3.) Charakterizace symetrických designů, cykly na pěti prvcích [D, 3.4-6].
(20.3.) Konstrukce a jednoznačnost symetrického 2-[11,5,2] a 2-[11,6,3] designů [D, 3.7-9]
Cvičení: Kombinatorické vlastnosti pěticyklů.
(26.3.) Existence a jednoznačnost lineárního samoduálního [24,12,8]2
a permutační ekvivalence jeho propíchnutí kódu [D, 3.11-12].
(27.3.) Jednoznačnost [24,12,8]2 a perfektního [23,12,7]2 kódů [D, 4.2-4].
Cvičení: Váhový polynom [23,12,7]2 kódu.
(2.4.) Cyklické kódy, jejich popis jako ideálů okruhu F[x]n [D, C.1-2.].
(3.4.) Generující a kontrolní matice cyklického kódu, rozklad polynomu xn-1 [D, C.3-6.],
Cvičení: Cyklotomické polynomy.
(9.4.) Cvičení: Ireducibilní rozklad polynomů x7-1 a x14-1 v oboru Z2[x]
a konstrukce lineárních cyklických [7,3]2 a [7,4]2-kódů. Počty lineárních cyklických kódů délky 12
a 60 nad tělesem Z5.
Uzavřenost lineárních cyklických kódů na součty a průniky, permutačně ekvivalentní lineární cyklické kódy [D, C.7-9.].
(10.4.) Maximální a minimální cyklické kódy, rozklad F[x]n na direktní sumu minimálních
cyklický kódů [D, C.11-14.]. Konstrukce lineárního MDS [n,k,n-k+1]q pro n/(q-1) [K, 6.2].
(16.4.) Reed Solomonovy [K, 6.2] a zobecněné Reed Solomonovy kódy [D, část 5].
(17.4.) Konstrukce BCH - kódů o ,, zaručené" vzdálenosti [D, 5.2, D.1-3]. Kvadratická rezidua.
Cvičení: Příklady BCH - kódů.
(23.4.) q.r.- kódy a rozšířené q.r.- kódy [D, část D].
(24.4.) Vzdálenost q.r.- kódů [D, část D, K část 9.5]. Reed-Mullerovy kódy [K, části 7.1 a 7.2].
Cvičení: Příklady q.r.- kódů: Hammingův [7,4,3]2-kód, Golayův [23,12,7]2-kód.
(30.4.) Dimenze a vzdálenost Reed-Mullerových kódů, kódování a dekódování [K části 7.3 a 7.4].
(7.5.) Entropická funkce a odhad velikosti binární koule [D, část Asymptotické odhady 1.1 - 1.4].
Teorie informace, spolehlivost dekódování, formulace Shannonovy věty, Zákon velkých čísel [D, část Teorie informace].
(15.5.) Inverzní Shannonova věta, [D, část Teorie informace], [K, kapitola 11].
(21.5.) Důkaz Shannonovy věty. [elegantní důkaz Š.Holuba].
(22.5.) Hadamardovy matice a kódy. Plotkinův odhad [D, část 7], [K, část 10.3].
Cvičení: Hadamardovy matice a designy.
[D] - skripta A. Drápala,
[K] - skripta T. Kaisera