Expanderové kódy
Název práce v češtině: | Expanderové kódy |
---|---|
Název v anglickém jazyce: | Expander codes |
Klíčová slova: | expander|konduktor|samoopravný kód|efektivní dekódování |
Klíčová slova anglicky: | expander|randomness conductor|error-correcting code|linear-time decoding |
Akademický rok vypsání: | 2019/2020 |
Typ práce: | diplomová práce |
Jazyk práce: | čeština |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | Mgr. Martin Mareš, Ph.D. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 10.09.2020 |
Datum zadání: | 10.09.2020 |
Datum potvrzení stud. oddělením: | 22.09.2020 |
Datum a čas obhajoby: | 02.09.2021 09:00 |
Datum odevzdání elektronické podoby: | 22.07.2021 |
Datum odevzdání tištěné podoby: | 22.07.2021 |
Datum proběhlé obhajoby: | 02.09.2021 |
Oponenti: | RNDr. Radek Hušek, Ph.D. |
Zásady pro vypracování |
Student se seznámí s technikou konstrukce samoopravných kódů z grafů s expanzními vlastnostmi a s různými konstrukcemi těchto grafů. Cílem práce je nalézt konstrukci expanderů s vhodnými vlastnostmi, pomocí nichž půjdou sestrojit kódy s dobrými parametry. Zaměří se i na otázky praktické implementace. |
Seznam odborné literatury |
Reingold, Vadhan, Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of mathematics, 2002.
Guruswami: Guest column: error-correcting codes and expander graphs. ACM SIGACT News, 35(3), 2004. Sipser, Spielman: Expander codes. IEEE Transactions on Information Theory, 42(6), 1996. Capalbo, Reingold, Vadhan: Randomness Conductors and Constant-Degree Lossless Expanders. Proceedings of STOC'02. ACM, 2002. |