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

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

ПОТЕХИН Егор Николаевич

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

05.13.17 - Теоретические основы информатики

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

2 ( 2014

005556087

Самара-2014

005556087

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

Научный руководитель:

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

Сметанин Юрий Геннадьевич, доктор физико-математических наук, федеральное государственное бюджетное учреждение «Российский фонд фундаментальных исследований», начальник отдела инфокоммуникационных технологий и вычислительных систем;

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

Ведущая организация:

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новгородский государственный университет имени Ярослава Мудрого», г. Великий Новгород.

Защита состоится «24» декабря 2014 года в 12:00 часов на заседании диссертационного совета Д 212.215.07, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке и на сайте федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», http://ssau.ru/resources/dis_protection/Potekhin/.

Автореферат разослан «18» ноября 2014 года

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

диссертационного совета Д 212.215.07

д.т.н., профессор

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

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

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

Проблема построения бинарных последовательностей, оптимальных по минимаксному критерию, зародилась в начале 1950-х годов. Однако, несмотря на большие усилия, приложенные такими исследователями как Paley, Singer, Golomb, Hall, Stanton, Sprott, Gordon, Mill, Welch, Berlekamp для развития теории построения оптимальных апериодических бинарных последовательностей, ее не удалось решить к середине 1970-х годов. Поэтому следующим этапом развития теории построения бинарных последовательностей были подходы, основанные на методе компьютерного поиска и дискретной оптимизации LABS проблемы (low autocorrelated binary sequences).

В 1975 году Линднер, используя метод полного перебора, нашел все оптимальные по минимаксному критерию бинарные последовательности до длины N < 40. В дальнейшем была предложена стратегия перехода от полного перебора к исчерпывающему бинарному поиску, что позволило найти в 1990 году бинарные оптимальные по минимаксному критерию (MPS) последовательности длин N<48 и в 2005 году длины N = 64.

На других длинах компьютерный поиск бинарных последовательностей проводился с использованием алгоритмов локального поиска, в результате чего в 2008 году были найдены бинарные последовательности с наименьшими известными на сегодняшний день значениями максимального бокового лепестка до длины N<105 и бинарных последовательностей с наибольшими значениями мерит-фактора (MF) до длины N<271. Однако, начиная с длин N>300, на сегодняшний день преимущество имеют аналитические алгоритмы построения.

При разработке новых методов построения бинарных последовательностей в период с 1970-х годов по настоящее время приняло участие огромное количество зарубежных, советских и российских ученых. Следует отметить значительный вклад в развитие теории построения и применения псевдослучайных последовательностей следующих ученых: Gold, Hufimann, Golay, Luke, Beth, Helleseth, Arasu, Viterbi, Baumert, Coxson, Russo, Cohen, Beth, Jungnickel, Kasami, Brenner, Carlet, Chan, Cheng, Dillon, Ding, Dreier, Smith, Frank, No, Kumar, Dobbertin, Pott, Klapper, Moreno, Tirckel, Gong, Gaal, Glynn, Xiang, Boztas, Mow, Maschietti, Segre, И.Н. Амиантов, B.K. Слока, М.И. Пелехатый, В.И. Винокуров, В.М. Сидельников, В.Е. Гантмахер, Ю.С. Лезин, Л.Е. Варакин, М.Б. Свердлик, P.M. Седлецкий, В.П. Ипатов,

Б.Ж. Камалетдинов, Э.М. Габидулин, Е.И. Кренгель, Н.Е. Быстров, Д.В. Чеботарев, В.А. Едемский, А.Н. Леухик и др.

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

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

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

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

3. Осуществить поиск всех оптимальных бинарных последовательностей в диапазоне длин N = [2;80].

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

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

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

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

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

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

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

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

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

5. Произведен поиск оптимальных минимаксных бинарных последовательностей в диапазоне длин ^ = [2; 80]. Впервые доказана оптимальность построенных бинарных последовательностей для длин N = {49,50,52..80}.

6. Получены экспериментальные законы распределения количества оптимальных минимаксных бинарных последовательностей в диапазоне длин ЛГ = [2;80].

7. Проведён анализ следующих свойств синтезированных бинарных минимаксных последовательностей:

• поиск последовательностей с минимальным значением максимального

уровня взаимнокорреляционных функций;

• ансамбли последовательностей;

• влияние частоты Доплера на апериодические автокорреляционные свойства

последовательностей;

• оценка линейной сложности синтезированных последовательностей;

• поиск балансных последовательностей;

• оценка значения коэффициента МГ синтезированных

последовательностей.

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

• разработан модифицированный алгоритм исчерпывающего поиска

бинарных оптимальных последовательностей;

• разработано программное обеспечение для распределенных вычислений для

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

• разработано программное обеспечение для обработки результатов

найденных последовательностей и вычисления их свойств;

• проведен анализ полного множества бинарных последовательностей с

позиций их взаимнокоелляционных характеристик, ансамблей

последовательностей, свойств периодической АКФ, линейной сложности,

функции неопределенности, распределения коэффициента МР и

балансности;

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

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

Разработанное в рамках диссертационной работы программное обеспечение компьютерного поиска минимаксных бинарных последовательностей может быть использовано при решении ЬАВБ-проблемы дискретной оптимизации.

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

1. Грант РФФИ 09-07-00072-а, «Теория синтеза ортогональных и квазиортогональных алфавитов сигналов на базе дискретных фазокодированных последовательностей», 2009-2011 (исполнитель).

2. Государственный контракт № П 783 в рамках ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», мероприятие 1.2.1 «Проведение научных исследований под руководством докторов наук» по теме «Разработка и реализация регулярных алгоритмов построения оптимальных по минимаксному критерию импульсных последовательностей», 2010-2012 (исполнитель).

3. Государственный контракт №8112р/12783 по теме «Разработка и изготовление программного обеспечения и модулей цифрового синтеза и цифровой обработки широкополосных фазокодированных сигналов и ансамблей на их основе для информационно-телекоммуникационных систем», 2010-2012 (исполнитель).

4. Договор №02.120.11.5418-МД по гранту Президента РФ для государственной поддержки молодых российских ученых МД-5418.2010.9, «Аналитическая теория синтеза фазокодированных последовательностей с одноуровневой импульсной автокорреляционной функцией», 2010-2011 (исполнитель).

5. Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы», мероприятие 1 «Проведение фундаментальных исследований в рамках тематических планов», по заданию Минобразования и науки РФ, тема «Развитие теории построения унимодулярных дельтакоррелированных последовательностей» НИР №1.01.11, 2011 (исполнитель).

6. Аналитическая ведомственная целевая программа «Развитие научного потенциала высшей школы», мероприятие 1 «Проведение фундаментальных исследований в рамках тематических планов», Минобразования и науки РФ

№1.07.2012 по заданию Минобразования и науки РФ, тема «Разработка и реализация метода построения многофазных последовательностей Баркера», 2012-2013 (исполнитель).

7. Грант РФФИ № 12-07-00552, «Теория синтеза многофазных последовательностей Баркера», 2012-2013.

8. НИОКР «Автосигнализация с GPS-трекингом, управляемая по GSM/GPRS/Bluetooth каналам», грант Фонда содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К», ГК 10508р/16915 от 08.06.2012 г., 2012-2013 (руководитель).

9. НИОКР «Разработка автосигнализации с бесключевым доступом, управляемой по беспроводным каналам сотовой связи», грант Фонда содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К.», ГК 12157р/20835 от 29.07.2013 г., 2013-2014 (руководитель).

Теоретические и практические результаты диссертационной работы внедрены в учебный процесс по специальности 090303 - «Информационная безопасность автоматизированных систем» (специалист) при изучении дисциплин «Сети и системы передачи информации», по специальности 090900 -«Информационная безопасность» (магистратура) при изучении дисциплины «Основы радиотехники», в курсовом и дипломном проектированиях, выполняемых студентами специальности 090303 - «Информационная безопасность автоматизированных систем» (подтверждено актом о внедрении).

Апробация работы. Результаты работы докладывались и обсуждались на 67-ой Всероссийской конференции с международным участием «Научная сессия, посвященная Дню Радио - RDC-2012» (Москва, 2012); на 68-ой Международной конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий RES-2013», на 14-ой, 15-ой и 16-ой Международных конференциях «Цифровая обработка сигналов и ее применение - DSPA-2012, DSPA-2013 и DSPA-2014» (Москва, 2012, 2013 и 2014); на Европейской неделе микроволн «European Microwave Week» (Нюрнберг, Германия, 2013); на 6-ой международной конференции «Распределенные вычисления и Грид-технологии в науке и образовании» (Дубна, 2014), на ежегодных научных конференциях по итогам НИР ПГТУ и научных семинарах кафедры Информационной безопасности (2011-2014).

Публикации. Всего по теме диссертации опубликовано 15 работ. Из них 4 статьи опубликованы в рецензируемых журналах, входящих в Scopus, 4 работы опубликованы в центральных рецензируемых научных журналах, рекомендованных перечнем ВАК, 5 работ опубликованы в сборниках трудов' (DSPA-2012, RDC-2012, DSPA-2013, RES-2013, DSPA-2014), засчитывающихся ВАК РФ при защите диссертации, 2 статьи - в других рецензируемых журналах, получено 2 свидетельства о государственной регистрации программы для ЭВМ.

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

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

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

• Полные множества бинарных, оптимальных по минимаксному критерию последовательностей длин N = [2;80];

• Результаты анализа полного множества бинарных последовательностей с позиций их взаимнокорреляционных характеристик, формирования ансамблей последовательностей, свойств периодической АКФ, функции неопределенности, линейной сложности, распределения коэффициента MF и балансности.

Структура и объем работы. Диссертация состоит из Введения, 4 глав, Заключения и Приложений, содержит 20 рисунков и 16 таблиц. Список литературы включает 121 наименование.

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

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

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

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

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

• определению критериев оптимальности последовательностей по апериодической корреляционной функции: минимаксный (1-2) и мерит фактор (3):

М{А)=тМА\ (1)

О<г<ЬГ

PSL = mmM{A), (2)

А

MF(A)=-; (3)

2 ZfcMl1

r=I

• существующим алгоритмам глобального и локального поиска последовательностей;

• классификации известных разностных, почти разностных и неоптимальных разностных множеств для 4 возможных случаев (4), которые позволяют синтезировать близкие к оптимальным бинарные последовательности:

N = 0 (тос!4) Лг = 1(то<14)

* (4)

ЛГ = 2(то<14)'

N = 3 (тос! 4)

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

Во второй главе диссертации приводится подробное описание алгоритма исчерпывающего поиска бинарных оптимальных последовательностей в элементах теории графов. Описываются разработанные алгоритмические методы модификации исчерпывающего поиска бинарных оптимальных последовательностей. Произведена оптимизация вычисления боковых лепестков ААКФ (5):

г, = "ТМп' ип+г, г = 0,1,...Л-1 • (5)

л=0

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

^тш'

Однако особенностью алгоритма исчерпывающего поиска является тот факт, что биты искомой последовательности формируются парами, начиная с краев, где номера бит связаны с ярусом дерева (6):

Ь (6)

N

где т = 1,2,...,— - текущии ярус дерева.

Вследствие этого, рассчет боковых лепестков выполняется в порядке (7):

N

т = N-1,ЛГ-2,...,—+ 1, N-четное,

N ' (7)

т = N-Х.Ы-2,...,— + 2 N-нечетное.

2

а затем происходит смена направления вычисления боковых лепестков ААКФ в порядке (8):

N

г = 0,1,...,—, N -четное,

N <8)

