Классические помехоустойчивые коды кодируют сообщения из \( k \) бит кодовыми словами из \( n \) бит, позволяя однозначно восстанавливать сообщения даже из искажённых кодовых слов. Некоторым неудобством является то, что для восстановления даже одного бита сообщения, как правило, необходимо прочесть всё искажённое кодовое слово. Локально декодируемые коды — это коды, которые позволяют этого неудобства избежать. Простейшим примером локально декодируемых кодов является код Адамара, кодирующий сообщения \( (x_1,x_2,x_3) \) длины 3 кодовыми словами \( (x_1,x_2,x_3,x_1\oplus x_2, x_1\oplus x_3, x_2\oplus x_3, x_1\oplus x_2\oplus x_3) \) длины 7. Несложно убедиться, что даже после того, как какие-либо три символа кодового слова оказываются стёрты, любой символ сообщения можно восстановить, прочитав только два из четырёх оставшихся символов. Например, если стёрты символы \( x_1,x_2, x_1\oplus x_3, \) то \( x_1 \) можно восстановить по символам \( x_2\oplus x_3 \) и \( x_1\oplus x_2\oplus x_3. \)
Теория локально декодируемых кодов — это относительно новый, активно развивающийся раздел теории кодирования. Локально декодируемые коды имеют приложения в криптографии и теории сложности вычислений. Они также используются на практике для обеспечения надёжности в больших распределенных системах хранения данных. В данном курсе мы рассмотрит основные семейства локально декодируемых кодов. Курс предполагает минимальное знакомство с алгеброй над конечными полями.
Материалы:
