Анализ эффективности декодирования циклических кодов с использованием двойственного базиса

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

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

1. Аспекты применения двойственного базиса поля Галуа.

1.1. Двойственный базис поля Галуа

1.2. Применение двойственного базиса.

1.3. Проблемы работы с полями Галуа

1.4. Выводы. Задачи диссертационной работы.

2. Анализ эффективности декодирования двоичных циклических кодов

2.1. Особенности построения двоичных циклических кодов.

2.1.1. Двоичные циклические коды БЧХ.

2.1.2. Построение циклических кодов как рекурсивных последовательностей

2.1.3. Коды максимальной длины..
2.2. Методы декодирования циклических кодов
2.2.1. Оцениваемые параметры системы передачи данных.
2.2.2. Алгебраический декодер. Таблица остатков
2.2.3. Корреляционный метод
2.2.4. Синдромный метод декодирования кодов БЧХ
2.3. Обработка рекуррентных последовательностей двойственным базисом поля Галуа .
2.3.1. Декодрование кодов максимальной длины.
2.3.2. Использование децимаций при декодировании кодов максимальной длины
2.3.3. Декодирование кодов БЧХЭ
2.3.4. Эффективность методов декодирования кодов БЧХ.
2.4. Выводы
3. Разработка методов оценки качества канала.
3.1. Особенности методов оценки качества канала.
3.2. Разработка методов оценки качества канала на основе двойственного базиса.
3.2.1. Метод разности двух наибольших деревьев
3.2.2. Метод оценки канала по частоте появления деревьев
3.2.4. Выбор метода оценки канала.
3.3. Выводы.
4. Разработка методики адаптации системы к состоянию канала.
4.1. Подходы к построению адаптивных систем.
4.2. Система с адаптивным выбором кода
4.3. Выводы.
5. Разработка инструментария для работы в полях Галуа
5.1. Программная реализация калькулятора Галуа
5.1.1. Формирование поля и его хранение.
5.1.2. Реализация базовых операций в калькуляторе Галуа.
5.1.3. Особенности работы с полем большого порядка
5.1.4. Метод контрольных точек
5.2. Организация калькулятора Галуа.
5.2.1. Структура калькулятора Галуа.
5.2.2. Калькулятор Галуа для работы в локальной сети
5.2.3. Калькулятора Галуа для работы в глобальной сети
5.3. Выводы.
Заключение. Выводы диссертационной работы.
Список литературы


Данные действия над элементами выполняются в соответствии со свойствами конечных полей, вместе с этим могут быть реализованы как классические математические операции. Например, умножение двух элементов поля е' и г7 легко представить как сложение показателей степеней элементов /я = (/ + у)тос1н. В результате обратного преобразования получается искомый элемент поля е". Аналогичным образом осуществляется деление одного элемента поля на другой ненулевой элемент, но вместо сложения показателей степеней производится вычитание. Таким образом, представление элементов поля как показателей степеней является наиболее удобным при проведении некоторых математических операций над ними. Для сравнения приведем пример реализации алгоритма умножения элементов поля в векторном виде []. Ь2є2 + . Умножение многочленов (1. V = (a„&0) + («A +аД)є + (а<Д +e,6, + «2і0)є2 + - + . В результате из (1. Элементу поля sm, выраженному через левый степенной базис (1. Fk = а0Е + a}F + a2F2 +. Fk~', (1. F— характеристическая матрица. С учетом (1. Лы)Р' =(a0arak. E + b,F + . F,-') = ba(. F) +. Fk-') = (c0c,. Что касается такой математической операции, как сложение элементов, то здесь использование показателей степеней оказывается бесполезным. Для выполнения этой операции требуется обязательное представление элементов поля через левый степенной базис (1. Сложение многочленов (1. Ьк_х)хк~ (1. Запишем равенство (1. Переход от (1. Другой важной задачей является обращение элемента поля. В работе [] описан метод нахождения обратного элемента на основе алгоритма Евклида, предполагающий решение системы уравнений. При этом, с увеличением характеристики поля к сложность вычислений возрастает. При обращении элемента поля d можно воспользоваться свойством конечного поля GF(2*), ненулевые элементы которого образуют циклическую мультипликативную группу порядка 2к-. Из равенства (1. Как видно из вышеприведенных равенств, установление соответствия между элементом и показателем его степени позволяет значительно упростить логику вычислений в полях Галуа, сводя действия над элементами к математическим операциям классического вида с организацией переходов от векторного вида к степенному и обратно. Введем понятия логарифма в конечном поле. Известно, что любой элемент d поля GF(2*) может быть представлен многочленом (1. Возьмем логарифм по основанию s от левой и правой части (1. Для целочисленных значений i данный вид логарифма принято называть дискретным [, ]. Смысл операции (1. Показатель степени может принимать значения і =0; 1; 2; . Операция, противоположная (1. В этом случае необходимо найти вектор при известном показателе степени элемента. Из (1. Процедура дискретного логарифмирования используется при решении задач декодирования помехоустойчивых кодов, а также в современных криптографических системах. Определение-дискретного логарифма в конечном поле является достаточно сложной задачей, поэтому ей уделено повышенное внимание как в отечественных [, ], так и в зарубежных работах [ - ]. В частности безопасность протокола шифрования Диффи-Хсллмана [] и эффективность применения схемы Эль-Гамаля [] в криптографических системах основаны на трудности вычисления дискретного логарифма в конечном поле. Трудности, возникающие при вычислении дискретного логарифма и антилогарифма в поле Галуа, проявляются при росте порядка поля. Так для поля с параметром к= 4 будет определено ненулевых элементов, для &=8 их будет 5, а для к= порядок поля превысит 4-Ю9 элементов. Очевидно, что определение дискретного логарифма в поле ОР(2) является сложной задачей, требующей значительных затрат ресурсов системы. Поэтому для больших полей1 при к> целесообразно применение сложных алгоритмов дискретного логарифмирования. В настоящее время одним из самых эффективных методов вычисления дискретного логарифма в конечном поле является метод Полларда []. Также большой интерес представляют эллиптические кривые, при использовании которых возникают обширные перспективы в области криптографии. При помощи эллиптических кривых имеется возможность вычисления дискретных логарифмов в полях Галуа большого порядка [, ].