Теория кодирования
В данный момент курс ведётся в магистратуре кафедры дискретной математики школы ПМИ МФТИ. В разных версиях курс читался в МФТИ с 2012 года в качестве спецкурса и основного курса.
Задания
Лекции
Слайды некоторых лекций прошлого года можно найти по ссылке.
План лекций
- Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова.
- Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
- Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
- Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
- Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
- Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона, Плоткина.
- Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
- Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
- Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
- Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
- Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Спилмана.
- Матрицы Адамара. Конструкции Сильвестра и Пэли. Коды на основе матриц Адамара.
- Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
- Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
- Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
- Каскадные коды. Коды Форни: конструкция и простой алгоритм декодирования.
- Циклические коды. Проверочный и порождающий многочлены, критерий существования кода с заданным порождающим многочленом. Вид порождающей и проверочной матриц. Систематическое кодирование.
- Граница Боуза—Чоудхури—Хоквингема. Коды БЧХ.
- Задача восстановления синхронизации. Восстановление синхронизации для смежных классов циклических кодов.
- Совершенные коды. Коды Голея. Теорема Васильева.
- Графовая модель канала. Шенноновское произведение графов, шенноновская ёмкость. Теорема о верхней оценке шенноновской ёмкости.
- Теоремы Шеннона о пределе скорости в вероятностной модели канала.
- Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема МакЭлиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации в задаче MAX-SAT и к задаче разделения секрета.
Материалы по курсу
Литература
Для более глубокого освоения материала обращайтесь к литературе из списка ниже. Обратите внимание на книгу [5].
- М. Н. Аршинов, Л. Е. Садовский. Коды и математика. М.: Наука, 1983.
- С. Б. Гашков. Графы-расширители и их применение в теории кодирования // Математическое просвещение, сер. 3, вып. 13, 2009. С. 104–126.
- Ф. Мак-Вильямс, Н. Слоэн. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
- У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. М.: Мир, 1976.
- А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. М.: МЦНМО, 2011.
- Ю. Л. Сагалович. Введение в алгебраические коды. М.: изд-во МФТИ: 2007.
- Ф. И. Соловьева. Введение в теорию кодирования. Новосибирск: изд-во НГУ, 2006.
- Ye. Lindell. Introduction to Coding Theory. Lecture notes. Bar-Ilan University.
- J. H. van Lint. Introduction to Coding Theory. Third edition. Springer-Verlag, 1999.
- M. Sudan. Algorithmic Introduction to Coding Theory. Lecture notes. MIT, 2001.