Дневник лекций 2012 года
13-Feb-2012
Оценка Хэмминга и граница Гилберта
Линейные коды и граница Гилберта-Варшамова.
20-Feb-2012
Коды Хэмминга.
Неравенство Синглтона.
Коды Рида-Соломона.
27-Feb-2012
Каскадные коды.
Коды Форни.
5-Mar-2012
Коды Возенкрафта. Использование кодов Возенкрафта в
каскадных кодах — коды Форин-Возенкрафта-Юстесена.
Оценка Плоткина (начало)
12-Mar-2012
Коды Возенкрафта — обобщение и исправление ошибки.
Оценка Плоткина (завершение). Улучшение оценки Синглтнона.
Коды Адамара. Исправление вероятностным полиномиальным от длины
сообщения алгоритмом чуть менее чем четверти ошибок.
19-Mar-2012
Коды Рида-Маллера.
Коды БЧХ.
26-Mar-2012
Коды БЧХ и коды Хэмминга.
Декодирование списком, оценка Хэмминга.
2-Apr-2012
Декодирование списком размера n+1 любого кода с данным
кодовым расстоянием. Декодирование списком постоянного размера
кода Адамара с исправлением (1-\eps)n/2 ошибок.
Оценка Джонсона. Оценка Элайеса-Бассалыго — улучшение улучшенной
оценки Синглетона и оценки Хэмминга.
9-Apr-2012
Декодирование списком за полиномиальное время
кода Рида-Соломона.
16-Apr-2012
Декодирование списком за полиномиальное время
каскадного кода (Рида-Соломона+Адамар).
Вероятностный алгоритм декодирования списком за полиномиальное время
от длины кодируемого слова кода Адамара.
23-Apr-2012
Экспандерные коды низкой плотности и их декодирование
за полиномиальное время.
Вероятностная конструкция эскпандера и параметры получающегося экспандерного
кода.
28-Apr-2012
NP трудность задачи поиска в решетке вектора, ближайшего к данному.
7-May-2012
Локально декодирумые и локально корректируемые коды.
Преобразование локально корректируемого линейного кода в
локально декодируемый. Кодовое расстояние локально корректируемого
кода.
Локальная коррекция кодов Рида-Маллера: коррекция с помощью прямых,
улучшенная коррекция с помощью прямых и коррекция с помощью
квадратичных многочленов.
14-May-2012
Кратностные коды (multiplicity codes) на основе многочленов
от двух переменных и производных первого порядка.
Общее определение кратностных кодов.