г = 0,1,...,— + 1, N — нечетное.

В случае такого подхода к вычислению корреляции выигрыш в скорости может достигать 18% (рисунок 1). Также вычислительное ускорение обеспечивается применением современных аппаратных функций подсчета бит

рорсШО Для вычисления корреляции через операцию ХОЯ. Кроме этого, для оптимизации процесса поиска были разработаны следующие модификации:

• последующий отказ от вычисления значений ААКФ путем вычисления их через табилцу весов;

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

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

(I, если (п-2к< РБП) и (гг + гм_т е X),

Мк

[О, в противном случае^

Х = {х\А(х)}, (9)

Ах, ЛГ(тос14) = 0, х = -Р8ЦЛ\у2),...,Р8Ц$ы2),

Ах + \, Л/"(тос14) а 1, х = (-2Р5Х-1)(61у4),...,(2Р£/,-1)(сКу4),

Ах + 2, АЧтосМ) = 2,х = (-2 РБЬ - 2)((Иу А),...,{2Р8Ь - 2)(сИу 4),

Ах + 3, И(тойА) = 3,х = (-2Р51 - 3)(сИу А),...,(2Р5Ь - 3)(сНу 4).

А(х) = \

• оптимизация вычисления реверсной функции с использованием разположенной в памяти таблицы поиска, позволяющей за 4 обращения к памяти, 4 логических операции ИЛИ и 3 логических сдвига получить искомое значение;

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

• адаптация алгоритма для осуществления поиска на графических процессорах, поддерживающих технологию NVidia CUDA;

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

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

Рисунок 1. Выигрыш при изменении направления вычисления боковых

лепестков

&—третьей главе диссертации проводится анализ эффективности найденных последовательностей. Исследуется степень взаимного влияния последовательностей друг на друга по критерию их апериодической взаимно-корреляционной функции (10):

N-1-

г* = X ап®Ьп+Т,т = \,2,...Л-\,

(10)

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

Исследуется влияние частоты Доплера на бинарные оптимальные последовательности путем анализа поверхности функции неопределенности (11), производится сравнение их с М-последовательностями, где заключается, что найденные MPS последовательности, как и М-последовательности, можно считать устойчивыми к изменениям, связанным с влиянием эффекта Доплера

. (. л . Л Хт,ф= L *WexP — -ф-п , (11)

и=0 V Г )

r = -N+1,..„-1,0,1,...^-1, ф=-Г,..„-1,0,1, Анализируются периодические свойства найденных последовательностей, что позволяет сделать вывод о том, что на основе разностных и почти разностных множеств можно построить оптимальные последовательности лишь в узком диапазоне длин.

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

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

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

Таблица 1. Сложность модифицированного алгоритма исчерпывающего _поиска бинарных оптимальных последовательностей

Уровень РБЬ РБЬ = 2 Р8Ь = 3 РБЬ = 4 Р5Ь = 5

Линейная сложность 0(20.7-1.42") 0(18.3-1.57*) 0(9.91.7К) 0(6.9-1.79*)

различных уровней

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

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

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

• эффективность использования процессорного времени;

• сбор и анализ результатов.

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

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

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

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

Разработано дополнительно программное обеспечение, позволяющее:

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

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

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

• удалить эквивалентные последовательности;

• проверить уровень ААКФ;

• построить последовательности в нормализованном виде;

• построить полное множество последовательностей с учетом эквивалентных решений;

• построить таблицу АВКФ;

• найти ансамбли последовательностей по АВКФ с заданным максимальным уровнем;

• построить таблицу ПАКФ;

• получить значения мерит фактора и линейной сложности.

В приложении к диссертации приводятся:

• примеры оптимальных минимаксных бинарных последовательностей для длин ЛГ = [2;105];

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

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

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

ЗАКЛЮЧЕНИЕ

Основными результатами диссертационного исследования являются:

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

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

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

4. Полное множество существующих бинарных, оптимальных по минимаксному критерию бинарных последовательностей для диапазона длин N = [2;80].

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

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

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

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

в рецензируемых журналах, входящих в Scopus:

1. Potekhin, E.N. Optimal peak sidelobe level sequences up to length 74 / A.N. Leukhin, E.N. Potekhin // IEEE Proceedings of the 10th European Radar Conference, EuRAD'2013, Nuremberg, Germany, pp.495-498.

2. Potekhin, E.N. Optimal peak sidelobe level sequences up to length 74 / A.N. Leukhin, E.N. Potekhin // IEEE Proceedings of the 10th European Microwave Conference, EuMC'2013, Nuremberg, Germany, pp. 1807-1810.

3. Potekhin, E.N. A Bernasconi model for constructing ground-state spin systems / A.N. Leukhin, A.S. Shuvalov, E.N. Potekhin // Bulletin of the Russian Academy of Sciences: Physics, March 2014, Vol. 78, Issue 3, pp.207-209.

4. E.N.Potekhin. Exhaustive Search for Optimal Minimum Peak Sidelobe Binary Sequences up To Length 80 / A.N. Leukhin, E.N. Potekhin//Sequence and Their Applications-SETA2014, Proc. of 8th Internatinal Conference Melburn, Australia, November 20-24, 2014, Lecture Notes in Computer Science, Springer.

в центральных научных журналах, входящих в перечень ВАК:

5. Потехин, E.H. Оптимальные импульсные последовательности / А.Н. Леухин, A.C. Шувалов, E.H. Потехин, A.B. Харитонов // Вестник Марийского государственного технического университета. Серия "Радиотехнические и инфокоммуникационные системы". - 2012. - №1. - С. 37-46.

6. Потехин, E.H. Методы построения бифазных и четырехфазных унимодулярных периодических последовательностей с иррациональными фазами / E.H. Потехин, А.Н. Леухин // Цифровая обработка сигналов. Рубрика "Первые шаги в науке". - 2012. - №4. - С. 44-48.

7. Потехин, E.H. Методы и результаты синтеза апериодических бинарных последовательностей и многофазных последовательностей Баркера / E.H. Потехин, A.C. Шувалов, А.Н. Леухин // Цифровая обработка сигналов.-2013.-№4.-С. 45-54.

8. Потехин, E.H. Модель Бернаскони для построения низкоэнергетических спиновых систем / А.Н. Леухин, A.C. Шувалов, E.H. Потехин // Известия РАН. Серия «Физическая». -2014. -№3(78). - С. 316-318.

в центральных научных сборников трудов, рекомендованных ВАК при защите

диссертации:

9. Потехин, E.H. Новые бифазные унимодулярные последовательности на основе циклических оптимальных бинарных последовательностей с двухуровневой автокорреляционной функцией / E.H. Потехин, A.B. Харитонов, А.Н. Леухин // Доклады 14-ой Международной конференции «Цифровая обработка сигналов и ее применение - DSPA-2012».-Том 1.-М., 2012,-С. 30-33.

10. Потехин, E.H. Периодические четырехфазные последовательности с идеальными корреляционными характеристиками на основе четвертичных

оптимальных последовательностей / E.H. Потехин, А.Н. Леухин // Доклады 67-ой Всероссийской конференции с международным участием «Научная сессия, посвященная Дню Радио - RCD-2012». -М., 2012. -С. 155-157.

11. Потехин, E.H. Синтез бинарных оптимальных по минимаксному критерию последовательностей до длин N=70 / E.H. Потехин, В.О. Виноградов, А.Н. Леухин // Доклады 15-ой международной конференции «Цифровая обработка сигналов и ее применение - DSPA-2013». — М., 2013. - С. 33-37.

12. Потехин, E.H. Синтез фазоманипулированных последовательностей с идеальной периодической автокорреляционной функцией и малым числом фаз / Н.В. Парсаев, А.Н. Леухин, A.C. Шувалов, E.H. Потехин // Доклады 68-ой международной конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий - RES-2013, посвященная дню Радио». - М., 2013. - С. 370-374.

13. Потехин, E.H. Модификация алгоритма «ветвей и границ» для исчерпывающего поиска бинарных оптимальных последовательностей / E.H. Потехин, А.Н. Леухин // Доклады 16-ой международной конференции «Цифровая обработка сигналов и ее применение — DSPA-2014» . — М., 2014. - С. 64-66.

в других рецензируемых изданиях:

14. Potekhin, E.N. Binary Sequences with Minimum Peak Sidelobe Level up to Length 68/ A.N. Leukhin, E.N. Potekhin // arxiv.org on-line avalible

15. Потехин, E.H. Методы оптимизации задачи полного поиска бинарных апериодических оптимальных последовательностей / E.H. Потехин, А.Н. Леухин // Программные системы и вычислительные методы. - М.: Nota Bene, 2013.-№2.-С. 192-198.

свидетельства о государственной регистраиии:

16. Свидетельство о государственной регистрации программы для ЭВМ №2011610941 «Like-noise signais» / А.Н. Леухин, A.C. Шувалов, A.C. Петухов, E.H. Потехин, A.B. Харитонов.

17. Свидетельство о государственной регистрации программы для ЭВМ №2014616441 «Модуль планировщика задач распределенной вычислительной сети MarGrid v.l.0.0» / А.Н. Леухин, A.C. Шувалов, E.H. Потехин, В.И. Безродный, Н.В. Парсаев.

Подписано в печать 23.10.2014. Формат 60x84 1/16. Печатных листов 1,0. Тираж 100 экз. Заказ 5466 Поволжский государственный технологический университет, 424000, Йошкар-Ола, пл. Ленина, 3

Редакционно-издательский центр Поволжского государственного технологического университета, 424006, Йошкар-Ола, ул. Панфилова, 17