Магистратура
2020/2021
Элементы современной теории кодирования
Статус:
Курс по выбору (Науки о данных)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Кафедра технологий моделирования сложных систем
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Рыбин Павел Сергеевич
Прогр. обучения:
Науки о данных
Язык:
русский
Кредиты:
4
Контактные часы:
28
Программа дисциплины
Аннотация
Современный мир тяжело представить без различных систем передачи и хранения данных. С ежегодно возрастающими требованиями как к скорости, так и к надежности передаваемых данных, все более актуальным становятся задачи теории кодирования и информации. Курс посвящен изучению методов теории помехоустойчивого кодирования, активно используемых в современных системах связи. В рамках курса будут даны элементы теории информации и теории кодирования. Будут описаны методы построения и анализа современных кодовых конструкций таких, как коды с малой плотностью проверок (МПП-коды, LDPC codes), полярные коды (polar codes), сверточные коды (convolution codes) и т.д., а также их алгоритмы кодирования и декодирования. Также будут приведены способны применения данных кодов как для защиты данных, передаваемых по каналам связи, так и для хранения данных в том числе и в распределенных хранилищах. Будут сформулированы открытые на данный момент вопросы и задачи теории кодирования.
Цель освоения дисциплины
- Дать представление об основных теоретических и практических методах и подходах современной теории кодирования, многие из которых в настоящее время используются в современных системах связи/
Планируемые результаты обучения
- Знать основные теоретико-информационные границы и уметь их применять
- Знать основные границы на параметры линейных и нелинейных блочных кодов и уметь их применять
- Знать конструкции, параметры и алгоритмы декодирования алгебраических кодов
- Знать конструкции, параметры и алгоритмы декодирования сверточных кодов
- Знать конструкции, параметры и алгоритмы декодирования кодов на графах
- Знать конструкцию, параметры и алгоритмы декодирования полярных кодов
- Знать приложение теории кодирования в криптографии и методах хранения данных
Содержание учебной дисциплины
- Элементы теории информацииЭнтропия, дифференциальная энтропия, энтропийные неравенства, взаимная информация. Модели каналов. Пропускная способность канала.
- Блочные кодыГраницы на параметры кодов. Линейные коды (коды Хэминга, Рида-Маллера, Рида-Соломона, Боуза — Чоудхури — Хоквингема (БЧХ)). Методы комбинирования кодов (перемежение кодов, произведение кодов, каскадные коды, обобщенные каскадные коды).
- Сверточные кодыПостроение сверточных кодов. Параметры сверточных кодов. Алгоритм кодирования сверточных кодов. Алгоритмы декодирования сверточных кодов.
- Коды на графахПостроение кодов на графах. Код с малой плотностью проверок (МПП-код, LDPC code). Параметры кодов на графах. Алгоритмы декодирования кодов на графах.
- Полярные кодыПостроение полярных кодов. Параметры полярных кодов. Алгоритмы декодирования полярного кода.
- Другие приложения теории кодированияКодовая криптография. Распределенное хранение и доступ к данным.
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.2 * Домашнее задание 1 + 0.1 * Контрольная работа 1 + 0.1 * Контрольная работа 2 + 0.6 * Экзамен
Список литературы
Рекомендуемая основная литература
- Cover, Thomas M., Thomas, Joy A. Elements of information theory. – Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2006. – 774 pp.
Рекомендуемая дополнительная литература
- Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. - Алгеброгеометрические коды. Основные понятия - Московский центр непрерывного математического образования - 2003 - 504с. - ISBN: 5-94057-123-9 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9314