Automaty a konvoluční kódy
Průběh přednášky
(2.10.)
Motivace a nástin obsahu přednášky.
1.Od lineárních kódů ke konvolučním a zpět. Lineární blokové kódy. Generující řada posloupnosti a těleso formálních Laurentových řad.
(5.10.)
Racionální funkce, polynomy a formální mocniné řady. Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad.
(9.10.) Vnější stupeň generující matice, Forneyho indexy a stupeň kódu. 2. Konvoluční kódovač. Abstraktní a fyzický konvoluční kódovač:
lineární časově invariantní systémy jako konvoluce s odezvou. Abstraktní kódovač realizující konvoluci s racionální funkcí.
(16.10.) Přechod mezi abstraktním a fyzickým kódovačem. Fyzický kódovač realizující konvoluci s racionální funkcí.
(19.10.) Výpočet fyzického kódovače z abstraktního a naopak. 3. Smithova normální forma. Unimodulární matice.
(23.10.) Existence a jednoznačnost Smithovy normální formy polynomiální matice.
(30.10.) 4. Polynomiální generující matice. Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice.
(6.11.) 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.
(9.11.) 5. Časově invariantní systémy. "Nelineární" definice časově invariantního systému a jeho reprezentace
jako abstraktního konvolučního kódovače. (kapitola nebude zkoušena)
(13.11.) 6. Prostor abstraktních stavů. Prostor abstraktních stavů kódovače a kódu.
Dimenze prostoru abstraktních stavů kódu zdola omezuje dimenzi prostoru abstraktních stavů kódovače a ta je menší nebo rovna
dimenzi stavového prostoru kterékoli realizace kódovače jako abstraktního konvolučního kódovače.
(16.11.) Minimalita kódování: pouze nula je abstraktním stavem i kódovým slovem právě pro kódovače s minimální dimenzí prostoru abstraktních stavů. Věta o stavovém prostoru (dimenze stavového prostoru kódu je rovna stupni kódu).
(20.11.) Kostrukce minimálního abstraktního a fyzického konvolučního kódovače daného konvolučního kódu.
7. Regulární jazyky a konečné automaty. Racionálně uzavřené množiny.
(27.11.) Regulární výrazy, regulární jazyky jsou právě racionální množiny. Konečné automaty, jazyk přijímaný automatem, ekvivalentní konečné automaty.
(30.11.) Epsilon přechody a úplné deterministické konečné automaty. Kleeneova věta: regulární jazyky jsou právě jazyky přijímané konečnými automaty.
(4.12.) 8. Syntaktický monoid a minimální automat. Syntaktická kongruence a syntaktický monoid.
Myhill-Nerodova ekvivalence, konstrukce minimálního automatu.
(7.12.) Minimální automat je úplný deterministiocký automat s miniální množinou stavů. Monoid transformací automatu je izomorfní syntaktickému monoidu regulárního jazyka,
regulární jazyky jsou právě jazyky s konečným syntaktickým monoidem.
(11.12.) 9. Konečné překladače. Graf konečného překladače, abstraktní konvoluční kódovač jako konečný překladač.
Konečné překladače zachovávají regularitu vzoru i obrazu.
(18.12.) 10. Viterbiho dekódovací algoritmus. Mřížoví konečného překladače (a abstraktního konvolučního kódovače), vrstvy mřížoví.
Hledání minimální cesty v mřížoví konečného překladače.
(21.12.) Viterbiho algoritmus. MAP a ML dekódování pro kanál bez paměti.
(8.1.) Viterbiho metrika. Viterbiho algoritmus dává ML dekódování. Chybová událost. Počítání cest v grafu. Odhad pravděpodobnosti dávkové chyby.
[ŠH] většinu témat nalézt v Poznámkách k přednáškám Š. Holuba
[DF] Introduction to convolutional codes. Kapitola ze skript MIT ke kurzu
Principles of Digital Communication II.
[JL] skripta Jyrki Lahtonena,