Алгеброгеометрические методы избыточного кодирования информации

• Автор: Степанов, Михаил Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 93 с. : ил.

Оглавление
Введение

1 Алгеброгеометрические коды

1.1 Введение в алгебраическую геометрию .

1.1.1 Аффинные и проективные многообразия

1.1.2 Локальное кольцо в точке.

1.1.3 Дивизоры. Линейное пространство, заданное на дивизоре.

1.2 Коды на кривых

1.3 Некоторые алгеброгеометрические коды.

1.3.1 Коды рода ноль.

1.3.2 Эллиптические коды.

1.3.3 Эллиптические коды Грайсмера.
1.3.4 Коды Эрмита
1.4 Заключение и выводы по главе.
2 Множества, свободные от покрытий
2.1 Определения и обозначения
2.2 МСП и коды, исправляющие ошибки .
2.2.1 Построение МСП на кодах, исправляющих ошибки .
2.2.2 Параметры МСП на кодах РидаСоломона и эллиптических кодах
2.2.3 Анализ МСП, построенных на кодах РидаСоломона . .
2.2.4 Сравнение МСП, построенных на кодах РидаСоломона
и эллиптических кодах.
2.2.5 Примеры
2.3 Использование МСП.
2.3.1 Построение каскадных конструкций
2.3.2 Способ применения и использование МСП в системах связи.
2.3.3 Способ применения и использование МСП для задачи распознавания образов.
2.4 Заключение и выводы по главе
3 Быстрые вычисления на кривой в поле характеристики 3
3.1 Эллиптические кривые .
3.2 Группа точек на эллиптической кривой
3.3 Кривые, заданные над где р 2,3.
3.4 Кривые, заданные над полем характеристики 2.
3.5 Арифметика эллиптических кривых, заданных над полем характеристики 3
3.6 Алгоритмы умножения скаляра на точку
3.6.1 Алгоритм, использующий двоичное представление скаляра .
3.6.2 Алгоритм, использующий сбалансированное двоичное представление скаляра.
3.6.3 Метод окна.
3.6.4 Совместное умножение скаляров на точки
3.6.5 Использование эндоморфизмов для быстрых вычислений
3.6.6 таддическое представление скаляра
3.6.7 Метод разбиения.
3.7 Умножение скаляра на точку в поле характеристики 3
3.7.1 Представление скаляра.
3.7.2 Уменьшение длины последовательности.
3.7.3 Тернарное знаковое представление
3.7.4 Использование метода разделения.
3.7.5 Обобщающий метод
3.8 Заключение и выводы по главе
Заключение
Литература


Введение в алгебраическую геометрию . Локальное кольцо в точке. Дивизоры. Линейное пространство, заданное на дивизоре. Некоторые алгеброгеометрические коды. Коды рода ноль. Эллиптические коды. Эллиптические коды Грайсмера. Заключение и выводы по главе. МСП и коды, исправляющие ошибки . Построение МСП на кодах, исправляющих ошибки . Анализ МСП, построенных на кодах Рида-Соломона . Использование МСП. Способ применения и использование МСП в системах связи. Способ применения и использование МСП для задачи распознавания образов. Эллиптические кривые . Кривые, заданные над где р ^ 2,3. Кривые, заданные над полем характеристики 2. Алгоритм, использующий двоичное представление скаляра . Алгоритм, использующий сбалансированное двоичное представление скаляра. Метод окна. Метод разбиения. Представление скаляра. Уменьшение длины последовательности. Использование метода разделения. Актуальность темы. В настоящее время получили широкое распространение и продолжают быстро развиваться области, связанные с обработкой и передачей данных в беспроводных сетях, системах хранения данных, космической связи. Важной задачей является повышение эффективности существующих методов передачи и хранения информации. В том числе и повышение эффективности методов помехоустойчивого кодирования, используемых в этих системах. Одним из способов повышения эффективности методов помехоустойчивого кодирования является поиск и построение оптимальных кодов, а именно кодов, лежащих на верхних границах существования. В последние десятилетия методы алгебраической геометрии нашли применение в теории помехоустойчивого кодирования. Алгеброгеометрические коды представляют собой широкий класс эффективных кодов, исправляющих ошибки. Среди кодов, построенных на модулярных кривых, были найдены коды, параметры которых лежат выше асимптотической границы Варшамова-Гильберта. Существуют алгеброгеометрические коды, близкие к верхним границам существования. Для реализации процедур построения алгеброгеометрических кодов необходимо быстро вычислять различные преобразования над точками кривой. Поэтому задача быстрых преобразований является актуальной. Как качество алгеброгеометрических кодов, так и эффективность вычислительных алгоритмов, использующих кривые, зависит от выбора соответствующей кривой. Однако вопросы выбора кривых для указанных приложений остаются в значительной степени открытыми. Несмотря на многочисленные работы в этом направлении, в общем случае задача выбора "оптимальной" кривой остается нерешенной. Основной целью работы разработка и исследование методов использования эллиптических кривых в задачах избыточного кодирования информации. Методы исследования. Для решения поставленных задач используются методы алгебраической теории кодирования, алгебры, алгебраической геометрии, комбинаторики и теории сложности алгоритмов. Практическая ценность и реализация результатов. Практическая ценность работы заключается в том, что в ней предложен способ построения нового оптимального подкласса д-ичных кодов. Использование таких кодов позволяет улучшить существующие системы передачи информации. Кроме того, были предложены эффективные методы умножения скаляра на точку на эллиптической кривой, обладающие преимуществами перед известными методами. Публикации. Основные результаты работы отражены в 8 публикациях. Из них 2 работы опубликованы в журналах, входящих в список ВАК. Структура работы. Диссертация состоит из введения, трех глав, заключения и списка использованной литературы. Работа изложена на страницах. Основное содержание работы включает рисунков, 8 таблиц и алгоритмов. Первая глава посвящена сведениям, необходимым для построения алгеброгеометрических кодов. Показаны различные конструкции алгеброгеометрических кодов и доказано, что подкласс эллиптических кодов будет лежать на границе Грайсмера.