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

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

ЕДЕМСКИЙ Владимир Анатольевич

2 7 АО 1 'и

СИНТЕЗ ДВОИЧНЫХ И ТРОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ЗАДАННОЙ

СОВОКУПНОСТЬЮ СВОЙСТВ ИЛИ ОГРАНИЧЕНИЙ НА ИХ ХАРАКТЕРИСТИКИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Великий Новгород - 2009

003475807

003475807

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

Научный консультант: доктор технических наук, профессор

Гантмахер Владимир Ефимович

Официальные оппоненты: доктор физико-математических наук,

профессор

Леухин Анатолий Николаевич

доктор физико-математических наук Панов Евгений Юрьевич доктор физико-математических наук Золотухина Лидия Анатольевна

Ведущая организация: Институт прикладных математических

исследований Карельского научного центра РАН

Защита диссертации состоится () i. 4 0 ■ 2009 года в 0О на заседании диссертационного совета Д 212.168.04 при Новгородском государственном университете имени Ярослава Мудрого по адресу: 173003, г. Великий Новгород, ул. Б. С-Петербургская, д. 41, ауд._

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

Автореферат разослан " 0 8 • 2009 г.

Ученый секретарь диссертационного Совета

Д 212.168.04, кандидат физико-математических л Токмачев М. С.

наук, доцент Ж^

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

Актуальность работы. Двоичные и троичные последовательности являются самыми широко востребованными дискретно-кодированными последовательностями, область применения которых с каждым годом расширяется. В вычислительных системах их используют в качестве псевдослучайных последовательностей для имитационного моделирования, обеспечения связи между компьютерами, тестирования, решения задач методом Монте-Карло. В телемеханических системах на основе двоичных и троичных последовательностей строят самосинхронизирующиеся коды с обнаружением и исправлением ошибок. В системах связи и передачи информации на основе двоичных и троичных последовательностей осуществляют скрытную связь с высокой криптостойкостью. В системах радиолокации, гидролокации, радионавигации их используют в качестве модулирующих последовательностей при формировании сложных шумоподобных сигналов, обеспечивая высокие потенциал и помехоустойчивость при низкой пиковой мощности передатчиков. Столь широкий спектр применений обуславливает набор требований к таким характеристикам и свойствам последовательностей, как: период, вес, уровень боковых лепестков корреляционных функций, пик-фактор, уравновешенность, эквивалентная линейная сложность и другим. Число требований к набору свойств последовательностей год от года увеличивается.

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

- автокорреляция - Свердлик М.Б., Ипатов В.П., Камалетдинов Б.Ж., Пелехатый М.И., Габидулин Э.М., Гантмахер В.Е., Леухин А.Н., Холл М., Кренгель Е. И., Сторер С., Динг К.,...;

- эквивалентная линейная сложность - Лидл Р., Нидеррайтер Г., Берлекэмп Э., Мешковский К.А., Ипатов В.П., Камалетдинов Б.Ж., Динг С., Мальцев С. В.,...;

- взаимная корреляция (расчет и оценка) - Сидельников В.М., Мешковский К.А, Кренгель Е. И., Гантмахер В. Е., Ким Я.Х., Сонг Н.Е.,...

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

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

вычетов, которые обладают, по сравнению с известными последовательностями, более плотной сеткой периодов и более плотным рядом значений пик - фактора. Сравнение известных способов синтеза ДКП показывает, что синтез ДКП с использованием СРКВ является наиболее универсальным методом синтеза двоичных, троичных и бинарных последовательностей, формируемых на основе классов степенных вычетов. Но и ему, в том виде, в котором он представлен в [1], присущи серьёзные недостатки:

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

- в этом методе заложена потенциальная возможность синтеза ДКП с заданной совокупностью свойств, но она не реализована;

- нет метода расчёта эквивалентной линейной сложности ДКП, сформированных по обобщенному правилу кодирования, на основе СРКВ;

- представляет интерес распространение методов синтеза ДКП с периодом р, в основе которых лежат СРКВ, на синтез ДКП с составным периодом тр.

Настоящая диссертационная работа посвящена вопросам синтеза и анализ двоичных и троичных последовательностей, сформированных на основе классов степенных вычетов по простому модулю р , с заданной совокупностью свойств. Особенность постановки задачи синтеза заключается в том, что ограничения задаются на произвольный набор перечисленных выше свойст или характеристик последовательностей. Задачи синтеза и анализа решаются н основе единого математического аппарата СРКВ и циклотомических чисел.

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

- усовершенствование методики анализа и синтеза дискретнс кодированных последовательностей на основе СРКВ путём применен! циклотомических чисел;

- разработка методов синтеза двоичных и троичных последовательностей заданной совокупностью свойств или ограничений на их характеристики синтез последовательностей с определённым набором свойств ил характеристик;

- расчёт эквивалентной линейной сложности дискретно-кодированны последовательностей, сформированных на основе классов степенны вычетов;

- распространение методики синтеза ДКП с простым периодом р н последовательности с периодом тр, где т - натуральное число, взаимн простое с р;

- разработка алгоритмов и комплекса программ, реализующр предложенные методы синтеза последовательностей.

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

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

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

• определены новые правила кодирования семейств двоичных последовательностей с периодом р и квазиодноуровневыми периодическими автокорреляционными или взаимно корреляционными функциями;

• получены новые семейства троичных и бинарных последовательностей с периодом р и квазиидеальными периодическими автокорреляционной и взаимно корреляционной функциями;

• предложен унифицированный метод расчета эквивалентной линейной сложности ДКП, формируемых на основе классов степенных вычетов по простому модулю;

• расширена область применения теории СРКВ по простому модулю на синтез двоичных и троичных последовательностей с периодом тр;

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

Теоретическая и практическая значимость. Диссертационная работа носит теоретический характер. Полученные в ней результаты, разработанные методы и комплекс программ могут быть использованы для синтеза широкого класса двоичных и троичных последовательностей, применяемых в математических моделях, в вычислительных системах, в криптографии, в качестве модулирующих последовательностей в системах связи, радиолокации и других областях. В частности, результаты диссертационной работы были использованы в следующих научно-исследовательских работах:

1. Грант РФФИ № 07-01-97615-р_офи «Разработка принципов построения квазиодноуровневых разностных множеств с заданными ограничениями на их параметры», руководитель Гантмахер В. Е.

2. Фундаментальная НИР "Теория анализа, синтеза и обработки шумоподобных сигналов в радиотехнических системах различного назначения", руководитель Гантмахер В.Е., по заданию Рособразования, гос. per. № 0120.0 503550, 2005-2009 г.

3. Фундаментальная НИР "Исследование методов синтеза сложных сигналов, видов модуляции и способов обработки для перспективных

радиолокационных систем", руководитель Гантмахер В.Е., по научно -технической программе Рособразования «развитие научного потенциала высшей школы», гос. per. № 0120.0 603815, 2006-2008 г.

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

Личный вклад автора. В диссертационной работе обобщены результаты, выполненные лично автором или при его непосредственном участии. Постановка задач принадлежит научному консультанту Гантмахеру В. Е. Исследования по комплексному применению СРКВ и циклотомических чисел для анализа и синтеза последовательностей, а также расчету их эквивалентной линейной сложности выполнены лично автором. Программы для ЭВМ разработаны совместно с Вагуниным И. С.

Апробация работы. Результаты работы обсуждались на всемирном форуме «Signal Design and Its Applications in Communications (IWSDA'07)»(KirraH, Чанджоу), неоднократно докладывались и обсуждались и международных научно-технических конференциях «Цифровая обработк сигналов и её применения» (г. Москва - 2007, 2008); «Радиолокация, навигащ и связь» (г. Воронеж -2007- 2008); «Научные исследования и их практическо применение. Современное состояние и пути развития» (г. Одесса - 2006-2008)-«Современные проблемы математики и естествознания» (г. Нижний Новгород 2006); «Математика в вузе» (г. Санкт-Петербург - 2005-2008); на симпозиум по «Прикладной и промышленной математике», осенняя сессия (г. Йошкар-Ол - 06); на семинаре «Шумоподобные сигналы и их применение» (НовГУ), i также на семинарах кафедр КПМИ и PC НовГУ.

Публикации. Всего по теме диссертации опубликовано 35 работ, из ни одна монография, 2 статьи - в международных изданиях, 10 - в журналах входящих в перечень, рекомендованный ВАК для публикации основны результатов докторских диссертаций. Получено два свидетельства регистрации программ для ЭВМ. При участии автора подготовлено 5 отчего по НИР. Перечисленные работы достаточно полно отражают содержани диссертации.

Структура и объем диссертации. Диссертация состоит из введения, сем глав, заключения, приложений и списка литературы. Общий объем диссертаци составляет 266 страниц. Библиография содержит 125 наименований.

На защиту выносятся следующие основные положения:

1. Обобщенная методика синтеза двоичных, троичных и бинарны последовательностей, сформированных на основе классов степенны вычетов, с заданной совокупностью свойств или ограничений на и характеристики;

2. Методы и результаты синтеза двоичных, троичных и бинарны последовательностей с заданной совокупностью свойств ил

ограничений на их характеристики на основе обобщенной методики синтеза дискретно-кодированных последовательностей;

3. Метод и результаты расчета эквивалентной линейной сложности двоичных и троичных последовательностей. Новые правила кодирование семейств дискретно-кодированных последовательностей с большой линейной сложностью;

4. Методика и результаты синтеза двоичных и троичных последовательностей с периодом тр и заданной совокупностью свойств или заданными ограничениями на их характеристики;

5. Алгоритмы и комплекс программ, реализующих предложенные методы синтеза.

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая глава посвящена краткому анализу известных результатов синтеза двоичных (ДП) и троичных последовательностей (ТП), сформированных на основе классов степенных вычетов по обобщённому правилу кодирования (ПК), предложенному Свердликом М. Б.,

1, если / е Нк,к е I, их(Г) = - -1, если ¡еЯ,,/е J, (1)

0, в ост. случаях.

Здесь р = (Ш+1 - простое число; Л,Я - натуральные числа; Нк- класс степенных вычетов с номером к: Нк ={вк*Л, / = 0, Я-1}, 0 - первообразный корень по простому модулю, /, У — непересекающиеся подмножества индексов к и I, 0<к,1<Л-\,к*1.

В диссертации используются следующие характеристики методов синтеза:

- универсальный, если синтез осуществляется по совокупности характеристик (период, абсолютная величина разности между наибольшим и наименьшим боковыми лепестками (БЛ) ПАКФ или ПВКФ, относительная разность между максимальным и минимальным БЛ ПАКФ или ПВКФ, пик-фактор, уравновешенность, эквивалентная линейная сложность и т.п.);

- обобщенный, если известные ДКП получаются как подмножество синтезированных;

- продуктивный - при возможности получения множественных результатов синтеза ДКП (семейств ДКП, ПК);

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

Проведённый анализ показал, что наиболее универсальным, обобщенным и эффективным методом синтеза двоичных, троичных и бинарных последовательностей, формируемых по ПК (1), является метод, основанный на СРКВ. Согласно теории СРКВ для ПАКФ ДКП, сформированной по ПК (1), справедливо взаимно однозначное соответствие:

(2)

где 5Л-/ = *>0" ХСФ.О+ЭД.*))» - спектр разности

классов степенных вычетов Нк и Я/, к,1 = 0,г/-1. Соотношение (2) обобщается наПВКФпары ДКП.

Таблицы СРКВ полностью определяют рельефы ПАКФ и ПВКФ ДКП, сформированных по обобщенному правилу кодирования.

Вторая глава посвящена усовершенствованию методики анализа и синтеза дискретно-кодированных последовательностей на основе СРКВ путём применения циклотомических чисел. Для достижения заявленной цели необходимо:

- показать, что использование циклотомических чисел повышает результативность применения математического аппарата СРКВ для расчета рельефов корреляционных функций;

- разработать комплексную методику синтеза широкого класса двоичных и троичных последовательностей с заданной совокупностью свойств или ограничений на их характеристики на основе СРКВ и циклотомических чисел;

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

Решение первой задачи главы рассмотрено в подразделе 2.2. Обозначим через («, ])Л , «,у' = 0,£/-1 циклотомические числа порядка с!.

Теорема 1. СРКВ ¿"(О, Л, ¿У) связан с циклотомическими числами соотношением:

$(0А«*) = ((0,Д)<„(1,Д)1/,......,(</-

При <1 = 3,4,6,8,12 циклотомические числа определяются посредством разложения простого числа р на сумму квадратов целых чисел. Следовательно, теорема 1 позволяет выразить гармоники СРКВ через две-четыре переменные, в частности, через:

- если <1 = 3, 4р = 12 +27М2, Ь =1 (шоёЗ);

- х,у, если ¡1 = 4, р = х2+4у2, (тос!4);

- А,В, если ¿ = 6, р = А2 +ЗВ2, А = 1(тоаЗ);

- х,у,а,Ь, если с! = 8, ^ = х2 + 4у2 = а2 + 2Ь2 , хза = 1(тос)4);

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

Теория СРКВ и теорема 1 позволяют предложить в подразделе 2.3 методику синтеза ДКП с заданной совокупностью свойств или ограничений на характеристики из следующего набора: период, ПАКФ, ПВКФ, пик-фактор, вес, степень уравновешенности, состоящую из четырех этапов:

A) Расчет допустимых значений р,с!,11,и на основе анализа исходных данных и требований к синтезируемым ДКП;

B) Вычисление спектральных составляющих таблицы СРКВ, в том числе, с использованием циклотомических чисел по теореме 1, если заданы ограничения на ПАКФ (ПВКФ);

C) Расчет характеристик синтезируемых ДКП;

Б) Анализ характеристик ДКП, сопоставление с заданными свойствами и ограничениями на характеристики.

