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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. ЯРОСЛАВА МУДРОГО

РГб ОД 2 7 ОКТ 1998

На правах рукописи

ЗАХАРИН ЮРИЙ ВЛАДИМИРОВИЧ

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

Новгород-1998

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

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

Официальные оппоненты:

- доктор технических наук, профессор Песошин Валерий Андреевич;

- кандидат технических наук, доцент Быстрой Николай Егорович.

Ведущая организация: Московский государственный институт электроники и математики (технический университет)

Защита состоится ноября 1998 г. в_.„„„^ на заседании диссертационного совета К 064.32.05 при Новгородском государственном университете им. Ярослава Мудрого (173003, Россия, г. Великий Новгород, ул. Б. Санкт-Петербургская, 41).

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан _ октября 1998 г.

Ученый секретарь

диссертационного совета К 064.32.05 к.ф.-м.н., доцент каф. прикладной математики

Беляев К.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Т.о., актуальность исследования РМ и НП над конечными полями обусловлена их разнообразным применением в различных областях науки и техники.

Основными параметрами РМ, сбалансированного на т уровней,

В^КГ, К+ Д1Л2.-Лт) являются модуль N. число вычетов К+, число уровней т и множество значений уровней {Яи} (и = 1,т). . . . ■

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

Интерес к циклотомии был возрожден в 1935г. важными результатами Л. Диксона. Вычисления циклотомических чисел низкого порядка, начатые статьями Л. Диксона, были продолжены другими математиками (Muskat J.B., Whiteman A.L.).

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

Циклотомические числа нашли свое применение для решения прикладных задач в теории сигналов (Boehmer A.M., Свердлик М.Б.). Попытка реализовать возможности обобщенного анализа и синтеза ДКП привела к разработке В.Е. Гантмахером основ теории спектров разности классов вычетов (СРКВ) над простыми полями Галуа, которая позволяет решать задачи анализа, синтеза и формирования ДКП на основе математического аппарата циклотомических чисел. Т.о., теория СРКВ позволяет строить алгоритмы синтеза РМ. Однако, предложенная В.Е. Гантмахером теория СРКВ применима для синтеза РМ лишь по простому модулю. Вместе с тем существование примитивного элемента для чисел N = рт или2рт дает возможность упорядочить смежные классы вычетов и распространить теорию СРКВ на модуль N ~ру или 2р7 .

Одно из решений задачи построения РМ, сбалансированных на один уровень, а

именно - РМ Зингера, сводится к поиску НП над полями Галуа. В зарубежной научно-технической литературе представлены разработки алгоритмов построения НП над простым полем Галуа (Popovici O.P.), получения новых примитивных многочленов над GF(p) на основе одного такого многочлена (Alanen J.D., Knuth D.E.), описаны вероятностные алгоритмы для построения НП (Rabin М.О., Calmet J.). В отечественной литературе разработки методов генерирования НП над конечными полями представлены в работах P.P. Варшамова, A.M. Антоняна, Л.И. Гамкрелидзе.

В.Е. Гантмахером предложен алгоритм расчета коэффициентов НП второй и третьей степени над простыми полями Гатуа, однако уже для третьей степени НП алгоритм расчета становится громоздким.

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

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

НП с коэффициентами из поля GF(2) применяются для синтеза бинарных последовательностей, пользующихся наибольшей-популярностью у разработчиков радиоэлектронных систем. Поэтому в научно-технической литературе наиболее широко представлены таблицы НП над GF(2).

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

для п и добавившим случаи р=11 и и < 4. Другие расширения таблиц предусматривали случаи 11 < р < 37 для irf и 11 < р < 19 для n=3 (Chang J.A., Godwin H.J.).

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

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

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

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

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

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

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

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

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

Актуальность работы обусловлена разнообразным применением результатов исследований при решении прикладных задач. Следует отметить, что наиболее эффективным является использование полученных результатов в математическом моделировании для построения генераторов псевдослучайных чисел и в теории сигналов для синтеза ДК1Т.

Актуальность работы обусловлена отсутствием унифицированных регулярных методов синтеза РМ по модулю Ы=р1' шш2р1', отсутствием быстрых алгоритмов формирования полных таблиц НП над простыми и расширенными полями Галуа произвольной степеш! и произвольной характеристики.

Цель диссертационной работы состоит в разработке удобных для реализации на ЭВМ методов синтеза РМ по модулю N = рг или2рг и расчета полных таблиц НП над простыми и расширенными полями Галуа, а также в разработке на основе полученных методов алгоритмов и программ для ЭВМ.

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

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

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

