Samoopravné kódy
Průběh přednášky
- týden:
(4.10.)
0.Motivace a cíle přednášky. Jak lze matematicky modelovat úkol bezztrátového přenosu informace?
1.Vzdálenost a nosnost blokového kódu. Blokový kód délky n,
vzdálenost a váha kódu, koule v prostoru Fn.
(5.10.)
Detekce a oprava chyby. Nosnost kódu, Hammingova nerovnost a perfektní kódy, Singletonův odhad, pojem MDS-kódu, příklady (paritní a triviální kódy). Permutační ekvivalence kódů.
[J.Ž, 1]
- týden:
(11.10.)
2.Lineární kódy.
Generující a kontrolní matice lineárního kódu. standardní tvar generující matice , výpočet vzdálenosti lineárního kódu pomocí kontrolní matice.
(12.10.) Bodový součin a duální kódy [JŽ, 2].
Cvičení: Matice a výpočet vzdálenosti lineárních kódů, duální kódy. Binární Hammingovy kódy.
- týden:
(18.10.)
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ů. Příklady netriviálních lineárních MDS-kódů [JŽ, 3.1-6].
(19.10.) Samoortogonální a samoduální kódy. Propíchnutí MDS kódu [JŽ, 3.7-9.].
Cvičení: q-ární Hammingovy kódy, konstrukce samoduálních kódů.
- týden:
(25.10.) 4.Polynomy nad konečnými tělesy.
Opakování: popis struktury konečných těles.
Frobeniův automorfismus a struktura podtěles konečných těles, iredcubilní polynomy nad konečným tělesem F jako faktory polynomu xu-x pro u=|F|n [JŽ, 4.1-5].
(26.10.) Grupa kořenů polynomu xn-1, výpočet a ireducibilní faktory n-tého cykotomického polynomu [JŽ, 4.6-8].
Cvičení: Ireducibilní a cykotomické polynomy.
- týden:
(1.11.) 5.Cyklické kódy. Popis lineárních cyklických kódů jako ideálů okruhu F[x]/(xn-1). Generující a kontrolní matice lineárního cyklického kódu [JŽ, 5].
(2.11.) Cvičení: Cyklické kódy. Konstrukce GRS a RS kódů.
- týden:
(8.11.) 6. GRS kódy a jejich reziduální kódy
Zobecněné Reed-Solomonovy kódy. Generující matice Reed-Solomonových kódů
Konstrukce kontrolní matice GRS-kódu.
Cyklické kódy dané nulovými body polynomů a Reed-Solomonovy kódy [JŽ, 6.1-3]
(9.11.) Reziduální kódy, konstrukce kódů o zaručené vzdálenosti (designed distance), BCH a alternantní kódy [JŽ, 6.3-7].
Cvičení: Konstrukce BCH kódů.
- týden:
(15.11.)
7. Reedovy-Mullerovy kódy. Konstrukce Reedových-Mullerových kódů. Boolevy funkce, Booleovy polynomy a binární RM-kódy. Vzdálenost Reed-Mullerových kódů [JŽ, 7.1].
(16.5.) Parametry a dualita Reed-Mullerových kódů. Kódování a dekódovcí algoritmus RM kódů.
[JŽ, 7.2-6].
Cvičení: Příklady Reed-Mullerových kódů a jejich dekódování.
- týden:
(22.11.) 8. Golayovy perfektní kódy.
Matice incidence systému podmnožin. Symetrické designy, konstrukce 2-[11,5,2]-desgnů pomocí neorientovaných grafů na pěti vrcholech [JŽ, 8.1-2].
(23.11.)
Existence a jednoznačnost 2-[11,6,3]-designů.
Existence a jednoznačnost lineárního dvojnásobně sudého samoduálního [24,12,8]2 kódu a jeho vztah k 3-perfektnímu Golayovu [23,12,7]2 kódu [JŽ, 8.3-6].
- týden:
(29.11.) 9. Konvoluční kódy a kódovače.
Těleso formálních Laurentových řad a jeho podobory. Těleso racionálních funkcí a realizovatelné mocninné řady.
(30.11.)
Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad, generující matice a její
vnější stupeň, Forneyho indexy a stupeň kódu. Fyzický konvoluční kódovač.
- týden:
(6.12.) Abstraktní konvoluční kódovač:
lineární časově invariantní systém s odezvou. Abstraktní kódovač realizující konvoluci s racionální funkcí.
(7.12.) Přechod mezi abstraktním a fyzickým konvolučním kódovačem. Fyzický kódovač realizující konvoluci s racionální funkcí. Výpočet fyzického kódovače z abstraktního a naopak.
Cvičení: Generující matice a fyzickým konvoluční kódovač.
- týden:
(13.12.) 10. Polynomiální generující matice. Unimodulární matice a Smithova normální forma polynomiální matice. Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice.
(14.12.) Cvičení: Přechod mezi abstraktním a fyzickým konvolučním kódovačem.
Výpočet vnitřního a vnějšího stupně generující matice. Unimodulární a základní matice.
- týden:
(20.12.) Ekvivalentní podmínky popisující redukované matice. Kanonické (tj. základní a redukované) jsou právě polynomiální generující matice konvolučního kódu s minimálním vnějším
stupněm.
(21.12.) Cvičení: Redukované a kanonické matice. Nalezení kanonické generující matice a výpočet stupně konvolučního kódu.
- týden:
(3.1.)
11. Viterbiho dekódovací algoritmus. Multigraf a mřížoví abstraktního konvolučního kódovače, vrstvy mřížoví. Reprezentace kódování prostřednicvím cest mřížoví.
Cvičení: Výpočet multigrafu a vrstvy mřížoví konvolučního kódovače.
(4.1.) Viterbiho algoritmus pro hledání minimální cesty v mřížoví abstraktního konvolučního kódovače.
Cvičení: Dékódování chybové posloupnosti slov pomocí Viterbiho algoritmu.
Doporučená četba.
[JŽ] - Text k letošní přednášce
[D] - skripta A. Drápala,
[K] - skripta T. Kaisera
[ŠH] Poznámky Š. Holuba o konvolučních kódech
[JL] skripta o konvolučních kódech Jyrki Lahtonena,
[BT] - skripta L.Barta a J. Tůmy,
[Z] - můj text o lineárních rekurentních posloupnostech
[DF] Introduction to convolutional codes. Kapitola ze skript MIT ke kurzu
Principles of Digital Communication II.