Содержание к диссертации
Введение
Часты. Теоретические и реализационные основы решения модулярных разностных уравнений однородных линейных рекуррентных последовательностей 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
Список литературы
- Определение и основные свойства линейных рекуррентных последовательностей
- ЛРД-последовательности и их свойства
- Матричный способ умножения элементов поля
- Мажоритарные алгоритмы декодирования комбинаций эквидистантного циклического кода по k-элементным участкам
Введение к работе
Актуальность проблемы. В телекоммуникациях и информационных системах широкое применение находят рекуррентные последовательности над конечными полями. Наибольший интерес вызывают линейные рекуррентные последовательности (ЛРП), которые широко применяются в телекоммуникациях и информационных технологиях.
Значительное число работ как зарубежных так и отечественных авторов посвящено анализу и синтезу ЛРП максимального периода, называемых также М-последовательностями, псевдослучайными (ПСП) или шумоподобными (ТТТПС) последовательностями. Наибольшую известность получили работы в этом направлении Н.Цирлера, Б. Элспаса, Д. Сарвате, С. Голомба и др. Из отечественных авторов, внесших существенный вклад в развитие линейных рекуррентных последовательностей, следует назвать P.P. Варшамова, А.И. Маркушевича, А.А. Нечаева, В.И. Нечаева, Ю.Л. Сагаловича.
Значительное количество работ посвящено использованию теории линейных рекуррентных последовательностей в теории помехоустойчивого кодирования.
Большой обобщающий материал по теории ЛРП содержится в двухтомнике Р. Лидла и Г. Нидеррайтера. Конечные поля. - М.: 1988.
Одной из важных задач является выбор эффективного способа обработки линейных рекуррентных последовательностей в различных приложениях. При этом критерий эффективности определяется конкретными требованиями к системе.
Как следует из многих литературных источников, практическое применение находят, в основном, три способа обработки: корреляционная обработка, обработка на основе рекуррентного соотношения и алгебраическая обработка на основе теории конечных полей. Наиболее эффективной и простой реализацией корреляционного способа является применение согласованных фильтров, однако, при декодировании множества комбинаций этот способ требует значительных материальных затрат при апаратной реализации, так как необходим согласованный фильтр на каждую отдельную кодовую комбинацию. Другим вариантом решения такой задачи для эквидистантных кодов является метод максимального правдоподобия, в основе которого лежит умножение принятой комбинации на циркулянтную квадратную матрицу А размером NxN, строками которой будут все циклические сдвиги М-последовательности длиной N. Однако при больших длинах комбинации и этот метод требует также значительных материальных затрат при аппаратной реализации либо больших задержек при программной реализации.
Для обработки рекуррентных последовательностей, в том числе и произвольной структуры, часто применяют методы, основанные на свойстве рекуррентности. К ним можно отнести рекуррентный опознаватель по методу Р. Уорда и метод безошибочного «зачетного» участка. Такие способы просты в реализации, но решают очень узкую задачу, а именно, лишь опознавание рекуррентной последовательности, т.е. они не могут идентифицировать разные рекуррентные последовательности по начальной фазе.
Алгебраической структуре периодических рекуррентных последовательностей посвящены исследования P.P. Варшамова и В.А. Аракелова, в работах которых предложен метод определения специальных коэффициентов, позволяющих аналитически находить произвольный п-й элемент рекуррентной последовательности по начальным элементам данной последовательности. Вычисление специальных коэффициентов проводится на основе решения диофантова уравнения для заданного значения п. В связи с тем, что решать диофантовы уравнения необходимо для каждого из и, предложенный метод имеет большую вычислительную сложность. Кроме того, применение этого метода ограничивается анализом структуры лишь «чистой» рекуррентной последовательности и невозможностью его применения для декодирования (обработки) рекуррентной последовательности, содержащей ошибки. Поэтому он не нашел практического применения.
Известен другой алгебраический метод, позволяющий определять произвольный п-й член линейной рекуррентной последовательности sn по известным корням характеристического многочлена и специальным коэффициентам, однозначно
определяемым начальными членами s0,s1,...,sk_1 ЛРП. Вычисление этих коэффициентов
производится, как правило, путем решения системы из к линейных уравнений, неизвестными в которой являются к искомых коэффициентов. При этом, задача решения алгебраической системы уравнений, число неизвестных в которой к > 3, становится достаточно громоздкой и трудно реализуемой. Поэтому поиск эффективных методов решения этой задачи в конечных полях представляет собой одно из актуальных направлений исследований.
Исследования в этом направлении были проведены Р.Г. Фараджевым, который
применил для решения указанной выше задачи дискретное преобразование Лапласа (Dp -
преобразование). Однако разработанный им метод, как и указанный выше метод на основе диофантовых уравнений, находит п-й член линейной рекуррентной последовательности также только относительно исходных начальных членов рекуррентной последовательности над простым полем с характеристикой р. Это, следовательно, не позволяет применить предложенный метод в тех случаях, когда должна быть решена обратная задача -определение начальных элементов последовательности (её фазы) по некоторым произвольным принимаемым элементам последовательности.
Все выше перечисленные факторы явились основанием к определению направлений исследований настоящей диссертационной работы по разработке теории, методов и алгоритмов обработки ЛРП на основе применения двойственного базиса конечного поля.
Таким образом, объектом исследований являются линейные рекуррентныые последовательности (ЛРП), широко применяемые в настоящее время в телекоммуникациях, в навигации и в телеметрии: М-последовательности, последовательности Гоулда, ЛРД-последовательности, а также комбинации циклических кодов как рекуррентные последовательности.
Предметом исследований являются теория, методы и алгоритмы мажоритарной обработки ЛРП и решения задач в телекоммуникациях на основе нетрадиционного математического аппарата - двойственного базиса в конечных полях.
Показана возможность распространения полученных теоретических результатов и новых алгоритмов на обработку числовых рекуррентных последовательностей в бесконечном поле (последовательности чисел Фибоначчи, чисел Люка и др.).
Целью диссертационной работы является разработка теории, новых методов и алгоритмов обработки однородных ЛРП с использованием двойственного базиса, обеспечивающих повышение достоверности принятия решения, уменьшение времени обработки и упрощение реализации этих алгоритмов при решениии различных прикладных задач телекоммуникаций.
Для достижения этой цели в диссертации поставлены следующие задачи:
разработать аналитические методы общего решения однородных ЛРП;
разработать алгоритмы обработки ЛРП на основе двойственного базиса;
исследовать влияние децимаций на достоверность мажоритарной обработки ЛРП с использованием двойственного базиса;
разработать основы реализации алгоритмов обработки ЛРП с учетом использования двойственного базиса;
исследовать возможности применения двойственного базиса для обработки ЛРП при решении различных задач в телекоммуникациях - помехоустойчивом кодировании, цикловом фазировании, измерениях и исследовании каналов передачи данных;
- провести путем имитационного моделирования экспериментальное исследование
влияния на достоверность мажоритарной обработки ЛРП с использованием двойственного
базиса;
- провести сравнение разработанных алгоритмов обработки ЛРП с другими известными
алгоритмами.
Методы исследования. Для решения поставленных в диссертационной работе задач использовались математические методы z-преобразований, высшая алгебра, теория конечных полей, в частности, полей Галуа, а также матричное исчисление.
Для подтверждения полученных теоретических результатов использовались компьютерное моделирование, электронный инструментарий - калькулятор Галуа, методы математической статистики и теории вероятностей.
Научная новизна определяется тем, что в работе развита алгебраическая теория двойственного базиса применительно к обработке однородных ЛРП. Показано, что использование двойственного базиса позволяет совершенствовать построение аппаратно-программных средств в телекоммуникациях при решении задач помехоустойчивого кодирования, циклового фазирования, оценки качества каналов передачи данных и других специальных задач.
В процессе проведения исследований получены новые научные результаты:
Теоретического характера
Разработан аналитический метод общего решения линейных модулярных рекуррентных уравнений в конечных полях на основе z-преобразований, выведены расчётные формулы.
Разработан аналитический метод общего решения линейных модулярных рекуррентных уравнений в конечных полях на основе двойственного базиса. Выведены простые формулы для вычисления коэффициентов двойственного базиса в зависимости от вида характеристического многочлена анализируемой рекуррентной последовательности, а также формула для определения значения произвольных, в том числе, начальных членов рекуррентной последовательности.
Разработан аналитический метод общего решения на основе двойственного базиса составных рекуррентных последовательностей, в частности, последовательностей Гоулда и ЛРД-последовательностей, выявлен новый класс «зеркальных» последовательностей Гоулда и определены их свойства.
Предложен новый единый алгоритм обработки «прямых» и инверсных рекуррентных последовательностей на основе применения двойственного базиса.
Разработаны основы реализации алгоритмов обработки линейных рекуррентных последовательностей над полем GF(p), в том числе - формирования элементов двойственного базиса поля.
Разработана, основанная на применении двойственного базиса, методика анализа рекуррентных последовательностей в бесконечном поле целых чисел (чисел Фибоначчи, чисел Люка и др.), выявлены новые свойства таких последовательностей.
Пприкладного характера
Разработаны на основе двойственного базиса алгоритмы декодирования комбинаций дуальных циклических кодов: эквидистантных, БЧХ и Рида-Соломона, как рекуррентных последовательностей.
Доказаны теоремы, показывающие, что при определенных условиях эффективность обработки комбинаций циклических кодов, как рекуррентных последовательностей, с использованием двойственного базиса может быть повышена вследствие применения децимаций над принятой комбинацией.
Предложены новые алгоритмы обработки рекуррентных последовательностей на основе двойственного базиса в задачах циклового фазирования. При этом предложенные алгоритмы позволяют, по сравнению с другими, уменьшить время поиска фазирующей комбинации.
Предложены эффективные, основанные на применении двойственного базиса, алгоритмы обработки линейных рекуррентных последовательностей в специальных задачах, в частности:
при измерении дальности до объекта;
в квазисинхронных системах с относительным изменением фазы рекуррентной последовательности;
для выделения адресных рекуррентных последовательностей.
5. Разработана новая методика оценки качества канала передачи данных, отличающаяся тем, что оценка производится непосредственно в процессе передачи и обработки кодовых комбинаций как рекуррентных последовательностей.
Практическая ценность диссертационной работы определяется тем, что применение двойственного базиса для обработки однородных ЛРП позволит:
повысить достоверность принятия решения при обработке принятых по каналу с ошибками однородных рекуррентных последовательностей;
уменьшить время поиска ЛРП, используемых в качестве комбинаций циклового фазирования;
повысить оперативность в оценке качества каналов передачи данных;
- расширить возможности и способы применения однородных ЛРП при решении
специальных задач в области телекоммуникаций.
Практическая ценность и новизна подтверждается тем, что на основе предложенных алгоритмов разработан ряд устройств, защищенных авторскими свидетельствами на изобретения, а также свидетельством о государственной регистрации программы для ЭВМ на мультиоперационный калькулятор Галуа.
Реализация и внедрение результатов исследований
На основе разработанных в диссертации мажоритарных алгоритмов обработки рекуррентных последовательностей в СПбГУТ им. проф. М.А. Бонч-Бруевича выполнены фундаментальные НИР по разработке эффективных помехоустойчивых циклических кодов с использованием двойственного базиса (отчеты с номерами государственной регистрации № 01200964865, 2009 и № 01970006723, 2010).
Разработан «Мультипрограммный калькулятор Галуа, версия 1.1», свидетельство № 2009612476, зарегистрировано в Реестре программ для ЭВМ 18.05.2009.
Методы и алгоритмы обработки рекуррентных последовательностей с применением двойственного базиса использованы в организациях:
- научно-производственное предприятие «ИСТА-Системс» - в опытно-
конструкторской разработке автоматизированной информационной системы
видеонаблюдения Санкт-Петербурга, созданной в рамках реализации программы
«Автоматизированная информационная система обеспечения безопасности
жизнедеятельности»;
- научно-производственное предприятие «Импульс» - при создании аппаратуры
дистанционного управления и контроля для системы телеметрических измерений,
шифр разработки «4202-АУКТ»;
- Санкт-Петербургский институт информатики и автоматизации РАН (СПИИРАН)-
в НИР «Разработка методов и алгоритмов моделирования жизненных циклов мобильных информационных технологий», выполняемой в рамках программы фундаментальных научных исследований отделения нанотехнологий и информационных технологий Российской академии наук (Проект 0-2.3);
- ФГУП ЦНИИ «Электроприбор» - в планируемой ОКР (шифр «Кудесник») по
созданию аппаратуры связи специального назначения;
- СПбГУТ им. проф. М.А. Бонч-Бруевича - в учебном процессе на кафедре
«Обработки и передачи дискретных сообщений» при преподавании дисциплины
«Передача дискретных сообщений», при подготовке аспирантов, магистров, а также в
дипломном проектировании.
Соответствующие акты об использовании результатов работы прилагаются.
Апробация. Основные положения диссертационной работы были представлены и обсуждались на:
4-й Всесоюзной школе-семинаре по вычислительным сетям «Помехоустойчивое кодирование и сжатие данных». Москва-Ташкент, 1979;
9-й Всесоюзной конференции по теории кодирования и передачи информации. Одесса, 1988;
У11 научно-технической конференции НТОРЭС им. А.С. Попова «Оптические, сотовые и спутниковые сети и системы связи». Санкт-Петербург (г. Пушкин), 1996;
X Санкт-Петербургской международной конференции «Региональная информатика -2006». Санкт-Петербург, 2006;
Международной научно-технической конференции «Актуальные проблемы анализа и построения информационных систем и процессов». Таганрог, 2010;
1 Международном конгрессе «Современные аспекты математики гармонии и ее применение в экономике, естествознании, технологии, социуме и образовании». Одесса, 2010;
а также на семинарах и научно-технических конференциях профессорско-преподавательского состава СПб ГУТ им. проф. М. А. Бонч-Бруевича.
Публикации. Основные результаты диссертационной работы опубликованы в 53 работах, в числе которых 18 научных статей, из них 13 в периодических изданиях, находящихся в перечне ВАК или находившихся в этом перечне на момент опубликования, 10 авторских свидетельствах СССР и два патента РФ на изобретения, одно свидетельств о государственной регистрации программы для ЭВМ, одна монография, одна брошюра и два учебных пособия.
Структура и объем работы. Диссертационная работа состоит из введения, 9 глав в двух частях, заключения, списка литературы и приложения. Общий объем диссертации составляют 427 страниц, включая 106 рисунков и 36 таблиц.
Определение и основные свойства линейных рекуррентных последовательностей
Рекуррентная последовательность это такая последовательность, каждый член которой легко получить с помощью определенной рекурсивной процедуры над предшествующими ему членами последовательности. Эти последовательности называют также «возвратными» — возвращающиеся к началу (recurrente) [11]. Практический интерес имеют такие последовательности, у которых её члены линейно зависят от фиксированного числа предыдущих членов. Такие последовательности называют линейными рекуррентными последовательностями (ЛРП). Чаще всего на практике применяют двоичные ЛРП, поэтому их определили как линейные рекуррентные последовательности над полем GF(2). Вместе с тем, теория рекуррентных последовательностей в настоящее время также хорошо развита для конечных полей GF(p), где/) - простое целое число,/? 2.
ЛРП над конечным полем обладают целым рядом полезных структурных свойств. Рассмотрим их подробнее.
Пусть имеется последовательность {s}, состоящая из следующих друг за другом последовательных элементов SQ,S[,S2,--- некоторого конечного простого поля GF(p). Если существуют такие элементы конечного поля а, р\, р2, ..., р , которые позволят произвольный элемент s„+k последовательности {s} выразить уравнением sn+k = P\ Sn+k-i +Pi S„+A-2+. .) то последовательность {s} будет линейной возвратной [11] или рекуррентной [3] последовательностью к-то порядка, а само линейное уравнение (1.1) -возвратным или рекуррентным уравнением к-го порядка. В [10] и во многих других литературных источниках такие уравнения названы также разностными уравнениями.
Линейное рекуррентное уравнение (1.1) называют однородным если а=0, и неоднородным - в противном случае. Соответственно рекуррентная последовательность {s} , будет однородной или неоднородной.
Рассмотрим основные структурные свойства, которые вытекают из построения рекуррентных последовательностей.
Свойство начального состояния. Значения членов последовательности {s}, сформированной по линейному рекуррентному уравнению к-го порядка вида (1.1), определяются вектором начальных её ЧЛеНОВ ( So S\ . . .s .i ).
Свойство периодичности. Характерной особенностью линейных возвратных последовательностей над конечным полем является то, что такие последовательности, начиная с некоторого элемента, проявляют свою периодическую структуру. Последовательность so, S\, S2- . . называют периодической, если существуют такие целые числа т 0 и п 0, что sn+m=sn для всех п по. Тогда число т называют периодом рекуррентной последовательности {s}, а целое неотрицательное число щ - предпериодом этой последовательности..
Периодическую рекуррентную последовательность с периодом т называют чисто периодической, если равенство sn+m= s„ выполняется для всех п — О, 1, 2,..., т. е. если предпериод щ =0 .
Как доказано в [3], любая однородная линейная рекуррентная последовательность к-то порядка над полем G(p) является периодической с периодом т рк -1.
Наименьший из всех возможных периодов периодической последовательности называется минимальным периодом.
Однородную линейную возвратную последовательность к-то порядка, минимальный период которой равен рК — 1, называют последовательностью максимальной длины или М-последовательностью.
Минимальный период является делителем максимального периода рекуррентной последовательности. ) последовательности {s} &-го порядка над простым полем с характеристикой р, удовлетворяющей рекуррентному соотношению (1.1), соответствует характеристический многочлен Р{х) =рохк-РххкЛ -р2хк-2 - ... -ркЛх-рь A-eGF(p) (1-2)
Линейной однородной рекуррентной (возвратной) последовательности {s} k-ro порядка над простым полем с характеристикой р с характеристическим многочленом (1.2) соответствует сопровождающая квадратная матрица F, имеющая вид: F = 0 0 0 элементы расширенного поля GF(p), которые однозначно определяются начальными членами s0, s\,..., sk.i рекуррентной последовательности {s}» [3]. В дальнейшем решением линейной рекуррентной последовательности, заданной рекуррентным уравнением (1.1), будем считать определение коэффициентов с\, с2, ...,ch позволяющих находить произвольный член sn ЛРП.
Как следует из фундаментальных работ [3,10,12], коэффициенты сь с2, ..., ск определялись путем прямого решения системы линейных уравнений (1.7) при п = 0,1,...,{к- 1), т.е. по заданным начальным членам s0, s\,..., sk.x. Однако, как отмечают авторы указанных работ, в частности Р. Фараджев, решение системы уравнений при к Ъ вызывает определённые затруднения реализационного плана, учитывая, что число возможных вариантов начальных векторов последовательности {s} равно рк. Поэтому многие исследователи пытались решить эту задачу так, чтобы коэффициенты с\, с2, ..., ск можно было находить из простых выражений, легко реализуемых как программно, так и аппаратно.
Именно такая задача решена автором в первой части книги. Отметим, что это решение получено только для однородных линейных рекуррентных последовательностей. Рекуррентные последовательности максимального периода (М-последовательности) над полем GF(p) и их свойства.
Изучение последовательностей максимальной длины (М последовательностей) началось примерно в середине 50-х годов прошлого века. Теория М-последовательностей развивалась и применялась на практике такими исследователями как С. Голомб, Н. Цирлер, Б. Элспас и др. Первые исследования в этой области в основном были направлены на изучение автокорреляционных и "шумоподобных" свойств М-последовательностей, благодаря которым их и стали называть также псевдослучайными (ПСП) или шумоподобными (ШП) последовательностями
Наиболее полно результаты исследования свойств М- последовательностей отражены в работах Н Цирлера [25], Ф.Дж. Мак-Вильямса и Н.Дж.А. Слоена [35], а также Д.В. Сарвате и М.Б. Персли [22].
Именно М-последовательностям в работе уделяется большое внимание. Это обосновывается тем, что применение этих последовательностей в системах связи, в системах передачи и обработки данных, для целей измерения и решения других задач даёт хорошие результаты. Применение же других кодовых последовательностей, даже если их свойства аналогичны свойствам линейных возвратных последовательностей максимальной длины, как правило, не позволяет достичь подобных результатов. Поэтому представляется актуальной задача рассмотрения линейных возвратных последовательностей максимальной длины, их свойств и способов обработки.
Структурные свойства М-последовательностей.
Все однородные линейные возвратные последовательности к-го порядка над простым конечным полем с характеристикой р=2 обладают следующими свойствами [ 2, 7, 10, 13, 22, 24, 25, 26, 28, 30]: 1.2.1. В двоичной М-последовательности число ненулевых элементов равно 2 " , а число "нулей" - на единицу меньше, т. е. 2к х - 1. В случае недвоичных последовательностей с характеристикой простого поля р 2 каждый ненулевой элемент в периоде М-последовательности входит/? "1 раз, а нулевой - (рк 1 — 1) раз.
Любая r-элементная комбинация (sn sa . . sir), кроме нулевой, 0 г к, в одном замкнутом в кольцо периоде М-последовательности, длиной 2к - 1, появляется ровно 2 " раз; r-элементная комбинация, состоящая из одних нулей, появляется ( 2к г — 1) раз.
Из этого свойства следует, что любая ненулевая -элементная двоичная комбинация в замкнутом периоде М-последовательности появляется только один раз, а нулевая -элементная комбинация - отсутствует.
ЛРД-последовательности и их свойства
Такая задача возникает довольно часто при обработке возвратных последовательностей. Но не менее часто возникает и в некотором смысле обратная задача, когда по произвольному -элементному участку принимаемой рекуррентной последовательности необходимо определить ее начальные элементы или ее начальную фазу со- Такая задача стоит при обеспечении циклового фазирования в системах передачи данных с помощью М- последовательностей, при декодировании циклических кодов максимальной длины и в некоторых других случаях. Похожие задачи стоят при определении расстояния (в числе элементов) от выделенного it-элементного участка (sn, sn+\,..., S„+A-I) М-последовательности до ее начала. Задачи такого типа впрямую не решает ни метод, рассмотренный в данном параграфе, ни аналогичный метод, изложенный в [10]. Поэтому следующий параграф данной работы посвящен решению именно такого рода задач.
Двойственный базис конечного поля и его применение для решения однородных линейных МРУ
Рассмотрим, как и ранее, однородную линейную возвратную последовательность {s} к-го порядка, удовлетворяющую рекуррентному уравнению (2.1). Как было показано, произвольный элемент sn такой последовательности может быть выражен соотношением (2.2).
Поставим задачу - определить начальную фазу последовательности {s} или ее начальные элементы (so, s\, ..., sk.\) по произвольному безошибочному к - элементному участку последовательности {s}, т.е. (s„, s„+i, ..., .УИ+А-І)- Здесь индекс п определяет расстояние -элементного безошибочного участка относительно начала последовательности. Другими словами, будем рассматривать случай с так называемой «фиксированной» фазовой точкой, что имеет место, например, при декодировании циклических эквидистантных кодов максимальной длины [26].
Решив указанную систему уравнений относительно коэффициентов сь сг, ..., с/,, мы сможем, исходя из уравнения (2.2), определить начальный участок (s0, si, ..., Sfc-і) последовательности {s}. Из уравнений (2.19) следует, что любой к- элементный участок последовательности {s} позволяет вычислить одни и те же коэффициенты c\,c2,...,Ck.. Именно этот факт позволяет осуществить мажоритарную обработку псевдослучайной последовательности во многих прикладных задачах, и, как показано ниже, правильное ее декодирование даже при больших вероятностях ошибок в канале связи. а через Д обозначен [14] определитель Вандермонда (&-1)-го порядка, являющийся алгебраическим дополнением, полученным из определителя д вычеркиванием &-ой (последней) строки иу-го столбца.
Покажем, что любую сумму (2.30) можно выразить в виде многочлена от одной переменной є с коэффициентами р0, рх, ..., рк исходного примитивного полинома Р{х) в записи (2.21), корнями которого являются, как уже отмечалось, элементы поля є1,є2,...,єі. Обозначим в формуле (2.30) индекс k-i = т. Тогда сумма SJ будет содержать в качестве слагаемых произведения т различных корней характеристического полинома Р(х), кроме є . В соответствии с формулами
Виета, сумма всех возможных произведений по т различных корней полинома Р(х) из всей совокупности из к корней є1,є2,...,єк представляет собой значение (-1)ш „ . Поэтому сумма т будет равна (-1)т „ за вычетом суммы тех произведений по т корней в каждом, которые будут содержать также элемент є , т.е.
Таким образом, мы доказали, что любая сумма SmJ) выражается полиномом от одной переменной є с коэффициентами рт , рт.\ ,..., р\ , /?о примитивного полинома Р(х) в записи (2.21).
Далее найдем выражение в общем виде для значения определителя Вандермонда (-1)-го порядка Akj- в формуле (2.29), составленного из корней примитивного полинома Р(х), кроме є , т.е. из множества корней
Очевидно, что значение определителя A kJ будет равно значению полного определителя Вандермонда А из множества всех корней, поделенному на произведение сомножителей, содержащих корень є , которое будет иметь следующий вид: тк]= n vffr)Ilc .-ej r t6 0) (2-36) производная характеристического полинома (2.21) при подстановке вместо переменной х корня полинома є . характеристический полином степени к, порождающий поле GF(pk), - его примитивный корень, а Р (х) - производная от полинома Р(х). По поводу предложенных С. Ленгом выражений (2.44) можно заметить следующее. Формулы С. Ленга представляют собой выражения для двойственного базиса только для одного частного случая, а именно только относительно левого степенного базиса (\,є ,...,є ).
Таким образом, в диссертационной работе, в отличие от результата С. Ленга, получены и строго математически доказаны общие выражения для двойственного базиса поля GF(p ) относительно произвольного степенного
Матричный способ умножения элементов поля
В третьей главе рассмотрены различные алгоритмы обработки рекуррентных последовательностей (последовательностей максимальной длины) над конечным полем Галуа. Все алгоритмы базируются на различных действиях над элементами конечного поля GF(pk). Таким образом, реализация рассмотренных алгоритмов обработки рекуррентных последовательностей над конечным полем основана на принципах реализации различных действий над элементами поля.
Рассмотрим реализацию таких основных действий над элементами поля Галуа как умножение, деление, возведение в степень, обращение, логарифмирование и др. Эти действия составляют основу специализированного устройства, которое специалисты в данной области стали называть "калькулятором Галуа", реализуемого как аппаратными, так и программными средствами.
Вопросы практической реализации действий над элементами конечного поля рассматриваются в работах [2, 5, 26, 55, 57]. В работе, кроме известных, приводятся также новые, полученные в этой области, результаты, например, при матричном умножении, а также при логарифмировании элементов поля.
Рассмотрим принципы реализации основных действий над элементами поля GF(pk), сопровождая их конкретными примерами для поля Галуа GF(24) с образующим данное поле характеристическим многочленом Р(х) = 1 + х + х\
Матричное представление элементов поля GF(pk) Пусть для построения поля GF(p) выбран примитивный образующий многочлен степени к Р{х)=хк+рххкл +р2хк-2 + ... +рк.іх+рк;рі є GF(p) (4.1) одним из корней которого будет первообразный элемент є GF(pk). Тогда все множество ненулевых элементов поля представляет собой поле классов вычетов по двойному модулю - mod р и mod Р(в). С другой стороны каждый ненулевой элемент поля GF(p) может быть представлен как некоторая степень одного и того же первообразного элемента є. Все отличные от нуля элементы поля GF(pk) образуют мультипликативную группу порядка (рк-1), элементы которой могут быть выражены в полиномиальном виде через левый степенной
В соответствии с теоремой Гамильтона-Кэли [37] матрица F является корнем характеристического многочлена flX) степени к от переменной X, который определяется как определитель характеристической матрицы [ХЕ — F], то есть С другой стороны, как показано в [57], вид примитивного многочлена Р(х) полностью совпадает с характеристическим многочленом J{X) при подстановке х = X, то есть Р(Х) = /{X). Следовательно, сопровождающая матрица F будет также корнем многочлена Р(х), то есть
Последнее приводит к важному следствию, заключающемуся в том, что множество элементов поля GF(pk), построенного по примитивному многочлену Р(х), изоморфно множеству полиномов — вычетов по модулю P(F). Другими словами, любому элементу є " поля GF(pk), выраженному через левый степенной базис
Таким образом, элементу гт, приведенному по модулю Р(в), соответствует матрица Fm, приведенная по модулю P(F). Указанное свойство используется при реализации основных действий над элементами поля GF(pk) [57].
Как было показано, любой элемент поля GF(pk) может быть выражен через базисные элементы как (а0 + щг + ... + а -іЄ "1), где Й?О, а\, ..., ак.\ є GF(p). Назовем генератором прямых элементов поля GF(pk) устройство, формирующее последовательность ненулевых элементов ПОЛЯ Є, Є , Б , ..., БР . Как видим, произвольный элемент данной последовательности равен предыдущему элементу, умноженному на Б. на элемент є может быть реализовано в матричной форме как произведение вектор-строки [ з0 а.\ ... ак.\\ на сопровождающую матрицу F, имеющую вид (4.2). Тогда вектор [б0 Ь\ ... бы] соответствующий элементу є;+І, будет равен то в следующий тактовый момент будет сформирован очередной элемент є путем умножения предыдущего элемента на є и приведения по mod P(s), что реализуется путем сдвига содержимого регистра вправо на один шаг. Действительно, очередной элемент є +1 будет получен, с учетом (4.7), следующим образом:
Генерация обратных элементов поля GF(p ) При решении задач обработки М-последовательностей, как следует из второй главы работы, требуется генерировать элементы поля в обратном порядке, то есть єр -1,єр 2, ..., є , є. Ниже показано, что такой генератор также реализуется с помощью регистра сдвига на к ячеек с такими же сумматорами и умножителями, но с другим направлением сдвига. Напомним, что одним из свойств поля GF(p) является наличие для любого ненулевого элемента є обратного ему элемента є" , которые удовлетворяют равенству s є" = 1. соответственно обратных элементов поля, а именно 1, с"1, є"2,..., є"(р 3), є (р 2). Если в последовательности прямых элементов каждый элемент равен предыдущему, умноженному на є, то в последовательности обратных элементов каждый ее элемент равен предыдущему, умноженному на є"1. Таким образом, если генератор прямых элементов реализуется на базе сопровождающей матрицы F, то генератор обратных элементов может быть реализован на базе обратной матрицы К1.
Мажоритарные алгоритмы декодирования комбинаций эквидистантного циклического кода по k-элементным участкам
Во многих случаях при решении задач по обработке рекуррентной последовательности над полем GF(2k) необходимо выполнять действия по умножению на матрицу. Умножение на матрицу, например, осуществляется, как было показано в предыдущем параграфе, при преобразовании элементов принимаемой рекуррентной последовательности в соответствующие элементы поля GF(2k), а также во многих других случаях. В частности, при перемножении элементов є я є3 в конечном поле GF(2k) необходимо умножить вектор (айаха2...ак_х), соответствующий элементу є , на матрицу FJ, соответствующую элементу Є1.
Для упрощения реализации умножителя на двоичную матрицу, имеющую большее число единиц, чем нулей, можно рекомендовать алгоритм, впервые изложенный в описании изобретения [59]. Рассмотрим предложенный алгоритм на примере перемножения элементов є и є1. Суть алгоритма в этом случае может быть сформулирована в виде следующей теоремы.
Теорема 4.1 Если результатом умножения вектора {а аха2 ... %_,), соответствующего элементу є1 поля GF(2k), на степень характеристической матрицы FJ, отображающей элемент є1 того же поля, будет вектор(b0bx...bk_x),то такой же вектор будет получен приумножении
вектора {а0а{а2 ...аА_,) на инвертированную матрицу F1 при условии, что вес со вектора {а0аха2 ...ак_х) будет четным.
Если же вес со будет нечетным, то в результате умножения вектора (aQ,ax,...,ak_x) на инвертированную матрицу FJ будет получен вектор (bo,bi,...,bk-\), инвертированный по отношению к вектору (Ь0, Ъх,..., bk_x).
Доказательство этой теоремы чрезвычайно простое и состоит в следующем. Пусть, как было сказано, элементу е] поля GF(2k) соответствует 7-ая степень характеристической матрицы F, т.е. FJ. Очевидно, что инвертированная матрица F1 равна сумме по модулю 2 матрицы FJ и квадратной матрицы I, состоящей полностью из единиц. Тогда в результате умножения вектора
Отсюда видно, что если число единиц в двоичном векторе (а0,ах,...,«[_,) четное, то имеем: [aQax...ak_x]-FJ = [а0 ах ...ак_х]- FJ = [b0bx...bk_x] (4.74) Т.е., в этом случае при умножении вектора (а0,ах,...,ак_х) на инвертированную матрицу F3 будет получен тот же результат, что и при умножении на матрицу F1 без инверсии. Если же число единиц в векторе (а0,ах,...,ак_х) нечетное, то в результате умножения к каждому элементу вектора-произведения [a0ai...aA_,]-FJ будет добавлена единица по модулю 2. В этом случае, как видим, результат умножения вектора (а0,ах,...,ак_х) на инвертированную матрицу FJ будет также инвертирован, т.е. [а0 ax...ak_x]-FJ =\boЫ...bk-i ] Тогда, для восстановления результата умножения вектора {а0,ах,...,ак_х) на матрицу F}, полученный вектор необходимо снова инвертировать. Таким образом, теорема 4.1 доказана.
Из данной теоремы вытекает следующее следствие: Следствие 4.1 Для реализации умножения двоичного вектора (а0,ах,...,ак_х) на некоторую двоичную матрицу Н число сумматоров по mod2 в схеме умножения не будет превышать половины от общего числа элементов матрицы Н. Действительно, если общее число единиц матрицы Н не превышает половины общего числа её элементов, то инвертировать матрицу Н не следует и тогда общее число сумматоров по mod 2 будет также меньше половины элементов матрицы.
Если же число единиц в матрице Н превышает половину элементов этой матрицы, то для уменьшения числа требуемых сумматоров по mod 2 при умножении на матрицу Н её необходимо инвертировать.
Таким образом, мы видим, что при умножении на инвертированную матрицу н вектора с четным числом единиц получен тот же самый вектор, что и при умножении на матрицу Н. Второй же вектор имеет нечётное число единиц, поэтому для получения требуемого результата полученный вектор от умножения на матрицуя необходимо инвертировать.
Очевидно, что, инвертировав матрицу //, имеющую более половины единичных элементов (45 из 64), мы получим умножитель на матрицу Я с более простой реализацией. Действительно, если расписать результат умножения
Из приведенных уравнений видно, что для умножения на матрицу Н требуется 11 сумматоров по модулю 2 (это без проведения минимизации). Следует отметить, что при умножении на матрицу по рассматриваемому алгоритму в умножителе необходимо добавить схему определения четности (нечетности) единиц в векторе (а0,ах,...,ак_х) и схему инвертирования результирующего вектора (с0,сх,...,ск_х). При этом, последняя должна включаться только при нечетном числе единиц в исходном векторе (а0,а:,...,ак_х). Поэтому, решение о том, инвертировать матрицу Н или нет, необходимо принимать с учетом указанных дополнительных схем и общего числа единиц в матрице Н.
Аналогично можно доказать, что описанный алгоритм позволяет упростить умножитель двоичного вектора (а0,ах,...,ак_х) на матрицу Н, если в ней будут инвертироваться не все столбцы, а только те, которые имеют много единиц (больше половины). При этом, в случае нечетного числа единиц во входном векторе (а0,ах,...,ак_х), в результирующей строке, полученной после перемножения, одноименные разряды необходимо снова инвертировать.