- получить метод расчета коэффициентов НП над простыми и расширенными полями Галуа для заданных характеристики поля и степени НП;

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

Научная новизна', по мнению автора, заключается в том, что:

- распространение теории СРКВ на модуль N = ру или 2рт не только является обобщением известной теории СРКВ по простому модулю, но и содержит свойства СРКВ, специфические для модуля N = рт или2ру, а также связь СРКВ по различному модулю;

- разработанные программы синтеза РМ и расчета таблиц НП позволяют вычислять РМ и НП с заданными ограничениями на параметры (РМ с ограничением на максимальное число и значение уровней; НП с заданным периодом корней, числом ненулевых коэффициентов, характеристикой поля и др.);

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

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

- синтеза РМ, выполнешюго по методам, предложенным в диссертации;

- определение неприводимости полиномов в рассчитанных таблицах по различным критериям;

- обсуждений научных и практических выводов диссертации и их положительной оценкой на научно-технических конференциях различного ранга.

- результатами двух НИР, выполненных по теме диссертации при непосредственном участии автора.

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

Апробация результатов. Основные положения диссертационной работы докладывались, обсуждались и одобрены на:

-НтеНовГУ. 1995, 1996;

- всероссийской НТК с международным участием "Электроника и информатика". Москва. Зеленоград. 1995;

- третьей межведомственной НТК «Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах». Санкт-Петербург. Пушкин. 1997;

- первой международной конференции и выставке «Цифровая обработка сигналов и ее применение». Москва. 1998.

В полном объеме диссертация докладывалась на

- расширенном заседании кафедры прикладной математики НовГУ им. Ярослава Мудрого, апрель 1998.

Научные результаты опубликованы автором в 8 работах. Из них две книги, 4 печатные работы, 2 отчета о НИР. Зарегистрированы в РосАПО 2 программы для ЭВМ.

Структура. Диссертационная работа состоит из введения, грех глав, заключения, списка использованной литературы из 72 наименований и двух приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ ВВЕДЕНИЕ

Введение содержит общую характеристику работы, включающую актуальность, формулировку проблем, цель исследований а также основные задачи, решаемые в диссертации.

Глава 1. СПЕКТРЫ РАЗПОСТИ КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ N = p7 или 2рт

Теория СРКВ над простым полем Гаяуа GF(p), основанная на применении математического аппарата циклотомических чисел, имеет важное прикладное значение в теории сигнатов дай анализа и синтеза ДКП. Однако эта теория применима лишь по простому модулю N=p. Настоящая глава посвящена распространению теории СРКВ над полем GF(p) па модуль N = рг или 2ру .

