2.2. Алгебраическо-комбинаторные основания построения ПСП вМУ
Выше было показано, что исследование свойств ПСП вМ\У может быть сведено к исследованию соответствующих свойств вМ\У разностных множеств, являющихся через свои векторы инцидентности алгебраическо-комбинаторными основаниями этих последовательностей.
Теория ОМ1^ разностных множеств [44] состоит из ряда лемм и теорем, наиболее важные из которых приводятся ниже. Начнем с определения.Определение.
Линейный функционал из поля Е в подполе Р есть отображение Е-»^, линейное над Р.
Лемма 2.1 [44].
Пусть F - конечное поле , Е — конечное расширение поля F и L - не нулевой линейный функционал из Е в F. Тогда каждый линейный функционал из Е в F имеет вид , где цеЕ и Ьц(и))=Ццы) для VcoeE. Кроме того, если |j*v, тогда LM*LV
Согласно известной теореме Зингера о гиперплоскостях геометрии PG(N,q) [43] для любой степени простого числа q=pe и любого целого N>2 существуют циклические разностные множества с параметрами:
v=qN-l/q-l, k=q>M-l/q-l, , X=qNI-l/q-l . (2.6)
Впоследствии эти разностные множества получили название зингеровских. Приведем описание алгебраической конструкции этих разностных множеств.
Пусть а - есть примитивный элемент поля Галуа GF(qN), a L - ненулевой линейный функционал из GF(qN) в GF(2) такой, что L(l)=l. Тогда множество Do всех j таких, что L(a?)=0, образует зингеровское разностное множество [44] с параметрами (2.6). Дополнение зингеровского разностного множества Do есть разностное множество D(L,a) с параметрами:
v=qN-l/q-l, k=qN*1, W"(q-D . (2.7)
При этом jeD(L,a)<-> L(ccV0 ДЛ* 0 Пусть q есть степень простого числа р и пусть N есть целое, N>2. Пусть L есть линейный функционал из конечного поля GF(qN) в подполе GF(q) такой, что Ц1)=1. Пусть Lo есть сужение L до подполя GF(qm), при этом m делит N. Пусть Ьг есть линейный функционал из GF(qN) в GF(qm) такой, что для VxeGF(qN) элемент L2(x) из GF(qm) удовлетворяет соотношению Lo(L2(x)y)=L(xy) для VyeGF(qm).
П(Х)=][УУ (2.9)
Суммирование здесь производится по всем i, для которых L2(ct>0, 0
w=qm-l/q-l, /= q' ^=qm"2(q-i) . (2.10)
Гордон, Милз и Велч показали, что если 0о(у) в выражении (2.8) заменить полиномом Холла Оь(у) произвольного разностного множества b с параметрами (2.10), тогда 0e(x)sQ(x)0b(y) (mod xv-l) есть полином Холла разностного множества В с параметрами (2.7). Построенные таким способом и отличные от зингеровских разностные множества получили в литературе название GMW-разностных множеств [45,46]. Из теоремы 2.1 вытекает следующее важное для построения ПСП GMW следствие [49]. Следствие 2.1. Пусть Ь| - линейный функционал из СР(2 ) в ОР(2), Ьл - сужение Ь| до подполя СР(2т), а Ьг - линейный функционал из ОР(2м) в СР(2т) такой, что Ьо(Ьг(х)у)= Ь|(ху) для Ухе СР(2Ы) и Ууе СР(2т). Пусть а и Р примитивные элементы соответственно СР(2М) и С?(2т). Пусть {с^, где 0<}<У/, есть двоичная ПСП, обладающая такой же автокорреляцией и балансностью, как т-последовательность {Ьо(Р])Ки ПРИ этом не совпадающая ни с каким ее сдвигом (в дальнейшем такие ПСП будем называть базисными). Тогда любая последовательность {Ь„} с элементами вида:
Ьп =.tfL2(an)) , (2.11)
где / GF(2m) -»GF(2) - функционал, определяемый парой условий: , (2.12)
РОССИЙСКАЯ ГОСУДАРСТВЕННА* является последовательностью GMW длины 2 -1. Теперь сформулируем условия, при которых два разностных множества В и С с параметрами (2.7), полученные этим способом, являются эквивалентными. Поставим в соответствие каждому (w, /, \х) разностному множеству о с полиномом Холла Эь(у) некоторое (v, k, X) - разностное множество В с полиномом Холла 6в(х)=О(х)0ь(х^) . Теорема 2.2 [44]. Пусть q есть степень простого числа р, и пусть N есть целое, N>2. Заметим, что хотя данная теорема и включает случай m=2, GMW разностных множеств для т=2 не существует. В силу того, что предметом нашего исследования в основном являются двоичные ПСП, далее нас будут интересовать исключительно разностные множества с параметрами q=p=2. На основе Теорем 2.1-2.2 может быть предложен следующий алгоритм построения GMW разностных множеств и связанных с ними последовательностей GMW. На первом шаге алгоритма строится комплиментарное (дополнительное) к зингеровскому разностное множество D(L,a) с параметрами v=2N-l, k=2N']Д=2К"2 .(2.13) Для этого из таблицы примитивных многочленов выбирается произвольный многочлен f(x) степени N над GF(2) и находится множество D(L,a)={n / L(an)*0, для 0
выражением = ¦ l,(i + ?j)eD(Z,,*) 0^y<2m-2 О, в противном случае 0 < / < % -1
Заметим, что с помощью построенной таблицы производи гея вычисление полинома Q(x)=^x,ym' ( mod xv-l). Суммирование здесь ведется по всем ненулевым строкам таблицы, a mi - есть число циклических сдвигов влево i - ой строки до ее совпадения с первой строкой этой таблицы. На следующем шаге алгоритма производится выбор базисной последовательности длины w=2m-l, не являющейся ни каким сдвигом, находящейся в первой строке ненулевой последовательности. На четвертом шаге производится замещение ненулевых строк исходной таблицы представителей соответствующими сдвигами базисной последовательности таким образом, что на место i-й ненулевой строки записывается сдвинутая на т, разрядов вправо базисная последовательность. Обозначая элементы образованной таблицы через by , в результате получаем разностное множество GMW, состоящее из всех различных вычетов , для которых Ьц=1.
Базисные разностные множества состоят из двух изоморфных (7,4,2) разностных множеств
Ь]={0, 2, 5, 6} и Ь2={0, 1, 2, 5} с инцидентными последовательностями 1010011 и 1110010.
Первому разностному множеству соответствует зингеровское разностное множество, а
второе ведет к образованию нового (63, 32, 16) разностного множества. Для его Декомпозия вМ"^ разностного множества (63,32,16). построения произведем замещение ненулевых строк таблицы 2.1 соответствующими сдвигами последовательности 1110010. В результате получаем следующую таблицу 2.2. С помощью этой таблицы находим, что вМ>У разностное множество есть {0, 2, 6, 7, 9, 11, 12, 15, 16, 18,22,23,24,26, 30, 38, 39,40, 41, 43, 44,45,48,49, 50, 51, 53, 56, 58, 59, 61,62}, а соответствующая ему последовательность СМ\\^ имеет вид: 101000110101100110100011101000100000001111011100111101001011011. Нетрудно убедиться, что класс эквивалентности содержит 6 изоморфных друг другу разностных множеств. Все они образуются посредством умножения полученного разностного множества на числа 5, -5, И, -11 и -1, являющимися немножителями разностного множества (63,32,16). Очевидно, столько же имеется и различных последовательностей ОМ>У. Теорема 2.3 [44]. Пусть и есть либо не тривиальное (V, к, X) - разностное множество В из Теоремы 2.1, либо не тривиальное зингеровкое (V, к, К) - разностное множество. Тогда множителями Э являются исключительно степени р по то<1 V. Очевидно, что применительно к случаю <{=р=2 множители О являются степенями числа 2. В заключение этого краткого экскурса в теорию вМ>У разностных множеств приведем формулировку основной теоремы Гордона, Милза и Велча. Теорема 2.4 [44]. Пусть q есть степень простого числа р. Пусть тик есть положительные целые числа, причем т>3. Пусть к есть произведение г простых не равных единице множителей и N=mk. Тогда существуют, по меньшей мере, 2Г неэквивалентных разностных множеств с параметрами (2.7). Заметим, что одно из этих разностных множеств в силу метода построения всегда является зингеровским, другие же являются GMW разностными множествами [44].
m,
41 БИБЛИОТЕКА