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

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

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

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

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

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

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

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

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

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

(1)

Здесь

- простое число; - натуральные числа; - класс степенных вычетов с номером

,

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

.

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

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

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

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

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

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

, (2)

,

- спектр разности классов степенных вычетов и , . Соотношение (2) обобщается на ПВКФ пары ДКП.

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

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

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

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

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

Решение первой задачи главы рассмотрено в подразделе 2.2. Обозначим через , циклотомические числа порядка .

Теорема 1. СРКВ связан с циклотомическими числами соотношением:

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

- , если , , ;

- , если , , ;

- , если , , ;

- , если , , ;

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

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

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

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

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

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

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

Обозначим упорядоченные по возрастанию уровни БЛ ПАКФ ДП, а рельеф ПАКФ ДП -

.

Пусть - разность между наибольшим и наименьшим значениями БЛ ПАКФ ДП, а

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

Теорема 2. Если ДП сформирована по ПК (1) при и , то

, .

Следствие 2.1. ДП с периодом

и весом для имеет двухуровневую ПАКФ

Это известный результат [4].

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

выполняется для ДП с периодом p:

, .

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

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

где

,

относительно ПК (1) при , и пик-фактор .

Следствие 3.1. ДП с периодом

,

весом имеет трехуровневую ПАКФ

с

, ,

и пик-фактор относительно ПК (1) для , .

Следствие 3.2. ДП с периодом и весом имеет трехуровневую ПАКФ

с

, ,

и пик-фактор относительно ПК (1) для , .

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

относительно ПК (1) для , и пик-фактор .

Следствие 4.1. ДП с периодом

или

и весом имеет четырехуровневую ПАКФ

с

,

и пик-фактор относительно ПК (1), .

Следствие 4.2. ДП с периодом

и весом имеет ПАКФ

,

пик-фактор относительно ПК (1) для , .

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

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

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

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

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

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

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

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

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

Теорема 5. ДП , сформированная по ПК (1) для с периодом

,

имеет двухуровневую (одноуровневую при ) ПАКФ

с ,

и пик-фактор . Здесь u, g - целые числа.

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

Теорема 6. Для нечетного значения ДП с периодом

и весом при

и

обладает ПАКФ

,

и ,

относительно ПК (1) при и пик-фактор .

Теорема 7. Для нечетного ДП с периодом

,

весом при

и

имеет ПАКФ

с

, ,

относительно ПК (1) при и пик-фактор .

Если

,

то в теореме 7 необходимо заменить на .

Теорема 8. ДП с периодом

, и ,

сформированная по ПК (1) при имеет ПАКФ

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

Частные случаи теоремы 8 () - известны [2,4].

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

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

,

и двумя уровнями БЛ ПАКФ (РМ, сбалансированных на два уровня, имеющих свой круг применений). Известные ДП, обладающие такими же свойствами, являются частными случаями синтезированных (теоремы 5,8).

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

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

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

Теорема 9. Если пара ДП и сформирована по ПК (1) при , , то

,

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

Следствие 9.1. Пара ДП и , сформированных по ПК (1) при имеет одноуровневую ПВКФ тогда и только тогда, когда

,

где - целое число и . В этом случае

, .

Теорема 10. Пара ДП и , сформированных по ПК (1) при , имеет одноуровневую ПВКФ тогда и только тогда, когда

и .

При выполнении условий теоремы

, .

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

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

для , рассчитать параметры ДП с квазиодноуровневой ПВКФ.

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

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

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

,

.

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

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

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

1. ; ,

если .

2. ;

, ,

если .

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

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

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

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

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

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

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

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

Теорема 13. ТП с периодом

,

сформированная по ПК (1) при , имеет двухуровневую ПАКФ

и пик-фактор .

ДП, соответствующая нулевым символам ТП, имеет двухуровневую ПАКФ:

, .

Здесь - целые числа.

Теорема 14. ТП с периодом

,

сформированная по ПК (1) при , имеет двухуровневую ПАКФ

и пик-фактор .

ПАКФ ДП:

([2]).

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

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

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

,

обладают квазиидеальной ПАКФ, то

.

Теорема 16. Если ТП , сформированные по ПК (1) при с периодом

,

обладают квазиидеальной ПАКФ, то

.

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

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

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

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

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

Теорема 17. Если БП сформирована по ПК (1) при и , , то

, ,

Следствие 17.1. Если - фиксировано, то в условиях теоремы 17 с ростом параметр убывает пропорционально . С увеличением ПАКФ БП стремится к идеальной.

Следствие 17.2. БП с периодом

для , имеет двухуровневую ПАКФ

Это известный результат [4].

Пусть .

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

,

относительно ПК (1) для ,, .

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

,

относительно ПК (1) для ,, .

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

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

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

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

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

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

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

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

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

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