Пусть ZN — кольцо элементов по модулю N = руили 2р7 . Элементы ZN взаимно простые с N образуют мультипликативную циклическую группу G(ZN ) порядка cp(N) = (p|pY j = pr - pr 1 (ф(-) - фи-функция Эйлера).

Пусть © - примитивный элемент группы G. Образуем смежные классы вычетов по правилу

Hk =|0k+id|, к = 0, d -1, i = О, R -1, где d - число классов, R - число элементов в классе (ф(Н) = d ■ R).

Обозначим t = ра или2ра (0< а <у) - делитель числа.N. Пусть Rt - число различных элементов в произведении t • Hk.

Для каждого t образуем множество элементов кольца G« по правилу: gW = |z sZN: t\z и = lj.

. Размерность множества оМ равна = ф(р7 а)

Распространим определение смежного класса, данное для группы, на кольцо :

где - длина класса, (1, - число классов множества : <1, = ! 14

Т. о., кольцо состоит из множеств

о« . Множество О« , в свою очередь, образовано из с14 классов длины К.(. Обозначим число классов кольца с1сумм = .

Функция определяющая номер класса, которому принадлежит элемент г,

в отличие от ранее введенной для простого модуля является двузначной: Л?(г) = т,1 , если геИт1.

Заметим, что | = (к)а Л (запись (к)а эквивалентна ктоё^).

Можно показать, что классы вычетов по модулю N. которым принадлежит разность классов Нт [ -Нк V, с точностью до циклического сдвига определяются разностью номеров этих классов.

¿(Н^-Но^Л^т-к)^.

Итак, классы, которым принадлежит разность Нга1 -Н^ у, с точностью до циклического сдвига на постоянную составляющую к, определяются таблицей значений

хг(нД1 -н0у) = 4*-©А+14' -у-вМ

^___(1.1)

где А£(т- к)й , 1 = 0, К{ -1, ] = 0,-1.

Распространим определение СРКВ, данное ранее для простого модуля, на модуль N = р7 или 2р7 .

Спектром разности классов вычетов с индексами 0,у и Д,1 по модулю N = ру или 2ру является упорядоченная по номерам классов матрица-строка из (Зсумм чисел, показывающую сколько раз множество элементов класса с индексом р,и встречается в таблице (1.1):

бго. v: дд) = зп„,, ,эр. „ „ ,...з„

Связь между зр>и — гармоникой СРКВ и числом Бр и, показывающим, сколько раз класс с индексом р,и встречается в ряду /<ф-0Л+1а1 - Д = (т-к)й

при 1 = О, (К( Ду) -1 определяется формулой:

С — 1-1 . о

ьр,ц „ ьр,и-хч-и

*

При одинаковых длинах классов числа 5р и и и совпадают, а определение СРКВ соответствует определению, данному для случая простого модуля.

Упростить исследование свойств СРКВ позволяет применение классов одинаковой длины Л|(р -1). Можно показать, что классы вычетов произвольной длины выражаются через классы одинаковой длины. Параметры классов

и а^, а также число

классов кольца с!сумм при условии 11|(р-1) определяется простыми формулами:

1) Л,. = Я, (1,. = — (особый случай II к = с1ы = 1 при N = 2ру ) - длины клас-

Ра 7 7

сов одинаковы вне зависимости от делителя.

N-1 N-2

2)^=— при N = р7 и (1сумн = +1 при N = 2рг .

Далее рассматриваются СРКВ только с одинаковыми длинами классов К|(р -1). Ниже приведены основные свойства спектров разности классов вычетов. Теорема 1.2. СРКВ 5(к,у;тД) и 5(0,у;Дд) связаны соотношением:

8(М; тд) = Вк8(0,у; Лд), А = (т-к) , Б — оператор циклического сдвига Хаффмана. Из-за двузначного номера класса циклический сдвиг выполняется по правилу Е^врц = и, где 5р и - гармоника СРКВ.

Теорема 1.3. СРКВ 8(тд; к,у) и 8(0,у; Лд) связаны соотношением

8(т, I; к, у) = Р у; Лд)

Теоремы 1.2-1.3 являются обобщением известных свойств СРКВ над простым

полем Галуа. Специфические свойства СРКВ прежде всего связаны с появлением для модуля N = р7 или 2р7 спектров вида 8(0,V; Ад) с V ^ г, которые не имеют аналогов в теории СРКВ над ОР(р).

Теорема 1.4. СРКВ §(0,у;дд) с т = (1,у)£1 является производным от спектра

Б(0,у/ т; ДД / т), гармоника спектра 8(0,V; Д,!:) с точностью до постоянного коэффициента определяется суммой значений гармоник 8(0, V /V, ДД/-ф

3Р„,«=С' 1Х,и> ■у/ = (ти,Н); ^с = 1,еслиН -Р7]

ряр„ тоёб,,.

Расчет СРКВ сравнительно трудоемкая процедура. Теорема 1.4 позволяет вычислить СРКВ Э(0,у; Ад) с (1,у) ^ 1 на основе блока спектров с М = 1.

Теорема 1.5. Спектр Э(0,у; Ад) с уЛ по модулю К = рт имеет гармоники со значением только 0 или 1.

В следующей геореме определены спектры, в которых присутствует гармоника, имеющая максимально возможное значение э ы = К.

о,— 2

Теорема 1.6. s N eS[o,pa; А*,2ра} и s N=R, где А* = А ■

0.Т ~ 1 Ъ У

р7+1Л

. 2

г 2 v '

по модулю N = 2ру.

Можно показать, что примитивный корень по модулю 2р7 всегда является примитивным корнем и по модулю рг , обратное утверждение неверно. Представим примитивный корень по модулю 2р7 как степень примитивного корня по модулю р7: CI = ©6 mod р7 , (§, cp(N)) = 1. Следующая теорема определяет рекуррентную связь между СРКВ по различному модулю.

Теорема 1.7. s(o,pa; Д,ра) по модулю рт и s(o,pa~p; Д,ра~Р) по модулю рт_Р

(0 < Р < а) совпадают по числу и значениям гармоник, причем соответствующие одинаковые гармоники связаны соотношением sp - sp .

Теорема 1.8. Спектры S^0,pa; Д,ра) и S^O, 2pa; A,2pa) по модулю 2pY

совпадают по числу и значениям гармоник со спектром S^O, ра; (5- Л)й ,ра j по модулю ру, причем соответствующие одинаковые гармоники связаны соотношением: Sp,2u = S(p+ t)du ,2u = S(5 p+ ^ u, (u = рР, 0 < ß < у; e = /¿¡2 + py /u)j.

Согласно теореме 1.8 спектры S^0,pa;Ä,paj и s|o, 2pa; Д2ра| по модулю 2ру определяются из спектра s|o, ра; А,ра| по модулю рг простой перенумерацией гармоник.

Т.о., найденная взаимосвязь между СРКВ по различному модулю позволяет значительно упростить анализ и расчет СГЮЗ.

Совокупность доказанных лемм, теорем и следствий можно рассматривать как распространение теории СРКВ над полем GF(p) на модуль N = ру или 2ру.

Кроме обобщения известных свойств СРКВ доказаны 3 теоремы, раскрывающие свойства СРКВ, специфические для модуля N = ру или 2ру, и 2 теоремы, определяющие взаимосвязь между СРКВ по различному модулю.

Это позволяет, в частности, перейти к построению эффективных алгоритмов синтеза РМ.

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

В настоящей главе на основе СРКВ по модулю N = ру или 2ру разрабатываются алгоригмы и программы синтеза РМ. В качестве иллюстрации разработанных методов и алгоритмов приводятся результаты синтеза РМ.

Пусть РМ b(n,K\Xj Я2,--Лт) образовано на основе I смежных классов |Hk() t() ,Hkj tl,.., Нк;_1>t(_I | (t; ф N/2,i = 0, l -1) длиной R, элементы которых являются К+ вычетами данного РМ |b1; Ь2,.., Ък+1 по модулю N:

B = jblfb2,..>bK+)=(Hko>toiHkl>tl,..,HkM>tM}I K+=/-R

Обобщенным понятием спектра разности классов вычетов является /-компонентный СРКВ - спектр разности между I классами {iVo^W-'^-iA-i}: Sko,to;-км>1;-1 '

Будем считать, что спектры имеют одинаковый «рельеф», если величина и число гармоник спектров одинаковы. Т.о. рельеф не учитывает порядок распределения гармоник по индексам классов.

Между рельефом /-компонентного СРКВ и множеством параметров РМ (А,[, Х-2,.., Хт] на основе / классов существует взаимно однозначное соответствие. Т.о., задача синтеза РМ сводится к поиску СРКВ, рельеф которых удовлетворяет заданным ограничениям на параметры РМ (Я.), Х2, ■• Д ш } : по числу уровней т < ттах,

по величине уровней < Хтах (и = 1,т) и др.

Обозначим <3^ - число циклически независимых /-компонентных СРКВ (наборов индексов / классов) среди всего множества СРКВ для заданного /. Циклически связанные СРКВ имеют одинаковый рельеф и отвечают изоморфным РМ. Для

синтеза РМ достаточно рассчитать <3^ спектров.

Исследования, проведенные для одного (/=1), двух (1-2) и трехкомпонентных (1=3) РМ позволяют сделать обобщение на произвольное число классов I. Формула расчета /-компонентного СРКВ:

8^4(0,^0,^ + 1 >Ч+1 (2Л)

¿-О j=^ 1=0 ^ '

где 3(0,То; Д,^) = 8(ОД0; ДД^ + З^.Ц; 0Д0).

Формула, объединяющая наборы номеров СРКВ, которые соответствуют изоморфным РМ:

к

^о'.^^мр^мач =с ^(ко-к,) а^-к,) а., ' ^

Методом исключения из (2.2), формируется <3^ наборов номеров спектров, не связанных циклическими сдвигами. Полученные формулы позволяют реализовать алгоритм синтеза РМ.

Алгоритм синтеза РМ, образованных на основе I классов вычетов, (рис. 2.1) 1. Задать входные данные: модуль N. длину класса К, число классов / и условие ограничения (максимальные число ттах и значение Хтах уровней).

2. Сформировать таблицу СРКВ 8(0, v; А, 1), Л = О, с1, - 1, v < .

3. Сформировать методом исключения набор 1 индексов классов, который не приводит к циклически зависимым СРКВ (2.2).

4. Рассчитать /-компонентный СРКВ по формуле (2.1).

5. Рассчитать множество параметров РМ {1,Д2,..Дт} в соответствии с

полученным рельефом СРКВ.

6. Проверить условия ограничения параметров РМ по максимальному числу т<тшах и значению < Хтах уровней.

7. Определить число изоморфных РМ Ь для данного решения.

8. Записать набор номеров, множество параметров РМ Д2,..Дт} и число изоморфных РМ в банк решений.

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

8 = (8)и+Би8(0Ди;0Ди)+2Ок'$Г0Д-(ки-к]) ,0, (2.3)

формировании таблиц СРКВ 8(0, v; Лд), Д = О, с1( -1, v < I, набора номеров спектров, не связанных циклическими сдвигами, и расчете /-компонентного СРКВ.

Теорема 2.1. /-компонентный и (/-1)-компоненгный СРКВ связаны следующей рекуррентной формулой

Ы

II

1=о

где (8)п =8ко.'с;-ки-1.ч-1;кии.1ин-;к|-1.«1-г

Следствие 2.3.1. Если РМ на основе / классов ограничено по максимальному значению уровней ^тах, то РМ с меньшим числом тех же классов также обладают этим свойством.

Рекуррентная формула (2.3) позволяет реализовать алгоритм синтеза РМ путем последовательного наращивания числа компонент I.

Оценка эффективности алгоритма синтеза РМ по числу элементарных операций по сравнению с прямым переборным методом синтеза РМ, показывает, что общий

2м

выигрыш по числу операций составляет —^-N11.

Одна из качественных оценок показывает, что по сравнению с правилом построения РМ К+,1,о| (М = р2у +ру +1; К+ =ру -1 + 1), образованных на основе

РМ Зингера путем удаления 1 = |1,2,3,..,рг -2| вычетов из общего множества вычетов размерностью рт -1, метод синтеза РМ, предложенный в. диссертации, имеет

следующие преимущества:

- сетка модуля N = ру для РМ на основе CFKB более частая;

- метод синтеза на основе СРКВ позволяет получить РМ с любыми ограничениями на параметры РМ {A.t Д2,.., А.т} : по максимальному числу или значению уровней, с точно заданными значениями уровней и т.д..

Ниже приведены характеристики программ и примеры синтеза РМ с заданными ограничениями по максимальному уровню Ятах для N = рг. Результаты расчетов распространяются на случай N = 2рг ввиду совпадения рельефов СРКВ по модулю 2ру и рт согласно теореме 1.8.

По предложенным алгоритмам были разработаны две программы для IBM PC с процессором Р-200 на языке высокого уровня Паскаль: программа синтеза РМ на основе одного и на основе нескольких классов вычетов. Более простая реализация алгоритма синтеза РМ на основе одного класса позволяет снизить объем используемой памяти и увеличить быстродействие при одинаковых параметрах РМ N и К+.

1) Программа синтеза РМ на основе одного класса при размере оперативной памяти 8 Мб позволяет рассчитывать РМ с параметрами N < 10б,( 3 < р < 997, у <12). В качестве иллюстрации работы программы приведены результаты синтеза РМ, ограни-тенных по уровню значением Х^ = 2, для N < 104, R < 20.

2) Программа синтеза РМ на основе нескольких классов (/ < 3) при размере оперативной памяти 8 Мб позволяет рассчитывать РМ с параметрами N<4'105,( 3<р<631, у <10). В качестве иллюстрации работы программы представ-1ены результаты синтеза РМ, ограниченных по уров!по величиной А^ = 1 и = 2 ум N <104,R< 15' с наименьшими значениями N/N'0Irr> где Nom =К+^К+ -^Д + Р

Следует отметить высокое быстродействие программ синтеза РМ: время расчета 'М, приведенных в диссертации, составляет несколько минут при объеме занимаемой щеративной памяти не более 0,2 Мб.

РМ на основе нескольких классов по сравнению с РМ на основе одного класса об-

ладают более плотной «упаковкой» (меньшее соотношение N / Моггг) и частой сеткой параметров N. Кроме того, согласно следствию 2.1, каждому РМ на основе I классов, ограничешгого по уровню величиной А.шах, соответствует совокупность РМ на основе

] классов ] = 1, / -1, объединяющая 21 -1 РМ, которые можно сформировать путем комбинирования 1 классов.

Результаты проведенных расчетов РМ позволяют оценить быстродействие программ и показать возможности синтеза РМ по предложенным алгоритмам. Результаты синтеза РМ, приведенные в диссертации, по сравнению с известными результатами расчетов (М.Б. Сверддик) являются новыми, но уступают им по параметру оптимальной «упаковки» N / Мопт.

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

Разработанные алгоритмы синтеза РМ отличаются:

- универсальностью: применимы для синтеза РМ на основе произвольного числа классов I любой длины К, по произвольному модулю N = рг или 2рг ;

- простой реализуемостью на ЭВМ - все операнды числа;

- возможностью синтезировать РМ с заданными ограничениями на параметры (РМ, с ограничением на максимальное число и значение уровней и др.);

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

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

ПОЛЯМИ ГАЛУА

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

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

мов и программ расчета таблиц 1ПТ над простыми и расширешн>ши полями Галуа.

Пусть GF(q) — алгебраическое расширение поля GF(p) степени n, q = р" и GF(q) порождается некоторым образующим элементом а — корнем НП f(a) степени п с коэффициентами из GF(p).

Пусть нормированный полином m-ой степени с коэффициентами из GF(q) F(x)HXm+ ат_1хш_1+...+а1х + а0 mod(f(a),p), am_j еGF(q) неприводим над GF(q).

В кольце вычетов по модулю М = qm -1 выделим подгруппу Н0 в группе взаимно простых с М: Н0 = jl, q, q2,.., qm_1 j ■

Построим смежные классы вычетов по подгруппе Н0 по правилу HkShkHo = )hk>hkq>hkq2,..thkqn'-1) modM.

Смежный класс определяет корни полинома, которые являются q-сопряженными и принадлежат одному полиному.

Периоды q-сопряженных корней одинаковы и равны периоду НП. Если с - первообразный корень поля GF^qm j и xh = eh mod (F(x),f(a), p), то период x равен

N»=W ' (ЗЛ)

Теорема 3.1. Пусть {Zh} - М-последователыюсть, построенная на основе примитивного над GF(q) полинома F(x) m-ro порядка с начальными условиями {1, 0,.., О, 0} и jh^jj - k-ый смежный класс вычетов но модулю М (j = l,mj, имеющий m различных элементов. Полином с коэффициентами

г>

am-j = naod(f(a),p), j = l,m,

S=1

^(Ьк/, +Ьк>/2+-+Ьч)М1 О-'1 </2 <-<1} ~т)

неприводим над полем ОР^).

Доказательство теоремы основано на упорядочении неггулевых элементов расши-

репного поля по степеням £ (причем в качестве модульного полинома используется сопряженный полином Р.* (х)) и замене корней НП в формуле Виета их степенями. Неприводимость полинома* с .приведенными выше коэффициентами следует из того,

что его корнями являются различные элементы с * , е

поля ей

И-

М-последовательяость имеет цутовую структуру. Длина цуга равна Нц = -

4-1

Назовем блок НП, соответствующий смежным классам с Ьк < , основным информационным блоком. Запишем элемент класса в виде

Ь = МЦ1111+Ь1,' (3.2)

где Ьп - номер цуга, Ъ1 - номер элемента М-последовательности в первом цуге.

Следствие 3.1. Пусть {г^} - первый цуг М-последовательности, построенной на основе примитивного над ОР(с)) полинома Б(х) т-го порядка с начальными условиями {1, 0,.., 0, 0}. {ь^} - к-ый смежный класс вычетов по модулю М ^ = имеющий т различных элементов (Ц.о <!ЯЦ). Тогда все множество НП можно

