среда, 18 апреля 2012 г.

Теория кодирования, лекция 10

Тема лекции: Теория кодирования, лекция 10

Курс лекций: Теория кодирования

Предмет семинара: Computer Science

Аудитория курса: Computer Science клуб при ПОМИ РАН

Лектор лекции: Андрей Ромащенко

Тип лекции: Спецкурсы

Описание лекции: Проверочная матрица линейного кода как матрица смежности двудольного графа. Двудольные экспандеры и экспандерные коды. Лемма об уединенных соседях.

Простейшая оценка снизу для расстояния экспандерного кода. Алгоритм декодирования экспандерного кода для графа с коэффициентом расширения больше  (от степени вершин в левой доле графа). Алгоритм Видермана декодирования экспандерного кода для графа с коэффициентом расширения больше . Коды на графах, исправляющих стирания: идея "цифрового фонтана" и raptor-кода.

Описание курса: С появлением технической возможности хранить и пересылать большие объёмы данных немедленно появилась необходимость бороться со спорадически возникающимися в этих данных ошибками. Эта практическая потребность дала рождение теории кодирования - науке о надежном хранении и передаче информации. Типичный вопрос, изучаемый этой наукой: как передавать по каналу связи полезную информацию, если один процент пересылаемых битов теряется или искажается? Методы, развитые в теории кодирования, оказываются эффективны в задачах, не связанных непосредственно с защитой сообщений от шума (например, в теории коммуникационной сложности, в схемах разделения секрета, при дерандомизации вероятностных алгоритмов, и т.д.). В этом курсе мы изучим базовые результаты теории кодирования, а также рассмотрим некоторые недавние достижения этой науки. Курс будет ориентирован на студентов, изучающих computer science; особое внимание будет уделено алгоритмическим задачам теории кодирования. Для понимания курса полезно знакомство с основами теории вероятностей и линейной алгебры.