Original title:
Řetězové zlomky v teorii kódů
Translated title:
Continued fractions in coding theory
Authors:
Fišer, Jan ; Šťovíček, Jan (advisor) ; Holub, Štěpán (referee) Document type: Bachelor's theses
Year:
2014
Language:
cze Abstract:
[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.
Keywords:
Continued fractions; Equivalence of decoding algorithms; Reed-Solomon codes; ekvivalence dekódovacích algoritmů; Reed-Solomonovy kódy; řetězové zlomky
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/73015