Статья: Метод вычисления периодической автокорреляционной функции бинарной последовательности основанный на алгоритме факторизации многочленов в gf(2)

Метод вычисления периодической автокорреляционной функции бинарной последовательности основанный на алгоритме факторизации многочленов в gf(2)

В.И. Безродный, А.Н. Леухин

Аннотация

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

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

Sequences with good structure properties, such as sidelobes of periodic and aperiodic autocorrelation and cross correlation functions are used in radar, communications and measurements. The algorithm for calculating periodic autocorrelation function of a binary sequence, based on using pre-calculated tables of shifts and weights of the sequence.

Keywords: periodic autocorrelation function; polynomial factorization; finite field. бинарная последовательность автокорреляционный

Введение

Проблема построения бинарных последовательностей оптимальных по минимаксному критерию зародилась в начале 1950-х годов. В 1953 году Вудворд в работе [1] показал, что качество работы РЛС целиком определяется формой излучаемого сигнала. При этом для достижения наилучших характеристик излучаемый сигнал, должен иметь наименьший уровень боковых лепестков корреляционной функции неопределенности в плоскости частота Доплера - время задержки. С позиций обеспечения минимального значения уровня боковых лепестков используют два критерия: - минимаксный критерий (minimum peak sidelobe), при котором уровень максимального бокового лепестка (peak sidelobe) должен быть минимальным; - критерий (merit factor), при котором отношение энергии основного лепестка к энергии всех боковых лепестков должно быть максимальным.

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

(1)

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

, (2)

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

(3)

где

(4)

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

Обозначим количество 1 в двоичной последовательности через . Для двоичной последовательности аналогично с выражением (2) определим ПАКФ в виде:

(5)

Тогда ПАКФ бинарной последовательности можно записать в виде

(6)

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

ПАКФ обладает свойством симметрии боковых отсчетов

(7)

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

Алгоритм

Полином факторизуется в поле как [2]. В работе [3] показано представление бинарной последовательности длины в виде суммы м-последовательностей. Таким образом, бинарная последовательность раскладывается на групп м-последовательностей (в каждой группе по последовательностей), длины которых кратны .

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

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

а. Инициализация

Шаг инициализации состоит в заполнении таблиц сдвигов и весов последовательностей длины .

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

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

b. Вычисление

Первым шагом вычисления ПАКФ является разложение бинарной последовательности на м-последовательности [3]. Переходя к числовым характеристикам обозначим как номер сдвига -й м-последовательности относительно эталонной в группе (сгенерированной полиномом ).

Если номер корреляционного отчета не кратен :

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

(8)

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

3. Вес суммарной двоичной последовательности определяется как:

(9)

4. Циклический отчет автокорреляционной функции можно получить, используя выражение (6).

Если номер корреляционного отчета кратен : , то м-последовательности при циклическом сдвиге накладываются сами на себя, соответственно не нужно учитывать начальное состояние и сдвиги м-последовательности, и выражение (8) можно упростить:

(10)

c. Пример

Пусть , .

.

Разложение последовательности представлено в таблице 1.

Таблица 1. Разложение последовательности А.

Полином в данном примере можно игнорировать, поскольку генерирует только нулевые последовательности.

Эталонные м-последовательности - и полиномов и соответственно. Заполнение таблицы сдвигов: для этого сдвигаем циклически влево эталонные последовательности, складываем с эталоном и ищем номер сдвига результата. Например, - 3 сдвиг. В данном примере таблица весов представляет собой одномерная таблица. Фиксируя одну эталонную м-последовательность, вторая последовательность циклически сдвигается влево и в строку записывается вес суммарной последовательности. Индекс таблицы определяется разницей сдвигов последовательностей.

Начальные сдвиги последовательностей - , , , .

Таблицы сдвигов и весов представлены в таблице 2.

Таблица 2. Разложение последовательности А.

Корреляционный отчет :

- нулевая последовательность

- вес м-последовательности длины 7

.

Корреляционный отчет :

.

Заключение

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

Литература

1. Woodward P. Probability and Information Theory, with Applications to Radar. Pergamon Press: Oxford, 1953. - 146 p.

2. Cantor D, Zassenhaus H. A new algorithm for factoring polynomials over finite fields. //Mathematics of Computation, 1981, Vol. 36, No. 154. - Pp. 587-592

3. Безродный В. И. Модифицированный Алгоритм Берлекэмпа-Месси для анализа бинарных последовательностей. / Безродный В.И., Григорьев Н. Ю., Леухин А.Н.// Радиолокация, навигация, связь, 2016. - С. 250-254.