С целью иллюстрации комплексной методики в подразделе 2.4 рассмотрена задача синтеза ДП с квазиодноуровневой ПАКФ и р/~2.

Обозначим Яо,...,Ая_, упорядоченные по возрастанию уровни БЛ ПАКФ ДП, а рельеф ПАКФ ДП - Ах(г) = {Д0,Л1,...,Д„_1}. Пусть АЛХ- разность между

наибольшим и наименьшим значениями БЛ ПАКФ ДП, а у = -

кх

относительная разность. Применение комплексной методики синтеза ДКП приводит к следующим результатам.

Теорема 2. Если ДП X сформирована по ПК (1) при с! = 4 и / = {0,1}, то Р-3-2Ы

—--,если Л-нечетное, п. Л-нечетное,

« ,м >ЛЛИ , „

-5-2 у м + 1, если л-четное -—, если Л - четное

Следствие 2.1. ДП X с периодом р = х2+ 4 и весом для ¿ = 4

имеет двухуровневую ПАКФ Ах(т)-{л0,Л0+1},т = 1,р-1. Это известный результат [4].

Теорема 2 определяют достаточные условия существования ДП с квазиодноуровневой ПАКФ. Если А1тах - заданное пороговое значение для

ПАКФ, то ограничение Мх < ДЯгаах выполняется для ДП с периодом р: р = х2 + 4у2, ¡Д'! +1 ^ ААшах.

Обозначим через (В)3 — наименьший положительный вычет числа В по модулю 3.