представить в виде q-l информационных блоков - основного блока и производных от него. Коэффициенты НП основного блока рассчитываются по формуле

.с'

тос^офр), ~ 1,т,

(3.3)

где О - первообразный элемент, по степеням которого упорядочены цуги в М-последовательности еОБ^)).

1

I

1=1

1=1

¡=1

К/,

N.

то(1 ^ - 1), (1 < /1 < 12 <..< ^ < ш).

Коэффициенты и-го блока НП находятся через коэффициенты основного блока по формуле |

v -"'ч-!

тос! (£(а), р) •

(3.4)

5=1

Практическим применением теоремы являются два алгоритма расчета таблиц НП - над простыми и расширенными полями Галуа. Согласно предложенным алгоритмам расчеты всех коэффициентов производятся только на основе первого цуга М-последовательности. Согласно следствию 3.1 достаточно рассчитать коэффициенты и периоды основного информационного блока, а остальные q-l блоков можно получить простым пересчетом.

Алгоритм расчета таблиц НПнад полем СР(ф.

1. Сформировать мультипликативную группу поля ОР(<}) на основе выбранного неприводимого полинома 1:((х).

2. Случайным выбором коэффициентов найти примитивный полином Р(х).

3. Сформировать базовый цуг М-последователыгости с начальными условиями {1,0,..,0,0} длиной Иц.

4. Разделить все индексы 11 = 1,МЦ -1 на смежные классы вычетов по модулю М по подгруппе Н0. Индексы записываются в виде (3.2)

4. Рассчитать коэффициенты НП основного блока по формуле (3.3).

6. Рассчитать период НП по формуле (3.1).

7. Рассчитать коэффициенты и-го блока НП через коэффициенты основного блока по формуле (3.4).

Алгоритм расчета таблиц НП над полем ОР(р) отличается от приведенного выше алгоритма наиболее простой реализуемостью на ЭВМ, т.к. коэффициенты НП и элементы М-последовательности не полиномы степени п - элементы поля ОР(ф, а числа. Это позволяет при реализации алгоритма на ЭВМ увеличить размер входных данных: степени полинома и характеристики простого поля при одинаковых объеме используемой памяти и быстродействии ЭВМ по сравнению с расчетом таблиц НП над расширенным полем Галуа.

Недостатком алгоритмов является наличие переборного этапа расчета, в ходе которого находится один НП заданной степени и вычисляется его период.

По предложенным алгоритмам были разработаны две программы для ШМ РС с процессором 80486БХ на языке высокого уровня Паскаль с использованием встроенного Ассемблера.

1) Программа расчета таблиц НП над простым полем Галуа ОР(р) нечетной характеристики при размере оперативной памяти 5,7 Мб позволяет рассчитывать все НП информационного блока с параметрами:

3 < р < 1103 и 3 < п < 13 при рпЧ <106, р< 32749 при а = 2. (3.5)

По результатам расчетов опубликованы таблицы НП над ОР(р) для

рп~ 1 < 2 • 104, 3 < р < 97, п < 10 и по одному примитивному полиному с минимальным числом ненулевых коэффициентов для (3.5)

2) Программа расчета таблиц НП над расширенным полем Галуа ОР(ф при размере оперативной памяти 5,2 Мб позволяет рассчитывать все НП информационного блока с параметрами:

Чш4<4105, 2 < р < 73 (п<18,т<10), (Ч=рп). (3.6)

Для п = т = 2 характеристика поля ограничена значением р < 787 .

По результатам расчетов опубликованы таблицы НП для qm~1 < 104, 2 < р < 97, п < 11, т < 7 и по одному примитивному полиному с минимальным числом непулевых коэффициентов для (3.6).

Общее время расчета всех информационных блоков таблиц НП над простыми и расширенными полями Галуа с указанными выше параметрами, составляет 20 минут при требуемой памяти не более 0,3 Мб.

Отличительными особенностями разработанных алгоритмов являются:

- универсальность (инвариантность к характеристике поля, степени полинома и виду поля - простое или расширенное);

- удобство в расчетах - одновременно с коэффициентами НП вычисляются корни и их периоды;

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

- простота реализуемости на ЭВМ;

- компактность представления результатов расчета полной таблицы НП в виде относительно небольшого информационного блока.

Рассчитанные таблицы НП по сравнению с наиболее полными таблицами НП из

известных автору в отечественной и зарубежной научно-технической литературе имеют не менее чем на единицу больше границу для п, а по максимальной характеристике границу ртах = 97 для п = 2. Опубликованные таблицы 11П над расширенными полями можно назвать уникальными, гак как среди множества публикаций аналогов, сравнимых по объему представленной информации, найти не удалось.

Предложенные алгоритмы расчета позволяют генерировать множества НП с заданными параметрами (характеристика поля, степень полинома, период корней и т.д.)

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты.

1. Доказаны леммы, теоремы и следствия, определяющие основные свойства спектров разности классов вычетов по модулю N = ру или 2рг . Т.о., теория СРКВ над простым полем Галуа обобщена на модуль N = рг или 2ру .

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

Разработанный метод позволяет компактно представить результаты синтеза в виде относительно небольшого информационного блока.

3. Предложены алгоритмы синтеза РМ, с заданным ограничением на число и величину уровней, на основе одного и нескольких классов. Достоинствами алгоритмов является:

- универсальность: применимы для синтеза РМ на основе произвольного числа классов I любой длины, по произвольному модулю N = рг или 2рт ;

- простая реализуемость на ЭВМ - все операнды числа.

4. Разработан комплекс программ синтеза РМ на основе одного и нескольких классов вычетов (/ < 3) .

В качестве иллюстрации работы программ приведены результаты расчетов на ЭВМ РМ, ограниченных по уровню Хтах = 1 и Л,тах = 2, при N < 104 на основе одного, двух и трех классов. Следует отметить, что расчеты РМ выполняются всего за несколько минут на компьютере средней производительности.

5. Доказана теорема, определяющая метод расчета глобального множества нормированных НП для заданных характеристики поля и степени полинома, на основе

одного примитивного полинома.

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

6. Предложены алгоритмы расчета коэффициентов НП и их периодов над простыми и расширенными полями Галуа. Достоинствами алгоритмов являются:

- универсальность - они применимы для расчета коэффициентов НП произвольной степени как над простыми, так и над расширенными полями Галуа произвольной характеристики;

- простота реализуемости на ЭВМ - большинство операндов числа;

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

7. Разработан комплекс программ расчета таблиц НП над простыми и расширенными полями Галуа.

По результатам расчетов опубликованы таблицы НП значительно превосходящие по объему все известные автору в отечественной и зарубежной научно-технической литературе: таблицы НП над вР(р) для рп_1 <2-104, 3<р<97, п<10 и таблицы НП над (ч=Рп) Для <104, 2<р<97, п<11, т<7.

Следует отметить, что опубликованные таблицы НП составляет лишь 0,2 % от рассчитанных для простых полей и сотые доли процента для расширенных полей, а время расчета таблиц НП составляет всего несколько минут на компьютере средней производительности. Достоинствами разработанных 'алгоритмов и программ синтеза РМ и расчета таблиц НП является возможность вычислять РМ и НП с заданными ограничениями на параметры (НП с минимальным числом ненулевых коэффициентов, с заданным периодом и др.; РМ, сбалансированные на определенное число уровней, с ограничением по максимальному значению уровня и др.)..;.

ПРИЛОЖЕНИЕ

включает в себя программу синтеза РМ на основе СРКВ по модулю N = ру или 2рт и программу расчета таблиц НП над расширенными полями Галуа.

СПИСОК ПУБЛИКАЦИЙ Ю.В. ЗАХАРИПА

1. Гантмахср В.Е., ЗахаринЮ.В. Расчет коэффициентов неприводимых над простыми полями Галуа полиномов. Программа для ЭВМ. Зарег. в Реестре программ для ЭВМ в РосАПО №970105 от 13.03.97.

2. Гантмахер В.Е., ЗахаринЮ.В. Расчет коэффициентов неприводимых над расширенными полями Галуа полипомов. Программа для ЭВМ. Зарег. в Реестре программ для ЭВМ в РосАПО №970106 от 13.03.97.

3. Гантмахер В.Е., Захарин Ю.В. Вычисление коэффициентов неприводимых над полем GF(p) полиномов произвольной степени /НовГУ. -Новгород, 1995. -12 с. -Деп. в ВИНИТИ №803-В95 от 31.03.95.

4. Гантмахер В.Е., ЗахаринЮ.В. Вычисление коэффициентов неприводимых над расширенным полем Галуа полиномов /НовГУ. -Новгород, 1995. -8 с. -Деп. в ВИНИТИ №3070-В95 от21.11.95.

5. Гантмахер В.Е., Захарин Ю.В. Таблицы неприводимых над GF(p) полиномов /НовГУ. -Новгород, 1995. -270 с. -Деп. в ВИНИТИ №910-В95 от 05.04.95.

6. Гантмахер В.Е., Захарин Ю.В. Таблицы неприводимых над GF|pnj полиномов

/НовГУ. -Новгород, 1995. -465 с. -Деп. в ВИНИТИ №3006-В95 от 10.11.95.

7. Гантмахер В.Е., Захарин Ю.В. Эффективный метод построения таблиц неприводимых над простыми полями Галуа полиномов произвольной степени //Электроника и информатика: Тез. докладов Всероссийской науч.-техн. конференции. МГИЭТ ТУ. - М.: 1995.-с. 322-323.

8. Гантмахер В.Е., Захарин Ю.В. Расчет таблиц неприводимых над простыми и расширенными полями Галуа полиномов //Цифровая обработка сигналов и ее применение: Труды Iй Международной науч.-техн. конференции. -М.: 1998. Т. 2, -с. 46-50.

9. Сложные диасретно-кодированные сигналы для радиотехнических систем различного назначения: Отчет о НИР 9/ЦОС-ГБ/ НовГУ; Науч. руководитель Гантмахер В.Е., исполнитель ЗахаринЮ.В. - Новгород, 1997.

10. Применение псевдослучайных последовательностей в диагностических и информационно-поисковых системах: Отчет о IfflP Ю5/ЦОС-ГБ/ НовГУ; Науч. руководитель Гантмахер В.Е., отв. исполнитель Захарин Ю.В. - Новгород, 1997.