Дневник лекций 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
Кратностные коды.