Теорема 3. Для нечетного Л ДП с весом имеют трехуровневую ПАКФ Лх(т) = [л0,А0+^,Л0+ААх^,т = 1,р-1,где [р-3 Щ

4 3 ' р-3 М±5|

если (В)3 = О, , если (В)3 ^ 0.

, =

4|5|

-у1, если (В) з =0,

2|Л + В|

, если (В)з * 0,

4 з »-/з-

относительно ПК (1)при Л = 6,/ = {0,1,2} и пик-фактор р/ ~2.

Следствие 3.1. ДП с периодом р = 4(Зи-1)2 +3(1+6и)2 = 144и2 + 12и+7 или р = 4(2+3«)2 + 3(1 + (м)2 = 144м2 +84«+19, весом имеет трехуровневую ПАКФ

Л.х(т) = {Я0,Я0+1,Л0 + 2}, г = 1,р-1 с М^г.Ло

р-3

-1, у=

р-1

и пик-фактор

р/ и 2 относительно ПК (1) для ¿/ = 6, / = {0,1,2}.

Следствие 3.2. ДП X с периодом р = Л2 +27и2 и весом

р-1

имеет

трехуровневую ПАКФ Дх(г) = {я0,Л0+|и|,^)+2|ы|}, г = 1,р-1 с АЛХ = 2\и\, и пик-фактор р/«2 относительно ПК (1) для с! = 6,

/ = {0,1,2}.

Теорема 4. Для четного Я ДП с весом имеет ПАКФ с

Ло =

Р-5 Щ 4 3

если (В) з = 0,

=

4|В|

если (В) з =0,

2\А±В\

+1, если <В>з * О,

4 3

относительно ПК (1) для <1 = 6,1 = {0,1,2} и пик-фактор р/ ~ 2.

Следствие 4.1. ДП X с периодом р = 4(1+6м)2+з(би-1)2 или р = 4(1+6и)2 + 3(4 +6и)2 и весом имеет четырехуровневую ПАКФ

Ад-(г) = {^,,^0++2,^0 + 3}, г = 1,р-1, ДЛ^З с —г и пик-

фактор р/«2 относительно ПК (1), / = {0,1,2}.

6 р-1

Следствие 4.2. ДП X с периодом р = А2 + Ши2 и весом ——- имеет

ПАКФ

относительно ПК (1) для ¿ = 6, I = {0,1,2}.

В условиях теорем 3, 4 параметр у убывает обратно пропорционально р, если значения В или А±В - постоянны. ПАКФ ДП, определяемой следствиями 3.1-4.2, несколько отличается от одноуровневой, но с ростом р это отличие становится незначительным.

Теоремы 2-4 определяют новые регулярные ПК ДП с заданными свойствами и показывают, что комплексное использование СРКВ и циклотомических чисел результативно.

Всего в подразделе 2.4 получено десять новых регулярных ПК ДП с квазиодноуровневой ПАКФ и р/ я 2. Известные ДП, обладающие такой же совокупностью свойств являются частным случаем синтезированных (следствие 2.1). В подразделе 2.5 рассчитаны характеристики ПВКФ ДП, синтезированных в подразделе 2.4.

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

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

- разработка методов синтеза ДП с заданными ограничениями на характеристики, такие как: период, рельеф ПАКФ или ПВКФ, пик-фактор и поиск новых ПК ДП, обладающих квазиодноуровневой ПАКФ или ПВКФ;

- анализ ПВКФ (ПАКФ) синтезированных ДП с квазиодноуровневой ПАКФ (ПВКФ).

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

Задача подраздела 3.2 - разработка методов синтеза ДП с заданными ограничениями на период, рельеф ПАКФ, пик-фактор. Справедливы следующие утверждения.

Теорема 5. ДП X, сформированная по ПК (1) для ¿ = 4 с периодом р = (1 + 4§)2 + 4(2ы+1)2, имеет двухуровневую (одноуровневую при я = 0) ПАКФ

и пик-фактор р/ ~ 4. Здесь - целые числа.

Теорема 5 обобщает известные результаты о ДП на основе класса биквадратичных вычетов [ 1,2,4].

Теорема 6. Для нечетного значения Л ДП с периодом р-А2 +ЪВ2 и весом

^ при г = 0(то<33) и |2Л + 1|<|Л| обладает ПАКФ

6

Лх (г) = {Ло, ^о + ДЯ,, Ло + ДА^}, т = 1, р -1, где ¿о =0>-5 + 4Л-6|в|)/36, ДАх=у и

_ ; относительно ПК (1) при ¿/ = 6 и пик-фактор р/ « 6. р-1

Теорема 7. Для нечетного Л ДП с периодом р = А2+ЗВ2, весом ^ при

6

/ \ {В-\<,А<2В, если5>О П11р;1.

В = -1(тос13) (В = -Ыв2(тоаЗ)) и А-А „ имеет ПАКФ

( ! --1-В + 11 1

Лх(т) = {Я0,Л0 + Л^,Я0+АЯх1 т = \,р-\, С = ,

Ло =тт((р-5-2^ + 6В)/Зб;(/7-11-2Л)/36) относительно ПК (1) при <1 = 6 и пик-фактор р/ я 6.

Если В = l(modЗ), то в теореме 7 необходимо заменить В на - В.

Теорема 8. ДП с периодом р = х2 + 64н2 =а2 +2Ь2, а = 1±8^ и же [-а-2,-За], сформированная по ПК (1) при ¿ = 8 имеет ПАКФ ЛХ(Т) = {Л,Л + А1Л,Л+АЛХ}, г = 1,р-1 и пик-фактор р/*8. Здесь х,и,Ь- целые числа.

Частные случаи теоремы 8 (АЛХ =0;1) - известны [2,4].

Теоремы 5-8 задают достаточные условия существования ДП с квазиодноуровневой ПАКФ и позволяют формировать ДП с заданными ограничениями на их характеристики.

Всего в подразделе 3.2 найдено семнадцать новых регулярных ПК ДП с квазиодноуровневой ПАКФ и пик-фактором р/: Ъ<р/ <10. Сформированы новые семейства ДП, которые обладают, за счет отказа от одноуровневости ПАКФ, большей плотностью сетки периодов, чем у известных последовательностей, а также значениями пик-фактора, отличного от значений известных ДП. Рассчитаны параметры р,К,Л(),АЛх,у ДП с квазиодноуровневой ПАКФ при <1 = 4,6,8 и ДЯд- < 4. Кроме этого, в подразделе 3.2 определены необходимые и достаточные условия существования ДП с периодом р = \+1№, с! = 3,4,6,8 и двумя уровнями БЛ ПАКФ (РМ, сбалансированных на два уровня, имеющих свой круг применений). Известные ДП, обладающие такими же свойствами, являются частными случаями синтезированных (теоремы 5,8).

Комплексная методика и теоремы, доказанные в подразделе 3.2, определили методы синтеза ДП с заданными ограничениями на их характеристики: период, рельеф ПАКФ, пик-фактор.

Задачей подраздела 3.3 является разработка методов синтеза ДП с заданными ограничениями на период, рельеф ПВКФ, пик-фактор.

Справедливы следующие утверждения.

Теорема 9. Если пара ДП Хи У сформирована по ПК (1) при ¿ = 4,

- /| = 2, то

Д'Хг =

если Я - четное,

:1+Н

, если Я - нечетное

2

где ДгХу ~ разность между наибольшим и наименьшим значениями ПВКФ

Следствие 9.1. Пара ДП Хи У, сформированных по ПК (1) при с1 = 4 имеет одноуровневую ПВКФ тогда и только тогда, когда р = \виг+\, где и -целое число и \к -1\ = 2. В этом случае гХУ(г) = и2, т = \,р-\.

Теорема 10. Пара ДП X и У, сформированных по ПК (1) при <1 = 6, имеет одноуровневую ПВКФ тогда и только тогда, когда р = 1 + 108ы2 и \к-1\ = 3.

При выполнении условий теоремы гх Г[г)=^—^ = 3иг, т = \,р~\.

36

Теоремы 9,10 определяют необходимые и достаточные условия существования пар ДП с одноуровневой ПВКФ. В подразделе 3.3 также определены параметры ДП с квазиодноуровневой ПВКФ.

Комплексная методика определила методы формирования ДП с ограничениями на ПВКФ, период и пик-фактор. Их применение позволило сформулировать семь регулярных ПК семейств ДП с квазиодноуровневой ПВКФ и простым периодом p = dR+1 для й = 4,6,8, рассчитать параметры ДП с квазиодноуровневой ПВКФ.

Задачей подраздела 3.4 является корреляционный анализ синтезированных ДП.

Пусть гИшб- наибольшее значение Б Л ПВКФ ДП, сформированных по ПК (1) на основе одного класса степенных вычетов. Справедлива следующая

Теорема 11. Для ДП, сформированных на основе одного класса биквадратичных вычетов, с квазиодноуровневой ПАКФ и периодом

, = 4(2^1)4(1+4^ значение ,иаиб = + + \ а Ит =

В частности, теорема 11 определяет наибольшее значение ПВКФ пар известных ДП с одноуровневой ПАКФ (# = 0).

В диссертационной работе для всех синтезированных ДП с квазиодноуровневой ПАКФ определены рельефы ПВКФ, гнаиб и отношение

гнаиб.

Для каждой из синтезированных ДП с квазиодноуровневой ПВКФ

рассчитаны рельефы ПАКФ ДП. Имеет место следующая

Теорема 12. Если пара ДП X, У, удовлетворяющих условиям теорем 9 или 10, имеет одноуровневую ПВКФ, то каждая из этих ДП имеет ПАКФ:

1. Л(г) = {(р-17)/16,(р-1)/16,(р-1±16и)/16}; х = 1, р-\АЛ = 2\и[у = щ, если £/=4.

2. Л.(г) = {(р -1)/36 ± и, (р - 37)/36, (р -1) / 36, (р -1) / 36 ± Зм}; т = 1,р-1 , ДЯ = б|м|,

Таким образом, в третьей главе разработаны методы синтеза двоичных последовательностей с заданными ограничениями на характеристики, такие как: период, период, рельефы корреляционных функций, пик-фактор. Определены новые правила кодирования семейств двоичных последовательностей с периодом р и квазиодноуровневыми периодическими автокорреляционными или взаимно корреляционными функциями. Синтезированы новые семейства ДП, обладающие определенным набором свойств и характеристик. Результаты синтеза позволяют сделать вывод об универсальности, продуктивности и обобщенности разработанных методов синтеза ДП с заданной совокупностью свойств или ограничений на их характеристики.

Четвертая глава посвящена разработке методов синтеза ТП и БП с заданной совокупностью свойств или ограничений на их характеристики. Для достижения поставленной цели решаются следующие задачи:

— разработка методов синтеза ТП и ДП с ограничениями на период, рельефы ПАКФ, пик-фактор, степень уравновешенности ТП;

— разработка методов синтеза ТП с ограничениями на период, рельеф ПВКФ, пик-фактор;

— разработка методов синтеза БП с заданными ограничениями на: рельеф ПАКФ, период, степень уравновешенности, позволяющих формировать новые семейства БП, обладающих квазиидеальной ПАКФ и большей плотностью сетки периодов, чем известные последовательности.

Также в главе выполнен анализ взаимно корреляционных функций синтезированных ТП и БП.

Цель подраздела 4.2 - разработка методов синтеза ТП со следующими ограничениями: уравновешенность, квазиидеальная ПАКФ, р/ к 2,3, ДП, соответствующая нулевым символам ТП имеет квазиодноуровневую ПАКФ. Последовательности, удовлетворяющие заданным ограничениям, можно использовать в качестве модулирующих для радиотехнических систем связи и передачи информации, радиолокации и радионавигации с шумоподобными сигналами, фазовой или амплитудно-фазовой манипуляцией и корреляционной обработкой сигналов, то есть для радиолокационных станций, работающих в квазинепрерывном режиме.

Расчет и анализ рельефов ПАКФ ТП и соответствующих ДП приводит к

следующим утверждениям для ТП, сформированных по ПК (1) при / = {*>,/ = {/}.

Теорема 13. ТП с периодом р = (1+4и)2+4(2Л + 1)2, сформированная по ПК (1)при с! = 4,\к-1\ = \, имеет двухуровневую ПАКФ Лх(г) = {Л,-(А +1)}, г --=1,р-\ и пик-фактор р/ и 2.

ДП, соответствующая нулевым символам ТП, имеет двухуровневую ПАКФ: = + т = \,р-Л. Здесь и,Х- целые числа.

Теорема 14. ТП с периодом р = (1+2А)2 + 4у2, сформированная по ПК (1) при с1 = 4,|*-/| = 2, имеет двухуровневую ПАКФ ЯЛ-(г) = {Я,-(Я + 1)}, т = \,р-\ и пик-фактор р/ « 2.

ПАКФ ДП: Л(г)={л,Д + 1}([2]).

В подразделе 4.2 получены три ПК уравновешенных ТП с квазиидеальной ПАКФ и пик-фактором р/ ~ 2,3.

Для синтезированных ТП рассчитаны рельефы ПВКФ и их характеристики. Следующие две теоремы определяют наибольшее значение ПВКФ ТП, удовлетворяющих условиям теорем 13 и 14.

Теорема 15. Если ТП Х0,Х1,Х2, Х3, сформированные по ПК (1) при

¿ = 4,|£-/| = 1 спериодом р = (1+4м)2 + 4(2Л+1)2, обладают квазиидеальной ПАКФ, то гнайб. =|1+Зи|.

Теорема 16. Если ТП Х0, ХЬХ2, Х3, сформированные по ПК (1) при <1 = 4, \к - /| = 2 с периодом р = (1+21)2 +4у2, обладают квазиидеальной ПАКФ, то 'наиб. = М-

Следовательно, при синтезе ТП, с заданными в подразделе свойствами, можно ввести ограничение и на рельеф ПВКФ.

Комплексная методика определила методы синтеза ТП с определенными ограничениями на их характеристики. Результаты синтеза ТП с четырьмя заданными ограничениями, позволяют сделать вывод об универсальности методов, а новые регулярные ПК семейств ТП с квазиидеальной ПАКФ свидетельствуют об их продуктивности.

В подразделе 4.3 диссертации разработаны методы синтеза пар уравновешенных ТП с ограничениями на ПВКФ, пик-фактор. Как и в подразделе 4.2, но только для ПВКФ, на основе комплексного использования СРКВ и циклотомических чисел, рассчитаны наибольшие абсолютные значения БЛ ПВКФ пар ТП; определены достаточные условия синтеза уравновешенных ТП с квазиидеальной ПВКФ и пик-фактором р/ я 2,3,4. Полученные результаты позволяют решать задачу синтеза ТП с квазиидеальной ПВКФ при заданном значении Гтах.

Найдено одиннадцать новых регулярных ПК ТП с квазиидеальной ПВКФ и определены параметры семейств пар ТП с гнаиб = 1. Результаты расчетов показывают, что синтезированные ТП обладают достаточно плотной сеткой периодов.

Подраздел 4.4 посвящен разработке метода синтеза почти уравновешенных БП с ограничениями на ПАКФ. Справедливы следующие утверждения.

Теорема 17. Если БП X сформирована по ПК (1) при с/= 4 и / = {0,1}, / = {2,3}, то

|2Ы + 1,если Л-нечетное, (ЧЫ, если К - нечетное,

тахЦд-(г) =•! , ДАд-Н . , ,

г*0 [2|у| + 3, если К - четное. [4р>| + 4, если К - четное.

Следствие 17.1. Если у-фиксировано, то в условиях теоремы 17 с ростом

р параметр у убывает пропорционально —. С увеличением р ПАКФ БП

Р

стремится к идеальной.

Следствие 17.2. БП X с периодом р = х2+4 для </ = 4, / = {0,1} имеет двухуровневую ПАКФ Лх (г) = {- 3;1}, г = 1, р -1. Это известный результат [4]. Пусть (1 = 6.

Теорема 18. Для нечетного Я БП имеет трехуровневую ПАКФ с

тах^г) | =

1 + -^, если (В)3 =0,

4\А±В\ / . 1+ 2—если

относительно ПК (1) для ¿ = 6,1 = {0,1,2}, J = {3,4,5}. Теорема 19. Для четного К БП имеет ПАКФ с

тах|Ях(г)| =

г#0

щв\

3+-^, если <5>3 = 0,

3+4И±д1)если ^ ^о^

3

относительно ПК (1) для с! = 6,1 = {0,1,2}, 3 = {3,4,5}.

Теоремы 17-19 определяют достаточные условия БП с квазиидеальной ПАКФ. Для синтезированных БП рассчитаны рельефы ПВКФ и их характеристики.

В подразделе 4.4 найдено шесть новых регулярных ПК почти уравновешенных БП с квазиидеальной ПАКФ. Сформированы новые семейства БП, которые обладают, за счет отказа от оптимальности ПАКФ, большей плотностью сетки периодов, чем у известных последовательностей. Известные БП [4], обладающие такими же свойствами, являются частными случаями синтезированных (следствие 17.2). Рассчитаны параметры БП с

квазиидеальной ПАКФ при ¿1 = 4,6,8.

Таким образом, в четвертой главе на многочисленных примерах показана результативность методики, заключающейся в комплексном использовании теории СРКВ и циклотомических чисел, для синтеза ТП и БП. На её основе разработаны методы синтеза троичных и бинарных последовательностей с заданными ограничениями на период, рельефы БЛ ПАКФ (ПВКФ), пик-

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

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

- разработать унифицированный метод расчёта эквивалентной линейной сложности двоичных (бинарных) последовательностей, сформированных по обобщенному ПК;

- проиллюстрировать метод посредством расчета линейная сложность двоичных последовательностей, синтезированных в третьей главе;

- обобщить метод для расчета линейной сложности троичных последовательностей;

- продемонстрировать возможности метода расчетом линейной сложности троичных последовательностей, синтезированных в четвертой главе.

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

Линейная сложность Lx ДП X с периодом р над полем GF(2) определяется известным соотношением:

Lx (ДП) = р-|{л |s(a") = 0,n = 0,p-1}|, (3)

где S(i) = х0 + xj/ +... + хр_,(- многочлен последовательности, а а -примитивный корень степени р из единицы в поле разложения многочлена ip -1 над GF(2) [5,6]. Если Sd(t) = ]>V - многочлен последовательности,

п еЯ0

сформированной по ПК (1) для класса степенных вычетов с нулевым номером, то S(a")= ^Sd(a"),n = 0,p-l, следовательно, для вычисления линейной

kel

сложности любой ДП, сформированной на основе классов степенных вычетов, достаточно найти Sd(ae'), / = O.rf-l, то есть Sd(a) = (a),Sd(a°).....Sjia0"

Теорема 20. Если к = 0, d -1, то

с / / <?\ {ЖМ)' Sd О/, если R 3 0(mod 2), Sd{a)Sd{a )= (4)

[S(d /2, k,d)-Sd(af+ S, если R = l(mod 2),

где г- операция транспонирования матрицы Sd(a), а

_ Jl. если Я =l(mod2)H k = dl2, [О, в ост. случаях.

Теорема 20 формирует систему уравнений для неизвестных 5<Да6|/), / = 0,</-1 с использованием таблицы СРКВ, в частности, при известных циклотомических числах порядка с!. Её решение позволяет определить значения многочлена ДП и рассчитать линейную сложность Ьх ДП по формуле (3).

Таким образом, доказанные в подразделе 5.2 теоремы определяют метод расчета линейной сложности ДП (БП), сформированных на основе классов степенных вычетов, с использованием СРКВ.

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

Решение системы (4) позволило найти 8ы(а) = ^5а(а),5а(а°),...,5а(ав'")^ для

¿ = 4,6,8 и вычислить линейную сложность ДП по формуле (3). Результаты расчетов представлены ниже.

Лемма 1. Если ДП X с периодом р = (1+4н)2 +4(2^+1)2, где - целые числа, сформирована по ПК (1) при Л = 4, то её линейная сложность

{р, если |/| = 1, р—1, если|/| = 2.

Лемма 2. Если ДП X с периодом р = (\+4и)2 +\6g2, где - целые числа сформирована по ПК (1) при й = 4, то для I - {0} её линейная сложность

— 1

-—, если и = 0(то<12), £ = 0(тск12), 4

если " = 1(т°<12),£з1(т<х12),

_I

3——, если и = 1(тос12), ? = 0(тос12), 4

р-1, если иг0(тос!2),££1(тос12), а для / = {0,1} линейная сложность последовательности

I , если £ = 0(тос12),

ьх -< 2

[р-1, если # = 1(то<12).

Найденные при вычислении линейной сложности корни многочлена последовательности позволяют также определять минимальный многочлен ДП ДО = (1Р-1)/НОД(гр -1,5(0) • Так как

„«/+4\ „„„ ¡Г?

нот" -1,5(0)=

ПЕК'-«' ), если/ = 0,3,5(ай ) = 0,5(1)#0,

/ 5 = 0

С-ОПШ'-« ), если/ = 0,3,5(а" ) = 0,5(1) = 0.

/ 5 = 0

Результаты расчетов линейной сложности для ряда других синтезированных последовательностей приведены в табл. 1-3 и лемме 3.

Таблица 1

Линейная сложность ДП па основе одного класса шестеричных вычетов

¡-X р = А2+ЪВг

р-1 6 А з 1(тосП2), В з 0(тосП2)

р-1 3 Л з 7(таН2), В з б(тос112)

р-1 2 Л = 1(1110(112), Дэ±4(тосП2)

2 ЛнЮ(то<И2),ЯвЗ(тос16)

2^1 + 1 3 Л з 4(то(112), В з 3(то(16)

6 Лн 7(тоа12), 5 з 0(то(112)

р-1 Лз1(тос112),.Взб(то<112); А = 1(то<16), В з ±2(то<112); Л = 7(тос112), В = +4(тоаб)

Р А и 4(то<16), В = ±1(тос1б)

Таблица 2

Линейная сложность ДП при с! = 6, I = {0,1,2}.

1-Х р = Л2+ЗВ2

Р-1 2 з 1(то<16), В я 0(то(112)

2 Лз10(то<Ш), 3(то(16)

Р-1 Л з 1(тос16), В э 6(тос112); Л з 1(тоа 6), В = ±2(тос16)

Р Л 3 4(то<112), В 3 3(то<16), Л в 4(то(16), В = + 1(тос16)

Таблица 3

Линейная сложность ДП на основе одного класса восьмеричных вычетов

1-Х р = хг+^г = а2 + 2Ь2

3(Р-1) + ] 4 I з 5(то<116), ^ з 0(тос12)

3(р-1) + 1 8 хв13(тоа16),гз1(то(12)

5(р-.) + 1 8 *з5(тоа16),гз1(тоа2)

Р хэ!3(тоа16),г = 0(тоа2)

Лемма 3. Если ДП сформирована по ПК (1) при ¿/ = 8, / = {0,1,2,5} с периодом р = х2+ 64$2 =а2+2Ь2 и нечетном значении Я, то её линейная сложность

-, если g s l(mod2),

4

если g = 0(mod2).

Как и при </ = 4 элементы матриц S6(a),Ss(a) позволяют рассчитать минимальный многочлен ДП.

Таким образом, вычислена линейная сложность ДП, сформированных по обобщенному ПК (1) при 3,4,6,8 с квазиодноуровневой ПАКФ и одноуровневой ПВКФ. Найденные при этом значения многочлена последовательности позволяют найти линейную сложность ДП, сформированных при любом числе классов степенных вычетов, а также её минимальный многочлен, в том числе и тех последовательностей, например Лежандра или Холла, линейная сложность и минимальный многочлен которых были рассчитаны другими способами. Все перечисленное позволяет сделать вывод о продуктивности и обобщенности разработанного в подразделе 5.2 метода. Полученные результаты позволяют формировать по обобщенному ПК новые семейства ДП с большой линейной сложностью (Lx >р/2).

Задача подраздела 5.4 - метод расчета линейной сложности ТП над полем

GF{3). Пусть 1d(P) = (та(P),Td{p°),...,Td(ped~l)], где Td{t) - многочлен >

4 J пвН0

принадлежащий GF(3)[i], а р - примитивный корень степени р из единицы в поле разложения многочлена tp -1 над GF{3).

Теорема 21. Если к = 0,</-1, то

ÎS(0,к,d)-Td(P)r +Ô, еслиR = 0(mod2), / 2, к, d) • Td (Р)т + S, если R s l(mod2), где

[Л, если R s 0(mod2) и k = 0 или R = l(mod2) и k-d!2,

TdWW У- ,___________r

[О, в ост. случаях.

Теорема 21 определяет систему уравнений для Тл{рв'\ / = Её

решение позволяет найти значения многочлена ТП т(Рв/)=^Т,1(Рв1*/)-'£т11(рв'*/), что, делает возможным расчет линейной

*е/ ;е./

сложности ТП.

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

Лемма 4. Если ТП сформирована по (1) при |А:-/| =1,2; ^ = 4 и р?П(тс^З), то её линейная сложность Ьх=р-\.

Лемма 5. Если ТП сформирована по (1) при \к-1\ = 2, ¿ = 4 и р = 1(тсх13), то справедлива формула:

_I

——-, если у = О(шоёЗ),

[/? -1, если у Ф О(тоёЗ). Лемма 6. Если ТП сформирована по (1) при |£-/| = 1, с/ = 4 и /)5 1(тос13), то её линейная сложность

Леммы 4—6 определяют линейную сложность ТП сформированных на основе двух классов биквадратичных вычетов, в том числе и с квазиидеальной

Лемма 7. Если ТП сформирована по (1) при \к-1\ = 2, с! = 6 с периодом р = (4+бы)2 +352,то её линейная сложность

Леммы 4-7 определяют линейную сложность ТП с квазиидеальной ПАКФ, синтезированных в четвертой главе. Найденные значения многочленов троичных последовательностей позволяют найти линейную сложность и минимальный многочлен любой другой ТП, сформированной на основе классов биквадратичных или шестеричных вычетов, что свидетельствует о продуктивности разработанного метода расчета линейной сложности ТП.

Таким образом, в пятой главе на основе теорем 20 и 21 получен метод расчета линейной сложности ДКП, сформированных по обобщенному ПК, с применением СРКВ и циклотомических чисел, что позволяет добавить в меню комплексной методики синтеза ДКП ещё одно свойство. Вычислена линейная сложность ДП и ТП. Результаты расчетов подтверждают обобщенность метода. В то же время известные методы расчета линейной сложности ДКП, сформированных по ПК (1), пригодны лишь для последовательностей на основе разностных или почти разностных множеств [5,6]. Найдены новые правила кодирование семейств ДП (БП) и ТП с большой линейной сложностью.

Шестая глава диссертации посвящена распространению методики синтеза ДКП с простым периодом р на последовательности с периодом тр, где т — натуральное число, взаимно простое с р. В настоящий момент известны [2,3,7,8] правила кодирования некоторых последовательностей с периодом тр, но отсутствует методика конструирования последовательностей с заданной совокупностью свойств или ограничений на их характеристики.

Для решения поставленной задачи целесообразно:

- расширить область использования теории СРКВ и модернизировать методику синтеза ДКП с простым периодом р;

если у = 0(тси16), Ьх = ■ если х = 0(тос13),_у г 1(тос12),

р -1, в ост. случаях.

ПАКФ.

- проиллюстрировать применение модернизированной методики на примерах синтеза ДП, ТП с периодом тр\

- найти новые ПК ДП с ограничениями на рельеф ПАКФ, период, пик-фактор;

- найти новые ПК ТП с ограничениями на рельеф ПАКФ, степень уравновешенности, период, пик фактор.

В подразделе 6.2 для модернизации комплексной методики предложены два ПК последовательностей с периодом тр, позволяющие расширить область применения теории СРКВ.

Пусть ДКП 2 и У составного периода тр формируются из т ДКП

Х0,...,периода^?: Xj={Xj¡„},j = Q,m-\,n = 0,p-\ на основе двух ПК:

*'= *('>»'<')„' (5)

Л=х</)т,[;/т] > (6)

