Электронный научный журнал
Международный студенческий научный вестник
ISSN 2409-529X

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

Поправко Е.Д. 1 Марущенко С.Г. 1
1 ФГБОУ ВПО Комсомольский-на-Амуре государственный технический университет
Наиболее важной характеристикой дискретной последовательности является ее автокорреляционная функция (АКФ). В практических приложениях АКФ дискретного сигнала должна иметь максимальный центральный пик и минимальный уровень боковых лепестков. В данной статье рассмотрен алгоритм получения последовательностей с хорошими автокорреляционными свойствами из последовательностей Лежандра. Бинарные последовательности Лежандра формируются на основе двузначного характера и имеют хорошую периодическую АКФ. Также представлена рабочая программа, выполненная с использованием комплекса LabVIEW, с помощью которой можно осуществлять поиск и синтезировать последовательности с минимальным боковым лепестком АКФ. Данная программа предназначена для использования в учебном процессе. С помощью данной программы студенты изучают принцип формирования уникальных дискретных последовательностей и исследуют их корреляционные характеристики.
дискретная последовательность
автокорреляционная функция
последовательность Лежандра
среда графического программирования LabVIEW
алгоритм
программа.
1. Бинарные последовательности с оптимальными периодическими автокорреляционными свойствами. [Электронный ресурс] - Режим доступа: http://www.studfiles.ru/preview/1649303/ (дата обращения: 30.11.14)
2. Бронов С.А., Малеев А.В., Михайленко Я.В. Синтез уникальных фазоманипулированных сигналов для интеллектуальной системы обнаружения подвижных объектов [Электронный ресурс] / Журнал научных публикаций аспирантов и докторантов - Режим доступа: http://jurnal.org/articles/2008/izmer9.html (дата обращения: 17.12.14)
3. Информационный сайт [Электронный ресурс] / Стандарт беспроводной связи IEEE 802.11 - Режим доступа: http://compress.ru/article.aspx?id=17782 , свободный. Загл. с экрана. Яз. рус., англ. (дата обращения: 15.02.15)
4. Поправко Е.Д., Марущенко С.Г. Симулятор для изучения корреляционных свойств дискретных сигналов. Свидетельство о государственной регистрации программы для ЭВМ № 2015612832, 26 февраля 2015г.
5. Mossinghoff M.J. Wieferich pairs and Barker sequences // Designs, Codes and Cryptography, 53, No. 3, 2009, pp.149-163.
6. Storer J.E., Turyn R. Optimum finite code groups// roceedings IRE (Correspondence), 1958, V. 46, pp.1649.

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

Хорошо известно, что наилучшими корреляционными характеристиками обладают сигналы Баркера. [6] Однако, у них есть один недостаток: они имеют малую длину последовательности. В настоящее время максимальная длина последовательности Баркера составляет тринадцать символов. Хорошо известно практическое применение сигнала Баркера длиной одиннадцать символов, в телекоммуникационных системах стандарта WiFi.[3]

На данный момент доказано, что не существует сигналов Баркера с числом позиций в диапазоне 13< N ≤ 2×1030. [5] Однако, потребность в сигналах с хорошими корреляционными свойствами остается насущной, так как такие сигналы хорошо зарекомендовали себя в системах обнаружения.

Кодовые последовательности могут характеризоваться как периодической, так и апериодической АКФ. Необходимым условием «хорошей» апериодической АКФ является периодическая АКФ,  имеющая максимальный центральный лепесток и малые боковые лепестки.

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

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

Конечным полем (полем Галуа) называют конечное множество элементов, на котором определены две операции, именуемые сложением и умножением и обозначаемые привычными символами «+» и «×». В любом поле обязательно присутствуют нулевой «0» и единичный «1» элементы, которые оставляют любой элемент поля неизменным в операциях сложения и умножения соответственно. Таблицы сложения и умножения в поле строятся таким образом, чтобы указанные операции были коммутативны, ассоциативны, дистрибутивны и обратимы. Последнее означает, что определены также операции вычитания и деления на ненулевой элемент. Аналогично арифметике по модулю два можно использовать правила сложения и умножения по модулю числа p, удерживая после обычных операций сложения и умножения целых чисел только остаток от деления результата на целое p. Если p является простым числом, то эти операции порождают конечное поле GF(p) порядка p (т.е. содержит p элементов), называемое простым полем. Специфический элемент ξ поля GF(p), степени которого пробегают все ненулевые элементы поля GF(p) называется примитивным. Поскольку любой ненулевой элемент α поля GF(p) есть некоторая степень примитивного элемента ξ, то вполне естественно назвать показатель этой степени логарифмом элемента α по основанию ξ:

.

Двузначным характером (символом Лежандра) ψ(a) ненулевого элемента a поля GF(p) называется функция, принимающая значения +1 и -1 в зависимости от четности или нечетности логарифма элемента a:

