Expanderové kódy
| Thesis title in Czech: | Expanderové kódy |
|---|---|
| Thesis title in English: | Expander codes |
| Key words: | expander|konduktor|samoopravný kód|efektivní dekódování |
| English key words: | expander|randomness conductor|error-correcting code|linear-time decoding |
| Academic year of topic announcement: | 2019/2020 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | Mgr. Martin Mareš, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 10.09.2020 |
| Date of assignment: | 10.09.2020 |
| Confirmed by Study dept. on: | 22.09.2020 |
| Date and time of defence: | 02.09.2021 09:00 |
| Date of electronic submission: | 22.07.2021 |
| Date of submission of printed version: | 22.07.2021 |
| Date of proceeded defence: | 02.09.2021 |
| Opponents: | RNDr. Radek Hušek, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |