автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Комплексы алгоритмов и программ синтеза разностных множеств и расчета таблиц неприводимых полиномов над конечными полями

/

Новгородский государственный университет им. Ярослава Мудрого

На правах рукописи УДК 27.41.23

Захарин Юрий Владимирович

КОМПЛЕКСЫ АЛГОРИТМОВ И ПРОГРАММ СИНТЕЗА РАЗНОСТНЫХ МНОЖЕСТВ И РАСЧЕТА ТАБЛИЦ НЕПРИВОДИМЫХ ПОЛИНОМОВ

НАД КОНЕЧНЫМИ ПОЛЯМИ

Специальность 05.13.18 — Теоретические основы математического моделирования, численные методы и комплексы программ-

Диссертаци я"" на соискание ученой степени кандидата физико-математических наук

Научный руководитель, д. т. н. Гантмахер Владимир Ефимович

Новгород - 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.....................................................................................................................6

Глава 1. СПЕКТРЫ РАЗНОСТИ КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ

К = ру шш2ру....................................................................................................................13

1.1. Упорядочение смежных классов вычетов....................................................13

1.1.1. Смежные классы по модулю N = ру....................................................13

1.1.2. Особенности упорядочения смежных классов по модулю N = 2ру . 15

1.2. Спектры разности классов вычетов..............................................................18

1.3. Общие свойства спектров разности классов вычетов.................................23

1.3.1. Обобщение основных свойств СРКВ над ОР(р) на модуль

N = ру или 2ру.........................................................................................................24

1.3.2. Свойства СРКВ, специфические для модуля N = ру или 2ру ...........27

1.4 Взаимосвязь СРКВ по различному модулю..................................................30

1.5. Выводы.............................................................................................................37

Глава 2. АЛГОРИТМЫ И ПРОГРАММЫ СИНТЕЗА РАЗНОСТНЫХ МНОЖЕСТВ........................................................................................................................38

2.1. Взаимосвязь между СРКВ и основными параметрами РМ........................38

2.2. Метод синтеза РМ на основе одного, двух и трех классов.........................40

2.3. Алгоритмы синтеза РМ..................................................................................45

2.4. Оценка эффективности алгоритмов синтеза РМ.........................................49

2.5. Характеристика программ и результаты расчетов......................................55

2.5. Выводы.............................................................................................................58

Глава 3. АЛГОРИТМЫ И ПРОГРАММЫ РАСЧЕТА ТАБЛИЦ НЕПРИВОДИМЫХ ПОЛИНОМОВ НАД ПРОСТЫМИ И РАСШИРЕННЫМИ ПОЛЯМИ ГАЛУА..................................................................................................................................59 -

3.1. Метод построения неприводимых полиномов над полем ОБ^)..............59

3.2. Алгоритмы расчета таблиц неприводимых полиномов..............................63

3.3. Характеристика программ и результаты расчетов......................................66

3.4. Выводы.............................................................................................................68

ЗАКЛЮЧЕНИЕ.............................................................................................................69

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ....................................................71

Приложение 1. Программа расчета таблиц неприводимых полиномов над

расширенными полями Галуа......................................................................................77

Приложение 2. Программа синтеза разностных множеств на основе спектров разности классов вычетов по модулю N = или 2р^.................................101

Список сокращений

ПСП — псевдослучайная последовательность

ДКП — дискретно-кодированная последовательность

НП — неприводимый полином

РМ — разностное множество

СРКВ — спектр разности классов вычетов

Список основных обозначений

[а] — целая часть дроби

[а] — ближайшее целое большее

р — простое число

(а,Ь) — наибольший общий делитель чисел а и b

[a,b] — наименьшее общее кратное чисел а и b

a|b — а делит b

ф(а) — фи-функция Эйлера

< a >m — amodm

a=b mod m — а сравнимо с b no mod m 0 — первообразный корень

B(N,K+ ,X) — разностное множество, сбалансированное на один уровень b|n, К+, X i,.., X m j—разностное множество, сбалансированное на m

уровней

а е G — а принадлежит множеству G

ZN — кольцо чисел по модулю N

GF(p) — простое поле Галуа

GF|qmj, q = pn — расширенное поле Галуа

А(х) = В(х) — полином А(х) сравним с В(х) по двойному модулю F(x) и р

mod(F(x),p)

F * (х) — полином, взаимный полиному F(x)

Dn — оператор задержки на п дискретов (оператор Хаффмена)

L — число изоморфных разностных множеств

/С(а) — класс, которому принадлежит число а

S(0,v; A,t) — спектр разности классов вычетов по модулю

N = pY или 2ру

ВВЕДЕНИЕ

Решение широкого круга задач методами математического моделирования требует формирования случайных (псевдослучайных) последовательностей. При проектировании различных радиотехнических комплексов и систем связи очень часто приходится решать проблемы имитации и обработки случайных сигналов [1-3]. В системах технической диагностики имитация случайных сигналов необходима для исследования работоспособности сложных систем и сетей, встроенного тестового контроля [4]. Как правило, вместо случайных успешно применяются псевдослучайные последовательности (ПСП), которые удовлетворяют определенным критериям случайности (уравновешенность, свойство серий, свойство корреляции и др.) [5-7].

Одним из методов получения ПСП является их построение на основе разностных множеств (РМ) [8]. Для построения ПСП путем рекуррентных вычислительных процедур требуются неприводимые полиномы (НП) над полями Галуа. В качестве генератора ПСП применяются автономные линейные последовательностные машины [9].

В теории и практике сложных широкополосных сигналов РМ, сбалансированные на один или два уровня, широко применяются для синтеза дискретно-кодированных последовательностей (ДКП) с хорошими автокорреляционными свойствами [8,10-13]. В свою очередь, для построения некоторых РМ используются НП [14].

Спектр применения НП очень широк. НП необходимы для построения ПСП, которые используются для решения задач методом Монте-Карло, для защиты от несанкционированного доступа. Кроме того, НП лежат в основе наиболее распространенных правил кодирования, которые в радиотехнических системах различного назначения применяются для формирования сложных широкополосных и сверхширокополосных сигналов [3, 8,13], в системах связи и передачи информации - для построения циклических кодов, контролирующих и исправляющих ошибки, и их декодеров [15, 16] и многих других приложениях.

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

Основными параметрами РМ, сбалансированного на ш уровней, ••Ат) являются модуль ]ЧГ, число вычетов К+, число уровней ш и

множество значений уровней {Л,и} (и = 1,т) [8]. Обзор РМ, сбалансированных на

один уровень можно найти, например, в [13, 14, 17, 18]. Известно несколько семейств разностных множеств: это РМ Зингера и их обобщения Гордона-Миллса-Велча [19, 20], РМ биквадратичных вычетов, РМ биквадратичных вычетов с добавлением нуля, РМ восьмеричных вычетов, РМ восьмеричных вычетов с добавлением нуля и РМ типа Адамара, которые объединяют РМ Зингера с 0^1 (общие в классах РМ Зингера и Адамара), РМ квадратичных вычетов, Якоби и Холла [13].

РМ широко применяются для синтеза ДКП, который заключается в поиске новых или деформации известных правил кодирования для достижения заданных пороговых значений параметров ДКП [21]. Для синтеза бинарных последовательностей с т-уровневой автокорреляционной функцией требуются РМ, сбалансированные на ш уровней. Задача синтеза двоичных последовательностей со свойством «не более А,тах совпадений» (боковые лепестки периодической автокорреляционной функции двоичных последовательностей ограничены величиной А,тах) сводится к поиску РМ, ограниченных по уровню величиной А,тах. Т.о., синтез РМ заключается в поиске новых РМ, параметры которых удовлетворяют заданным пороговым значениям. Простейшее решение задачи синтеза РМ связано с перебором большого числа вариантов, который даже при сравнительно небольшом числе переменных невозможно выполнить с помощью ЭВМ. Алгоритмы направленного поиска, позволяющие резко сократить перебор, разработаны В.Е. Гантмахером в [22] для синтеза двоичных последовательностей со свойством «не более Хтах совпадений» на основе математического аппарата

циклотомических чисел.

Теория циклотомии восходит к Гауссу [23, 24]. Математики прошлого века [25] рассматривали случай простого поля ОБ(р). Обобщение на случай произвольного конечного поля ОР^рп| было получено X. Митчеллом [26]. Интерес к циклотомии был

возрожден в 1935г. важными результатами Л. Диксона [17, 27]. Вычисления циклотомических чисел низкого порядка, начатые статьями Л. Диксона, были продолжены

