Коды с исправлением ошибок

Аспирантура 2018/2019

Статус: Факультатив

Направление: 02.06.01. Компьютерные и информационные науки

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1 семестр

Формат изучения: без онлайн-курса

Преподаватели: Верещагин Николай Константинович

Язык: русский

Кредиты: 4

Контактные часы: 32

Полная версия программы учебной дисциплины

Аннотация

Ошибки бывают всюду, в том числе и при передаче и хранении информации. На компакт-диске может быть царапина, в оперативную память может врезаться залётный протон, в радиоэфире или кабеле могут быть помехи, и так далее. Чтобы с этим жить, нужен некоторый "запас надёжности": информация должна быть избыточной, чтобы частичная утрата была поправимой. Когда слышимость плохая, люди повторяют одно и то же много раз, создавая такую избыточность, но повторение не самый эффективный способ. Теория кодов с исправлением ошибок как раз и изучает, чего можно и чего нельзя добиться - и если можно, то как. Пусть мы знаем, что в длинной последовательности битов при передаче портится не более какого-то процента битов - каковы необходимы накладные расходы (потеря в скорости передачи), чтобы компенсировать такие искажения? До сих пор этот вопрос открыт -но получены достаточно хорошие оценки, причём соответствующие коды имеют эффективные алгоритмы декодирования. Наш курс - вводный, мы изучим лишь базовые результаты: нижние и верхние оценки (Варшамова-Гилберта, volume bound), рассмотрим наиболее важные коды (Хемминга, Рида-Соломона) и алгоритмы их декодирования, а также смежные вопросы.

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

Ознакомление с постановками задач в области кодов со стираниями
Ознакомление с постановками задач в области кодов с исправлением ошибок
Изучение основных нижних и верхних оценок на параметры кодов с исправлением ошибок
Ознакомление с наиболее известными кодами с исправлением ошибок

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

Знать основные верхние и нижние оценки параметров кодов, исправляющих ошибки или стирания
Уметь строить простейшие коды, исправляющие ошибки или стирания
Владеть навыками построения эффективных кодов (для которых есть быстрые алгоритмы кодирования и декодирования) с исправлением ошибок с данными параметрами
Применять коды с исправлением ошибок для построения трудных в среднем задач

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

Коды с исправлением ошибок: верхние и нижние оценки
Оценка Хэмминга. Коды Хэмминга. Оценка Синглтона. Коды Рида – Соломона. Эффективное исправление ошибок и стираний в коде Рида-Соломона. Оценка Гилберта. Оценка Варшамова – Гилберта (вероятностное доказательство).
Коды на границе Варшамова – Гилберта и вблизи нее
Коды Возенкрафта для скорости 1/2. Коды Возенкрафта для любой скорости, выражаемым рациональным числом с небольшим знаменателем. Коды Форни. Эффективное декодирование кодов Форни. Коды Форни – Возенкрафта – Юстесена.
Коды БЧХ и Адамара
Коды БЧХ. Код Адамара. Вероятностный алгоритм декодирования кода Адамара.
Декодирование списком с исправлением ошибок
Декодирование списком с исправлением ошибок. Аналоги оценок Хэмминга и Гилберта. Декодирование списком кода с данным расстоянием. Оценка Плоткина. Обобщение оценки Плоткина для относительного кодового расстояния 1/2. Кривая Плоткина. Оценка Элайеса – Бассалыго.
Локально декодируемые и корректируемые коды
Экспандерные коды. Связь кодового расстояния с параметрами экспандера. Локально декодируемые и корректируемые коды. Связь этих понятий. Связь с количеством исправляемых ошибок. Коды Рида – Маллера. Три процедуры локальной коррекции ошибок для этих кодов. Быстрый алгоритм исправления ошибок в экспандерном коде. Параметры экспандерных кодов. Декодирование списком кодов Адамара за полиномиальное от длины сообщения время. Соотношение кодов БЧХ и кодов Хемминга.

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

Домашние задания
7 домашних заданий в течение курса. Срок сдачи каждого задания – 14 дней.
Экзамен

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

Промежуточная аттестация (I семестр)
Оценка за курс является средним арифметическим оценки текущего контроля и оценки за экзамен.

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