Error-correcting Codes - NMMB337

• Title: Samoopravné kódy
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• Semester: winter
• E-Credits: 6
• Hours per week, examination: winter s.:3/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Additional information: https://www.karlin.mff.cuni.cz/~stanovsk/vyuka/kody.htm
• Guarantor: doc. RNDr. David Stanovský, Ph.D.
• Teacher(s): doc. RNDr. David Stanovský, Ph.D.
• Class: M Bc. MMIB; M Bc. MMIB > Povinné; M Bc. MMIT; M Bc. MMIT > Povinné; M Bc. OM; M Bc. OM > Povinně volitelné
• Classification: Mathematics > Algebra
• Incompatibility : NMIB004
• Interchangeability : NMIB004

Annotation

English

Required course for bachelor's program in Information security. An introduction to finite fileds, basic linear block codes, convolutional codes, their properties, applications and methods of decoding.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (29.04.2021)

Czech

Povinně volitelný předmět bakalářského oboru MIT. Přednáška podává přehled o konečných tělesech, základních používaných lineárních blokovýcha konvolučních kódech a jejich vlastnostech, aplikacích a metodách dekódování.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (29.04.2021)

Course completion requirements

Zápočet bude za domácí úlohy. Bude šest sérií (ne nutně stejně bodovaných). Je třeba mít alepoň třetinu bodů z alespoň pěti sérií, a dohromady alespoň polovinu bodů. Odevzdávání v systému Owl, přihlašovací instrukce přijdou zapsaným studentům emailem. Charakter zápočtu neumožňuje jeho opakování v případě neúspěchu.

Zkouška bude mít písemnou a ústní část. V písemné části (asi 90 min.) budou početní úlohy, znění definic, vět a jednoduché důkazy, v ústní části bude těžší důkaz nebo vyložení nějakého souvislého tématu. Bodování TBA.

Last update: Stanovský David, doc. RNDr., Ph.D. (10.10.2024)

Literature

English

lecture notes by Jan Žemlička: https://www.karlin.mff.cuni.cz/~zemlicka/23-24/SoKn.pdf

Cameron, van Lint: Designs, graphs, codes and their links, Cambridge Univ. Press 1991.

MacWilliams, Sloane: The theory of error-correcting codes, North-Holland 1977.

Roman, S.: Coding and Information Theory, Springer, 1992.

Last update: Stanovský David, doc. RNDr., Ph.D. (10.10.2024)

Czech

skripta Jana Žemličky: https://www.karlin.mff.cuni.cz/~zemlicka/23-24/SoKn.pdf

Cameron, van Lint: Designs, graphs, codes and their links, Cambridge Univ. Press 1991.

MacWilliams, Sloane: The theory of error-correcting codes, North-Holland 1977.

Roman, S.: Coding and Information Theory, Springer, 1992.

Last update: Stanovský David, doc. RNDr., Ph.D. (10.10.2024)

Requirements to the exam

Požadavky u zkoušky korespondují se sylabem přednášky a budou uplatňovány v rozsahu, ve kterém bylo téma prezentováno na přednášce.

Last update: Stanovský David, doc. RNDr., Ph.D. (10.10.2024)

Syllabus

English

Parameters of codes. Linear codes.

Polynomials over finite fields and cyclic codes.

Reed-Solomon, Reed-Muller codes. Residue codes.

Decoding - general and algebraic aspect. Connections with designs.

Golay codes and designs.

Convolutional codes and convolutional encoders.

Viterbi decoding algorithm.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (06.11.2022)

Czech

Parametry kódů. Lineární kódy.

Polynomy nad konečnými tělesy a cyklické kódy.

Reedovy-Solomonovy a Reed-Mullerovy kódy. Reziduální kódy.

Golayovy kódy, jejich souvislost s designy.

Konvoluční kódy a konvoluční kódovače.

Viterbiho dekódování konvolučního kódu.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (06.11.2022)