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

Коды на графах
Теория кодирования


Что: Лекция
Когда: Воскресенье, 01 апреля 2012, 15:35–17:10
Где: ПОМИ РАН

Описание

Проверочная матрица линейного кода как матрица смежности двудольного графа. Двудольные экспандеры и экспандерные коды. Лемма об уединенных соседях. Простейшая оценка снизу для расстояния экспандерного кода. Алгоритм декодирования экспандерного кода для графа с коэффициентом расширения больше \( 3/4 \) (от степени вершин в левой доле графа). Алгоритм Видермана декодирования экспандерного кода для графа с коэффициентом расширения больше \( 2/3 \). Коды на графах, исправляющих стирания: идея цифрового фонтана и raptor-кода.

Видео