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

Лектор: Н.К. Верещагин, nikolay.vereshchagin@math.msu.ru, Телеграм: nikolay_vereshchagin

Лекции проходят по понедельникам 10:45-12:10 в ауд. 428, первая лекция 2 октября.

Телеграм канал для вопросов и сообщений: https://t.me/+7w1cLI5fA9Q1ZmYy

Для получения зачета необходимо посетить не менее 8 лекций  и решать следующие задачи в указанные сроки. Решения задач нужно сдавать на английском языке не позже указанного дедлайна послать по адресу nikolay.vereshchagin@gmail.com в формате txt или pdf (в pdf можно включать фотографии). Сдача задач после дедлайна невозможна.

За задачи выставляются баллы, равные доле правильно отвеченных вопросов (решенных задач). При выставлении итогового балла задачи и тесты учитываются с равными весами. Зачет получат те, кто набрал 65% максимально возможного итогового балла. Оценка выставляется по следующей шкале:

отлично — итоговый балл нее меньше 80%,
хорошо — 65%,
удовлетворительно — 50%.

Отметки за решения задач

Краткое описание курса

В курсе рассказывается о некоторых общих оценках качества
кодов с исправлением ошибок, а также о конкретных кодах, используемых в Computer Science.

Примерная программа

• Code words, dimension, minimum distance of codes.
  The number of corrected errors and erasures. Hamming [n-1,n,2]-code.
• The Volume bound (aka Hamming bound). The Gilbert’s bound.
  The formula for the volume of a Hamming ball. The Shannon function.
• Linear codes.
  Varshamov-Gilbert nound.
• Wozencraft ensemble of codes.
• Hamming codes.
• Singleton bound. Reed-Solomon codes.
• Concatenated codes. Forney codes. Forney-Justesen-Wozencraft codes
• Plotkin’s bounds and improving the Singleton bound.
• Hadamard codes.
• Reed — Muller code.
• BCH codes.
• List decoding from errors. General bounds.
• List decoding and minimum distance.
• List decoding from n-sqrt{n(n-d)} errors for Reed-Solomon code.
• List decoding from (1-eps)/2 errors for Hadamard code
• Goldreich-Levin theorem.

Литература.

А. Ромащенко, А. Румянцев и А. Шень, Заметки по теории кодирования,
МЦНМО, 2011.

Конспект лекций.