Кафедра математической логики и теории алгоритмов

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

ЕНС на иностранном языке для студентов 6-го курса мехмата МГУ. Осенний семестр 2024

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

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

Телеграм канал для вопросов и сообщений: 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.


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