3.3. Взаимно-корреляционные пики т-последовательностей

Численные исследования показали, что в целом ансамбль т-последовательностей обладает плохими ПВКФ [20]. Это связано с существованием пар, пиковые значения взаимной корреляции которых достаточно велики и могут достигать одной трети от ее длины.

большое распространение получили также и аналитические, основанные на связи т~ последовательностей с конечными полями Галуа. В общем случае эта связь выражается формулой:

Ь;=Ца') , (3.13)

где Ь - линейный функционал из ОР(2м) в вР(2), 0<}<2**-\, а а - примитивный элемент вР(2ы). В качестве линейного функционала наиболее часто используется след элемента

N
2еОР(2 ) в СР(2),определяемый выражением [4]:

1^(2)-^ . (3.14)

/-0

По теореме, обобщенная формулировка которой приведена в [20], ПВКФ т-

последовательностей, связанных между собой либо децимацией 2'+1, либо 2 -2+1,

взаимно простыми с 2м-1, где N не есть степень 2, а 1<г<Ы/2 и е=(Ы,0 такие, что Ы/е -нечетно, является трехуровневой с максимальным абсолютным значением взаимной корреляции

Рвм-2(1Ч+е)/2+1 . (3.15)

В случае же # = тос14 и децимации 2(Ы+2)Г1-\ максимальное значение взаимной корреляции составляет

Рш.х=2(ГУ+2>/2-1 . (3.16) На практике широко используются так называемые предпочтительные пары т-последовательностей с е=1 для нечетных N и е=2 для четных Ы, образующие ПСП Голда. Заметим, что на практике широко используются так называемые предпочтительные пары т-последовательностей с е=1 для нечетных N и е=2 для четных образующие ПСП Голда.

В 1976г. норвежский математик Т. Хелесев опубликовал статью [60], в которой доказал, что в случае N=0 mod 2 ПВКФ m-последовательностей, связанных децимациями d=(2N-l)/3+2', где i равно 0 или 1, является 6-ти уровневой с максимальным значением a) Pmax=(2N+2N/2)/3, если N кратно 3 и не кратно 4;

б) Pnux=(2N+2N/2+2)/3, если N не кратно 3 и 4; .

в) PnefK^+f1**')/3, если N кратно 4;

Выражение (3.17) можно принять в качестве аналитической нижней границы максимума взаимной корреляции класса m-последовательностей (другой вопрос насколько эта граница наибольшая).

Как показывает практика, для подавляющего числа приложений требуются не пары, а большие подмножества m-последовательностей, отобранные по результатам компьютерного расчета их ВКФ. Свое дальнейшее развитие эта задача получила в работе А. Тиркеля [61], где на основе конечных полей и статистических свойств m-последовательностей предложена концепция, устанавливающая зависимость между пиковыми значениями взаимной корреляции m-последовательностей и их децимациями. Согласно этой концепции сверхбольшими пиками взаимной корреляции обладают пары, связанные децимациями вида:

r(2N-l) + p. d= , (3.18)

Pi

где 0<г<р;,0<1^я, a 2y-l = J2JpJ- есть факторизация 2N-1. Кроме того, должно

выполняться (2N-l,dr)=l. Нетрудно убедиться, что децимации вида (3.18) обладают свойством оставлять на месте ровно 2N-l/pj элементов исходной последовательности. На этом основании с учетом статистических свойств m-последовательностей в [61] делается вывод, что, во-первых, наибольшее пиковое значение ПВКФ, взятое по всему ансамблю т-

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

0=2*-1/ри , (3.19) а

где ри=тт {pi}, со среднеквадратичным отклонением от нее [(2м-1)(ри-1)/ри]1/2. Заметим, что оценка (3.19) применима не ко всем т-последовательностям, а только к тем, у которых длина есть составное число. В [61] приведена также таблица с результатами компьютерного расчета пиков ПВКФ т-последовательностей для 3<Ы<17. Предпринятая нами с целью устранения возможных неточностей компьютерная проверка этих результатов полная для 3<Ы<15 и выборочная для N=16 выявила ошибки в пиковых значениях для случаев N=4 и N=15 (отметим, что в последующей работе А. Тиркеля эти ошибки были исправлены). В

таблице 3.1 приведены скорректированные значения этих пиков, а также 0 для 3<^17.

Ь

