Введение
Часты. Теоретические и реализационные основы решения модулярных разностных уравнений однородных линейных рекуррентных последовательностей 19
1. Линейные рекуррентные последовательности над
конечным полем GF(p) и их особенности 19
1.1. Определение и основные свойства линейных рекуррентных последовательностей 19
1.2. Рекуррентные последовательности максимального периода (М-последовательности) над полем GF(p) и их свойства 22
1.3. Формирование линейных рекуррентных последовательностей 24
2. Аналитическое решение линейных модулярных возвратных уравнений над конечным полем 30
2.1. Решение однородных линейных МРУ на основе z-преобразова-ния над конечным полем 31
2.2. Двойственный базис конечного поля и его применение для решения однородных линейных МРУ 39
2.3. Матричный метод решения линейных возвратных уравнений над полем GF(pk) по к произвольным линейно-независимым элементам рекуррентной последовательности 54
2.4. Сравнение предложенных вариантов решения линейных МРУ 61
3. Составные рекуррентные последовательности над полем GF(p*) с приводимым характеристическим многочленом и их обработка с использованием двойственного базиса 64
3.1. , Последовательности Гоулда и их свойства 64
3.1.1. Класс «зеркальных» последовательностей Гоулда 66
3.2. ЛРД-последовательности и их свойства 70
3.3. Решение линейных уравнений составных рекуррентных последовательностей над полем GF^) на основе двойственного базиса 74
3.4. Обработка последовательностей Гоулда и ЛРД-последователь-ностей 83
3.4.1. Алгоритм быстрого поиска ЛРД-последовательности 83
3.4.2. Обработка последовательностей Гоулда и составных ЛРД-пос-ледовательностей с использо-ванием двойственного базиса поляСР(2") 84
3.5. Прямые и инверсные рекуррентные последовательности 89
4. Основы реализации алгоритмов обработки рекуррентных последовательностей над полем GF(pk) 98
4.1. Матричное представление элементов поля GF(pk) 98
4.2. Генераторы элементов поля GF(pk) 99
4.2.1. Генерация прямых элементов поля 99
4.2.2. Генерация обратных элементов поля GF{pk) 101
4.3. Реализация умножения и деления элементов поля GF(pk) 103
4.3.1. Матричный способ умножения элементов поля 103
4.3.2. Деление элементов поля через операцию обращения делителя и матричное умножение 108
4.4. Способы обращения элементов поля GF(2k) 108
4.4.1. Нахождение обратного элемента через умножение "сопряженных" элементов 108
4.4.2. Нахождение обратного элемента обращением сопровождающей матрицы 110
4.4.3. Определение обратного элемента на основе двух модульных регистров 112
4.5. Реализация процедуры нахождения функции следа 115
4.6. Использование операций логарифмирования и антилогарифмирования при выполнении действий над элементами поля GF(pk) 117
4.6.1. Умножение, деление и обращение элементов ПОЛЯ с использованием операций логарифмирования и антилогарифмирования 117
4.6.2. Табличные алгоритмы реализации операций логарифмирования и антилогарифмирования над элементами поля GF(pk) 118
4.6.3. Аналитический метод реализации операций логарифмирования и антилогарифмирования над элементами поля GF(2k) 120
4.7. Формирование, линейных рекуррентных последова-тельностей на примере М-последовательностей 131
4.7.1. Генератор М-последовательности на основе простого рекуррентного регистра сдвига с обратными связями 131
4.7.2. Генератор М-последовательности на основе модульного регистра сдвига. Каноническая М-последовательность 133
4.7.3. Формирование недвоичных М-последовательностей 136
4.8. Формирование двойственного базиса поля 140
4.9. Преобразование элементов поля GF(pk) в соответствующие элементы линейной рекуррентной последовательности и обратное преобразование 144
4.10. Алгоритм упрощенной реализации умножения на двоичную матрицу над полем GF(2k) 147
ЧАСТЬ 2. Применение двойственного базиса в задачах передачи и обработки линейных рекуррентных последовательностей 153
5. Алгоритмы декодирования комбинаций эвидистантного циклического кода 154
5.1. Декодирование эквидистантных циклических кодов методом корреляционной обработки 157
5.2. Мажоритарная обработка рекуррентных последовательностей максимальной длины на основе ортогональных проверок 161
5.3. Мажоритарные алгоритмы декодирования комбинаций эквидистантного циклического кода по k-элементным участкам 165
5.3.1. Матричное мажоритарное декодирование комбинаций эквидистантного циклического кода 166
5.3.2. Мажоритарное декодирование комбинаций эквидистантного циклического кода по k-элементным участкам на основе двойственного базиса GF(pk) 170
5.3.3. Декодирование децимированных комбинаций эквидистантного циклического кода с использо-ванием двойственного базиса поляОР(рк) 176
5.4. Декодирование комбинаций эквидистантного циклического кода
по к произвольным линейно независимым ее элементам 185
5.5. Эквидистантный циклический код (М-последовательность) в
конечных полях с двойным расширением 187
6. Декодирование дуальных циклических кодов БЧХ и Рида-Соломона, как рекуррентных последовательностей, с использованием двойственного базиса 190
6.1. Декодирование кодов БЧХЭ на основе многочленов Мэттсона-Соломона 192
6.2. Циклические коды БЧХЭ и их декодирование с использованием двойственного базиса 198
6.3. Мажоритарное декодирование децимированных комбинаций кода БЧХЭ над полем GF(2k) на основе m-элементных участков с использованием двойственного базиса 204
6.4. Принципы реализации кодирующих и декодирующих устройств кодов БЧХЭ как рекуррентных последовательностей 215
6.5. Дуальные коды Рида-Соломона как рекуррентные последовательности и их декодирование с использованием двойственного базиса 227
6.6. Укороченные циклические коды как рекуррентные последовательности 246
7. Применение двойственного базиса поля GF(pk) в задачах циклового фазирования 253
7.1. Поиск рекуррентной последовательности в асинхронных системах передачи данных методом последовательного оценивания 256
7.1.1. Рекуррентный поиск по методу Уорда и его анализ 256
7.1.2. Рекуррентный поиск с решением по «скользящему» зачетному участку и его анализ 266
7.1.3. Обнаружение М-последовательности как фазирующей комбинации методом последовательного оценивания с использованием двойственного базиса 271
7.1.4. Обнаружение последовательностей Гоулда или ЛРД-после-довательностей как фазирующих комбинаций в асинхронных системах с использованием двойственного базиса 276
7.2. Цикловое фазирование в синхронных системах передачи данных 283
7.2.1. Использование двойственного базиса для обработки /с-эле-ментных участков М-последовательностей как комбинаций циклового фазирования в синхронных системах передачи данных 284
7.2.2. Обработка последовательностей Гоулда и ЛРД-последователь-ностей как фазирующих комбинаций в синхронных системах передачи данных с использованием двойственного базиса 288
7.2.3. Цикловое фазирование приемника синхронной системы по к произвольным линейно независимым элементам М-последовательности 291
7.2.3.1. Цикловое фазирование по к произвольным линейно независимым элементам М-последовательности на базе рекуррентного регистра 292
7.2.3.2. Цикловое фазирование по к произвольным линейно независимым элементам М-последовательности на базе модулярного регистра 299
7.2.3.3. Фазирование дескремблера в ATM-сетях 303
7.3. Цикловое фазирование с несколькими ступенями обнаруже ния 308
8. Применение двойственного базиса в специальных зада чах 321
8.1. Применение двойственного базиса для обработки линейной рекуррентной последовательности при измерении дальности до объекта 321
8.2. Применение двойственного базиса в системах с относительным изменением фазы рекуррентной последовательности с «незакрепленной» начальной фазовой точкой 327
8.3. Применение двойственного базиса для выделения адресных рекуррентных последовательностей 338
8.4. Оценка качества каналов передачи данных на базе рекуррентных последовательностей 340
8.4.1. Оценка качества каналов передачи данных в синхронных системах со сбоями цикловой фазы 341
8.4.2. Возможность построения адаптивной системы передачи данных на основе применения двойственного базиса 347
9. Применение двойственного базиса для анализа и обработки числовых рекуррентных рядов 355
9.1. Использование двойственного базиса для анализа числовых рекуррентных последовательностей, удовлетворяющих уравнению «золотой пропорции» второго порядка 355
9.1.1. Обобщенные числа Фибоначчи (по Люка) 358
9.1.2. Классическая последовательность чисел Фибоначчи 360
9.1.3. «Смещённая» последовательность чисел Фибоначчи 362
9.1.4. Последовательности Люка 363
9.2. Свойства обобщённых последовательностей чисел Фибоначчи (по Люка), удовлетворяющих характеристическому уравнению «золотой пропорции» второго порядка 364
9.3. Обобщённые р-числа Фибоначчи (по А.П. Стахову) и их анализ
с помощью двойственного базиса 378
9.4. Рекурсивные числовые последовательности и их анализ с помощью двойственного базиса 388
9.5. Проблемы помехоустойчивого кодирования с использованием чисел Фибоначчи 397
Заключение 410
Список литературы
