City: Saint-Petersburg Kazan Language: Русский English

Error correcting codes: basics
Saint-Petersburg / autumn 2017, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Теория кодирования - важная часть дискретной математики и теоретической информатики, и кое-что там вполне можно понять и оценить, не углублясь в детали и почти без формул. Мы попробуем разобраться в самом простом и важном в этой науке.

План курса:

I Задача исправления ошибок. Вероятностная и невероятностная постановки (мы рассматриваем только вторую). Комбинаторная интерпретация: точки на расстоянии, упаковка шаров. Основная проблема теории кодирования. Исправление одной ошибки: код Хемминга. Нижние и верхние оценки (volume bound, Варшамов-Гильберт).

II Коды в большем алфавите. Код Рида-Соломона. Как декодировать код Рида-Соломона? Как построить код с линейным увеличением длины и постоянной долей исправляемых ошибок? Каскадные коды, полиномиальное декодирование. Код Адамара и его локальность. Многочлены от нескольких переменных. Кодирование и вероятностная проверка равенства.

Date and time Class|Name Venue|short Materials
19 November
11:15–12:45
Лекция I, lecture ПОМИ РАН No
19 November
13:00–14:30
Лекция II, lecture ПОМИ РАН No