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

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

Курс состоит из 10 учебных недель. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами.

1. Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова.
2. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
3. Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
4. Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
5. Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
6. Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона, Плоткина.
7. Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
8. Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
9. Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
10. Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
11. Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
12. Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
13. Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
14. Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Спилмана.
15. Теоремы Шеннона для вероятностной модели канали.
16. Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема Мак-Элиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации в задаче MAX-SAT.