Курс «Error correcting codes»
Осенний семестр 2017
Среда 12:30-14:05, ауд. 1213.
Для получения зачета необходимо посещать лекции (посетив не менее шести лекций) и решить не менее 65 проц. следующих задач в указанные сроки. Решения задач нужно сдавать на английском языке не позже указанного дедлайна перед лекцией на листочках или послать по адресу nikolay.vereshchagin@gmail.com в формате txt или pdf (в pdf можно включать фотографии). Сдача задач после дедлайна возможна, но тогда их решение учитывается с коэффициентом 0.5. Присылать дважды решение одной и той же задачи нельзя.
Не получившие зачета по этим правилам могут тем не менее его получить, придя на зачет, на котором им будет предложен билет, содержащий один теоретический вопрос из списка и три задачи того же типа, что в этом списке.
Зачет сдается на английском языке. Дата зачета — 25 декабря 2017 года с 10:30 до 14 в ауд. 449 второго учебного корпуса.
Для записи на зачет заполните эту форму.
ЗАПИСЬ НА ЗАЧЕТ ЗАКОНЧЕНА 24 ДЕКАБРЯ В 16:30.
Краткое описание курса
В курсе рассказывается о некоторых общих оценках качества кодов с исправлением ошибок, а также о конкретных кодах, используемых в 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.
Осенний семестр 2016
Зачет по курсу состоится во вторник 31 января в 11 часов в ауд. 1605 ГЗ.
На зачете надо сдать решение
следующих задач
и ответить на один вопрос по теории из вопросов, разобранных на лекциях
(см. Course Log). Сдача зачета происходит на английском языке.
Wednesday 12:30-14:05, room 1306.
Задачи с указанием
сроков сдачи, которые нужно решить для получения
зачета (файл находится на Dropbox и должен быть доступен, даже если
кафедральный сервер упал). Решения задач нужно сдавать на английском языке
не позже дедлайна перед лекцией на листочках или послать
по адресу nikolay.vereshchagin@gmail.com в формате txt или pdf.
Оценки за сданные задачи.
Для получения зачета нужно решить 60% всех задач (получить 0.6 максимума очков).
Книга Ромащенко, Румянцева и Шеня с некоторыми изменениями и добавлениями
о кодах Возенкрафта и локально корректируемых кодах.
Эта книга покрывает весь курс лекций.