Длина последовательности Лежандра принадлежит множеству вида , где t - целое число.

Алгоритм поиска последовательности с хорошей апериодической АКФ заключается в следующем:

1) Для длины N, которую требуется найти, отбирается множество последовательностей, имеющих хорошие периодические АКФ. Примем их число равным M.

2) Далее осуществляется полный перебор c поиском минимума максимального бокового лепестка апериодической АКФ среди всех однопериодных сегментов последовательностей-кандидатов. Всего необходимо произвести тестовых проверок.

3) Итогом поиска является один или несколько сегментов одной или нескольких последовательностей, имеющий минимальное значение бокового лепестка p(a)max, среди всех последовательностей, отобранных на первом этапе.

Рассмотрим подробнее на примере. Найдем последовательность  длиной в 23 позиции. Длина N=23 принадлежит множеству вида . В поле GF(23) элемент ξ=5 является примитивным, так как его возведение в степень 0, 1,2,..., 21 генерирует все различные ненулевые элементы GF(23): 50=1,51=5,52=2, 53=10, 54=4, 55=20, 56=8, 57=17, 58=16, 59=11, 510=9, 511=22, 512=18, 513=21, 514=13, 515=19, 516=3, 517=15, 518=6, 519=7, 520=12, 521=14. Из этого ряда видно, что логарифмы элементов 1, 2, 3, 4, 6, 8, 9, 13, 13, 16, 18 четны, а элементов 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 и 22 - нечетны. Расстановка символов +1 на позициях i =0, 1, 2, 3, 4, 6, 8, 9, 13, 13, 16, 18 и -1 на позициях i = 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 дает последовательность Лежандра:

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

В данной работе, с использованием среды разработки приложений LabVIEW была разработана программа, с помощью которой можно осуществлять поиск и синтезировать последовательности с минимальным боковым лепестком АКФ, основываясь на приведенном выше алгоритме [4]. LabVIEW (Laboratory Virtual Instrumentation Engineering Workbench) – это среда разработки и платформа для выполнения программ, созданных на графическом языке программирования «G» фирмы National Instruments.

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

Всю программу можно условно разделить на три части: «1» - установка начальных значений и перебор степени, «2» - составление числовой последовательности, «3» - поиск АКФ и сдвиг числовой последовательности.

Рис.1.- Графическая реализация алгоритма программы

В блоке «1» задаются начальные условия поиска последовательности. Блок «2» вычисляет последовательность чисел, и проверяет правильная ли она. На вход подается основание и текущая степень, на выходе получаем составленную последовательность. Если последовательность правильная, блок «3» вычисляет АКФ последовательности. Если последовательность не правильная, то подается сигнал «True» об окончании вычислений элементов последовательности, с переходом к поиску элементов следующей последовательности для заданного основания.

На рисунке 2 представлено рабочее окно программы и интерфейс пользователя. В рабочем окне присутствует поле графиков «1», на котором отображаются АКФ найденной последовательности и АКФ сдвинутой последовательности. Также имеется окно «сдвиг» - «2» и шкала «сдвиг» - «3». В окне «сдвиг» отображается число позиций, на которое необходимо передвинуть ползунок на шкале, чтобы увидеть АКФ с минимальным боковым лепестком. Передвижение ползунка осуществляется вручную, чтобы можно было наглядно посмотреть, как меняется последовательность с каждым сдвигом. К тому же присутствуют две шкалы с найденной последовательностью. На шкале «4» представлена числовая последовательность, полученная при вычислении конечного поля, а шкала «5» это полученная последовательность Лежандра. В окнах «6» и «7» вручную задаются примитивный элемент и степень, которая является эквивалентом длины последовательности. Окна «8», «9», «10» являются информационными, в них можно посмотреть длину полученной последовательности, сдвиг, который необходимо сделать, чтобы получить последовательность с наилучшей АКФ и значение максимального бокового лепестка АКФ такой последовательности.

Рис.2. – Интерфейс пользователя

На рисунке 2 представлен пример работы программы. Найдена последовательность длиной в двадцать три позиции. На графике присутствует исходная АКФ «а» и АКФ последовательности, сдвинутой на шесть позиций «б». Наглядно видно, что уровень боковых лепестков сдвинутой АКФ ниже, чем у исходной. С помощью ползунка на шкале «Сдвиг» можно просмотреть последовательности, полученные при другом сдвиге. При нажатии на кнопку «Поиск» программа находит другую последовательность и считает ее АКФ.

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


Библиографическая ссылка

Поправко Е.Д., Марущенко С.Г. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПОИСКА КОДОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ЗАДАННЫМИ КОРРЕЛЯЦИОННЫМИ СВОЙСТВАМИ // Международный студенческий научный вестник. – 2015. – № 1.;
URL: https://eduherald.ru/ru/article/view?id=12235 (дата обращения: 25.07.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074