хотя приведенные в таблице 3.1 значения пиков в целом согласуются с предсказанной оценкой (3.19), нельзя не заметить и случаев, когда это не так. Во-первых, при N=11 имеется более чем трехкратное превышение реальным пиком его ожидаемого значения. Во-вторых, при п=9 пиковое значение, взятое со знаком, равно -113 и обнаруживается при децимациях отличных от (3.18). И если случай N=11 еще может быть объяснен значительной статистической флуктуацией, то наличие пика с отрицательным знаком при децимации отличной от (3.18) противоречит сделанному в [6|3 предположению о положительном знаке пика. Выход из этого может состоять в отказе от утверждения об обязательно положительном знаке корреляционного пика, а все отклонения от оценки (3.19) считать результатом действия статистических флуктуации. Ни в какой мере не умаляя значения оценки (3.19), остановимся на некоторых ее принципиальных недостатках, обусловленных особенностями статистического подхода. Первое, на что следует обратить внимание, статистическая оценка не может полностью исключить возможность флуктуации, в результате которой на месте предсказуемого пика обнаружится пик с совершенно иным

значением, а то и вовсе его отсутствие, как это имеет место при N=9. Другими словами, полученная оценка имеет вероятностный характер и не может считаться полностью достоверной. Поэтому принять ее в качестве новой нижней границы максимума взаимных корреляций для всего класса т-последовательностей, строго говоря, нельзя. Во-вторых, будучи инвариантной к любым случайным последовательностям, оценка (3.19) не учитывает структурной специфики псевдослучайных последовательностей, которые по своей природе, как известно, являются строго детерминированными последовательностями. Напротив, выражение (3.17), полученное в результате представления т-последовательностей посредством следов в полях Галуа, эту специфику учитывает. Однако, как следует из [60], это выражение справедливо только для случая четных N и р^З. В качестве альтернативы в настоящей работе предлагается подход, основанный на структурных свойствах т-последовательностей, связанных децимацией (3.18).

одних нулей. Нетрудно подсчитать, что число нулевых строк всегда равно е-2к*т. Пусть я

2Ы -1 = \\р1 есть факторизация 2м-1, а ри =ггап{^-}. Пусть /=тах{/у}, где к < #, /\н

1-1 I у

и рМ|(2А(-1)/(2/У -1). Рассмотрим декомпозиции т-последовательностей {а^} и {^}, связанных

децимацией (3.18), где 1^г<Ы при условии т=/. Тогда е=21Ч-1/2/-1 и, следовательно, ри|е.

Очевидно, что при децимации (3.18) в/ри строк последовательности {а,} с номерами 0,ри,2ри,..., е-ри останутся на своих местах. А так как за счет выбора соответствующего сдвига последовательности {а*} строку с номером 0 всегда можно сделать ненулевой, то все ненулевые строки в декомпозиции {Ь;} окажутся сдвигами этой строки. Полагая далее остальные е(ри-1)/ри строк не совпадающими, находим, что смещение пика ПВКФ от его

среднего значения (2к-1)/р„ влево не может быть более чем на є(ри-1)/ри- Таким образом, мы доказали следующую теорему [62].

Теорема 3.1.

я

Пусть 2"-1 = Цр, есть факторизация 2м-1. Пусть /=тах{//}, где 1 І 3

Рі

N Ч

(2 -1)/(2у-1). Пусть © (т) есть пиковое значение ПВКФ класса т-

последовательностей. Тогда

© (т)?0 , (3.20) с с

где ёс=^-^0^> . (3.21) Рі (2і -1) р,

Очевидно, что оценку (3.21) можно использовать только при (2'-1)/рі > 2.Анализ

А

показывает, что при ри=тіп{рі} © имеет наибольшее значение и для нечетных N является

с

наибольшей нижней границей максимального значения корреляционного пика, взятого по всему классу т-последовательностей. Можно показать, что когда N четно и не кратно 3, то ри=3, а 2и-\ не кратно 9. В этом случае а\ принимает единственное значение: (2м-1)/3+1 или 2(2м-1)/3+1. В результате получаем следующее полезное для практических приложений следствие.

Следствие 3.1.

Пусть N четно, не кратно 3 и удовлетворяет условиям Теоремы 3.1.

Проиллюстрируем данное следствие на примере т-последовательностей значности

2,4-1=16383. В этом случае мощность М=756, с1г=5461 и 0 (/я)=5631. Разделим пары,

с

связанные децимацией 5461 (а таких ровно 378), на два подмножества. В результате каждое

будет содержать по 378 последовательностей с пиковым значением 897. Это всего лишь в 3,5 раза превышает аналогичное значение для последовательностей Голда, обладающих худшими автокорреляционными функциями. Расчеты показывают, что при р;>ри также могут существовать пары последовательностей со сверхвысокими пиками взаимной корреляции. Например, при N=12, т=6 и р* =5 все пары последовательностей с децимациями

А

1639, 2458 и 3277 имеют корреляционный пик 0С ?0 769; при N=18, ш=9, р\=\9 и

с

4=13798 0С>0 =13311; при N=20,111=10,^=5 и а\=209716 0С?0 = 209919. с с

Выражение (3.21) было получено в предположении минимального вклада в

корреляционный пик строк с некратными ри номерами. Очевидно, что это крайний,

граничный случай. Если же исходить из равновероятности сдвигов в ненулевых строках

декомпозиции, то реально пиковое значение будет больше. Более того, по меньшей мере, р„

сдвигов между последовательностями {а,} и {Ъ\} приводят к совпадению е/ри строк их

декомпозиций. А по Теореме 3.1 каждый такой пик должен быть не менее 0 .

с

Следовательно, Теорема 3.1 гарантирует существование, по меньшей мере, р„ пиков со

А

значениями ^0С- В таблице 3.1 приведены полученные в соответствие с формулой (3.21)

А

значения 0С для N=6, 10, 12, 14, 15. Кроме того, в таблице приведены значения корреляционных пиков последовательностей с децимациями (5) для N=18 (ри=3) и N=21 (ри=7). И хотя 0С оказывается дальше от истинного значения пика, чем 0ь, тем не менее,

А

это совершенно достоверное значение. Причем для случаев N=6, 10, 14 граница 0С даже

совпадает со значениями некоторых вычисленных на компьютере сверхвысоких пиков. К сожалению, предлагаемый структурный метод неприменим для случаев К=р1, где р-простое, а ^1-целое число, так как не выполняются условия Теоремы 3.1.