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

ЕНС на иностранном языке «Коды с исправлением ошибок». Осенний семестр 2021

Лекции проходят по пятницам 13-14:35 онлайн с помощью

Zoom https://us02web.zoom.us/j/87590290380?pwd=NFE3ditPSDN4RUdFbzl6cUk4NU5NQT09
Идентификатор конференции: 875 9029 0380.
Код доступа: 434560.

Первая лекция 2 октября.

Ссылки на электронную доску Google Jamboard:

Доска 1,
Доска 2.

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

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

Ссылка на видеозаписи лекций на Ютубе

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


Результаты Теста 1

Результаты Теста 2

Результаты Теста 3

Результаты Теста 4

Результаты Теста 5

Результаты Теста 6

Результаты Теста 7

Результаты Теста 8

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

В курсе рассказывается о некоторых общих оценках качества
кодов с исправлением ошибок,
а также о конкретных кодах, используемых в 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.


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


Дневник лекций