ЕНС на иностранном языке «Коды с исправлением ошибок». Осенний семестр 2019
Пятница 12:30-14:05, ауд. 1225. Первая лекция 4 октября.
Для получения зачета необходимо посещать лекции (посетив не менее 7 лекций) и решить не менее 65% следующих задач в указанные сроки. Решения задач нужно сдавать на английском языке не позже указанного дедлайна перед лекцией на листочках или послать по адресу nikolay.vereshchagin@gmail.com в формате txt или pdf (в pdf можно включать фотографии). Сдача задач после дедлайна невозможна.
Не получившие зачета по этим правилам могут тем не менее его получить, придя на зачет, на котором им будет предложен билет, содержащий один теоретический вопрос из списка и три задачи того же типа, что в этом списке.
Зачет сдается на английском языке.
Дата зачета — 23.12.2019 в 10.00. Аудитория 1603.
ЗАПИСЬ НА ЗАЧЕТ ЗАКОНЧЕНА 20 декабря 23:59 MSK!
Краткое описание курса
В курсе рассказывается о некоторых общих оценках качества кодов с исправлением ошибок, а также о конкретных кодах, используемых в 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.