Коды с исправлением ошибок (осень 2020)
Курс ЕНС на иностранном языке
Лекции проходят по пятницам 13-14:35 онлайн с помощью
Google Meet meet.google.com/ajn-djar-fmw
Zoom https://us02web.zoom.us/j/86965796255?pwd=UUphcVBxZml4aHY0ak5vUTJKaGpSZz09
Zoom https://us02web.zoom.us/j/89057185267?pwd=cHRZcGh1dXJNdFBVOHg4V1JEMlZKdz09
Zoom https://us02web.zoom.us/j/87590290380?pwd=NFE3ditPSDN4RUdFbzl6cUk4NU5NQT09 Идентификатор конференции: 875 9029 0380. Код доступа: 434560.
Первая лекция 2 октября 2020 года.
Ссылки на электронную доску Google Jamboard: Доска 1, Доска 2.
Для получения зачета необходимо сдавать тесты в конце каждой лекции и решать следующие задачи в указанные сроки. Решения задач нужно сдавать на английском языке не позже указанного дедлайна послать по адресу nikolay.vereshchagin@gmail.com в формате txt или pdf (в pdf можно включать фотографии). Сдача задач после дедлайна невозможна. За тесты и задачи выставляются баллы, равные доле правильно отвеченных вопросов (решенных задач). При выставлении итогового балла задачи и тесты учитываются с равными весами. Зачет получат те, кто набрал 65% максимально возможного итогового балла.
Ссылка на видеозаписи лекций на Ютубе
Отметки за решения задач и тестов
Краткое описание курса
В курсе рассказывается о некоторых общих оценках качества кодов с исправлением ошибок, а также о конкретных кодах, используемых в 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.