Город: Санкт-Петербург Казань Язык: Русский English

Ликбез: коды, исправляющие ошибки
Санкт-Петербург / осень 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

План курса:

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

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

Дата и время Название Место Материалы
19 ноября
11:15–12:45
Лекция I, лекция ПОМИ РАН Нет
19 ноября
13:00–14:30
Лекция II, лекция ПОМИ РАН Нет