где (/) — наименьший положительный вычет / по модулю р, а [а] - целая часть числа а.

Если ДКП г сформирована по ПК (5), то ее ПАКФ ((Г) )> если гз0(то(1т)>

' ' (7)

т-1 ' ^ 7

Лг( г) =

(<Т>„). если г*0(т<и1м),

]=0

где Лх.{х),Х2{г), соответственно, ПАКФ ДКП Х;- и 2, а гх Хн(т) -ПВКФ пары последовательностей , у,й = о,»»-1.

Если же ДКП У сформирована по ПК (6), то ее ПАКФ

ш-1

([т/т]), если гзО(тос!т), "' (8)

т—I

Т.гх,,хи„) если т?0(то<1т),

}=о "

Лу(т) =

{О, если / + (г) <т, 1, если / + (г)и >т

Формулы (7) и (8) обобщаются на ПВКФ пар ДКП, сформированных по ПК (5) и (6).

Таким образом, предложенные ПК формируют ДКП периода тр, ПАКФ и ПВКФ которых, определяются ПАКФ и ПВКФ ДКП периода р. Если ДКП XJ■,j = 0,m-l простого периода конструируются по обобщенному ПК (1) при подмножествах индексов = 0,т-1, то (7) и (8) позволяют использовать

для анализа и синтеза ДКП с периодом тр теорию СРКВ, результаты третьей и четвертой глав. В частности, согласно (7), для ПАКФ ДП 1, сформированной по ПК (5), справедливо взаимно - однозначное соответствие:

Л2 (г) о

}=о

т-1,

1

если (г) * О,

(9)

если (г)р=о-

которое показывает, что ПАКФ ДП полностью определяется таблицей СРКВ для простого поля Галуа, за исключением значений аргумента кратного р. Аналогичные утверждения имеют место и для ПАКФ, ПВКФ ТП, БП.

При машинном синтезе ДКП применение (9) предпочтительнее по сравнению с формулами (7), (8), так как вычисление таблиц СРКВ не вызывает затруднений.

Соотношения (7) и (8) позволяют предложить следующую модификацию рассмотренной ранее методики синтеза ДКП:

A) Выбор одной из стратегий синтеза на основе анализа исходных данных и требований к ДКП:

Стратегия 1 - синтез осуществляется на основе известных или полученных в третьей и четвертой главах ДКП с простым периодом и заданным рельефом ПАКФ или ПВКФ;

Стратегия 2 - синтез осуществляется аналитическим расчётом или направленным перебором на вычислительной машине последовательностей, сформированных по ПК (1);

B) Определение допустимых параметров ДКП простого периода

C) Расчет характеристик последовательностей простого периода с использованием СРКВ и циклотомических чисел (глава 2).

Б) Расчет по формулам (5-8) параметров ДКП составного периода, сопоставление с заданными требованиями.

С целью иллюстрации первой стратегии модифицированной методики синтеза ДКП в подразделе 6.3 рассмотрены: задача синтеза двоичных последовательностей с характеристиками: период 2р, р/ ~2, квазиодноуровневая ПАКФ; задача синтеза уравновешенных троичных последовательностей с характеристиками: период 3р, />/«3, квазиидеальная ПАКФ. На примерах показана возможность использования полученных ранее результатов синтеза ДКП с простым периодом для конструирования последовательностей с составным периодом и заданными характеристиками. Справедливы следующие утверждения.

