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.