3.4. Взаимно-корреляционные пики последовательностей СМ
Как уже отмечалось выше, в качестве базисных последовательностей при построении ПСП вМУУ, кроме т-последовательностей, могут быть также выбраны любые другие идеальные ПСП, в том числе ПСП Холла, Лежандра, ПСП У7 меньшей значности, последовательности Бомера-Фридриксена [14] и др.
Очевидно, что описанный выше структурный подход может быть распространен также и на классы ПСП СМ\У. Согласно [21,22,63] для построения ПСП ОМ"УУ В декомпозиции т-последовательности с параметрами у/=2т-1 и е=2м-1Лу, где К=тк и т>3, к>2, необходимо все нулевые строки, являющиеся сдвигами некоторой более короткой т-последовательности длины заместить на строки с теми самыми сдвигами, но уже другой базисной последовательности. Причем эта базисная последовательность должна удовлетворять следующим двум условиям:обладать двухуровневой ПАКФ;
не являться никаким сдвигом замещаемой короткой т-последовательности.
Строки же, состоящие из одних нулей, остаются без изменения. И хотя данный метод в силу его сложности на практике не применяется, он оказывается весьма эффективным при анализе ПВКФ последовательностей с описанной выше структурой. Действительно, из алгоритма построения ПСП ОМУУ следует, что для всех /Ц удовлетворяющим условиям теоремы 3.1 при т=/у, 0^ (#)=0^ (>и), где ©^ (#) и ©^ (т) соответственно значения
пиков ПВКФ пар ПСП вМ'уУ и т-последовательностей при децимации (3.18). Этот результат может быть сформулирован в виде следующей теоремы [62].
Теорема 3.2.
Пусть гЛ>6 составное число, удовлетворяющее условиям Теоремы 3.1, а 0 (#) есть пиковое
с
значение ПВКФ класса ПСП вМ^' с параметрами м? = 2 - 1 и е=2м-1Лу. Тогда
0 (?);>© , (3.22) с с
где 0 определяется выражением (8) и 0, = (т). с аг г
Следствие 3.2.
Пусть N четно, не кратно 3 и удовлетворяет условиям теоремы 3.1. Тогда любой класс ПСП ЄІУ^ можно разбить на два не пересекающихся равномощных подмножества, связанных между собой децимацией (3.18) при рі=3.
На компьютере были исследованы ПВКФ ПСП СМ'УУ для всех 6<Ы<15 и некоторые для N=16.
Результаты этих вычислений приведены в таблице 3.2. При этом рассматривались все возможные классы ПСП ОМ\У [14], а пары последовательностей выбирались только в пределах одного и того же класса. Исследования показывают, что для N=6, 8,10, 12, 14 и 15имеет место равенство 0 (#)=0 , (#), т.е. пиковое значение всецело определяется
с «г
децимацией <1г. Очень вероятно, что это может быть справедливо и при больших значениях N. При рассмотрении Таблицы 3.2 особо следует выделить случай N=12 с ш=3, 4, 6, для
которых 0 (#) имеет одно и то же значение, равное 1407. То, что это так, когда ш-3 или 4, с
следует непосредственно из Теоремы 2. Для случая ш=6 условия Теоремы 3.2 не выполняются. Однако вследствие того, что сами строки в декомпозициях последовательностей {а;} и {ЬІ} в свою очередь представимы в виде декомпозиций с параметрами ^=7 и є=9 на базе одной и той же последовательности длины 7, результат оказывается таким же, как для ш=3. Неприменима также Теорема 3.2 и для случаев N=8, 9 и 16, хотя то, что при N=8, 16 имеет место 0 , (#)=0 , (/и), вряд ли можно считать
результатом простого совпадения. Другим итогом проделанных расчетов является вывод, что пики ПВКФ ПСП СМ\У при других децимациях ведут примерно так же, как в случае т-последовательностей. В качестве иллюстрации рассмотрим класс ПСП ОМ\? значности 214-1=16383, представителем которого является последовательность, сформированная на
основе характеристического полинома х14+х13+хп+х9+1 и базисной последовательности класса Бомера-Фридриксена длины 127 [64,65] вида:
"0111101011011101000010110100100000011110100011001000111010101111111110010011010 011110110010010101011001111000110000110001000100".
Исследования показывают, что этот класс может быть разбит на 6 подмножеств из 126 последовательностей, имеющих одни и те же взаимно-корреляционные матрицы с
0 (#)=815, тогда как равномощный класс т-последовательностей при аналогичном с
разбиении содержит подмножества с 0 (/и) =897.
с
Декомпозиционный метод может оказаться также весьма полезным и при анализе межклассовых ПВКФ ПСП ОМУУ.
Очевидно, что в этом случае нижняя граница максимума взаимной корреляции будет определяться как числом совпадающих нулевых строк, так и корреляционными параметрами самих базисных последовательностей, подставляемых в одну и ту же декомпозицию исходной т-последовательности.Сформулируем теперь следующие важные утверждения, касающиеся спектров взаимной корреляции рассматриваемых последовательностей при децимации (3.18) [66].
Утверждение 3.1.
Спектры взаимной корреляции т-последовательностей с децимацией (3.18) при Ы, удовлетворяющих условиям Теоремы 3.1, совпадают со спектрами взаимной корреляции последовательностей вМШ с той же децимацией.
Доказательство этого утверждения основывается на следующем: - совпадении ПВКФ пар т-последовательностей с децимацией (3.18) с ПВКФ пар последовательностей СМ>^, образованных на основе тех же самых примитивных многочленов, что и эти т-последовательности;
равенстве спектров взаимной корреляции любых пар т-последовательностей (последовательностей СМ.>У) с одной и той же децимацией.
Утверждение 3.2.
Значения взаимной корреляции 9х,у(0 т-последовательностей (последовательностей х и у, связанных децимацией (3.18) при всех N1, удовлетворяющих условиям Теоремы 3.1, определяются выражением:
9^0=^2*-(2М)/(2т-1) ,(3.23) где и! - положительное целое или нуль.
Для доказательства рассмотрим декомпозиции последовательностей х и у. В силу построения ненулевые строки их декомпозиций являются сдвигами друт друга. Предположим, что при 1-ом сдвиге у этих последовательностей совпадает щ строк. Тогда число несовпадающих строк равно (2Ь1-\)/(2т-\)- щ. Отсюда, имеем: ех,у(1)=и1 (2т-1> (2"-1)/(2т-1> и; = Щ2т- (2"-1)/(2га-1). Ч.Т.Д.
Согласно теоремам 3.1 и 3.2 при 1=0, по меньшей мере, (2м-1)/р1(2т-1) строк их декомпозиций должны совпадать. Обозначим через Уо число дополнительных совпадений. Тогда ех>у(0)= [(2ь,-1)/р|(2т-1) +У0] 2т - (2к-1)/(2т-1). Нетрудно убедиться, что существуют еще рМ сдвигов вида ] (2ы-1)/р1, где 0<)<р\, при которых также имеет место совпадение (2м-1)/р((2т-1) строк.
Таким образом, мы доказали следующее утверждение.Утверждение 3.3.
Для пар т-последовательностей и последовательностей ОМАУ, связанных децимациями (3.18) при N. удовлетворяющих условиям Теоремы 3.1, существует ри взаимно-корреляционных пиков вида
6х,у0 (2м-1)/Р|)= [(2м-1)/Р1(2т-1) +УЛ 2т - (2к-1)/(2т-1) , (3.24) равно ОТСТОЯЩИХ один от другого на (2м-1)/р1 сдвигов. Здесь 0<)<рь а V] - положительное целое или нуль.
Проиллюстрируем сказанное на примерах. При этом будем рассматривать случаи, когда Р1=ри- Пусть N=10 и р;=3. Тогда в силу (3.23) и (3.24) имеем: 9х,У0)=32и4 - 33 и
9x.y(343j)=319 + 32Vj, где 0 Рассмотренные примеры демонстрируют хорошую согласованность теоретических и практических результатов. Отметим, что корреляционные спектры т-последовательностей для четных N и pi=3 получены Т. Хеллесофом в работе [60]. В заключении сделаем одно важное замечание, касающееся поиска пиковых значений взаимной корреляции. Исследования показали, что при pi>pu также могут существовать пары последовательностей со сверхвысокими пиками взаимной корреляции, правда, меньшими, чем при р„. Соответствующие децимации и оценки находятся подстановкой в формулы (3.18) и (3.21) значения pi вместо ри . Так, например, для N=20 такие пики имеют место при ри=3, 5,11 и 41. Сответственно их значения будут больше или равны: 326975, 208895, 64575 и 24575. 3.5. Взаимная корреляция последовательностей Холла и Лежандра Класс ПСП Холла имеет следующие параметры [43]: p=4m2+27, w=2m2+13, dx=2m2+14, р=-1, М=6 ,(3.25) где р-значность ПСП(р-простое число),\у-вес ПСП, dx-хэммингово расстояние ПСП от ее циклических копий, р - неглавное значение ненормированной ПАКФ. с!пвкФ=<1элЕм(2т2+13)/3 , (3.26) где С!ЭЛЕМ - расстояние по Хэммингу между ПСП в пределах каждой элементарной группы из шести чисел с последовательно возрастающими степенями первообразного корня g. Наименьшее С!ЭЛЕМ=2 (см. таблицу 2 работы [67]) дает наибольшую нижнюю границу &с (Н) для максимума ПВКФ ПСП Холла. В итоге получаем 0с(Н)=г>2с1пвкФ==4т2+27-4(2т2+13)/3=(4п12+29)/3=р/3+2/3 . (3.27) В таблице 3.3 представлены параметры класса ПСП Холла вместе со значениями 0С (Н). А Сравнение Таблицы 3.1 с таблицей 3.3 показывает полное совпадение значений 0С(Н) с 0 (т) при р=31, что не удивительно, так как в этом случае m-последовательности и ПСП с Холла совпадают. В результате проведенных расчетов было установлено, что при р=31,43 и А 127 реальные пики ПВКФ совпадает со значением 0С(Н), т.е. найденная нижняя граница для этих случаев является также и верхней. Но если при змачности 127 в классе т-последовательностей можно выделить так называемое максимально связанное подмножество из 6 последовательностей с 0 (т) =17, то в классе ПСП Холла нет ни одной пары со с значением пика меньшим 41. Еще меньшую мощность (равную двум) имеет класс ПСП Лежандра змачности р, где р=4т-1 простое число. Известно [43], что символы ПСП Лежандра, за исключением нулевого, связаны между собой равенством
.р] \ Р > ,где
= А 1 ,если i есть квадратичный вычет по mod р -1,если i есть квадратичный невычет по mod р
Это равенство устанавливает зеркально-инверсную симметрию символов этих двух последовательностей. С помощью его получаем следующее точное выражение для пика ПВКФ ПСП Лежандра [62]: © (1)=2-р , (3.28) с Значения пиков взаимной корреляции т-последовательностей. справедливое при всех возможных значениях р. 2м-1 - значность т-последовательностей; М - Мощность класса т-последовательностей; 0 (т) - пиковое значение ПВКФ со знаком ; с 0 - статистическая оценка (3.19); о @с - нижняя граница максимума ПВКФ. Таблица 3.2. Значения пиков взаимной корреляции последовательностей ОМУУ.
N т К М Р(т,к) 0 (?) с ©С
6 3 2 6 1 +23 15
8 4 2 16 1 +95 85
9 3 3 48 1 +149 —
10 5 2 60 7 +383 319
12 3 4 144 1 +1407 1183
12 4 3 144 1 +1407 1183
12 6 2 144 11 +1407 —
14 7 2 756 79 +5631 5375
15 5 3 1800 7 +4927 3775
15 3 5 1800 1 +4927 —
16 8 2 2048 63 ?22015 —
18 9 2 7776 239 >87551 87039
21 7 3 84672 79 ? 300159 285439
Р(т,к) - число различных классов при заданных тик;
© (#) - пиковое значение ПВКФ ПСП ОКШ. Таблица 3.3. Значения пиков взаимной корреляции последовательностей Холла.
ш Р ёс (Н)
1 25-1=31 11
2 43 15
5 27-1=127 43
7 223 75
8 283 95
14 811 271
16 1051 351
19 1471 491
20 1627 543
23 2143 715
26 2731 911
28 3163 1055
29 3391 1131
34 4651 1551
37 5503 1835
181 217-1=131071 43691
р - значность ПСП Холла; @^(Н)- нижняя граница максимума ПВКФ ПСП Холла.