Теория кодирования

Общая информация
ЛекторА. Е. Ромащенко
Семестрвесна 2012
Дата начала24.03.2012
Количество пар10
Язык курсарусский
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/?id=22864
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/8015-teoriya-kodirovaniya
Анонс habrahabr.ruhttp://habrahabr.ru/events/419/
Аннотация

С появлением технической возможности хранить и пересылать большие объёмы данных немедленно появилась необходимость бороться со спорадически возникающимися в этих данных ошибками. Эта практическая потребность дала рождение теории кодирования — науке о надежном хранении и передаче информации. Типичный вопрос, изучаемый этой наукой: как передавать по каналу связи полезную информацию, если один процент пересылаемых битов теряется или искажается?

Методы, развитые в теории кодирования, оказываются эффективны в задачах, не связанных непосредственно с защитой сообщений от шума (например, в теории коммуникационной сложности, в схемах разделения секрета, при дерандомизации вероятностных алгоритмов, и т.д.).

В этом курсе мы изучим базовые результаты теории кодирования, а также рассмотрим некоторые недавние достижения этой науки. Курс будет ориентирован на студентов, изучающих computer science; особое внимание будет уделено алгоритмическим задачам теории кодирования.

Для понимания курса полезно знакомство с основами теории вероятностей и линейной алгебры.

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

1. Комбинаторная модель канала с шумом. Базовые определения и простейшие оценки
(24.03.2012 - 17:20 - 18:55)

Определение кода, исправляющего $ e $ ошибок; код как отображение и код как множество слов. Кодовое расстояние. Обозначение параметров кода $ [n,k,d]_q $. Граница Хэмминга, граница Гилберта. Линейный код. Расстояние для линейного кода. Порождающая и проверочная матрица линейного кода. Расстояние линейного кода и число линейно независимых столбцов проверочной матрицы. Граница Варшамова–Гилберта. http://www.lektorium.tv/lecture/?id=13665
2. Классические линейные коды: код Хэмминга и код Рида-Соломона
(24.03.2012 - 19:05 - 20:40)

Код Хэмминга — совершенный код, исправляющий $ 1 $ ошибку. Естественные алгоритмы кодирвания и декодирования. Игра "угадай число" с неадаптивными вопросами и одним ложным ответом. Граница в $ 25\% $ (двоичный код длины $ n $, исправляющий более $ 25\% $ ошибок, имеет не более $ n+1 $ кодовых слов). Код Рида-Соломона, его параметры. Граница Синглтона. Полиномиальный алгоритм декодирования кода Рида--Соломона. http://www.lektorium.tv/lecture/?id=13666
3. Каскадные коды, явная конструкция асимптотически хорошего кода
(25.03.2012 - 11:15 - 12:50)

Код Адамара. Коды Рида-Маллера. Определение кода БЧХ. Каскадные коды (конкатенация кодов). Алгоритм декодирования, исправляющий до $ d/4 $ ошибок в каскадном коде. Конструкция асимптотически хорошего кода с полиномиальными алгоритмами кодирования и декодирования (конкатенация кода Рида-Соломона и произвольного кода с границы Варшамова-Гилберта). http://www.lektorium.tv/lecture/?id=13667
4. Декодирование списком
(25.03.2012 - 13:00 - 14:35)

Декодирование списком. Граница Хэмминга для декодирования списком. Существование кода, допускающего декодирование списком линейного размера. Алгоритм декодирования списком кода Рида-Соломона. Конструкция кода, допускающего декодирование списком на расстоянии $ (1/2-\varepsilon)n $ (с полиномиальным алгоритмом декодирования списком). http://www.lektorium.tv/lecture/?id=13668
5. Вероятностная модель канала с шумом и классические теоремы Шеннона
(25.03.2012 - 15:35 - 17:10)

Энтропия Шеннона. Теорема Шеннона об оптимальном блоковом кодировании для канала без шума. Взаимная информация пары случайных величин. Пропускная способность дискретного канала без памяти. Теорема Шеннона об оптимальном блоковом кодировании для канала с шумом (без доказательства). http://www.lektorium.tv/lecture/?id=13669
6. Вычислительная трудность декодирования линейного кода
(31.03.2012 - 17:20 - 18:55)

$ \mathrm{NP} $-трудность общей задачи декодирования линейного кода: по проверочной матрице кода $ H $, вектору $ y $ и числу $ e $ найти кодовое слово $ x $ на расстоянии не больше $ e $ от $ y $. Криптографическая схема МакЭлиеса. Двоичные коды Гоппы. http://www.lektorium.tv/lecture/?id=13689
7. Декодирование списком и генераторы псевдослучайных битов
(31.03.2012 - 19:05 - 20:40)

Конструкция семейства трудных битов для любой односторонней перестановки. Построение псевдослучайного генератора из произвольной односторонней перестановки. Вероятностная схема Гурусвами: передача данных по каналу с искажением $ p $ ошибок ($ 1/4 < p < 1/2 $) с небольшой дополнительной информацией, пересылаемой по каналу без ошибок. http://www.lektorium.tv/lecture/?id=13690
8. От декодирования списком и к однозначному декодированию
(01.04.2012 - 11:15 - 12:50)

Теорема Зяблова и Пинскера о существование линейного кода размерности $ k $ с кодовыми словами длины $ n $, допускающего декодирование списком размера $ O(1) $ на расстоянии $ e $ (достаточное условие $ V(n,e)<2^{(1-\varepsilon)(n-k)} $ для произвольного $ \varepsilon>0 $). Коммуникационная задача передачи $ n $-битного $ x $ от Алисы к Бобу при условии, что Бобу заранее известно некоторое $ y $ на расстоянии $ \alpha n $ от $ x $. Нижняя оценка коммуникационной сложности $ h(\alpha)n-o(n) $ (для $ \alpha<1/2 $). Детерминированный 3-раундовый детерминированный коммуникационный протокол с коммуникационной сложностью $ h(\alpha)n+o(n) $ для $ \alpha<1/2 $. http://www.lektorium.tv/lecture/?id=13691
9. Псевдослучайные перестановки и случайное кодирование
(01.04.2012 - 13:00 - 14:35)

Вероятностный коммуникационный протокол с оптимальной коммуникационной сложностью и полиномиальными алгоритмами для Алисы и Боба. Вероятностное кодирование Гурусвами-Смита для аддитивного канала, искажающего не более доли $ p $ битов в сообщении. http://www.lektorium.tv/lecture/?id=13692
10. Коды на графах
(01.04.2012 - 15:35 - 17:10)

Проверочная матрица линейного кода как матрица смежности двудольного графа. Двудольные экспандеры и экспандерные коды. Лемма об уединенных соседях. Простейшая оценка снизу для расстояния экспандерного кода. Алгоритм декодирования экспандерного кода для графа с коэффициентом расширения больше $ 3/4 $ (от степени вершин в левой доле графа). Алгоритм Видермана декодирования экспандерного кода для графа с коэффициентом расширения больше $ 2/3 $. Коды на графах, исправляющих стирания: идея "цифрового фонтана" и raptor-кода. http://www.lektorium.tv/lecture/?id=13693
Ваша оценка: Пусто Средняя: 4.5 (8 votes)
Share |
Теория кодирования
Лекция по теории кодирования
Андрей Евгеньевич и студенты
Андрей Евгеньевич
Андрей Евгеньевич Ромащенко
Андрей Евгеньевич Ромащенко
Обсуждение
Андрей Евгеньевич Ромащенко
Андрей Евгеньевич Ромащенко
Теория кодирования
Теория кодирования