другими математиками. В зарубежной научной литературе приводятся таблицы цик-лотомических чисел до двадцатого порядка включительно [28-31].

М. Холл [14] использовал математический аппарат циклотомических чисел для описания РМ, сбалансированных на один уровень, а именно для описания РМ квадратичных, биквадратичных, восьмеричных вычетов и РМ, впоследствии названных его именем.

Циклотомические числа нашли свое применение для решения прикладных задач в теории сигналов. В 1967 г. А.М. Boehmer [32] применила математический аппарат циклотомических чисел для синтеза оптимальных по минимаксному критерию бинарных импульсных сигналов. В 1975 г. М.Б. Свердлик [8] предпринял неудачную попытку применить циклотомические числа для синтеза бинарных периодических квазиортогональных сигналов, после чего они были незаслуженно забыты.

Использование математического аппарата циклотомических чисел для построения ДКП оказывается привлекательным в силу своего обобщающего характера. Попытка реализовать возможности обобщенного анализа и синтеза ДКП привела к разработке В.Е. Гантмахером [33-36] основ теории спектров разности классов вьиетов (СРКВ) над простыми полями Галуа, которая позволяет решать задачи анализа, синтеза и формирования ДКП на основе математического аппарата циклотомических чисел. В терминологии теории СРКВ циклотомическое число соответствует гармонике СРКВ, порядок циклотомического числа - числу смежных классов d разбиения ненулевых элементов поля GF(p). Т.о., теория СРКВ позволяет строить алгоритмы синтеза РМ. Результаты расчетов В.Е. Гантмахера приведены, например, в [37]. Однако, предложенная В.Е. Гантмахером теория СРКВ применима для синтеза РМ лишь по простому модулю. Вместе с тем существование примитивного элемента для чисел

N = pY или 2pY дает возможность упорядочить смежные классы вычетов и распространить теорию СРКВ на модуль N = р7 или 2р7 .

Одно из решений задачи построения РМ, сбалансированных на один уровень, а именно - РМ Зингера, сводится к поиску НП над простыми и расширенными полями Галуа. Известно много исследований свойств неприводимых многочленов с коэффициентами из простых и расширенных полей Галуа. Одно из первых крупных иссле-

дований неприводимых многочленов от одной переменной над полем GF(q) было проведено Л. Диксоном [38] в 1901 г. Классические методы построения неприводимых многочленов можно найти в работах [38-40]. Алгоритм построения НП над конечным простым полем был предложен в статьях [41, 42]. В работах [43, 44] описаны вероятностные алгоритмы для построения НП. P.P. Варшамов и A.M. Анто-нян [45] описали метод построения новых НП над полем GF(2) на основе неприводимого многочлена. В статье Р.Р. Варшамова [46] показано как строить НП над GF(2) на основе примитивных многочленов, а также содержится теоретико-матричный метод построения НП, степени которых делят п на основе некоторого НП степени п. В работе P.P. Варшамова и Л.И. Гамкрелидзе [47] описаны методы поиска примитивных полиномов для случая простого поля GF(p). Разработки методов генерирования НП над конечными полями предприняты также в работах P.P. Варшамова [48, 49]. В статье [50] приведены алгоритмы для построения новых примитивных многочленов над GF(p) на основе одного такого многочлена.

На основе разработанного в [51] алгоритма расчета коэффициентов НП второй степени над простыми полями Галуа рассчитаны самые полные из известных ранее таблицы НП второй степени с р < 997 [52]. Метод построения алгоритма базируется на использовании формулы решения нормированного уравнения второй степени. Однако область применения такого алгоритма ограничена четвертой степенью НП (п < 4), поскольку общее уравнение n-ой степени при п > 4 неразрешимо в радикалах [53]. Уже для третьей степени НП алгоритм расчета коэффициентов НП [54] становится громоздким.

Проведенный обзор показал, что алгоритмов построения НП много, но они очень специализированные - одни применимы только для GF(2), другие только для GF(p), р Ф 0 mod 2, третьи только для п - не простое число и т.д. Кроме того, практически

все они неудобны для реализации на ЭВМ. Следовательно, одна из проблем построения НП состоит в необходимости унификации алгоритма вычисления коэффициентов НП и адаптации его к ЭВМ.

