• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2019/2020

Элементы современной теории кодирования

Статус: Курс по выбору (Науки о данных)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 2 модуль
Формат изучения: без онлайн-курса
Преподаватели: Рыбин Павел Сергеевич
Прогр. обучения: Науки о данных
Язык: русский
Кредиты: 4

Программа дисциплины

Аннотация

Современный мир тяжело представить без различных систем передачи и хранения данных. С ежегодно возрастающими требованиями как к скорости, так и к надежности передаваемых данных, все более актуальным становятся задачи теории кодирования и информации. Курс посвящен изучению методов теории помехоустойчивого кодирования, активно используемых в современных системах связи. В рамках курса будут даны элементы теории информации и теории кодирования. Будут описаны методы построения и анализа современных кодовых конструкций таких, как коды с малой плотностью проверок (МПП-коды, LDPC codes), полярные коды (polar codes), сверточные коды (convolution codes) и т.д., а также их алгоритмы кодирования и декодирования. Также будут приведены способны применения данных кодов как для защиты данных, передаваемых по каналам связи, так и для хранения данных в том числе и в распределенных хранилищах. Будут сформулированы открытые на данный момент вопросы и задачи теории кодирования.
Цель освоения дисциплины

Цель освоения дисциплины

  • Дать представление об основных теоретических и практических методах и подходах современной теории кодирования, многие из которых в настоящее время используются в современных системах связи/
Планируемые результаты обучения

Планируемые результаты обучения

  • Знать основные теоретико-информационные границы и уметь их применять
  • Знать основные границы на параметры линейных и нелинейных блочных кодов и уметь их применять
  • Знать конструкции, параметры и алгоритмы декодирования алгебраических кодов
  • Знать конструкции, параметры и алгоритмы декодирования сверточных кодов
  • Знать конструкции, параметры и алгоритмы декодирования кодов на графах
  • Знать конструкцию, параметры и алгоритмы декодирования полярных кодов
  • Знать приложение теории кодирования в криптографии и методах хранения данных
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Элементы теории информации
    Энтропия, дифференциальная энтропия, энтропийные неравенства, взаимная информация. Модели каналов. Пропускная способность канала.
  • Блочные коды
    Границы на параметры кодов. Линейные коды (коды Хэминга, Рида-Маллера, Рида-Соломона, Боуза — Чоудхури — Хоквингема (БЧХ)). Методы комбинирования кодов (перемежение кодов, произведение кодов, каскадные коды, обобщенные каскадные коды).
  • Сверточные коды
    Построение сверточных кодов. Параметры сверточных кодов. Алгоритм кодирования сверточных кодов. Алгоритмы декодирования сверточных кодов.
  • Коды на графах
    Построение кодов на графах. Код с малой плотностью проверок (МПП-код, LDPC code). Параметры кодов на графах. Алгоритмы декодирования кодов на графах.
  • Полярные коды
    Построение полярных кодов. Параметры полярных кодов. Алгоритмы декодирования полярного кода.
  • Другие приложения теории кодирования
    Кодовая криптография. Распределенное хранение и доступ к данным.
Элементы контроля

Элементы контроля

  • неблокирующий Контрольная работа 1
  • неблокирующий Контрольная работа 2
  • неблокирующий Домашнее задание 1
  • неблокирующий Экзамен
    письменный
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (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 - ISBN: 5-94057-123-9 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/9314