Název: Řetězové zlomky v teorii kódů
Překlad názvu: Continued fractions in coding theory
Autoři: Fišer, Jan ; Šťovíček, Jan (vedoucí práce) ; Holub, Štěpán (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2014
Jazyk: cze
Abstrakt: [cze] [eng]
Tato práce nás nejprve seznamuje s Reed-Solomonovy kódy, způsoby jejich konstrukce a kódování. Zároveň uvádíme důkazy jejich nejvýznamnějších vlastností s příslušným teoretickým základem. Ve druhé kapitole zavádíme pojem řetězových zlomků nad tělesem a zkoumáme jejich strukturu. Ap- likací provedených obecných pozorování na konkrétní případ Laurentových formálních řad se pak dostáváme k účinnému dekódovacímu algoritmu Reed- Solomonových kódů. Bez kompletních důkazů uvádíme ještě další dva dekó- dovací algoritmy, které jsou také založeny na řešení klíčové rovnice, a to Berlekampův-Masseyův a Eukleidův. V závěru práce ukazujeme ekvivalenci těchto tří algoritmů. The first part of the thesis acquaints us with the Reed-Solomon codes, methods of their construction and encoding. At the same time we provide the evi- dence of their most important properties including the relevant theoretical basis. In the second chapter we introduce the theory of continued fractions over a field and examine their structure. Applying the executed general ob- servations on the specific case of the formal Laurent series we get to efficient Reed-Solomon decoding algorithm. Without complete proofs we also men- tion other two decoding algorithms that are based on solving the key equation as well, namely Berlekamp-Massey and Euclidean algorithm. In the end we show the equivalence of these three algorithms.
Klíčová slova: ekvivalence dekódovacích algoritmů; Reed-Solomonovy kódy; řetězové zlomky; Continued fractions; Equivalence of decoding algorithms; Reed-Solomon codes

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/73015

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-342375


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce