Локальное декодирование

Общая информация
ЛекторС. Еханин
Семестрвесна 2012
Дата начала16.06.2012
Количество пар5
Язык курсарусский
Видеоhttp://www.lektorium.tv/course/?id=22879
Анонсы
Объявление для печати
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/9177-lokalnoe-dekodirovanie
Анонс habrahabr.ruhttp://habrahabr.ru/events/670/
Аннотация

Классические помехоустойчивые коды кодируют сообщения из $ 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. $

Теория локально декодируемых кодов — это относительно новый, активно развивающийся раздел теории кодирования. Локально декодируемые коды имеют приложения в криптографии и теории сложности вычислений. Они также используются на практике для обеспечения надёжности в больших распределенных системах хранения данных. В данном курсе мы рассмотрит основные семейства локально декодируемых кодов. Курс предполагает минимальное знакомство с алгеброй над конечными полями.

Материалы:
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция
(16.06.2012 - 17:20 - 18:55)

Основные понятия теории кодирования: линейные коды, систематические коды, скорость, расстояние, информационные множества, модели ошибок. Граница Синглтона. Определение локально декодируемых кодов.

http://www.lektorium.tv/lecture/?id=13837
2. Лекция
(16.06.2012 - 19:05 - 20:40)

Отсутствие локальности в кодах МДР. Коды Адамара. Локальное декодирование после одного стирания. Пирамидальные коды. Практическая мотивация локального декодируемых кодов. Оптимальность пирамидальных кодов (формулировка теоремы).

http://www.lektorium.tv/lecture/?id=13838
3. Лекция
(17.06.2012 - 11:15 - 12:50)

Оптимальность пирамидальных кодов (доказательство теоремы). Коды с оптимальным восстановлением. Пример кода МДР с нетривиальной обобщённой локальностью. Нижняя оценка на обобщённую локальность. Коды МДР с оптимальной обобщённой локальностью информационных символов (начало).

http://www.lektorium.tv/lecture/?id=13839
4. Лекция
(17.06.2012 - 13:00 - 14:35)

Коды МДР с оптимальной обобщённой локальностью информационных символов (завершение). Локальное декодирование после линейно растущего количества стрираний. Коды Рида Маллера. Асимптотические параметры кодов Рида Маллера.

http://www.lektorium.tv/lecture/?id=13840
5. Лекция
(17.06.2012 - 15:35 - 17:10)

Сочетающиеся вектора. Коды из сочетающихся векторов. Конструкция. Семейства сочетащихся векторов. Приложения локально декодируемых кодов в криптографии (private information retrieval schemes).

http://www.lektorium.tv/lecture/?id=13841
Ваша оценка: Пусто Средняя: 4.2 (5 votes)
Share |
Сергей Еханин
Сергей Еханин
Сергей Еханин
Локальное декодирование
Сергей Еханин
Сергей Еханин
Сергей Еханин
Сергей Еханин и студенты
Ответы на вопросы