Другая проблема состоит в необходимости расширения известных полных таблиц НП с указанием периодов корней, поскольку объемы известных таблиц НП уже не

удовлетворяют возрастающим потребностям в НП для решения многих прикладных задач. Так для обеспечения криптостойкости систем связи производят многократную замену НП, взятых из некоторого множества НП. Глобальное множество НП необходимо также для построения ансамблей ДКП, обладающих низким уровнем боковых лепестков периодических авто- и взаимнокорреляционных функций. Ансамбли ДКП применяются в системах связи, например, для обеспечения кодового разделения абонентов в одной и той же полосе частот [1].

НП с коэффициентами из поля СР(2) применяются для синтеза бинарных последовательностей, пользующихся наибольшей популярностью у разработчиков радиоэлектронных систем. Поэтому в научно-технической литературе наиболее широко представлены таблицы НП над ОБ(2) [16, 55-57].

Таблицы НП над простыми полями нечетной характеристики были рассчитаны еще в 1935 г. [58]. Опубликованные таблицы были ограничены четвертой степенью (п < 4) для характеристики р=7. В 1970 г. они были расширены Г.А. Гараковым [59],

поднявшим на единицу границу для п и добавившим случаи р=11 и п < 4. Другие расширения таблиц были получены в работе [60], где были рассмотрены случаи 11 <р<37 для п=2 и 11<р<19 для п=3. Наиболее полные из известных автору

таблиц примитивных полиномов [61] над полями с нечетной характеристикой ограничены пятой степенью (п < 5) для ртах = 47.

Сформулируем перечисленные выше проблемы синтеза РМ и построения НП над конечными полями.

Проблема синтеза РМ заключается в том, что отсутствуют удобные для реализации на ЭВМ методы синтеза РМ по модулю N = ру или 2р7.

Проблемы построения множества НП над конечными полями заключаются в том,

что:

- отсутствуют удобные для реализации на ЭВМ методы расчета глобального множества НП для заданной характеристики поля и степени полинома над простыми и расширенными полями Галуа;

- на нынешнем этапе развития науки и техники существующие полные таблицы НП уже не удовлетворяют запросам разработчиков современных радиотехнических и вычислительных систем.

Т.о., объектом исследований являются разностные множества и неприводимые полиномы над конечными полями, а предметом исследований - вычислительные методы и программы синтеза РМ и построения полных таблиц НП.

Цель диссертационной работы состоит в разработке удобных для реализации на

ЭВМ методов синтеза разностных множеств по модулю N = р7 или 2р7 и расчета

полных таблиц неприводимых полиномов над простыми и расширенными полями Галуа, а также в разработке на основе полученных методов алгоритмов и программ для ЭВМ.

Структура и содержание диссертации определяются решением сформулированных выше проблем.

Первая глава посвящена распространению теории СРКВ на модуль

N = р7 или 2р7. Доказан ряд лемм, теорем и следствий, определяющих основные

свойства СРКВ.

Во второй главе разрабатываются алгоритмы синтеза РМ на основе СРКВ, и в качестве примера приводятся результаты синтеза РМ на ЭВМ, выполненные по предложенным алгоритмам.

В третьей главе исследуются алгоритмы расчета полных таблиц нормированных НП на простыми и расширенными полями Галуа и приводятся результаты расчетов.

Удобный для реализации на ЭВМ алгоритм вычисления коэффициентов НП произвольной степени над полями произвольной характеристики состоит в получении всего множества НП заданной степени на основе одного примитивного полинома и базируется на использовании М-последовательностей, смежных классов вычетов по

модулю М = -1 и обобщенной формулы расчета коэффициентов. Сокращение вычислений и решение проблемы компактного вывода результатов расчета достигается за счет цуговой структуры М-последовательности.

В заключении содержатся выводы и оценка полученных результатов.

Приложение содержит две программы для ЭВМ: синтеза РМ на основе СРКВ и расчета таблиц НП над расширенными полями Галуа.

Основные задачи, решаемые в диссертации:

- распространить теорию СРКВ и метод синтеза РМ на основе СРКВ на модуль N = ру или 2ру;

- разработать алгоритмы и программы синтеза РМ на основе СРКВ;

- получить удобный для реализации на ЭВМ метод расчета коэффициентов НП над простыми