Автоматика и телемеханика, № 7, 2015
© 2015 г. Б.Ф. КИРЬЯНОВ, д-р техн. наук (boris.kiryanov@novsu.ru) (Новгородский государственный университет им. Ярослава Мудрого,
Великий Новгород), В.М. КУЗНЕЦОВ, д-р техн. наук (kuznet@evm.kstu-kai.ru), В.А. ПЕСОШИН, д-р техн. наук (pesoshin-kai@mail.ru) (Казанский национальный исследовательский технический университет им. А.Н. Туполева-КАИ)
УТОЧНЕНИЕ ФОРМУЛЫ ДЛЯ АВТОКОРРЕЛЯЦИОННОЙ ФУНКЦИИ М-ПОСЛЕДОВАТЕЛЬНОСТИ
Делается замечание о широко распространенной неточности формулы автокорреляционной функции М-последовательностей. Предлагается вывод точного выражения нормированной автокорреляционной функции р-ичной последовательности почти во всех точках временного аргумента в пределах периода. Обосновывается свойство баланса значений периодической автокорреляционной функции, позволяющее получить аналитические выражения пиковых выбросов автокорреляции внутри минимального периода для троичных и пятеричных М-последовательностей.
1. Введение
В исторической ретроспективе одни из первых результатов корреляционного анализа М-последовательностей были получены Голомбом С.В., Цирле-ром Н. и Гиллом А. Аналитические выражения для автокорреляции являются приближенными, однако в многочисленных публикациях на эту тему, например в [1], они представляются как точные зависимости.
Рассмотрим материал из широко известной работы А. Гилла [2], посвященной линейным последовательностным машинам, преобразующим сигналы из конечного поля ОЕ (р). Один из режимов работы автономной машины п-го порядка при простом р соответствует формированию в тактовом времени Ь периодической последовательности максимальной длины, известной как М-последовательность. Приводится корреляционный анализ такой числовой последовательности у(Ь) в общем р-ичном случае. Результатом анализа является выражение для нормированной автокорреляционной функции (НАКФ), представленное как
(1) вд= -3(!'-1)
pn(p + 1) - 3(p — 1)
для временных сдвигов § = 0 (mod 1 + p + p2 + ... + pn-1).
Однако несмотря на строгость формальных рассуждений автора при выводе формулы, в начале постановки задачи анализа допущена замена точного выражения средней величины элементов y(t) на периоде pn — 1 в виде
(2) ^fr"1} v 7 2(pn — 1)
приближенным предельным значением у = \{р — 1), справедливым для рп~^> 1. Затем это значение использовано в соотношении y(t) = y(t) — y(t) для введенного понятия "нормализованная последовательность".
Дальнейшие преобразования ориентированы на общее выражение НАКФ последовательности y(t) с периодом pn — 1:
pn- 2
Е y(t)y(t + •&)
(3) ВД = -
£ y2(t) t=0
как отношение смешанного центрального момента второго порядка (ненормированной автокорреляционной функции) к центральному моменту второго порядка (дисперсии). При подробном рассмотрении выражений числителя и знаменателя наряду с точными значениями сумм элементов y(t), y(t + $) и y2(t) на периоде М-последовательности были использованы нормализованные элементы y(t) и y(t + $) на основе приближенной формы средней величины у = 7j(p — 1). Естественно, такой порядок вывода требует считать результирующее выражение (1) лишь приближенной формулой вычисления НАКФ p-ичной М-последовательности n-го порядка. Так, например, в двоичном случае (p = 2) это выражение записывается как
(4) = дЛя -Q ф 0 (mod 2" - 1).
Следует отметить, что большинство публикаций, касающихся двоичных М-последовательностей, либо повторяют это неточное выражение, либо самостоятельно его выводят в этом же виде, предполагая у = \ в форме строгого равенства, что является ошибкой. Аналогичный неточный результат для НАКФ М-последовательности получается также при переходе от алфавита {0, 1} к алфавиту {—1, 1} или {-1/2, 1/2}, если принимать при этом среднее значение нулевым.
Цель предлагаемой статьи - вывод строгого соотношения для НАКФ М-последовательностей при любых n и простых p от целочисленных отсчетов временного аргумента "почти везде" (по терминологии А. Гилла) в форме
(5) •& = 0 (mod 1 + p + p2 + ... + pn-1).
Дополняют этот материал формулировки условий баланса для автокорреляционных функций периодических последовательностей в их общем представлении. Использование этих условий применительно к М-последователь-ностям позволяет получить для случаев p = 3 и p = 5 точные автокорреляционные оценки скрытых периодичностей y(t) в точках временного аргумента находящихся внутри минимального периода pn — 1.
2. Вывод точного выражения НАКФ М-последовательности
Материал вывода построим на максимальном использовании математической символики, формулировок и некоторых точных промежуточных результатов А. Гилла из [2, раздел 18, гл. 3].
Предлагается выразить соотношение (3) через начальные моменты в виде
М[у(Ь)у(Ь + 0)] - у2
ад =
м[у2(ь)] - у2
или с учетом равенств ^р= 0 2 у(Ь + 0) = Ер=0 2 У(Ь) = (рп — 1)У и точного вы- Рп(р-1)
ражения (2) для среднего значения у = как
рп —2 рп — 2 ^ Е у{Шг + 0) - Е + - ^г
т = _ *=о
1 ру2„2т р2"(р-1)2 р3"(р-1)2
п"-1 У 4 ^ У { ' 4 (»)«— 1)
(=0 ^ у (=0 ^ '
Тогда, включив в полученное соотношение выражения сумм для начальных моментов второго порядка, записанных А. Гиллом в формах
рп-2 рп-2
£ у(Ш1+ д) = -рп(р- I)2 и £ у\1) = -рп(р-1)(2р-1), (=0 (=0
получаем точную формулу НАКФ р-ичной М-последовательности п-го порядка в виде
(6) Д(0) = , -
1 ; ^ ' рп(р + 1) - 2 (2р- 1)
для значений аргумента, определенных неравенством (5). Назовем значения автокорреляции в указанных областях аргумента фоновыми. При этом наиболее распространенный случай р = 2 характеризуется формулой
(7) ад = - 1
2п - 2
отличающейся от широко распространенного соотношения (4) при 0 = 0(шоё2п — 1). Данный факт для двоичной М-последовательности впервые был отмечен в [3].
3. Условия баланса периодических автокорреляционных функций
Известно, что периодические процессы характеризуются периодическими автокорреляционными функциями с полным совпадением величин периодов в области независимой переменной Ь процесса и временного сдвига 0 как аргумента корреляционной функции. Выясним закономерности формирования автокорреляционной функции внутри периода Т.
Проведем подобный анализ для случая дискретных временных переменных Ь, 0 и Т, измеряемых в тактах. В этом случае процесс у(Ь) является последовательностью, в частном случае М-последовательностью. Вычислим
среднее значение автокорреляционной функции К ($) для произвольной периодической последовательности у(Ь) по всем точкам периода Т. Составим следующую запись:
1 т -1 1 т -1 т -1
т Е = т* Е Е м*) -я + - »]•
^=0 ^=0 4=0
Поменяем местами символы сумм и вынесем за пределы суммы по $ скобку с у(Ь), разделив эту сумму на две части, т.е.
т-1 т-1 т-1
(8) Е [у (Ь) - у] + $) - у] = £ [у (Ь) - у]
4=0 ^=0 4=0
т-1 т-1 '
Е у(*+$) - Е у
^=0 ^=0 .
Нетрудно видеть, что для периодической последовательности множество значений предела суммы $ и аргумента Ь + $ (сумма по модулю Т) при переменной у совпадают, что позволяет их заменить одной переменной I = О, Т — 1. Тогда получим у(1 + §) = = Ту- Так как 0 у = Ту, то правая прямоугольная скобка в выражении (8) равна нулю, что дает основание записать
т -1
(9) ^К ($)=0
^=0
как условие баланса значений периодической автокорреляционной функции последовательности у(Ь) на периоде Т.
Это свойство без аналитических подробностей впервые было выявлено в [3].
Учитывая, что К(0) есть дисперсия Б последовательности у(Ь), полученное условие баланса можно записать в другой форме -
т -1
(10) ^К ($) = -Б.
Эта запись позволяет утверждать, что сумма значений автокорреляции внутри периода (суммарная величина корреляционного фона без учета главного лепестка) всегда отрицательна по знаку и равна дисперсии по модулю.
Очевидно, что рассмотренные свойства баланса характерны и для нормированных форм функций, т.е. наряду с (9) и (10) справедливы соотношения
т-1 т-1
(11) ЕЕ($) = 0 и £ Д($) = -1.
При использовании периодической последовательности у(Ь) в качестве псевдослучайной желательно иметь минимальную величину модуля корреляционного фона внутри периода Т. Назовем такую периодическую автокорреляционную функцию идеальной. Основываясь на условии баланса в форме
правого выражения (11) и полагая одноуровневый характер расположения отсчетов R(ß) при § = 1, Т — 1, нетрудно выразить такую функцию лаконичной формулой
(12) R(§) = -TjT—r Для tf / О (mod Т).
T — 1
Выясним, насколько соответствуют М-последовательности условиям идеальности по автокорреляции.
4. Анализ пиковых значений НАКФ М-последовательностей
А. Гилл выделяет внутри периода pn — 1 отсчеты аргумента
(13) tf = 0 (mod 1 + p + p2 + ... + pn-1),
в которых величины НАКФ М-последовательности могут принимать пиковые значения, существенно превышающие фоновые R(tf) по модулю при противоположном условии (5) для аргументов ("почти везде"). Данное обстоятельство препятствует возможности формирования идеальной НАКФ применительно к недвоичным М-последовательностям (при p > 2).
Важно отметить, что только в случае p = 2 указанные отсчеты аргумента вида (13) полностью совпадают с отсчетами минимального периода tf = = 0 (mod 1 + 2 + 22 +... + 2n-1) = 0 (mod 2n — 1), при которых R(tf) = 1 естественным для периодической последовательности образом. Это дает основание говорить о полном отсутствии пиковых значений НАКФ внутри периода, что, в свою очередь, позволяет предполагать наличие идеальных автокорреляционных свойств у двоичных М-последовательностей n-го порядка. Действительно, выражая минимальный период 2n — 1 через T в соотношении (7), получаем формулу (12).
В результате анализа работ, включая [2], содержащих описания и исследования недвоичных М-последовательностей, не удалось найти аналитические формы записей пиковых значений НАКФ. В лучшем случае для иллюстрации конкретных примеров применяются методы статистического оценивания на реальных выборках y(t) длиной pn — 1, позволяющие считать полученные численные оценки ПАКФ соответствующими их теоретическим значениям.
Записывая из выражения (13) очевидное равенство для суммы геометрической прогрессии 1 + р + р2 + ... + pn~l = ppZi , нетрудно з
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.