Samoopravné kódy
Průběh přednášky
- týden:
(3.10.)
0.Motivace a cíle přednášky. Jak lze matematicky modelovat úkol bezztrátového přenosu informace?
1.Najít, opravit a neloudat se! Blokový kód délky n,
vzdálenost a váha kódu.
(4.10.)
Koule v prostoru Fn, detekce a oprava chyby. Nosnost kódu, Hammingova nerovnost a perfektní kódy, Singletonův odhad.
[J.Ž, 1.1-5]
- týden:
(10.10.)
Pojem MDS-kódu, příklady (paritní a triviální kódy) [J.Ž, 1.6].
2.S linearitou jde všechno lépe.
Generující a kontrolní matice lineárního kódu. Permutační ekvivalence kódů, standardní tvar generující matice, systematické kódování. [JŽ, 2.1].
(11.10.) Výpočet vzdálenosti lineárního kódu pomocí kontrolní matice. Bodový součin a duální kódy [JŽ, 2.2-5].
Cvičení: Perfektní Hammingův [7,4,3]2-kód.
- týden:
(17.10.) Cvičení: Matice a výpočet vzdálenosti lineárních kódů, duální kódy, obecné q-ární Hammingovy 1-perfektní kódy.
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ů. [JŽ, 3.1-4].
(18.10.) Příklady netriviálních lineárních MDS-kódů. Samoortogonální a samoduální kódy. Propíchnutí MDS kódu [JŽ, 3.5-8].
Cvičení: Samoduální [8,4,4]2-kód a jeho propíchnutí.
- týden:
(24.10.) 4.Rozkládáme 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].
(25.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:
(31.10.) 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Ž, sekce 5].
(1.11.) Cvičení: Rozklady polynomů xn-1. Popis a struktura cyklických kódů.
Konstrukce GRS a RS kódů.
- týden:
(7.11.) 6. GRS kódy a jejich reziduální kódy
Zobecněné Reedovy-Solomonovy kódy. Generující matice Reedových-Solomonových kódů
Konstrukce kontrolní matice GRS-kódu.
Cyklické kódy dané nulovými body polynomů a Reedovy-Solomonovy kódy [JŽ, 6.1-2]
(8.11.) Reziduální kódy, konstrukce kódů o zaručené vzdálenosti (designed distance), BCH a alternantní kódy jako reziduální kódy RS a GRS-kódů [JŽ, 6.3-6].
- týden:
(14.11.) Cvičení: Konstrukce MDS kódů jako GRS kódů. Reziduální kódy RS kódů.
(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, parametry a dualita Reedových-Mullerových kódů [JŽ, 7.1-3]
- týden:
(21.11.) Kódovací a dekódovcí algoritmus pro RM kódy. [JŽ, 7.4-6].
Cvičení: Příklady Reed-Mullerových kódů, jejich kódování a dekódování.
(22.11.) 8. Golayovy perfektní kódy.
Matice incidence systému podmnožin. Symetrické designy a jejich příklady: Fanova rovina a projektivní roviny. Konstrukce 2-[11,5,2]-designů pomocí neorientovaných grafů na pěti vrcholech.
Existence a jednoznačnost 2-[11,6,3]-designů [JŽ, 8.1-3].
- týden:
(28.11.) Váhový polynom 3-perfektního kódu délky 23. Existence 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.4-5].
(29.11.) Jednoznačnost dvojnásobně sudého samoduálního [24,12,8]2 kódu a jeho propíchnutí. Jednoznačnost 3-perfektního Golayova kódu délky 23.
[JŽ, 8.6-9].
- týden:
(5.12.) 9. Kódujme konvolučním kódem!
Těleso formálních Laurentových řad a jeho podobory. Těleso racionálních funkcí a realizovatelné mocninné řady. Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad, jeho generující matice [JŽ, 9.1].
(6.12.)
Existence generující matice konvolučního kódu. Vnější stupeň, Forneyho indexy a stupeň kódu, fyzický konvoluční kódovač jako posloupnost součtů konvolucí, realizace konvoluce s realizovatelnou racionální funkcí obvodem. [JŽ, 9.2-4].
- týden:
(12.12.) Cvičení: Generující matice, její vnější stupeň a fyzický konvoluční kódovač. Realizace fyzického konvoluční kódovače obvodem.
10. Konvoluční kódovač: obvod nebo překladač? Abstraktní konvoluční kódovač jako
lineární časově invariantní systém s odezvou [JŽ, 10.1].
(13.12.) Abstraktní kódovač realizující konvoluci s racionální funkcí. Přechod mezi abstraktním a fyzickým konvolučním kódovačem. Výpočet fyzického kódovače z abstraktního a naopak [JŽ, 10.2-4].
- týden:
(19.12.) Cvičení: Přechod mezi abstraktním a fyzickým konvolučním kódovačem.
11. Polynomiální generující matice. Unimodulární matice a Smithova normální forma polynomiální matice [JŽ, 11.1].
(20.12.) Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice a 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 [JŽ, 11.2-6].
Cvičení:
Výpočet vnitřního a vnějšího stupně jednořádkové generující matice.
- týden:
(2.1.) Cvičení: Čtvercové základní matice. Ověřování redukovanosti a kanoničnosti matice. Nalezení kanonické generující matice a výpočet stupně konvolučního kódu.
12. Viterbiho dekódovací algoritmus. Multigraf abstraktního konvolučního kódovače [JŽ, 12.1].
(3.1.) Mřížoví abstraktního konvolučního kódovače, vrstvy mřížoví, reprezentace kódování prostřednicvím cest mřížoví. Viterbiho algoritmus pro hledání minimální cesty v mřížoví abstraktního konvolučního kódovače [JŽ, 12.2-4].
Cvičení: Výpočet multigrafu a vrstvy mřížoví konvolučního kódovače.
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.