Статья: Экспериментальная оценка границ применимости гипотезы о блоках

Экспериментальная оценка границ применимости гипотезы о блоках

А.В. Борисенков, Д. В. Суханов

Аннотация

В докладе приводятся сведения о новом алгоритме синтеза минимаксных последовательностей с наименьшим максимальным боковым выбросом апериодической АКФ. Приведена эмпирическая оценка основных параметров алгоритма. алгоритм синтез блок код

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

The datas about a new algorithm for synthesis of sequences with minimal maximal sidelobe of an aperiodic autocorrelation function was shown in this paper. The empirical estimation of essential parameters of the algorithm is got.

Keywords: minimax sequences; hypothesis about the blocks; quantity of ones; partitioning to natural addendum; relief of correlation function; sidelobe level.

Введение

В радиолокации для зондирующих сигналов, а также в системах связи и телеметрии для синхросигналов, - нашли широкое применение сигналы, созданные на основе кодовых последовательностей, обладающих псевдошумовыми свойствами. В работах [1ч5] представлены некоторые методики поиска таких последовательностей (кодов) и полученные результаты. Проблему, казалось бы, решает полный перебор по всем последовательностям заданной длины. Однако, несмотря на прогресс в характеристиках вычислительной техники, достигнутый к настоящему времени, при экспоненциальном возрастании времени вычисления для больших длин (от 64-х и выше) остаётся актуальной проблема поиска не только глобально оптимальных кодов, но и кодов с локально минимальным уровнем максимального бокового лепестка апериодической АКФ (ААКФ). Современные методы поиска таких кодов используют известное соотношение между максимумами ААКФ и периодических АКФ (ПАКФ) [1, 4] и содержат 2 этапа, на 1-м из которых строятся для заданной длины коды с «хорошими» ПАКФ. На 2-м этапе поиска из полученного множества отбираются коды, обладающие минимальным максимумом бокового лепестка ААКФ (минимаксные последовательности). Традиционные подходы для поиска кодов на 1-м этапе методики основываются, например, на свойствах разностных множеств, сбалансированных на уровней [6].

1. Идея предлагаемого алгоритма

На начальном этапе исследования полным перебором найдены все минимаксные последовательности вплоть до . Начиная с , перебор становится затруднительным, в связи с чем возникает задача его сократить. Для этого предлагается использовать необходимые условия существования кодов с уровневыми ПАКФ [1], а также гипотезу о количестве блоков в «хороших» последовательностях [7]. Гипотеза заключается в том, что количество блоков в «хорошей» последовательности (количество блоков с одинаковыми символами подряд) связано с длиной последовательности соотношением . В таблице 1 приводятся сведения о количестве блоков в наиболее известных рекордных последовательностях.

Таблица 1. Гипотеза о блоках

В работах [8, 9] приведён алгоритм, в котором число блоков перебирается в пределах от до . Кроме того, в цикле перебирается число единиц в последовательности . Далее , а также число минус единиц в последовательности представляется в виде суммы натуральных слагаемых в количествах и соответственно, из условий . Для этого используется алгоритм посещения всех разбиений целого числа на сумму заданного числа натуральных слагаемых из [12].

2. Полученные результаты

Так как пока что остаётся открытым вопрос о существовании кода длины с (или, возможно, даже с ), то сосредоточим основное внимание на последовательностях с . В таблице 2 приведены основные свойства найденных перебором рекордных последовательностей.

Таблица 2. Результаты экспериментальной проверки гипотезы о блоках

Заключение

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

Литература

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

2. Алышев Ю. В., Борисенков А. В. Псевдослучайные последовательности с корреляционной функцией почти игольчатой формы // «Информатика, радиотехника, связь». Сборник трудов учёных Поволжья (Материалы НТК ПГАТИ), Самара, 2001, №6.

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

4. Ипатов В. П. Широкополосные системы и кодовое разделение сигналов. Принципы и приложения. М.: Техносфера, 2007. - 488 с.

5. Гантмахер В. Е., Кравцов С. Ю. Анализ и синтез двоичных последовательностей, сформированных на основе одного класса биквадратичных вычетов по простому модулю // Сборник докладов 18-й МНТК «Радиолокация, навигация и связь», Воронеж, 2012, Т. 1. - С. 46-53.

6. Холл М. Комбинаторика. М.: Мир, 1970. - 424 с.

7. Варакин Л. Е. Теория систем сигналов. М.: «Сов. радио», 1978. - 304 с.

8. Суханов Д. В. О последовательностях с хорошими апериодическими корреляционными свойствами. // Материалы XXV Российской НТК профессорско-преподавательского состава, научных сотрудников и аспирантов ПГУТИ, Самара, 2018. - С. 12.

9. Борисенков А. В., Суханов Д. В. Новый алгоритм поиска двоичных последовательностей с хорошими корреляционными свойствами // Материалы XVI МНТК «Физика и технические приложения волновых процессов-2018», Миасс, 10-14 сентября 2018. - С. 23-24.

10. Cohen, M., Fox, M. R., and Baden, J. M. «Minimum peak sidelobe compression codes», in Proceedings of the IEEE International Radar Conference, 7-10 May 1990, Arlington, VA, IEEE, 1990. - 633-639 p.

11. Deng, X., and Fan, P. «New binary sequences with good aperiodic autocorrelation obtained by evolutionary algorithm», IEEE Commun. Lett., Vol, 3, 1999. - 288-290 p.

12. Кнут, Д. Э. Искусство программирования, том 4, А. Комбинаторные алгоритмы, часть 1. Пер. с англ. М.: ООО «И.Д. Вильямс», 2013. - 960 с.