Automaty a konvoluční kódy - NMMB401

• Anglický název: Automata and Convolutional Codes
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:3/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: https://dl1.cuni.cz/course/view.php?id=10562
• Garant: doc. Mgr. Štěpán Holub, Ph.D.
• Třída: M Mgr. MMIB
• Kategorizace předmětu: Matematika > Algebra
• Záměnnost : NMIB401
• Je záměnnost pro: NMIB401

Anotace

čeština

Kurz je úvodem do konvolučních kódů. Výkladu kódovačů předchází přehled vlastností konečných automatů. Je vyložena algebraická struktura konvolučních kódů, jejich výkon a základní metody dekódování.

Poslední úprava: T_KA (14.05.2013)

angličtina

Course is an introduction into convolutional codes. Description of encoders is facilitated by an overview of finite automata. The algebraic structure of convolutional codes is explored, as well as its performance and basic decoding methods.

Poslední úprava: T_KA (14.05.2013)

Podmínky zakončení předmětu

čeština

Zápočet bude udělen za úspěšné napsání závěrečného testu. Charakter zápočtu umožňuje jeho opakování.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (28.10.2019)

angličtina

The conclusion of the course is by a final test which can be be repeated.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (28.10.2019)

Literatura

čeština

Rolf Johannesson, Kamil Sh. Zigangirov, Fundamentals of Convolutional Coding, Wiley-IEEE Press, 1998

T. Richardson, R. Urbanke, Modern Coding Theory, Cambridge University Press 2008

Poslední úprava: T_KA (14.05.2013)

Požadavky ke zkoušce

čeština

Zkouška sestává s písemné a ústní části. Student nejprve vyřeší písemný test sestávající z pěti úloh z teorie a její aplikace a posléze v rámci ústní části vysvětlí, případně doplní nejasné části vypracovaného testu.

Známka bude určena na základě bodového hodnocení obou částí zkoušky.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (06.10.2017)

angličtina

The course is ended by a written exam followed by an oral exam based on the results of the written one. The resulting grade is a combination of both stages.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (28.10.2019)

Sylabus

čeština

1. Základní vlastnosti konečných automatů

• konečné automaty, regulární výrazy, Kleenova věta.

2. Konvoluční kódy a jejich algebraická struktura

• reprezentace pomocí stavového diagramu a mřížky, vlastnosti

generujících matic a jejich realizace, minimální kódovače.

3. Výkon konvolučních kódů

• volná vzdálenost kódu, odhady chybovosti.

4. Dekódování

• Viterbiho algoritmus, sekvenční dekódování, iterativní dekódování.

Poslední úprava: T_KA (14.05.2013)

angličtina

1. Basic properties of finite automata

• finite automata, regular expressions, Kleene's theorem

2. Convolutional codes and their algebraic structure

• representation by transition diagram and trellis, properties of

generating matrices and their realization, minimal encoders

3. Performance

• free distance of the code, error-probability bounds

4. Decoding

• Viterbi algorithm, sequential decoding, iterative decoding.

Poslední úprava: T_KA (14.05.2013)