Кафедра математической логики и теории алгоритмов

Дневник лекций 2015 года

21 января 2015

Общая постановка задачи про передачу информацию по каналу с искажениями. Ошибки и
стирания. Коды, кодовое расстояние и другие его параметры.

Коды Хемминга.

28 января 2015

Неравенство Синглтона.

Коды Рида — Соломона и эффективное исправление ошибок для них.

4 февраля 2015

Оценка Гилберта (построение кода жадным алгоритмом).
Оценка Гилберта для линейных кодов (построение кода вероятностным алгоритмом).
Оценка Варшамова — Гилберта для линейных кодов (построение жадным алгоритмом в двух
домашних задачах.

Каскадные коды.

11 февраля 2015

Эффективный алгоритм исправления ошибок и пропусков в каскадном коде.

18 февраля 2015

Коды Форни (конкатенация кода Рида-Соломона и
кода на границе Гилберта).

Коды Возенкрафта и их обобщение.

Коды Форни — Возенкрафта — Юстесена.

25 февраля 2015

Оценка Плоткина для бинарного алфавита: сначала для относительного расстояния
не меньше 1/2, затем для произвольных относительных расстояний.

Оценка Плоткина для любого алфавита.

4 марта 2015

Коды БЧХ

11 марта 2015

Код Адамара. Вероятностный алгоритм исправления ошибок в
коде Адамара. Рид-Соломон плюс Адамар.

Декодирование списком с исправлением ошибок. Аналоги оценок Хэмминга и Гилберта
для декодирования списком с исправлением ошибок.

18 марта 2015

Декодирование списком кода Адамара.

Декодирование списком кода с данным расстоянием.

Оценка Джонсона для бинарных кодов.

25 марта 2015

Лекции нет (сессия между модулями).

1 апреля 2015

Оценка Элайеса — Бассалыго.

Декодирование списком кодов Рида — Соломона.

8 апреля 2015

Декодирование списком каскадного кода Рид-Соломон + Адамар.

15 апреля 2015

Декодирование списком кода Адамара с исправлением n/2(1-eps) ошибок
за полиномиальное от длины сообщений, 1/eps и вероятности ошибки время.

Применение этого алгоритма в протоколах электронной монеты на основе
односторонней функции.

22 апреля 2015

Экспандерные коды. Связь кодового расстояния с параметрами экспандера.
Быстрый алгоритм исправления ошибок в экспандерном коде.

Существование экспандеров и экспандерного кода для положительных значений
скорости передачи и относительного кодового расстояния.

29 апреля 2015

Параметры экспандерных кодов.

Коды Рида-Маллера и их параметры.

13 мая 2015

Локально декодируемые и корректируемые коды. Связь с количеством
нелокально исправляемых ошибок.
Локальная коррекция влечет локальное декодирование для линейных кодов.
Процедура локальной
коррекции для кодов Рида — Маллера.

20 мая 2015

Экзамен для 3 и 4 курсов.

27 мая 2015

Процедуры локальной коррекции для кодов Рида — Маллера
с помощью декодирования кода Рида — Соломона вдоль прямых и парабол.

3 июня 2015

Кратностные коды.