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