Теорема 22. Если ДП У сформирована по ПК (6) при <1 = 4, р = х2 +4у2 и /0 = {0,1},/[ = {0,3}, то АЛУ =[х{+1 и пик-фактор р/~2.

Теорема 23. Если ТП 2 с периодом 3р сформирована по ПК (5) при <1 = 6, Р = А2 + ЗВ2 и /0 = {0},У0 = {3}, /, = {1}, = {4}, 1г = {2}, Зг = {5} , то

тах]Яг(т)| =

г*0

А±В 3

В

, если (В)г * О,

если (В) 3 = 0

и пик-фактор р/ ~ 3.

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

Задача подраздела 6.4 - иллюстрация применения модифицированной методики при второй стратегии. Так как возможное число вариантов для ДП с простым периодом в ПК (5) и (6), равно 2тЛ, то, предварительно, в подразделе 6.4 найдены необходимые условия существования ДП, пар ДП с периодом тр и квазиодноуровневой ПАКФ (ПВКФ), а также ТП с ПАКФ близкой к идеальной для уменьшения числа рассматриваемых вариантов. Возможности модернизированной методики проиллюстрированы на примерах синтеза ДП, ТП с ограничениями на рельеф ПАКФ (ПВКФ), пик-фактор, период и степень уравновешенности для ТП. Имеют место следующие утверждения.

Теорема 24. ДП 2, сформированная по ПК (5) при {/о,...,/8} = {{0},{0},{3},{0},{2},{2},{3},{2}}, «/ = 4, р = 1 + 4(2м +1)2, где «-натуральное число, или {/0,...,78} = {{0},{0},{2},{1},{2},{2},{0},{1}}, имеет четырехуровневую

ПАКФ Ях{т) = {Я0,Х0 + 1,Я0+2,Я0+з},т = 1,^р-1, ДЛ2=Зс Лд = и пик-фактор

дГ«4.

Теорема 25. Если пара ДП 1ь2г сформирована по ПК (5) при <1 = 4, р = х2+4у2 и /((11)={0,1},/1(1)={2,3},41)-{2,3}, 42>={1,2}, /1(2) = {0,3>, 1(22)={0,3], то для ПВКФ г2 г2(г) величина Дг = (3|х|+1)/2, г = 1,Зр-1 и пик-фактор р/~2.

Теорема 26. Если ТП У сформирована по ПК (6) при с1 = 4, р = х2+Лу2 и /о={0},^о={2}, А={1},/!= {3}, то она обладает ПАКФ: Ху(г)е{-\,0,±у,±2у},

г = 1,2р-1.

В результате найдены новые регулярные ПК: ДП с периодом 8р и квазиодноуровневой ПАКФ (два ПК); ДП с периодом 3р и квазиодноуровневой ПВКФ; уравновешенных ТП с квазиидеальной ПАКФ и периодом 2р. Результаты синтеза показывают, что модифицированная методика продуктивна и универсальна.

Задача подраздела 6.5 заключается в поиске на основе вышеизложенной методики регулярных ПК ДП с ограничениями: период тр, квазиодноуровневая ПАКФ, пик-фактор. Сравнительный анализ результатов синтеза показал, что наиболее плотная сетка периодов ДП с квазиодноуровневой ПАКФ получается при с! = 4. В частности, справедливы следующие теоремы.

Теорема 27. ДП 2, сформированная по ПК (5), с периодом 2р при <1 = А, р = хг+\6и1 и /0= {0,1}, 7, ={0,3} имеет ПАКФ

Л2(г) = {2Д-2,2Д-1,2Д,2Д-(х + 3)/2,2Я±(х-1)/2}, ДЛ2=|х| + 1 и пик-фактор р/«2.

Теорема 27 определяет новое регулярное ПК ДП с периодом 2р и квазиодноуровневой ПАКФ.

Следующие теоремы определяют рельеф ПАКФ для ДП с периодами 4р и

8р.

Теорема 28. ДП 2, сформированная по ПК (5) при /0=/1={0,1}, /2 = {0,3}, 1Ъ = {1,2} или /<, = /,= {0,1}, /2 = {1,2}, /3 = {0,3}, т = 4, а = 4, обладает ПАКФ с

Ш, если 7 - нечетное,

ДЛ7 =Н

'| + 2, если - четное и пик-фактором р/ ~2.

Теорема 29. ДП формируемая по ПК (5) при р = х2 +4{2и + \)2, /0 = 7, = /5 = {0,1}, /2 = {1,2}, /3 = /6 = /7 = {0,3}, /4 = {2,3}, имеет ПАКФ

Дг(г) = {2р-6,2/>-4,2/?-2,2/>-4±*}, г = 1,8р-1,

[3, если х = 1, )2]ж|,если и пик-фактор р/~2.

Теоремы, доказанные в подразделе 6.5, задают необходимые и достаточные условия существования двоичных последовательностей с квазиодноуровневой ПАКФ и составным периодом, определяют способы формирования ДП с заданными свойствами.

В подразделе получено девять новых регулярных ПК ДП с квазиодноуровневой ПАКФ при т = 4 и два, для примера, при т = 8. Определены параметры семейств синтезированных ДП. Расчеты показывают, что они имеют достаточно плотную сетку периодов.

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

В подразделе 6.6 методика проиллюстрирована на примере синтеза ТП с ограничениями: уравновешенные, квазиидеальная ПАКФ, период 2р.

В частности, справедливы следующие теоремы.

Теорема 30. Если ТП 2 сформирована по ПК (5) при с1 = 4, то:

1) Л2(т) = {-1,0+2у},т = 12р-1 для /0={0},./0={2}, р/*2;

2) Хг(г) = {0,±у,-1 ±у}, х -\,2р-1 для /0={0},У0 = {1},/,={2},/,={3} или 'о = {0}. Л = {3}, А = {1}, А = {2}, р/ « 2.

Теорема 31. Если ТП У сформирована по ПК (6) при <1 = 4, р = х2+4у2 и /0 = {0}, ,/0 = {2}, /,={)}, У, = {3}, то она обладает ПАКФ: Лу(т)е{-1,0,±у,±2у}, т = 1,2р-1 и пик-фактором р/ ~2.

Теоремы 30 и 31 определяют рельефы ТП и достаточные условия существования ТП с квазиидеальной ПАКФ. Если 2|_у| < Лп,^, где Л1ПЗХ -заданное пороговое значение для ПАКФ ТП, то в условиях теорем 30,31 ТП обладают квазиидеальной ПАКФ. Результаты расчетов показывают, что синтезированные ТП имеют достаточно плотную сетку периодов.

В подразделе 6.6 найдено шесть новых регулярных ПК ТП с заданными характеристиками. Определены параметры семейств синтезированных ТП.

Таким образом, в шестой главе расширена область применения теории СРКВ, методика синтеза ДКП с простым периодом и заданной совокупностью свойств или ограничений на их характеристики распространена на последовательности с периодом тр. Найдены новые регулярные ПК ДП, ТП с периодом тр для т = 2,3,4,8, отличающиеся корреляционными функциями, пик-фактором и рядом других параметров от известных ДКП. Синтезированы ДП с квазиодноуровневой ПАКФ и уравновешенные ТП с квазиидеальной ПАКФ.

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

Для достижения поставленной цели необходимо разработать:

-обобщенный алгоритм синтеза ДКП с заданной совокупностью свойств или ограничений на их характеристики на основе комплексной методики, изложенной во второй главе;

-алгоритмы синтеза ДП, ТП и БП с простым периодом и заданными требованиями;

-алгоритм расчета линейной сложности последовательностей, сформированных на основе классов степенных вычетов;

— алгоритмы синтеза ДП, ТП с периодом тр и программы по предложенным алгоритмам.

Подраздел 7.2 посвящен разработке обобщённого алгоритма синтеза ДКП, исходными данными для которого являются:

1. Тип синтезируемой последовательности: ДП, ТП, БП.

2. Совокупность задаваемых свойств последовательностей или ограничений на их характеристики из следующего перечня: период, вес, пик-фактор, рельеф ПАКФ, рельеф ПВКФ, степень уравновешенности для ТП и БП, рельеф ДП, соответствующей нулевым символам ТП, эквивалентная линейная сложность.

3. Результаты синтеза определяется следующим меню: параметры ПК -рЛи; числовые значения характеристик, перечисленных выше; число последовательностей, удовлетворяющих заданным требованиям; сформированные последовательности.

Обобщенный алгоритм методики синтеза последовательностей, состоит из следующих этапов:

1. Анализ исходных данных.

2. Выбор метода или методов синтеза из числа разработанных в третьей-шестой главах в зависимости от результатов предварительного анализа:

- метод синтеза ДП с простым периодом и ограничениями на период, вес, пик-фактор, рельефы ПАКФ или (и) ПВКФ;

- метод синтеза ТП с простым периодом и ограничениями на период, вес, рельефы ПАКФ или (и) ПВКФ, рельеф ПАКФ ДП, соответствующей нулевым символам троичной последовательности, пик-фактор, степень уравновешенности;

- метод синтеза БП с простым периодом и ограничениями на период, рельефы ПАКФ или (и) ПВКФ, степень уравновешенности;

- метод расчета линейной сложности дискретно-кодированных последовательностей, сформированных на основе классов степенных вычетов;

- метод синтеза ДП с периодом тр и ограничениями на период, вес, пик-фактор, рельеф ПАКФ;

- метод синтеза уравновешенных ТП с периодом тр и ограничениями на: период, вес, рельеф ПАКФ, пик-фактор.

3. Расчет, в соответствии с выбранным методом синтеза, допустимых параметров обобщенного ПК- р,с1,1исходя из ограничений на период, вес, пик-фактор, степень уравновешенности,

4. Расчет свойств и характеристик последовательностей в соответствии с выбранными методами. При необходимости формирование последовательностей.

5. Вывод результатов синтеза в требуемой форме, согласно требованиям, заданным в меню «результаты».

Алгоритмы вышеупомянутых методов синтеза разработаны в подразделах седьмой главы.

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

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

В подразделе 7.4 предложен алгоритм синтеза последовательностей с ограничениями на период и линейную сложность на основе материалов пятой главы. В отличие от известного алгоритма Берлекэмпа-Месси он применим лишь для ДКП, сформированных на основе классов степенных вычетов, но при этом обладает целым рядом несомненных достоинств:

- линейная сложность ДКП, сформированных по обобщенному ПК при <1 = 3,4,6,8, определяется посредством разложения периода последовательности на сумму квадратов целых чисел;

- при его применении рассчитывается линейная сложность не одной последовательности, а семейства ДКП;

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

В подразделе 7.5 на основе модернизированной методики, предложенной в шестой главе, разработаны алгоритмы синтеза ДП с ограничениями на период тр, вес, пик-фактор, ПАКФ (ПВКФ) и ТП с ограничениями на период тр, вес, пик-фактор, ПАКФ (ПВКФ), степень уравновешенности.

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

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

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

Заключение

1. Применение циклотомических чисел позволило:

- упростить анализ таблиц СРКВ, а также расчет и анализ СРКВ, соответствующих корреляционным функциям ДКП, формируемых на основе нескольких классов степенных вычетов;

- обобщать полученные частные решения синтеза ДКП в правила кодирования и находить обобщенные формулы для характеристик синтезированных ДКП.

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

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

методы синтеза двоичных, троичных и бинарных последовательностей с простым периодом, в том числе и псевдослучайных:

- методы синтеза двоичных последовательностей с ограничениями на период, вес, пик-фактор, рельефы ПАКФ или (и) ПВКФ;

- методы синтеза троичных последовательностей с ограничениями на период, вес, рельефы ПАКФ или (н) ПВКФ, рельеф ПАКФ двоичной последовательности, соответствующей нулевым символам троичной последовательности, пик-фактор, степень уравновешенности;

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

Методы проиллюстрированы многочисленными примерами синтеза последовательностей с заданной совокупностью свойств или ограничений на их характеристики. Определены новые правила кодирования семейств двоичных последовательностей с периодом р и квазиодноуровневыми периодическими автокорреляционными или взаимно корреляционными функциями и троичных последовательностей с квазиидеальными периодическими

автокорреляционными или взаимно корреляционными функциями.

3. Разработан унифицированный метод расчета эквивалентной линейной сложности последовательностей, сформированных на основе классов степенных вычетов. Определена линейная сложность двоичных и троичных последовательностей. Показано, что подавляющее число вновь синтезированных последовательностей обладают высокой криптостойкостью. Получены новые правила кодирование семейств ДКП с большой линейной сложностью.

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

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

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

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

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

Список основных публикаций по теме диссертации Монографии

1. Едемский, В.А. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики / В.А. Едемский, В. Е. Гантмахер- Великий Новгород.: НовГУ, 2009.- 189 с.

Статьи в рецензируемых научных журналах, включенных в реестр ВАК МОиНРФ

2. Едемский, В. А. О линейной сложности троичных последовательностей на основе классов степенных вычетов / В. А. Едемский // Проблемы передачи информации. - 2008. - Т. 44. - Вып. 4. -С. 3-11.

3. Едемский, В. А. Результаты синтеза пар двоичных последовательностей простого периода с одноуровневой и двухуровневой взаимной корреляцией / В. Е. Гантмахер, В.А. Едемский // Известия вузов. Радиоэлектроника. - 2006. - Вып. 4. - С. 26-33.

4. Едемский, В.А. Результаты синтеза двоичных последовательностей с квазиодноуровневой автокорреляционной функцией, формируемых на основе классов вычетов по простому модулю / В. Е. Гантмахер, В.А. Едемский // Известия вузов. Радиоэлектроника. - 2007. - Вып. 4. - С.14—23.

5. Едемский, В.А. Квазиодноуровневые разностные множества / В. Е. Гантмахер, В.А. Едемский // Вестник МГТУ им. Н.Э. Баумана. Сер. "Естественные науки". - 2007. - №4. - С. 8-19 .

6. Едемский, В.А. Корреляционные функции троичных последовательностей с простым периодом / В. Е. Гантмахер, В.А. Едемский // Вестник КАИ им. А.Н. Туполева. - 2007. - № 2. - С.41-44.

7. Едемский, В.А. О бинарных последовательностях простого периода с квазиидеальной автокорреляцией / В. Е. Гантмахер, В.А. Едемский // Вестник Саратовского государственного технического университета. - 2007. — № 1(21). -Вып. 1.-С. 7-12.

8. Едемский, В. А. К вопросу синтеза троичных квазиортогональных последовательностей с одним нулевым символом на периоде / В. Е. Гантмахер, А. С. Евдаков, В.А. Едемский // Вестник НовГУ. Серия «Техн. науки». - 2004. - №26.-С. 101-103.

9. Едемский, В. А. О двоичных и троичных последовательностях с квазиодноуровневой периодической автокорреляционной функцией для р si mod4 / В. Е. Гантмахер, В.А. Едемский // Вестник НовГУ. Серия «Техн. науки». - 2004. - № 28. - С. 73-76.

10. Едемский, В. А. О ПАКФ двоичных и троичных последовательностей для р = 1 mod6 / В. Е. Гантмахер, В.А. Едемский // Вестник НовГУ. Серия «Техн. науки». - 2005. - № 30. - С. 52-57.

11. Едемский, В.А. О ПАКФ и ПВКФ двоичных и троичных последовательностей с периодом р э 1 mod6/ В. Е. Гантмахер, В.А. Едемский // Вестник НовГУ. Серия «Техн. науки». - 2005. - № 34. - С. 47-52.

Публикации в других изданиях

12. Gantmakher, V.E. The Synthesis Methodology of Periodic Discretely Coded Sequences Formed Basing on Cyclotomic Classes with Basic Parameters Constraints / V.E. Gantmakher, V.A. Edemskiy // Proc. 2007 International Workshop on Signal Design and Its Applications in Communications (IWSDA'07). - China, 2007 - PP. 4-8.

13. Gantmakher, V.E. Synthesis Results of the Periodic Discretely Coded Sequences with the Parameters Constraints Defined on the Basis of the Cyclotomic Classes / V.E. Gantmakher, V.A. Edemskiy // Proc. 2007 International Workshop on Signal Design and Its Applications in Communications (IWSDA'07). - China, 2007. - PP. 9-12.

14. Едемский В.А. Анализ и синтез троичных и бинарных последовательностей простого периода с квазиидеальной автокорреляцией / В. Е. Гантмахер, В.А. Едемский // Сборник докладов 9-ой международной конференции "Цифровая обработка сигналов и её применения". — М., 2007. — Т. 1. — С.14—17.

15. Едемский, В.А. О синтезе дискретно-кодированных последовательностей периода 2р! В. Е. Гантмахер, В.А. Едемский, С. М. Платонов // Сборник докладов 10-ой международной конференции "Цифровая обработка сигналов и её применения". - М., 2008. — Т. 1. — С.16-19.

16. Едемский, В. А. Методика построения разностных множеств, сбалансированных на несколько близких уровней / В. А. Едемский // Обозрение прикладной и промышленной математики. - 2007. - Т. 14. -Вып. 2. -С. 291-292.

17. Едемский, В. А. Разностные множества, сбалансированные на два уровня, сформированные на основе классов степенных вычетов по простому модулю / В. Е. Гантмахер, В.А. Едемский // Редакцией журнала «Известия вузов. Математика». - Казань, 2008. - 13 с. -Деп. в ВИНИТИ № 639-В2008.

18. Едемский, В. А. Результаты синтеза двоичных последовательностей с периодом 4р и автокорреляцией близкой к одноуровневой / В.А Едемский, И. С. Вагунин // Сборник докладов 14-й международной научно-технической

конференции "Радиолокация, навигация и связь". - Воронеж, 2008. - Т. 1. С. 291-296.

19. Едемский, В. А. О синтезе двоичных последовательностей составного периода с квазиодноуровневой автокорреляцией / В.А Едемский, И. С. Вагунин // Труды международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития ». - Одесса, 2007. - Т. 1. - С. 55-60.

20. Едемский, В. А. Метод синтеза двоичных последовательностей с квазиодноуровневой автокорреляцией и периодом mp / В.А Едемский, И. С.Вагунин // Журнал научных публикаций аспирантов и докторантов. - 2008. -№6. -С. 147-150.

21. Едемский, В.А. О ПАКФ и ПВК двоичных и троичных последовательностей / В.А Едемский // Труды международной научно-методической конференции «Математика в вузе». - СПб., 2005. - С. 108-109.

22. Едемский, В.А. Методика анализа и синтеза ДКП, формируемых на основе классов вычетов по модулю р/ В. Е. Гантмахер, В.А. Едемский // В. Новгород, 2005. - 49 с. Рус,- Деп. в ВИНИТИ № 1737 - В2005 от 26.12.05.

23. Едемский, В.А. Методика синтеза квазиодноуровневых разностных множеств / В. Е. Гантмахер, В.А. Едемский // Материалы XVI всероссийской научно-технической конференции "Современные проблемы математики и естествознания". - Нижний Новгород, 2006. - С. 15.

24. Едемский, В.А. О взаимной корреляции бинарных последовательностей, сформированных на основе классов степенных вычетов по простому модулю p = dR+\,d = 4,6,8, с квазиидеальной автокорреляцией / В. Е. Гантмахер, В.А. Едемский // Сборник докладов 13-й международной научно-технической конференции "Радиолокация, навигация и связь",- Воронеж, 2007. -Т. 1.-С. 105-111.

25. Едемский, В.А. Квазиодноуровневые разностные множества, формируемые на основе классов степенных вычетов / В. Е. Гантмахер, В.А. Едемский // Труды международной научно-практической конференции «Современные направления теоретических и прикладных исследований». -Одесса, 2007. - Т. 21. - С. 15-20.

26. Едемский, В.А. Метод синтеза бинарных последовательностей с составным периодом на основе классов степенных вычетов. / В. А. Едемский, И. С. Вагунин // Вестник НовГУ. Серия «Техн. науки». - 2007. - № 50. - С. 2629.

27. Едемский, В.А. О программе синтеза двоичных последовательностей с периодом mpll В. А. Едемский, И. С. Вагунин // Труды международной научно-методической конференции «Математика в вузе». -СПб: 2008.-С.82-83.

28. Едемский В.А. Синтез двоичных последовательностей составного периода на основе спектров разностей классов вычетов: Свидетельство о регистрации программ для ЭВМ № 200813592 / И. С. Вагунин, В. А. Едемский

// заявитель и правообладатель «Новгородский государственный университет».-№ 2008612439; заявл. 02. 06.08.; зарег. 28.07.08.

29. Едемский В.А. Синтез уравновешенных троичных последовательностей составного периода на основе спектров разностей классов вычетов: Свидетельство о регистрации программ для ЭВМ № 2009610230 / И. С. Вагунин, В. А. Едемский // заявитель и правообладатель «Новгородский государственный университет»,- № 2008614963; заявл. 28.10.08.; зарег. 11.01.09.

30. Едемский, В.А. Анализ и синтез двоичных последовательностей с заданными параметрами на основе классов степенных вычетов по простому модулю / В. Е. Гантмахер, В. А. Едемский // Труды международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития». - Одесса, 2006. - Т. 2. — С. 76-80.

Список литературы

1. Гантмахер, В.Е. Шумоподобные сигналы. Анализ, синтез, обработка / В.Е. Гантмахер, Н.Е. Быстров, Д.В. Чеботарёв. — СПб.: Наука и техника, 2005. -400 с.

2. Свердлик, М.Б Оптимальные дискретные сигналы / М.Б. Свердлик. - М.: Сов. радио, 1975. - 200 с.

3. Ипатов, В.П. Периодические дискретные сигналы с оптимальными корреляционными свойствами / В.П. Ипатов. - М.: Радио и связь, 1992. - 152 с.

4. Ding, С. Several Classes of binary sequences with tree-level autocorrelation / C. Ding, T. Helleseth Т., K.Y. Lam // IEEE Trans. Inform. Theory. - 1999. - V. 45. - P.2601-2606.

5. Ding, C. On the Linear Complexity of Legendre Sequences / C. Ding, T. Helleseth, W. Shan W // IEEE Trans. Info Theory. - 1998. - V. IT-44. -PP. 1276 -1278.

6. Kim, J.H. On the linear complexity of Hall's sextic residue sequences / J.H. Kim, H.Y. Song // IEEE Trans. Inf. Theory. - 2001. - V. 47. - Is.5. - PP. 2094-2096.

7. Arasu, K.T. Almost difference sets and their sequences with optimal autocorrelation / K.T. Arasu, C. Ding, T. Hellesenh, P. V. Kumar, H.M. Martinsen // IEEE transactions on information theoiy. - 2001. - V. 47. - № 7. - P. 2934-2943.

8. Zhang, Y. A new family of almost differences sets and some necessary conditions / Y. Zhang, J. G. Lei J. G., S. P. Zhang // IEEE Trans. Info. Theory.-2006,- V. 52. -PP. 2052- 2061.

Изд. лиц. ЛР № 020815 от 21.09.98. Подписано в печать 16.06.2009. Бумага офсетная. Формат 60x84 1/16. Гарнитура Times New Roman. Печать офсетная. Усл. печ. л. 2,0. Тираж 100 экз. Заказ № 57

Издательско-полиграфический центр Новгородского государственного университета им. Ярослава Мудрого 173003, Великий Новгород, ул. Б. Санкт-Петербургская, 41.

Отпечатано в ИПЦ НовГУ. 173003, Великий Новгород, ул. Б. Санкт-Петербургская, 41.

Введение

1. Обзор известных результатов синтеза дискретно — кодированных последовательностей, сформированных на основе классов степенных вычетов

1.1. Классификация дискретно — кодированных последовательностей

1.2. Характеристики известных дискретно-кодированных последовательностей на основе обобщенного правила кодирования

1.3. Математический аппарат теории спектров разностей классов вычетов

1.4. Выводы и постановка задач диссертационного исследования

2. Методика синтеза дискретно-кодированных последовательностей с заданной совокупностью свойств или ограничений на их характеристики

2.1. Постановка задач второй главы

2.2. Применение циклотомических чисел для расчета СРКВ

2.3. Методика синтеза дискретно-кодированных последовательностей с заданной совокупностью свойств или ограничений на их характеристики

2.4. Синтез двоичных последовательностей с квазиодноуровневой автокорреляцией и pf~

2.5. Анализ взаимной корреляции синтезированных двоичных последовательностей

2.6 Выводы по главе

3. Синтез двоичных последовательностей с заданной совокупностью свойств или ограничений на их характеристики

3.1. Постановка задач третьей главы

3.2. Методы синтеза двоичных последовательностей с ограничениями на ПАКФ, пик-фактор, период.

3.3. Методы синтеза двоичных последовательностей с ограничениями на ПВКФ, пик-фактор, период.

3.4. Корреляционный анализ синтезированных двоичных последовательностей

3.5. Выводы по главе

4. Синтез троичных и бинарных последовательностей с заданной совокупностью свойств или ограничений на их характеристики

4.1. Постановка задач четвертой главы

4.2. Методы и результаты синтеза троичных последовательностей с ' заданной совокупностью свойств или ограничений на их характеристики

4.3. Синтез троичных последовательностей с квазиидеальной ПВКФ 121 • 4.4. Метод и результаты синтеза бинарных последовательностей с заданной совокупностью свойств или ограничений на их характеристики

4.5. Выводы по главе

5. Применение СРКВ для расчета эквивалентной линейной сложности последовательностей, сформированных на основе классов степенных вычетов

5.1. Постановка задач пятой главы

5.2. Метод расчета линейной сложности двоичных последовательностей на основе классов степенных вычетов

5.3. Расчет линейной сложности двоичных последовательностей с квазиодноуровневой ПАКФ и одноуровневой ПВКФ

5.4. Метод расчета линейной сложности троичных последовательностей на основе классов степенных вычетов

5.5. Расчет линейной сложности троичных последовательностей с квазиидеальной ПАКФ

5.6. Выводы по главе

6. Синтез дискретно-кодированных последовательностей с составным периодом тр

6.1. Постановка задач шестой главы

6.2. Распространение методики синтеза дискретно-кодированных последовательностей с простым периодом р на последовательности с периодом тр

6.3. Примеры синтеза двоичных и троичных последовательностей на основе первой стратегии модернизированной методики

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

6.5. Синтез двоичных последовательностей с составным периодом тр и заданной совокупностью свойств или ограничений на их характеристики

6.6. Синтез троичных последовательностей с периодом 2р и заданной совокупностью свойств или ограничений на их характеристики

6.6. Выводы по главе •

7. Алгоритмы и комплекс программ синтеза последовательностей с заданной совокупностью свойств или ограничений на их характеристики

7.1. Постановка задач седьмой главы

7.2. Комплексная методика и обобщенный алгоритм синтеза последовательностей

7.3. Алгоритмы синтеза дискретно-кодированных последовательностей с простым периодом

7.4. Алгоритм метода расчета линейной сложности дискретно-кодированных последовательностей, сформированных на основе классов степенных вычетов

7.5. Алгоритмы синтеза дискретно-кодированных последовательностей с периодом тр

7.6. Выводы по главе

Диссертация' посвящена* решению актуальной научной задачи синтеза двоичных и троичных последовательностей, сформированных на основе классов степенных вычетов- по простому модулю, в том числе и псевдослучайных. Особенность постановки»задачи-синтеза-заключается в.том, что ограничения' задаются на совокупность, свойств или характеристик последовательности. Произвольный набор ограничений может быть выбран из следующего меню: период, вес, пик-фактор, рельефы автокорреляционной и взаимно корреляционной функций, рельеф автокорреляционной функции двоичной последовательности, соответствующей нулевым символам троичной^ последовательности, степень уравновешенности для троичных и бинарных последовательностей, эквивалентная линейная сложность.

Актуальность работы., Двоичные1 и троичные последовательности являются самыми широко- востребованными дискретно-кодированными^ последовательностями, область применения которых с каждым годом; расширяется. В вычислительных системах их используют в качестве-псевдослучайных последовательностей для- имитационного моделирования, обеспечения связи между компьютерами, тестирования, решения задач методом Монте-Карло. В. телемеханических системах на основе двоичных и троичных последовательностей строят самосинхронизирующиеся коды с обнаружением и исправлением ошибок. В системах связи и передачи информации на основе двоичных и троичных последовательностей осуществляют скрытную связь с высокой криптостойкостью. В системах радиолокации, гидролокации, радионавигации их используют в качестве модулирующих последовательностей при формировании сложных шумоподобных сигналов, обеспечивая высокие потенциал и помехоустойчивость при низкой пиковой мощности' передатчиков. Столь широкий спектр применений обуславливает набор требований к таким характеристикам и свойствам последовательностей, как: период, вес, уровень боковых лепестков корреляционных функций, пик-фактор, уравновешенность, эквивалентная линейная сложность и другим. Число требований к набору свойств или характеристик последовательностей год от года увеличивается.

Вопросам анализа и синтеза дискретно-кодированных последовательностей (ДКП) и их применениям посвящены многочисленные научные публикации [1-90]. Прежде всего, отметим работы Свердлика М. Б.[12], Ипатова В.Щ18,19,25,26],-Камалетдинова Б.Ж.[31]; Пелехатого М. И. [21] и других авторов, в том числе [7,13,16,33,48], посвященные синтезу бинарных и троичных последовательностей с идеальной периодической автокорреляционной функцией (ПАКФ). Фрэнк Р.[1], Габидулин Э. М.[46,47], Леухин А.Н.[57,66], Кренгель Е.И. [53] и другие синтезировали многофазные коды с хорошими корреляционными свойствами. Леухиным А. Н. в [54] было предложено алгебраическое решение задачи? синтеза последовательностей с заданной ПАКФ.

Работы Свердлика М. Б. [12], Холла М. [7], Сторера С. [82] и других авторов, в частности [35], посвящены синтезу последовательностей с одноуровневой ПАКФ и развитию теории разностных множеств, находящихся во взаимно однозначном' соответствии с указанными последовательностями. Почти разностные множества, которым соответствуют бинарные последовательности с оптимальной автокорреляцией, исследованы Дингом К. и иными авторами в [27,36,44,45,63,64].

Существенные результаты о ДКП с квазиодноуровневой (квазиидеальной) ПАКФ были получены Гантмахером В.Е. на основе разработанной им теории спектров разностей классов вычетов по простому модулю [20].

Методы и алгоритмы расчета эквивалентной линейной сложности изложены в [9,70,71], троичных последовательностей в [72,74,75,80], а бинарных последовательностей на основе классов степенных вычетов в [73,7679].

Взаимная корреляция (расчет и оценка) ДКП на основе классов степенных вычетов исследовалась в [20,37,67].

В то же время, несмотря на многочисленные публикации, посвященные синтезу ДКП, отсутствуют регулярные методы синтеза последовательностей с заданной совокупностью свойств или ограничений! на их характеристики. В*1 связи с этим задача синтеза последовательностей с заданной совокупностью свойств или ограничений на их характеристики является чрезвычайно актуальной.

В.Е. Гантмахером была предпринята попытка решить эту задачу с помощью теории спектров разности классов вычетов (СРКВ), но только для последовательностей, период которых — простое число, а набор характеристик последовательностей ограничен периодом, уровнем боковых лепестков корреляционных функций и пик — фактором [20].' На основе математического^ аппарата теории СРКВ были синтезированы ДКП, сформированные на основе классов степенных вычетов, которые обладают, по сравнению с известными последовательностями, более плотной сеткой периодов и более плотным рядом значений пик - фактора. Сравнение известных способов синтеза ДКП показывает, что синтез ДКП с использованием СРКВ является наиболее универсальным методом синтеза двоичных, троичных и бинарных последовательностей, формируемых на основе классов степенных вычетов. Но и ему, в том виде, в котором он представлен в [20], присущи серьёзные недостатки: * при большом числе классов степенных вычетов затруднён анализ СРКВ, соответствующих ПАКФ и периодической взаимно корреляционной функциям (ПВКФ) дискретно-кодированных последовательностей; в этом методе заложена потенциальная возможность синтеза ДКП с заданной совокупностью свойств, но она не реализована;

- нет метода расчёта эквивалентной линейной сложности ДКП; сформированных по обобщенному правилу кодирования, на основе СРКВ;

- представляет интерес распространение методов синтеза ДКП с периодом р, в основе которых лежат СРКВ, на синтез ДКП с составным периодом тр.

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

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

- усовершенствование методики анализа и синтеза дискретно-кодированных последовательностей на основе СРКВ путём применения циклотомических чисел;

- разработка методов синтеза двоичных и троичных последовательностей с заданной совокупностью свойств или ограничений на их характеристики и синтез последовательностей с определённым набором свойств или характеристик;

- расчёт эквивалентной линейной сложности дискретно—кодированных последовательностей, сформированных на основе классов степенных вычетов;

- распространение методики синтеза ДКП с простым периодом р на последовательности с периодом тр, где т — натуральное число, взаимно простое с р\

- разработка алгоритмов и комплекса' программ, реализующих предложенные методьгсинтезапоследовательностей.

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

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

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

• определены новые правила кодирования семейств двоичных последовательностей с периодом! р и квазиодноуровневыми периодическими» автокорреляционными или взаимно корреляционными функциями;

• > получены новые семейства троичных и бинарных последовательностей с периодом р и квазиидеальными периодическими автокорреляционной и взаимно корреляционной функциями;

• предложен унифицированный метод расчета эквивалентной линейной сложности ДКП, формируемых на основе классов степенных вычетов по простому модулю;

• расширена область применения теории СРКВ по простому модулю на синтез двоичных и троичных последовательностей с периодом тр\

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

Теоретическая и практическая значимость. Диссертационная работа носит теоретический характер. Полученные в ней результаты, разработанные методы и комплекс программ могут быть использованы для синтеза* широкого класса^ двоичных и троичных последовательностей, применяемых в математических моделях, в вычислительных системах, в криптографии, в качестве модулирующих последовательностей в системах связи, радиолокации' и других областях. В частности, результаты, диссертационной работы были! использованы в следующих научно-исследовательских работах:

1. Грант РФФИ № 07-01-97615-рофи «Разработка принципов, построения квазиодноуровневых разностных множеств- с заданными, ограничениями на их параметры», руководитель Гантмахер ЕГ. Е.

2. Фундаментальная* НИР "Теория анализа, синтеза и, обработки, шумоподобных сигналов в радиотехнических системах различного назначения", руководитель. Гантмахер В.Е., по заданию Рособразования, гос. per. № 0120.0 503550, 2005-2009 г.

3. Фундаментальная НИР "Исследование методов синтеза сложных сигналов, видов модуляции и способов обработки для перспективных радиолокационных систем", руководитель Гантмахер В.Е., по научно -технической программе Рособразования «развитие научного потенциала высшей школы», гос. per. № 0120.0 603815, 2006-2008 г.

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

Личный вклад автора. В диссертационной работе обобщены результаты, выполненные лично автором или при его непосредственном участии. Постановка задач принадлежит научному консультанту Гантмахеру В. Е. Исследования по комплексному применению СРКВ и циклотомических чисел для анализа и синтеза последовательностей, а также расчету их эквивалентной линейной сложности выполнены лично автором. Программы для ЭВМ разработаны совместно1 с Вагуниным И.С.

Апробация' работы. Результаты работы обсуждались на всемирном, форуме "Signal Design and Its Applications in Communications, (IWSDA'07)"(Kirraîî, Чанджоу), неоднократно докладывались и обсуждались нае международных научных и научно-технических конференциях:

• "Цифровая, обработка сигналов и её применения" (г. Москва - 2007,

2008);

• «Научные исследования, и их практическое применение. Современное состояние и пути развития» (г. Одесса — 2006-2008);

• "Радиолокация, навигация и связь" (г. Воронеж -2007— 2008);

• "Современные проблемы математики и естествознания" (г. Нижний Новгород - 2006);

• «Математика в вузе» (г. Санкт-Петербург — 2005—2008);

• на симпозиуме по «Прикладной и промышленной математике», осенняя сессия (г. Йошкар-Ола — 06);

• на семинарах «Шумоподобные сигналы и их применение» (НовГУ);

• на семинарах кафедры КПМИ НовГУ.

Публикации. Всего по теме диссертации опубликовано 35 работ, из них одна монография, 2 статьи - в международных изданиях, 10 — в журналах, входящих в перечень, рекомендованный ВАК для публикации основных результатов докторских диссертаций. Получено два свидетельства о регистрации программ для ЭВМ. При участии автора подготовлено 5 отчетов по НИР. Перечисленные работы достаточно полно отражают содержание диссертации.

Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения, приложений и списка литературы. Общий объем диссертации составляет 266 страниц. Библиография содержит 125* наименований.

7.6. Выводы по главе

Таким образом, в седьмой главе разработаны алгоритмы синтеза ДП, ТП и БП с заданной совокупностью свойств или ограничений- на их характеристики, реализующие:

- методы синтеза ДП с простым периодом и ограничениями на период, вес, пик-фактор, рельефы ПАКФ или (и) ПВКФ;

- методы синтеза ТП с простым периодом и ограничениями на период, вес, рельефы ПАКФ или (и) ПВКФ, рельеф ПАКФ двоичной последовательности, соответствующей нулевым символам троичной последовательности, пик-фактор, степень уравновешенности;

- методы синтеза БП с простым периодом и ограничениями на период, рельефы ПАКФ или (и) ПВКФ, степень уравновешенности;

- метод расчета линейной сложности дискретно-кодированных последовательностей, сформированных на основе классов степенных вычетов; метод синтеза ДП с периодом тр и ограничениями на период, вес, пик-фактор, рельеф ПАКФ; метод синтеза уравновешенных ТП с периодом тр и ограничениями на период, вес, рельеф ПАКФ, пик-фактор.

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

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

231

Заключение

1. Применение циклотомических чисел позволило: упростить анализ таблиц СРКВ, а также расчет и анализ СРКВ, соответствующих корреляционным функциям ДКП, формируемых на основе нескольких классов степенных вычетов; обобщать полученные частные решения синтеза ДКП в правила кодирования и находить обобщенные формулы для • характеристик синтезированных ДКП.

Все это привело к усовершенствованию методики анализа. и синтеза дискретно-кодированных последовательностей на основе СРКВ, повысило её

•ч результативность. Кроме этого, число задаваемых свойств или ограничений на характеристики последовательностей увеличено с трех до восьми. В настоящий момент, обобщенная методика1 синтеза последовательностей позволяет выбирать свойства или ограничения на их характеристики^ из следующего меню: период, вес, рельефы, автокорреляционной и, взаимно.корреляционной функций, рельеф автокорреляционной функции, двоичной'последовательности, соответствующей нулевым символам троичной последовательности, пик-фактор, степень уравновешенности для троичных и бинарных последовательностей, эквивалентная линейная сложность.

2. На основе комплексной методики СРКВ и циклотомических' чисел разработаны универсальные, обобщенные, продуктивные и» эффективные методы синтеза двоичных, троичных и бинарных последовательностей с простым периодом, в том числе и псевдослучайных: методы синтеза двоичных последовательностей с ограничениями на период, вес, пик-фактор, рельефы ПАКФ или (и) ПВКФ; методы синтеза троичных последовательностей с ограничениями на период, вес, рельефы ПАКФ или (и) ПВКФ, рельеф ПАКФ двоичной последовательности, соответствующей нулевым символам троичной* последовательности, пик-фактор; степень уравновешенности; методы синтеза бинарных последовательностей с ограничениями на период, рельефы ПАКФ или (и) ПВКФ, степень уравновешенности.

Методы проиллюстрированы многочисленными примерами синтеза последовательностей с заданной совокупностью свойств или ограничений на их характеристики. Определены новые правила кодирования семейств двоичных последовательностей с периодом р и квазиодноуровневыми периодическими автокорреляционными или взаимно корреляционными функциями и троичных последовательностей с квазиидеальными периодическими автокорреляционными или взаимно корреляционными функциями.

3. Разработав унифицированный метод расчета эквивалентной линейной сложности последовательностей, сформированных на основе классов степенных вычетов. Определена линейная сложность двоичных и троичных последовательностей. Показано, что подавляющее число вновь синтезированных последовательностей обладают высокой криптостойкостью. Получены новые правила кодирование семейств ДКП с большой линейной сложностью.

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

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

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

234

1. Фрэнк, Р. Многофазные коды с хорошими непериодическими корреляционными свойствами / Р. Фрэнк // Зарубежная радиоэлектроника. — 1963.-№ 12.-С. 39-44.

2. Мешковский, К.А. Кодирование в технике связи- / К.А. Мешковский, Н.Е. Кириллов. -М.: Связь, 1966. 324*с.

3. Вакман, Д.Е. Регулярный метод синтеза фазоманипулированных сигналов / Д.Е. Вакман. М.: Сов. радио, 1967. — 96 с.

4. Варакин, Л.Е. Синтез фазоманипулированных сигналов / Л.Е. Варакин // Радиотехника и электроника. — 1969. — Т. 14, № 5. — С. 796 — 806.

5. Алексеев, А.И. Теория и применение псевдослучайных сигналов / А.И. Алексеев, А.Г. Шереметьев, Г.И. Тузов и др. М.: Наука, 1969. — 368 с.

6. Варакин, Л.Е. Теория сложных сигналов / Л.Е. Варакин. — М.: Сов. радио, 1970. — 375 с.

7. Холл, М. Комбинаторика /М. Холл. М.: Мир, 1970. - 423 с.

8. Амиантов, И.Н. Избранные вопросы статистической теории связи /И. Н. Амиантов.-М.: Сов. радио, 1971. -416 с.

9. Берлекэмп, Э. Алгебраическая теория кодирования / Э. Берлекэмп; Пер. с англ. И.И. Грушко; Под ред. С.Д. Бермана. М.: Мир, 1971. — 479 с.

10. Кук, Ч. Радиолокационные сигналы. Теория и применение / Ч. Кук, М. Бернфельд; Пер. с англ.; Под ред. B.C. Кельзона. М.: Сов. радио, 1971. -568 с.

11. Трахман, A.M. Введение в обобщенную спектральную теорию сигналов / A.M. Трахман. М.: Сов. радио, 1972 351 с.

12. Свердлик, М.Б Оптимальные дискретные сигналы / М.Б. Свердлик. -М.: Сов. радио, 1975.-200 с.

13. Дядюнов, Н.Г. Ортогональные и квазиортогональные сигналы / Н. Г. Дядюнов, А. И. Сенин. М. Связь, 1977 . - 224 с.

14. Варакин, JI.E. Теория систем сигналов / JI.E. Варакин. — М.: Сов. радио, 1978.-304 с.

15. Варакин, JI.E. Системы связи с шумоподобными сигналами / JI.E. Варакин. М.: Радио и связь, 1985. - 384 с.

16. Винокуров, В.И. Дискретно-кодированные последовательности / В.И. Винокуров, В.Е. Гантмахер; Отв. редактор Б.Ф. Кирьянов. — Ростов-на-Дону: Ростовский ун-т, 1990. — 283 с.

17. Окунев, Ю.Б. Цифровая передача информации фазомодулированными сигналами / Ю.Б. Окунев. М.: Радио-и связь, 1991. -296 с.

18. Ипатов, В.П. Периодические дискретные4сигналы с оптимальными корреляционными свойствами / В.П. Ипатов. М.: Радио и связь, 1992. — 152 с.

19. Ipatov, V.P. Spread Spectrum and CDMA. Principles and Applications /. V.P. Ipatov. Wiley, 2005. 383 pp.

20. Гантмахер, В.Е. Шумоподобные сигналы. Анализ, синтез, обработка / В.Е. Гантмахер, Н.Е. Быстров, Д.В. Чеботарёв. — СПб.:, Наука и техника, 2005.-400 с.

21. Пелехатый, М.И. О последовательностях квадратичных вычетов с наилучшими автокорреляционными свойствами, / М.И. Пелехатый // Радиотехника и электроника. — 1971. Т. 16, № 5. — С. 788 - 796.

22. Lempel, A. A class of balanced binary sequences with optimal autocorrelation properties / A. Lempel, M. L. Cohn, W. L. Eastman // IEEE Trans. Info. Theory. 1977. -V. IT-23. -PP. 38 - 42.

23. Кренгель, Е.И. О числе псевдослучайных последовательностей Гордона, Милза, Велча / Е. И.,Кренгель, К. А. Мешковский // Техника средств связи. Сер. ТРС .-1979. №. 3. - С. 17-30.

24. Кренгель, Е.И. Генератор псевдослучайных последовательностей Гордона, Милза, Велча / Е. И. Кренгель, К. А. Мешковский // Техника средств связи. Сер. ТРС .-1979. №. 3.

25. Ипатов, В.П. Троичные последовательности с идеальными периодическими свойствами / В. П. Ипатов // Радиотехника и электроника. — 1979. -Т. 24. № 10. - С. 2053-2057.

26. Ипатов, В.П. К теории троичных последовательностей с идеальными периодическими свойствами / В. П. Ипатов // Радиотехника и электроника. 1980. -Т. 25. - № 4. - С 723-727.

27. Bernasconi, J. Low autocorrelation binary sequences: statistical5 mechanics and configuration space analysis / J. Bernasconi // J. Physique.— 1987—V. 48 .- PP. 559-567.

28. Гантмахер, B.E. О возможности синтеза троичных псевдослучайных последовательностей / В.Е. Гантмахер // Известия» вузов. Математика. — 1985. — № 7. С. 70 - 74.

29. Гантмахер, В.Е. Алгоритмы синтеза двоичных последовательностей„ со свойством «не более совпадений» / В.Е. Гантмахер // Вестник Новгородского государственного университета. Сер. Естественные науки. — Новгород, 1995. — № 3. С. 74-82.

30. Mertensy, S. Exhaustive search for« low-autocorrelation binary sequences / S. Mertensy // J. Phys. A: Math. Gen., 1996. -V. 29.- PP.473-481.

31. Камалетдинов, Б.Ж. Оптимальные множества бинарных последовательностей / Камалетдинов; Б.Ж. // Проблемы передачи информации, 1996 .- Т. 32. № 2.- С. 39-44.

32. Леухин, А.Н. Метод синтеза сложных сигналов по функции неопределенности / А.Н. Леухин, А.А. Роженцов // Материалы 1-ой Международной конференции и выставки «Цифровая обработка сигналов и ее применение». М., 1998. - Т. 3. - С. 90 - 97.

33. Helleseth, Т. Sequences with low correlation / Т. Helleseth, P. V. Kumar // Handbook of Coding Theory. V. Pless, W. C. Huffman, Eds., Elsevier, Amsterdam, The Netherlands, 1998. - V. II. - PP. 1765 - 1854.

34. Мешковский, К. А. Генерация псевдослучайных последовательностей Гордона, Милза, Велча / К.А. Мешковский, Е.И. Кренгель // Радиотехника. 1998. — № 5.

35. Pott, A. Difference Sets, Sequences and Their Correlation Properties / A. Pott, P. V. Kumar, T. Helleseth, D. Jungnickel. Kluwer , 1999.-542 c.

36. Ding, C. Several Classes of binary sequences with tree-level autocorrelation / C. Ding, T. Helleseth Т., K.Y. Lam // IEEE Trans. Inform; Theory. 1999. - V. 45. - P.2601—2606.

37. Кренгель, Е.И. Взаимная корреляция некоторых классов псевдослучайных последовательностей / Е. И. Кренгель, К. А. Мешковский К.А. //Радиотехника. 2000. - №6. - С. 8-13.

38. Мальцев, С.В. Бинарные последовательности для криптостойких систем связи / С.В. Мальцев, Р.П. Богуш // Известия Белорусской инженерной академии. 2000. - № 1 (9) / 1. - С. Г42 - 143.

39. Green, D.H. Linear complexity of modified, Jacobi sequences / D.H. Green, J. Choi // IEE Proc.: Comput. Digital Tech. 2000: -. V. 149. - №3. - P. 97101.

40. Мальцев, С.В. Формирование нелинейных бинарных последовательностей с расширенным ансамблем / С.В. Мальцев, Р.П. Богуш // Радиотехника.-2001.-№ 11.-С. 52-53.

41. Кренгель, Е.И. Классификация двоичных последовательностей Гордона, Милза, Велча / Е.И. Кренгель, К.А. Мешковский // Радиотехника. — 2001.-№ 12.-С. 13-15.

42. Архипкин, В.Я. Псевдослучайные последовательности для систем связи CDMA / В. Я. Архипкин, Е. И. Кренгель Е.И., А. Г.Соколов // Сборник докладов 7-ой международной научно-технической конференции "Радиолокация, навигация и связь".—Воронеж, 2001— С.

43. Parker, М. G. Even-length binary sequence families with low negaperiodic autocorrelation / M. G. Parker // Lecture Notes In Computer Science;

44. Proc. 14th Int. Symp. Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (AAECC-14), Melbourne, Australia. 2001. - V. 2227. - PP. 200-209.

45. Arasu, K.T. Almost difference sets and their sequences with optimal autocorrelation / K.T. Arasu; C. Ding, T. Hellesenh, P. V. Kumar, H.M. Martinsen // IEEE transactions on information theory. 2001. - V. 47. - № 7. - P. 2934-2943.

46. Ding, C. New families of binary sequences with optimal three-level autocorrelation / C. Ding, T. Hellesenh, H.M. Martinsen // IEEE Trans. Info. Theory. -2001. V. IT-47. - P. 428 - 433.

47. Габидулин, Э. M: Новые последовательности^ с нулевой автокорреляцией / Э. М. Габидулин, В. В. Шорин / / Проблемы передачиинформации. 2002. - Т.38. -№ 4. -С. 10-23.!

48. Габидулин, Э.М. Последовательности* с нулевой автокорреляцией, определенной на кольце / Э. М. Габидулин, В. В. Шорин // Электронный журнал «Исследовано в России». 2003— Т.167.-С.2011-2041,-http://www.zhurnal.mipt.ru/articles/2003/167.pdf

49. Luke, Н. D. Binary and quadriphase sequences with optimal autocorrelation properties: A survey / H. D. Luke, H. D. Schotten, H. Hadinejad-Mahram // IEEE Trans. Info. Theory. -2003. V. IT-49. - P. 3271 - 3282.

50. Кренгель, Е.И. Ансамбли двоичных последовательностей с малой взаимной корреляцией и большой линейной сложностью / Е.И. Кренгель, К.А. Мешковский // Радиотехника. — 2004. — № 4. — С. 3 — 5.

51. Кренгель, Е.И. Псевдослучайные двоичные последовательности с нулевой зоной автокорреляции и боковыми выбросами ±(р+1) / Е. И. Кренгель // Цифровая обработка сигналов. — 2004 №2. - С.2-6.

52. Леухин, А.Н1 Алгебраическое решение задачи синтеза- кодовых последовательностей / А.Н. Леухин // Квант. Электроника .— 2005.— Т. 35 — №8.- С. 688-692.

53. Leukhin, A.N. Algebraic solution of the synthesis problem for coded sequences / A.N. Leukhin // Quantum Electronics. 2005. - Vol. 35, No 8. - PP. 688 -692.

54. Кренгель, Е. И. Конструирование почти идеальных и нечетно-идеальных троичных последовательностей / Е. И. Кренгель // Радиотехника .— 2006.-№9.-С. 8-12.

55. Кренгель, Е. И; Несогласованные почти-идеальные двоичные последовательности// Сборник докладов 6-й международной конференции "Цифровая обработка сигналов и ее применение". М., 2006 — С. 71—74.

56. Кренгель, Е. И. Ортогональные последовательности с низким пик-фактором для MC-CDMA систем// Сборник, докладов 6-й международной конференции "Цифровая обработка сигнал ови= ее применение". М-., 2006 — С. 69-71.

57. Кренгель, Е.И. Несогласованные почти-идеальные двоичные последовательности / Е. И. Кренгель // Цифровая обработка сигналов — 2006 — №4'- С. 44-47.

58. Кренгель, Е. И. Конструирование почти идеальных и* нечетно-идеальных троичных последовательностей* / Е. И. Кренгель // Радиотехника .— 2006 .-№9.- С. 8-12.

59. Zhang; Y. A new family of almost differences sets and some necessary conditions / Y. Zhang, Js. G. Lei J. G., S. P. Zhang // IEEE Trans. Info.* Theory — 2006.- V. 52: -PP: 2052- 2061.

60. Chen, Z. Sequences related1 to-Legendre/Jacobi sequences/ Z. Chen, X. Du, G. Xiao // Information Sciences: an International Journal.- 2007.-V. 177.- Is. 21 .-PP. 4820-4831.

61. Леухин, A.H. Синтез и анализ сложных фазокодированных последовательностей / А.Н. Леухин, А.Ю. Тюкаев, С.А. Бахтин // Электромагнитные волны и электронные системы. 2007. — № 4. - С. 32 — 37.

62. Леухин, А.Н. Новые фазокодированные последовательности, с хорошими корреляционными характеристиками / А.Н. Леухин, А.Ю. Тюкаев, С.А. Бахтин, Л.Г. Корнилова // Электромагнитные волны и электронные системы. 2007. - № 6. - С. 51 - 54.

63. Щетинин В .И., 1 фитчина JI.С. Сингулярные ансамбли оптимальных дискретных сигналов; Сб. докл. 10-ой международной конференции "Цифровая обработка сигналов и её применения".— Mi, 2008 — Т. 1-С:22-25.

64. Лидл, Р. Конечные поля / Р. Лидл, Нидеррайтер Г. — М.: Мир, 1988,- 820 с.

65. Cusick, T.W. Stream? Ciphers and Number Theory / Т., W: Cusick, G. . Ding, A. Renvall Amsterdam.: Elsevier, 1998:— 466 c.

66. Ипатов, В. П. Эквивалентная; линейная сложность: троичных последовательностей' с идеальными автокорреляционными свойствами / В; П; Ипатов, Б: Ж. Камалетдинов;// Радиотехника и электроника — 19891—Т. 34. — № 11.-С. 2451-2454. . " /.

67. Ding, С. On the Linear Complexity of Legendre Sequences / C. Ding, T. Helleseth, W. Shan W // IEEE Trans. Info Theory. 1998: - V. 1T-44. -PP. 1276 -1278:

68. Kyureghyan G. M. On the Linear Complexity of the Sidelnikov-Lempel-Cohn-Eastman Sequences / M. G. Kyureghyan, A. Pott // Designs, Codes and Cryptography. 2003. - V. 29. -PP. 149-164.

69. Meidl, W. Some Notes on the Linear Complexity of Sidel'nikov-LempelLCohn-Eastman Sequences / W. Meidl, A. Winterhof // Designs, Codes and Cryptography. 2006.-V. 38.-PP. 159-178.

70. Bai, E. On the linear complexity of generalized cyclotomic sequences of order four over Zpq / E. Bai, X. Fu, G. Xiao // IEICE Trans. Fundamentals of Electron. Commun. Comput. Sci. V. E88-A il. -PP. 392-395.

71. Green, D.H. Linear complexity of modified' Jacobi sequences / D. H. Green, J. Choi // IEE Proc.: Comput. Digital Tech. -2002. -V. 149. Is. 3. PP. 97101.

72. Kim, J.H. On the linear complexity of Hall's sextic residue sequences / J.H. Kim, H.Y. Song // IEEE Trans. Inf. Theory. 2001'. - V. 47. - Is.5. - PP. 20942096.

73. Bai, E. Linear complexity of new generalized cyclotomic sequences of order two of length pq / E. Bai, X. Liu, G. Xiao // IEEE Trans. Info. Theory. -2005. -V. 51.-Is. 5.-PP. 1849-1853.

74. Kim, Y.-S. Chung H. Linear Complexity over Fp of Ternary Sidel'nikov Sequences / Y—S. Kim, J.-S. Chung, J.-S. No // Proceedings of SETA. — China, 2006.-PP. 61-73.

75. Dickson, L.E. Cyclotomy, higher congruenses, and Waring's problems / L.E.Dickson// Amer. J. Math.- 1935.-V. 57.-PP.391^124.

76. Storer, T. Cyclotomy and Difference Set / T. Storer, T. — Chicago.: Marham, 1967,- 134 p.

77. Lehmer, E. On the number of solutions of uk + D = w2 (mod p)/ E. Lehmer // Pacific J. Math.-1955. V.5. - PP.103-118.

78. Whiteman, A.L. The cyclotomic numbers of order twelve / A.L. Whiteman // Acta arithmetica. 1960. - №6. -PP. 53-76.

79. Whiteman, A.L. The cyclotomic numbers of order ten / A.L. Whiteman // Proc. Sympos. Appl. Math. 1960. - V. 10. -PP. 95-111.

80. Ding, C. Autocorrelation Values of Generalized Cyclotomic Sequences of Order Two / C. Ding // IEEE Trans. Info. Theory. -1998. V. IT-44. - PP. 1699 -1702.

81. Ding, C. Cyclotomy and Duadic Codes of Prime Lengths / C. Ding, V. Pless // IEEE Trans. Info. Theory. -1999. V. IT-45. - PP. 453 - 466.

82. Ding, C. New generalized cyclotomy and its applications / C. Ding, T. Heileseth // Finite Fields Their Appl. -1998. V. 4. -PP. 140 - 166.

83. Ding, С. Generalized Cyclotomic Codes of Length piel . ptet / C. Ding, T. Helleseth // ШЕЕ Transactions on Information theory. 1999. - V. 45. -PP. 467 -474.

84. Плёкин, В. Я. Формирование функции неопределенности дискретно-кодированных по частоте сигналов с заданными свойствами / В. Я. Плёкин, Т. X. Нгуен // Известия вузов. Радиоэлектроника. —2004. № 1. - С. 614.

85. Айерлэнд, К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен М.: Мир, 1987.-416 с.

86. Боревич, З.И. Теория чисел / 3. И. Боревич, И. Р.Шафаревич — М.: Наука, 1972.-496 с.

87. Виноградов, И.М. Основы теории чисел / И. М. Виноградов. — М.: Гос. изд. техн.-теор. лит, 1965 180 с.

88. Едемский, В.А. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики / В.А. Едемский, В. Е. Гантмахер Великий Новгород.:, НовГУ, 2009.- 189 с.

89. Едемский, В. А. Методика построения разностных множеств, сбалансированных на несколько близких уровней / В. А. Едемский //

90. Обозрение прикладной и промышленной математики. — 2007. — Т. 14. —Вып. 2. — С. 291-292.

91. Едемский, В.А. Методика анализа и синтеза ДКП, формируемых на основе классов вычетов по модулю р! В. Е. Гантмахер, В.А. Едемский // В. Новгород, 2005.-49 с. Рус.- Деп. в ВИНИТИ № 1737 В2005 от 26.12.05.

92. Едемский, В.А. Методика синтеза квазиодноуровневых разностных множеств / В. Е. Гантмахер, В.А. Едемский // Материалы.XVI всероссийской научно—технической конференции "Современные проблемы математики и естествознания". Нижний Новгород, 2006. — С. 15.

93. Едемский, В.А. Метод синтеза бинарных последовательностей с составным периодом на основе классов степенных вычетов. / В. А. Едемский, И. С. Вагунин // Вестник НовГУ. Серия «Техн. науки». — 2007. — № 50. — С. 2629.

94. Едемский, В.А. Двоичные последовательности с квазипостоянной автокорреляцией / В. Е. Гантмахер, В.А. Едемский // Труды междунар. Научно-методич. конф. «Математика в вузе». Псков. 2006 г. С. 114-115.

95. Едемский, В.А. Квазиодноуровневые разностные множества / В. Е. Гантмахер, В.А. Едемский // Вестник МГТУ им. Н.Э. Баумана. Сер. "Естественные науки". 2007. - №4. - С. 8-19 .

96. Едемский, В. А. О двоичных и троичных последовательностях с квазиодноуровневой! периодической* автокорреляционной: функцией- для: р = 1 mod4 / В. Е. Гантмахер, В:А. Едемский // Вестник НовГУ. Серия «Техн. науки». 2004.- № 28: - С! 73-76^:

97. Едемский, В.А. О ПАКФ и ПВКФ двоичных и троичных последовательностей / В.А Едемский // Труды международной: научно-методической конференции «Математика в вузе».— СПб., 2005. С. 108-109.

98. Едемский, В.А. Результаты синтеза пар двоичных последовательностей . простого периода: с одноуровневой и- двухуровневой взаимной^ корреляцией / В. Е. Гантмахер, В:А. Едемский: // Известия вузов. Радиоэлектроника. 2006. — № 4. — С. 26-33.

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

100. Труды международной научно-методической конференции- «Математика« в-вузе». СПб., 2007. - С. 104. ;

101. Едемский, В. А. К вопросу, синтеза троичных квазиортогональных последовательностей с одним нулевым символом на периоде / В. Е. I "ангмахер, А. С. Евдаков, В.А. Едемский // Вестник НовГУ. Серия «Техн. науки». 2004. - №26.-С. 101-103.

102. Едемский, В.А. О бинарных последовательностях простого ¿периода с квазиидеальной автокорреляцией^/ В. Е. Гантмахер, В.А. Едемский // Вестник Саратовского государственного»технического университета. — 2007. — № 1(21): —Вып. 11-С. 7-12.

103. Едемский, В.А. О' линейной сложности троичных, последовательностей на основе классов степенных вычетов /В; А. Едемский // Проблемы передачи информации. — 2008. — Т. 44. Вып.,4. -С. 3-11.

104. Едемский, В.А. О1 синтезе дискретно-кодированных последовательностей периода 2р/ В; Е. Гантмахер; В.А. Едемский, С. М:

105. Платонов // Сборник докладов 10-ой международной конференции-"Цифровая обработка сигналов и её применения". — М'., 2008. — Т. 1. — С.16-19.

106. Едемский, В. А. Метод синтеза* двоичных последовательностей с квазиодноуровневой автокорреляцией и периодом шр / В.А Едемский, Вагунин И: С. // Журнал научных публикаций аспирантов и докторантов. 2008. - № 6. -С. 147-150:

107. Едемский, В.А. О программе синтеза двоичных последовательностей с периодом трИ В: А. Едемский, И. С. Вагунин // Труды международной научно-методической, конференции «Математика' в вузе». — СПб, 2008.- С.82-83.

108. Новгородский государственный университет».— № 2008614963; заявл. 28.10.08.; зарег. 11.01.09.I