3.2. Метод изоморфных коэффициентов
Для оценки взаимокорреляционных свойств последовательностей часто используют пиковые значения их периодических (четных) взаимно-корреляционных функций (ПВКФ) и меандро-инвертированных (нечетных) взаимно-корреляционных функций (МИВКФ).
В работе [57] предложен метод исследования корреляционных функций периодических двоичных последовательностей, строящихся на основе разностных множеств, который позволяет существенно ускорить расчет этих функций на компьютере. Этот метод основывается на возможности применения ко всем классам таких последовательностей понятий изоморфизма и немножителей, введенных первоначально для разностных множеств. Поскольку немножители называют еще изоморфными коэффициентами [58], данный метод исследования ПВКФ получил наименование метода изоморфных коэффициентов.Пусть a=(ai, a2,...,otv) и b=(bb D2,...,bv) есть последовательности длины v= 2N-1 , принадлежащие одному классу, и пусть t есть некоторое положительное целое, взаимно простое с v. Так как t по определению есть немножитель, то последовательности
а' =(л ,л ,...,#,) и b' =(bi),blj,...,bl), где ik=(t(l-l)+l) mod v для всех / = l,v, также будут
принадлежать этому классу. Очевидно, что изоморфизм t : a -> a! является унитарным оператором в евклидовом пространстве Rv. В силу свойств этого оператора имеем:
(а, Ь)=(а', b') . (3.8)
Обозначим спектр взаимной корреляции последовательностей а и b через S(a, b). Тогда согласно (3.8)
S(a, b)=S(al, Ъх) . (3.9) и, следовательно, имеет место равенство их корреляционных максимумов, т.е.
maxS(a, b )=тах S(a', bl) . (3.10) Применяя соотношение (3.10) к вычислению ПВКФ последовательностей из одного класса эквивалентности, получаем, что достаточно исследовать ПВКФ одной произвольно взятой последовательности со всеми оставшимися. Более того, используя результаты теории чисел [59], можно показать, что множество изоморфных коэффициентов, состоящее из представителей смежных классов приведенной группы Т вычетов по модулю v по ее мультипликативной подгруппе Н автоморфных коэффициентов (множителей), также является группой относительно операции умножения.
Поэтому для любого немножителя t всегда найдется такой немножитель I, что / •/ ¦ 1 mod v. Отсюда получаемmax S(ct, a* )=max S(a,a7) . (3.11) Последнее означает, что число исследуемых пар последовательностей может быть уменьшено почти вдвое. Найденное свойство позволяет также значительно упростить процесс вычисления матрицы максимальных значений выбросов ПФКФ. Как следует из (3.9), строки этой корреляционной матрицы являются некоторыми различными подстановками любой произвольно выбранной строки. Однако в общем случае нельзя непосредственно по одной строке матрицы восстановить вид всей матрицы, так как для этого необходимо провести довольно трудоемкую работу по определению соответствия элементов исходной строки элементам остальных строк. Кроме того, возникают неудобства с запоминанием такой матрицы ввиду ее громоздкости. Тем не менее, все эти трудности можно избежать благодаря преобразованию корреляционной матрицы к одному из следующих видов:
1) когда каждая последующая строка этой матрицы является циклическим сдвигом предьщущей;
2) когда сама матрица состоит из циклических сдвигов некоторой совокупности и квадратных матриц порядка р<М, где up=M, а М - число всех изоморфных кодовых последовательностей, т.е. мощность. При этом строки образующих матриц также обладают циклическими свойствами.
При таком представлении, зная только первые строки образующих матриц и порядок их следования, можно довольно просто восстановить любую из строк корреляционной матрицы. Для доказательства этого среди множества различных изоморфных коэффициентов выберем коэффициент с максимально возможным порядком. Напомним, что под порядком изоморфного коэффициента t понимается наименьший, отличный от нуля, показатель степени /, для которого г/ mod v является множителем. Не нарушая общности рассуждений, всегда можно выбрать t таким, что t7 si mod v.
Рассмотрим две возможные ситуации: /=М и /<М. В первом случае / совпадает с мощностью ансамбля. Поэтому на основе одной какой-нибудь произвольно выбранной последовательности с помощью изоморфных коэффициентов t, Г2,...!7"1 строим систему остальных последовательностей этого класса, присваивая каждой полученной последовательности порядковый номер i, где l^i^/.
Затем, расположив последовательности в порядке возрастания их номеров, вычислим первую строку корреляционной матрицы. В силу того, что f1*1 t//2"=l mod v, достаточно найти только первые 112 +1 ее значений. Рассмотрим теперь вторую строку корреляционной матрицы, состоящей из максимальных значений выбросов ПВКФ пар последовательностей: (t,l), (tjt2), ...Xt,^"1) . Нетрудно проверить, что данные пары последовательностей изоморфны следующим парам:(1, г*"1), (1, 1), (1, t),...,(l, г/"2). Последнее означает, что вторая строка является циклическим сдвигом вправо первой строки. Аналогично показывается, что третья строка является сдвигом второй строки и т.д. Ч.Т.Д.
Перейдем теперь к рассмотрению второго, более сложного и чаще встречающегося случая, когда максимальный порядок, взятый по всему множеству изоморфных коэффициентов, меньше М. Аналогично предыдущему также строим мультипликативную группу изоморфного коэффициента 1| максимального порядка /[. . Предположим, что существует такая мультипликативная группа изоморфного коэффициента \гУ не принадлежащего группе {/,'} порядка \г , что 1\1т=Ъ\- Тогда поступаем следующим образом. Присваиваем номер 1 любой произвольно выбранной кодовой последовательности класса и на ее основе с помощью изоморфных коэффициентов вида 7,*^, где 0<к?/1-1, О^/г-Ь
строим /2 различных множеств, состоящих из 1\ упорядоченных последовательностей. Расположив упорядоченные таким образом последовательности по строкам и столбцам, получаем корреляционную матрицу К вида:
К=
^1 А^ А^,_,
А| А,
Ч I
где А^, 0?&/2-1» есть корреляционная матрица порядка 1/х12 , столбцы которой
соответствуют последовательностям вида ^, а строки - последовательностям $х'2. При этом в силу построения строки матриц А|( также обладают циклическими свойствами.
Заметим, что для случаев, когда М есть произведение большего числа сомножителей, построение производится аналогичным образом. Таким образом, получена простая процедура построения корреляционной матрицы по ее первой строке, позволяющая в М-1 раз ускорить расчет корреляционных параметров на компьютере.
В качестве иллюстрации сказанного рассмотрим построения корреляционной матрицы для последовательностей ОМУЫ длины у=63 и у=255.
Эти последовательности (по одной из каждого ансамбля) приведены ниже.Последовательность длины 63: 101000110101100110100011101000100000001111011100111101001011011.
Последовательность длины 255:
10000100001011111000101100100011010101011000010101110110111111110001001100111101 01110001001011001000110111001110000100011000100011111001111101111010101111101001 00011101001000000110111110001100101110000101100100100110100100100000001010011011 100001111011010.
Для случая у=63 (М=6) выбираем изоморфный коэффициент г=5 порядка 1=6. По исходной последовательности и множеству {51}, 1<х<5 , строим другие пять последовательностей ансамбля, которым присваиваем номера с 2-го по 6-ой. Так как /=М=6, то в соответствии с вышеизложенным корреляционная матрица К определяется ее первой строкой и имеет вид:
К=
"63 15 23 15 23 15
15 63 15 23 15 23
23 15 63 15 23 15
15 23 15 63 15 23
23 15 23 15 63 15
15 23 15 23 15 63
Легко проверить, что эта матрица полностью совпадает с корреляционной матрицей, полученной в результате вычислений обычным способом.
Для случая у=255 (М=16) в качестве изоморфного коэффициента, имеющего максимально возможный порядок, выбираем 11=7 с /|=8. Тогда 12=-1 , а /г=2, т.е. имеет место случай М= 1\ /2. Поэтому для построения корреляционной матрицы К достаточно найти лишь первые строки двух матриц А1 и А _|. В результате расчетов получаем, что матрица
255 47 47 63 63 63 47 47 31 31 63 63 95 63 63 31 47 255 47 47 63 63 63 47 31 31 31 63 63 95 63 63 47 47 255 47 47 63 63 63 63 31 31 31 63 63 95 63 63 47 47 255 47 47 63 63 63 63 31 31 31 63 63 95 63 63 47 47 255 47 47 63 95 63 63 31 31 31 63 63 63 63 63 47 47 255 47 47 63 95 63 63 31 31 31 63 47 63 63 63 47 47 255 47 63 63 95 63 63 31 31 31 47 47 63 63 63 47 47 255 31 63 63 95 63 63 31 31 31 31 63 63 95 63 63 31 255 47 47 63 63 63 47 47 31 31 31 63 63 95 63 63 47 255 47 47 63 63 63 47 63 31 31 31 63 63 95 63 47 47 255 47 47 63 63 63 63 63 31 31 31 63 63 95 63 47 47 255 47 47 63 63 95 63 63 31 31 31 63 63 63 63 47 47 255 47 47 63 63 95 63 63 31 31 31 63 63 63 63 47 47 255 47 47 63 63 95 63 63 31 31 31 47 63 63 63 47 47 255 47 31 63 63 95 63 63 31 31 47 47 63 63 63 47 47 255 Во многих случаях множители разностных множеств и образованных на их основе последовательностей образуют мультипликативных) группу по модулю V.
Это справедливо для многих классов последовательностей, в том числе для последовательностей Лежандра, Холла, а также т и вМу7 последовательностей. Покажем, что число целочисленных точек, в которых необходимо вычислить значения ПВКФ таких последовательностей может быть уменьшено с V до У|, где VI есть число смежных эквивалентных классов, получаемых при разбиении полной системы вычетов по модулю V по мультипликативной группе Н множителей разностного множества. Для доказательства этого утверждения воспользуемся теоремой Манна-Джонса о фиксирующем множителе разностного множества. Применительно к последовательностям на основе разностных множеств эта теорема утверждает существование такого циклического сдвига последовательности, который фиксируется каждым ее множителем. Обозначим этот сдвиг а. Тогда аь=а, где пеН. Очевидно, что если Ь=а', то Ь=ЬЬ. Можно показать, что для любого г взаимно простого с V справедливо равенство:(сцЬ) = ((ог)Т1Ьг) ,(3.12)
где т^пг тех! V.
Отсюда следует, что (О, Ъ) * (CL Ъ) для всех т^тп mod v и VheH. Таким образом, мы
доказали, что значения ПВКФ достаточно вычислять не во всех точках (сдвигах), а только в тех, которые являются представителями классов смежности, полученных при разбиении полной системы вычетов по модулю v по мультипликативной группе Н.
В качестве примера рассмотрим вычисление ПВКФ последовательностей символов Лежандра. Эти последовательности существуют для всех простых чисел вида v=4t-l и имеют М=2. Из свойств последовательностей Лежандра следует, что их множители совпадают с множеством квадратичных вычетов по модулю v, при этом порядок группы Н равен (v-l)/2. Поэтому, разбив числа от 0 до v-1 на смежные классы по множеству Н, в итоге получим три смежных класса, представителями которых являются элементы {0}, {1} и {-1}. В результате число точек, в которых достаточно вычислять значения ПВКФ, может быть уменьшено с v до 3. Ниже будет показано, что спектр взаимной корреляции последовательностей Лежандра может быть найден аналитически. Аналогичным образом можно показать, что число точек, необходимых для расчета ПВКФ последовательностей Холла, равно 7. Это, безусловно, не означает, что число различных значений в корреляционном спектре в точности равно числу классов смежности. Оно может быть и меньшим как, например, в случае трехуровневых m-последовательностей.