Original title:
Expanderové kódy
Translated title:
Expander codes
Authors:
Machová, Markéta ; Mareš, Martin (advisor) ; Hušek, Radek (referee) Document type: Master’s theses
Year:
2021
Language:
cze Abstract:
[cze][eng] Samoopravné kódy se dnes používají při většině přenosů informace. Abychom ale zbytečně neplýtvali místem, je dobré používat kódy, které opraví dostatečně mnoho chyb a přitom zprávu moc neprodlouží. Expanderové kódy jsou slibné - asymptoticky dosahují dobrých výsledků, ale v praxi se zatím bohužel ukázalo, že jsou moc dlouhé. Cesta k lepším konstrukcím expanderů by mohla vést přes konduktory, což jsou takzvané vodiče náhody. V této práci vysvětlíme, co konduktory jsou, a zmapujeme jejich konstrukce. Nakonec pomocí převodu na expandery téměř dokážeme, že je možné sestrojit kódy, které se zachováním dobrých vlastností budou dost malé na to, aby se daly použít v praxi. 1Error-corecting codes are used during most of data transmissions these days. To save space, we would like to use codes which are able to correct enough errors without extending the message too much. The expander codes look promising - they are asymptotically optimal, however, in practice they are just too long. Better expander constructions could be achieved via randomness con- ductors. In this thesis, we explain what conductors are and which constructions are possible for them. In the end we will convert them to expanders and almost get expander codes which are short enough for practical use but nevertheless good. 1
Keywords:
expander|randomness conductor|error-correcting code|linear-time decoding; expander|konduktor|samoopravný kód|efektivní dekódování
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/147655