Název:
Expanderové kódy
Překlad názvu:
Expander codes
Autoři:
Calábková, Markéta ; Mareš, Martin (vedoucí práce) ; Hušek, Radek (oponent) Typ dokumentu: Bakalářské práce
Rok:
2018
Jazyk:
cze
Abstrakt: [cze][eng] Kdekoliv se přenáší nějaká informace, jsou přítomny samooopravné kódy. Mezi nejpoužívanější třídy kódů patří LDPC (low density parity check) kódy. Expanderové kódy jsou jednou z nadějných tříd LDPC kódů. V této práci vysvětlujeme, co to expanderové kódy vlastně jsou, a ukazujeme, že je lze opravdu konstruovat tak, aby dosahovaly asymptoticky optimálních parametrů a zároveň je šlo dekódovat v čase lineárním s délkou zprávy. Bohužel uvedené konstrukce vytvářejí hodně dlouhé kódy, takže jsou v běžném provozu (například pro přenos paketů) prakticky nepoužitelné. Věříme ale, že s využitím lepší konstrukce expan- derů budeme schopni sestrojit dobré krátké kódy, které najdou mnohá využití. 1Wherever information is transmitted we can find error-correcting codes. LDPC (low density parity check) codes are one of frequently used classes of codes and expander codes are promising members of this class. In this work, we explain what expander code are. We also show that expander codes simulta- neously have both asymptotically optimal parameters and linear-time encoding and decoding. Unfortunately, our constructions grant us codes, which are too big for regular use, for example for packet transmission. However, we believe that with better construction of expander graphs we will be able to construct short codes with significant practical applications. 1
Klíčová slova:
efektivní dekódování; expander; samoopravný kód; error-correcting code; expander; linear-time decoding