Раздел 3. Алгеброгеометрические коды

Девятый семестр, 2012-2013 учебный год

Необходимые сведения из алгебры

Основные структуры алгебры: группы, кольца, поля, векторные пространства. Теория систем линейных уравнений с коэффициентами из некоторого поля. Теория делимости в кольце многочленов над полем. Теория линейных отображений векторных пространств. Теория идеалов в коммутативных кольцах. Теория конечных полей.

Раздел 1. Основы теории кодирования: блочные коды

Простейшая модель канала связи с шумом, блочные коды. Метрика Хэмминга на аффинном пространстве над конечным полем, её свойства. Вес слова. Параметры блочного кода: избыточность кода, скорость передачи, минимальное кодовое расстояние. Что значит, что блочный код обнаруживает/исправляет до t ошибок. Критерий обнаружения блочным [n,k,d]_q-кодом ошибок. Принцип максимального правдоподобия при декодировании и вероятностное обоснование его оптимальности. Критерий исправления блочным [n,k,d]_q-кодом ошибок. Граница Хэмминга, шары и сферы в аффинном пространстве, количество точек в шаре. Совершенные коды. Теорема о параметрах совершенных кодов (без док-ва). Двоичные коды с проверкой на чётность и n-кратным повторением символа. Коды Хэмминга и их совершенность. Декодирование двоичных кодов Хэмминга.

Раздел 2. Линейные коды и [n,k,d]q-системы

Определение блочного линейного [n,k,d]q-кода. Лемма о минимальном кодовом расстоянии для линейного кода. Кодирующая, или порождающая, матрица линейного кода, ранг кодирующей матрицы. Проверочная матрица линейного кода и ее свойства: критерий принадлежности сообщения пространству кодовых слов, алгоритм вычисления минимального кодового расстояния для линейного кода с помощью проверочной матрицы. Пример – вычисление минимального кодового расстояния для кодов Хэмминга. Гиперплоскости в конечномерных пространствах, количество гиперплоскостей в F_q^k_. Лемма о попадании k-1 точки в некоторую гиперплоскость, количество точек в гиперплоскости. Понятие [n,k,d]q-системы точек в конечномерном пространстве. Теорема о взаимнооднозначном соответствии между [n,k,d]q-линейными кодами и [n,k,d]q-системами. Граница Синглтона. Понятие МДР-кода. Коды Рида-Соломона – примеры МДР-кодов. Двоичные линейные коды – групповые коды. Таблица для декодирования группового кода посредством лидеров. Теорема об исправляемых ошибках при декодировании посредством лидеров. Декодирование посредством лидеров наименьшего веса. Методика полиномиального кодирования, матрица полиномиального кода. Циклические коды, реализация множества сообщений как факторкольца кольца многочленов, доказательство полиномиальности циклических кодов, особенности кодирующего многочлена и его корней. Построение кодирующего многочлена для циклического кода путем задания его корней. БЧХ-коды, конструктивное расстояние для БЧХ-кода. Примеры БЧХ-кодов: двоичные и троичные коды Голея. Особенности декодирования циклических кодов: случаи малой и большой скоростей передачи. Пример: декодер для двоичного и троичного кодов Голея.

Раздел 3. Алгеброгеометрические коды

Аффинное и проективное пространства над произвольным полем. Количество точек в аффинном n-мерном пространстве и проективном n-мерном пространстве над конечным полем из q элементов. Представление проективной плоскости в виде объединения аффинных частей. Аффинные и проективные плоские кривые: определения, примеры. Точки аффинных и проективных кривых. Неприводимые кривые, примеры. Кольцо регулярных функций аффинной кривой: пример – кольцо регулярных функций окружности. Поле рациональных функций аффинной кривой, пример – поле рациональных функций окружности. Особые и простые точки аффинной и проективной кривой, гладкие кривые. Проективные плоские кривые, их аффинные части, пример – проективная кривая второго порядка. Поле рациональных функций проективной кривой, гладкие кривые: пример – эллиптические кривые как гладкие плоские проективные кривые третьей степени, бесконечно удаленная точка эллиптической кривой, аффинная часть и ее уравнение. Локальное кольцо точки, максимальный идеал точки на кривой. Локальный параметр в простой точке на кривой, введение функции порядка на поле рациональных функций на кривой. Дивизоры на кривой: группа дивизоров, степень дивизора, носитель дивизора, эффективные дивизоры, всякий дивизор есть разность двух эффективных дивизоров, главные дивизоры, дивизоры нулей и полюсов рациональной функции, теорема о степени главного дивизора на гладкой проективной кривой. Пространство, ассоциированное с дивизором на кривой, и его конечномерность. L-конструкция и (X,P,D)_L-коды. Теорема о параметрах L-конструкции. Примеры: одноточечные коды на проективной прямой (коды Рида-Соломона) и на эллиптической кривой. Алгеброгеометричность произвольного линейного кода (без док-ва).

 

Программу составил доц. С. Ю. Попов 10 декабря 2012 года