Теория, методы и алгоритмы решения задач в телекоммуникациях на основе двойственного базиса и рекуррентных последовательностей

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

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

ЧАСТЫ. ТЕОРЕТИЧЕСКИЕ И РЕАЛИЗАЦИОННЫЕ ОСНОВЫ РЕШЕНИЯ МОДУЛЯРНЫХ РАЗНОСТНЫХ УРАВНЕНИЙ ОДНОРОДНЫХ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
1. Линейные рекуррентные последовательности над конечным полем СЁ(р) и их особенности

1.1. Определение и основные свойства линейных рекуррентных последовательностей

1.2. Рекуррентные последовательности максимального периода (М-последовательности) над полем СР(р) и их свойства

1.3. Формирование линейных рекуррентных последовательностей

2. Аналитическое решение линейных модулярных возвратных уравнений над конечным полем

2.1. Решение однородных линейных МРУ на основе г-преобразования над конечным полем

2.2. Двойственный базис конечного поля и его применение для решения однородных линейных МРУ
2.3. Матричный метод решения линейных возвратных уравнений над полем СР(рк) по к произвольным линейно-независимым элементам рекуррентной последовательности
2.4. Сравнение предложенных вариантов решения линейных МРУ
3. Составные рекуррентные последовательности над полем СЕ(р*) с приводимым характеристическим многочленом и
их обработка с использованием двойственного базиса
3.1. Последовательности Гоулда и их свойства
3.1.1. Класс «зеркальных» последовательностей Гоулда
3.2. ЛРД-последовательности и их свойства

3.3. Решение линейных уравнений составных рекуррентных последовательностей над полем (рк) на основе двойственного базиса
3.4. Обработка последовательностей Гоулда и ЛРД-последователь-ностей
3.4.1. Алгоритм быстрого поиска ЛРД-последовательности
3.4.2. Обработка последовательностей Гоулда и составных ЛРД-пос-ледовательностей с использо-ванием двойственного базиса поля GF(2n)
3.5. Прямые и инверсные рекуррентные последовательности
4. Основы реализации алгоритмов обработки рекуррентных
последовательностей над полем бД(рл)
4.1. Матричное представление элементов поля
4.2. Генераторы элементов поля вД(р'<)
4.2.1. Генерация прямых элементов поля
4.2.2. Генерация обратных элементов поля бД(рк)
4.3. Реализация умножения и деления элементов поля бД(р'<)
4.3.1. Матричный способ умножения элементов поля
4.3.2. Деление элементов поля через операцию обращения делителя
и матричное умножение
4.4. Способы обращения элементов поля бД(2к)
4.4.1. Нахождение обратного элемента через умножение “сопряженных" элементов
4.4.2. Нахождение обратного элемента обращением сопровождающей матрицы
4.4.3. Определение обратного элемента на основе двух модульных регистров
4.5. Реализация процедуры нахождения функции следа
4.6. Использование операций логарифмирования и антилогарифмирования при выполнении действий над элементами поля ОР(рк)

4.6.1. Умножение, деление и обращение элементов ПОЛЯ с использованием операций логарифмирования и антилогарифмирования
4.6.2. Табличные алгоритмы реализации операций логарифмирования и антилогарифмирования над элементами поля GF(pk)
4.6.3. Аналитический метод реализации операций логарифмирования
и антилогарифмирования над элементами поля GF(2k)
4.7. Формирование линейных рекуррентных последова-тельностей
на примере М-последовательностей
4.7.1. Генератор М-последовательности на основе простого рекуррентного регистра сдвига с обратными связями
4.7.2. Генератор М-последовательности на основе модульного регистра сдвига. Каноническая М-последовательность
4.7.3. Формирование недвоичных М-последовательностей
4.8. Формирование двойственного базиса поля
4.9. Преобразование элементов поля GF(pk) в соответствующие
элементы линейной рекуррентной последовательности и обратное преобразование
4.10. Алгоритм упрощенной реализации умножения на двоичную матрицу над полем GF(2к)
ЧАСТЬ 2. ПРИМЕНЕНИЕ ДВОЙСТВЕННОГО БАЗИСА В ЗАДАЧАХ ПЕРЕДАЧИ И ОБРАБОТКИ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
5. Алгоритмы декодирования комбинаций эвидистантного
циклического кода
5.1. Декодирование эквидистантных циклических кодов методом
корреляционной обработки
5.2. Мажоритарная обработка рекуррентных последовательностей максимальной длины на основе ортогональных проверок
5.3. Мажоритарные алгоритмы декодирования комбинаций эквидистантного циклического кода по k-элементным участкам
5.3.1. Матричное мажоритарное декодирование комбинаций
эквидистантного циклического кода

Таким образом, общее выражение у„ в соответствии с (2.15) при заданном начальном состоянии последовательности (у» .у, s2 s3) = (1 100) имеет вид:
5« = Т(е”+]3) = Т(е"со), GF(24).
Действительно, из этого выражения, при Р(х) = х4 + х + 1, можно определить, что начальные члены последовательности совпадают с заданными: sQ = Т(е13) = 1; 5] = T(s и) = 1; 52 =Т(1) = = 0; 53 = Т(е ) = 0. Так же может быть определен и любой другой член последовательности. Например, для п =
Sh = s8 = 7V1+13) = 71>6) = 1.
Пример 2.2. Рассмотрим теперь однородную рекуррентную последовательность {.у} над полем GF(3), которой удовлетворяет характеристический многочлен Р(х) — ррк - рх2 - р2х - рз , р,<= GF(3), у которого ро —р2 - Р,р = 0;р3 = 2, т.е. Р(х) = х3 — х — 2.
Тогда мы будем иметь рекуррентную последовательность 3-го порядка, члены которой будут удовлетворять рекуррентному уравнению: s,,+3 =Ps„+2 +PiS„+ + PiS„ = s„+i + 2sn GF(3).
Как было показано в первом разделе, генераторы рекуррентной последовательности {.у} могут быть построены на базе регистров сдвига, либо с вынесенными, либо со встроенными сумматорами по модулю р — Ъ.
Для построения генератора на базе регистра сдвига с вынесенными сумматорами составим матрицу Т, которая имеет вид:
р, 1 0' 'о 1 0'
т= Рг 0 1 = 1 0
.Рг 0 0 2 0
и для второго варианта ? матрицу F, имеющую вид:
‘0 1 0' '0 1
F = 0 0 1 = 0 0
_р, Рг р,_ 2 1
Легко проверить, что характеристический многочлен Р(х) полностью определяется характеристическими матрицами и определяется как Р(х) = бН хЕ - 71 = с!е! хЕ - Е = х3 -рХ2 -р2х-рз = х3 - х - 2.
Построенные по матрицам Т и Е1 генераторы рекуррентной последовательности 3-го порядка над полем ОР(3) показаны на рис.2.1.
Если в регистр с вынесенным сумматором (рис.2.1, а) записать в качестве начальных элементы (у0 5т х2) = (101), то на выходе получим следующую рекуррентную последовательность:
{5} = (уо 51 52 53 54 У5 Яь 57 58 59 5]0 5ц 512 513 5Ы 515 51б 5П 5]8 5]9 520 521 522 523 524 525) = 10121120111 00202 1 22 1 0222 00. Как видно, мы получили псевдослучайную последовательность максимальной длины (М-последовательность) с периодом _Л/=р3-1=26. Эта последовательность, как следует из свойства 1.2.6, состоит из двух подпоследовательностей одинаковой длины, одноименные члены которых