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

• Автор: Потехин, Егор Николаевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Йошкар-Ола
• Количество страниц: 184 с. : ил.

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

ААКФ - апериодическая автокорреляционная функция АВКФ - апериодическая взаимно-корреляционная функция АКФ - автокорреляционная функция

ПАКФ - периодическая взаимно-корреляционная функция

ЭПР - эффективная площадь рассеяния

ВВ - brunch and bound

LABS - low autocorrelated binary sequences

MF - merit factor

PSL - peak sidelobe level

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

1Л. Основные определения
1.2. Классификация бинарных последовательностей по виду периодической автокорреляционной функции
1.3 Классификация бинарных последовательностей по виду апериодической автокорреляционной функции
1.3.1. Граничные оценки для значения максимального уровня боковых лепестков случайных бинарных последовательностей
1.3.2. Граничные оценки для значения максимального уровня боковых лепестков некоторых регулярных бинарных последовательностей
1.3.3. Теоретическая оценка для минимального значения максимального уровня боковых лепестков бинарных последовательностей
1.3.4. Алгоритмы глобального поиска
1.3.5. Алгоритмы локального поиска
1.3.6. Оптимальные минимаксные бинарные последовательности
1.3.7. Оптимальные по критерию минимума энергии боковых лепестков бинарные последовательности
1.4. Конструкции известных разностных множеств
1.4.1. Случай 7V = 0 (mod 4)
1.4.2. Случай N = 1 (mod 4)
1.4.3. Случай N = 2 (mod 4)
1.4.4. Случай N s 3 (mod 4)
1.5. Конструкции известных почти разностных множеств

1.5.1. Случай TV s 0 (mod 4)
1.5.2. Случай TV = 1 (mod 4)
1.5.4. Случай N = 3 (mod 4)
1.6. He оптимальные конструкции почти разностных множеств
1.6.1. Конструкция Ding для циклотомических классов четвертого
порядка
1.6.2. Конструкция Ding, Helleseth, Lam циклотомических классов
четвертого порядка
1.6.3. Конструкция Ding для циклотомических классов восьмого порядка
1.7. Другие способы построения почти разностных множеств
1.7.1. Первый метод конструкции Davis
1.7.2. Второй метод конструкции Davis
1.7.3. Конструкция, основанная на совершенных нелинейных функциях
1.7.4. Конструкция, основанная на вычитании одного элемента из
разностного множества
1.7.5. Конструкция, основанная на добавлении одного элемента к
разностному множеству
1.8. Бинарные последовательности с тремя уровнями боковых лепестков ПАКФ
1.8.1. Конструкция Yu, Gong с использованием М-последовательности
1.8.2. Конструкция Tang, Gong на основе GMW-последовательностей .
1.8.3. Конструкция Tang, Gong на основе последовательностей Якоби .
1.8.4. Конструкция Tang, Gong на основе последовательностей Лежандра

известные локальные алгоритмы, с помощью которых осуществлялся поиск наилучших по значению MF бинарных последовательностей:
1998 - Militzer с соавторами [51] разработали эволюционный алгоритм (ЕА) с вычислительной сложностью “лучше, чем алгоритм ветвей и границ
2001 - Prestwich [52] разработал constrained local search (CLS) алгоритм с вычислительной сложностью o(l.68w);
2007 - Prestwich [53] разработал local search relaxation (LSR) алгоритм с вычислительной сложностью 0(1.51^);
2003 - Brglez [54] с соавторами разработали алгоритм Kernighan-Lin solver (KLS) o(l.46'v) и алгоритм с эволюционной стратегией (ES), основанный на эволюционном алгоритме с вычислительной сложностью 0(1.4^);
2005 - [55] с соавторами разработали алгоритм direct stochastic search (DSC) с вычислительной сложностью O^l.S^);
2006 - Dotu и van Henteryck [56] разработали tabu search (TS) алгоритм с вычислительной сложностью o(l .
2007 - Gallarado с соавторами [57] разработали memetic алгоритм (МА) с вычислительной сложностью o(l.32 w).
Кроме перечисленных алгоритмов локального поиска следует также отметить генетические алгоритмы [58], оптимизации колоний [59], симуляционные [60], итеративного локального поиска [61], scatter search [62] и переменного соседнего поиска [63].
При определенной модификации перечисленные алгоритмы могут также использоваться для поиска бинарных последовательностей с наименьшим значением максимального бокового лепестка.
1.3.6. Оптимальные минимаксные бинарные последовательности
В 1953 году в работе [2] Баркер синтезировал оптимальные бинарные последовательности с PSL = 1 для длин 7V = 2,3,4,5,7,11,13, а в 1968 году Турин в