Локальное декодирование
Курс Хит
Классические помехоустойчивые коды кодируют сообщения из k бит кодовыми словами из n бит, позволяя однозначно восстанавливать сообщения даже из искажённых кодовых слов. Некоторым неудобством является то, что для восстановления даже одного бита сообщения, как правило, необходимо прочесть всё искажённое кодовое слово. Локально декодируемые коды – это коды, которые позволяют этого неудобства избежать.
Простейшим примером локально декодируемых кодов является код Адамара, кодирующий сообщения (x1, x2, x3) длины 3 кодовыми словами (x1, x2, x3, x1⊕ x2, x1⊕ x3, x2⊕ x3, x1⊕ x2⊕ x3) длины 7. Несложно убедиться, что даже после того, как какие-либо три символа кодового слова оказываются стёрты, любой символ сообщения можно восстановить, прочитав только два из четырёх оставшихся символов.
Теория локально декодируемых кодов – это относительно новый, активно развивающийся раздел теории кодирования. Локально декодируемые коды имеют приложения в криптографии и теории сложности вычислений. Они также используются на практике для обеспечения надёжности в больших распределенных системах хранения данных. В данном курсе мы рассмотрит основные семейства локально декодируемых кодов. Курс предполагает минимальное знакомство с алгеброй над конечными полями.
Примерный план лекций:
- Модели локального декодирования. Код Адамара. Коды с оптимальным восстановлением. Пирамидальные коды.
- Коды Рида-Маллера.
- Коды с кратностями.
- Сочетающиеся вектора.
- Коды из сочетающихся векторов. Приложения.