Коды с исправлением ошибок

Постановка задачи и основные границы. Канал с ошибками и стираниями Код: алфавит, размерность, длина блока, минимальное кодовое расстояние. Связь расстояния с числом исправляемых ошибок. Скорость и относительное расстояние. Граница Синглтона. Граница Хэмминга. Объём шара Хэмминга, функция Шеннона, асимптотический вид границ для двоичного и произвольного алфавита. Граница Гилберта; граница Варшамова—Гилберта и жадный алгоритм.
Линейные коды и классические конструкции. Линейные коды. Коды Рида—Соломона и их декодирование от ошибок. Коды Хэмминга $[2^m-1,2^m-m-1,3]_2$ и $[2^m,2^m-m-1,4]_2$, кодирование и декодирование. Случайные линейные коды. Коды Возенкрафта. Коды Рида—Маллера и их кодовое расстояние. Коды БЧХ; связь БЧХ с кодами Хэмминга.
Каскадные коды и явные асимптотически хорошие коды. Каскадное кодирование. Полиномиальное декодирование каскадных кодов от $(d-1)/2$ ошибок. Теорема Форни. Коды Форни—Возенкрафта—Юстесена. Коды с малой плотностью проверок на чётность (LDPC) и их связь с экспандерами.
Верхние границы параметров кода. Геометрические леммы для границ Плоткина. Первая граница Плоткина. Вторая граница Плоткина для двоичного и для произвольного алфавита. Улучшенная граница Синглтона. Граница Джонсона. Граница Элайеса—Бассалыго.
Декодирование списком и локальные алгоритмы. Коды Адамара и расширенные коды Адамара; рандомизированное декодирование за время $\mathrm{poly}(\log n)$. Декодирование списком: определение, объёмная граница, теорема Элайеса как достаточное условие. Кодовое расстояние и декодирование списком. Декодирование списком кодов Адамара со списком постоянного размера; теорема Голдрайха—Левина. Декодирование списком кодов Рида—Соломона. Композиция Рида—Соломона с Адамаром и её декодирование списком.