2.3. Мощность н общее число классов ПСП GMW

В соответствии с [45] под мощностью класса эквивалентности или просто класса разностных множеств будем понимать число всех различных изоморфных разностных множеств в этом классе.

Теорема 2.5 [14].

Мощность класса эквивалентности любого GMW разностного множества с параметрами (2.13) равна:

м = 2(2^1) ,{2.14)

где N=mk, m>3, k>l, а cp - функция Эйлера.

Доказательство.

Согласно Холлу [43] каждая степень числа 2 есть множитель GMW разностного множества с параметрами (2.13). С другой стороны, в соответствии с теоремой 2.3 каждый множитель GMW разностного множества есть степень 2 по mod v. Отсюда получаем, что все множители GMW разностного множества образуют мультипликативную группу Т по умножению порядка N. Тогда в соответствии с определением изоморфности разностных множеств мощность класса эквивалентности GMW разностного множества равна порядку факторгруппы G/T, где G - группа классов вычетов по mod v, взаимно простых с v. По

теореме Лагранжа [51] порядок факторгруппы G/T равен отношению т^г, где |G| и |Т|

соответственно порядок групп G и Т. Согласно [50] порядок группы G равен IGI тО N — 1 ^ Отсюда получаем, что М= |G/T|= щ = M = ——— .

Теорема доказана.

Переходим теперь к вопросу построения всех неэквивалентных GMW разностных множеств. Здесь мы докажем ряд теорем и лемм, с помощью которых будет получена формула для общего числа этих множеств. В начале сформулируем одно очевидное следствие, вытекающее из теорем Гордона, Милза, Велча.

Следствие 2.2.

Пусть q=p=2 и N=mk, m>3, к>1.

Пусть 8(х)=Л(х)60(у) (mod xv-l) - полином Холла некоторого разностного множества с , а C - произвольный корень бинома хМ. Очевидно, 8(4)0(4*1)=к-Я . Отсюда в силу произвольности C получаем, что 0(х) и хМ взаимно просты. Таким образом, доказана лемма 2.2

Лемма 2.2 [14].

Если 9(х) - полином Холла разностного множества, для которого ЫХ,, тогда

(0(х), хМ)=1 .(2.15)

Пусть N=kmini2, к, mi,m2^2 - целые числа. Положив m=mirri2, из теоремы 2.1 имеем G(x)sQJ,m,(x)0 (у) mod xv-l, где &J,mi(x) определяется выражением (2.9), у=х4 ,

у

^>=~^ » ®mtm2(y) " полином Холла разностного множества Di(Loi.P). Здесь Loi -

линейный функционал из GF(2m) в GF(2), р=о/ . Применяя теперь теорему 2.1 к &щт2(у), получим:

0(х)=ОГЧх)^(х<) вв,0,) modxv-l, гДе ^Ш1(У|) - полином Хола разностного множества D2(Lo2,p2) . Здесь Lo2 - линейный

функционал из GF^™') в GF(2), yi=Jr', Ci =— . С другой стороны при m=mi имеем:

2 1 -1

0(х)=?^' (x)0mj (ух) modxv-l .Отсюда, по лемме 2.2 получаем:

ОДт,(х)А:;т1(х<) = Q™' (х) modxv-l.

ЭТОТ результат был сформулирован в виде следующей леммы.

Лемма 2.3 [14]. Пусть N=kmiiTi2, k, mi,m2>2 - целые числа. Тогда

^,n,,(x)^;m2(xO = Qj (х) modxM .(2.16)

Пусть множество {GMW?} есть совокупность всех неэквивалентных GMW

разностных множеств с параметрами (2.13), построенных на основе совокупности различных базисных (не являющихся сдвигами друг друга) разностных множеств с параметрами

w=2m-l, /=2т'1,ц=2т-2 . (2.17) Обозначим через | GMW™ | мощность множества {GM WJ}. Тогда справедлива теорема.

Теорема 2.6 [14]. Пусть N=kmini2, где к>2, !щ?2, тг^З - целые числа. Тогда

{GMWJ'"» }=> {GMWJ1} и I GMW"lWj I > |GMW*1 | . (2.18)

Доказательство.

Пусть A e{GMW,7?}. Тогда по теореме 2.1 полином Холла 0(x) разностного

множества А есть 0(х)=й^г(х)бтз(^2) то<* xv-l, ГДе У2=* » 4г = — • Согласно лемме

2.3 это выражение можно привести к виду:

е^йГЧх^Дх') ВЫг(у2) modxv-l.

Обозначив еш1И2(х)= GJ;-t(x) 0mi(x^1) modxv-l ,получаем:

9(x).QS-4x) en(M2(^)modxv-l.

Последнее означает, что любое разностное множество А, построенное на основе (w, /, ц) базисного множества с т=Ш2, может быть также образовано на основе (w, /, ц) базисного множества с т= питг.

{GMWyi}z> {GMW*1}. Далее, можно показать, что число базисных разностных множеств для {GMWJ1"'1}, по меньшей мере, в <р(2м,тг -l)/m,m2 раз превышает число базисных множеств для { GMW^1}. Действительно, все базисные разностные множества для { GMW^1} являются также базисными и для {GMW™1^}. Последнее же в свою очередь является базисным для { GMWN,Wi }. При этом мощность любого класса {} равна <р(2т,тг -])/т1т2. Теорема доказана.

Рассмотрим теперь разностное множество D(L,a) с полиномом Холла 0(х)=ЭД(х)9ш(.у) mod xv-l и параметрами (2.13). Предположим, что существует такой немножитель t разностного множества D(L,a), что выполняется сравнение

Q;(x)ax"e«S(xf) modxM . (2.19)

Разностное множество t D(L,a) с полиномом Холла 0(х*)=Й™(х,)0т(У) mod xv-l изоморфно D(L,a) по определению. Тогда с учетом (2.19) имеем:

0(х')=ЭД(х)0тО/)х* modxM . (2.20) Возможны следующие два случая:

еи(/) = ет(.у)х* modxv-l , (2.21)

O.O'Ve.OOx" modxv-l . (2.22) Однако, в случае (2.21) в силу (2.20) получаем, что t D(L,a) является сдвигом D(L,a), что не возможно, так как t - немножитель D(L,a). В случае же (2.22) из Теоремы 2.2 и выражения (2.20) следует, что t D(L,a) и D(L,a) не эквивалентны, что также не возможно. Следовательно, наше предположение о существовании немножителя, для которого выполняется сравнение (2.19) не верно, и справедлива лемма 2.4.

Лемма 2.4 [14].

Пусть N==mk, m>3, k>l - целые числа, а t есть произвольный немножитель разностного множества D(L,a). Тогда

ОДОО* х-ЦЖ) modxM. Теорема 2.7 [14].

Пусть N=mkik2, m>l, к\ >2, к2>2, mi=mkl, m2=mk2 . Пусть А и В - GMW разностные множества с параметрами (2.13) и полиномами Холла соответственно 0А(х)^Й™'(х)еш1СУ1) mod хМ и вв(х)вау(х)вЯ|10г2) mod хМ, где где у,=х*,

Ь =2~^? У2=^' Ь =2^Т' 3 QSl(X) " Q"(X) TаKИe, 4X0 6z(x)5Q;i(x)9z^)3

0.^г(x)Qz(y2) mod xv-l есть полином Холла зингеровского разностного множества. Тогда

для эквивалентности разностных множеств А и В необходимо и достаточно, чтобы

0л(х)ех50в(х) mod хМ .

Доказательство.

Достаточность теоремы очевидна. Для доказательства необходимости предположим, что выполняется:

02{*)Вщ(П)*ф&)ещ(у\) mi*x*-l • (2.24)

Умножим обе части этого сравнения на произведение полиномов Холла

02(3/,)9z(iy2l). В результате получаем:

Gz(x) ея10>,) 62(у2) =xs9z(x') вШ2(у2) 02С,) modxv-l .(2.25) Умножим левую и правую части сравнения (2.25) на произведение Ti(yi)T2(y2) mod хМ, где Ti(yi)=l + y, +У?+... + УГН и Ъ(У2)=\ + Уг+у\+... + у^-х После упрощения, получаем:

е2(х)Т1(у1)Т2(у2)^х802(х,)Т,(у,)Т2(у2) mod xv-l , (2.26) что, так как t - немножитель, не возможно. Теорема доказана.

Найдем условия, при которых выполняется сравнение (2.23). Пусть N=pip2, где pi, рг>3 есть не равные друг другу простые числа. Рассмотрим два GMW разностных множеств А и В с параметрами (2.13) и полиномами Холла :

вА(х)«аВ(х)еР|0'1) modxM и вв(х)«ОИ(х)вр1Си2) modxM. Здесь epiCVi) и 6р2(у2) - полиномы Холла базисных разностных множеств. Предположим, что А ~ В, тогда согласно предыдущей теореме имеет место сравнение:

ОЙ(х)вР1СУ,)«>0!?(х)вР1СК2) mod хМ .(2.27)

Умножим обе части этого сравнения на произведение полиномов Холла 9* (у,) бр2 (у2) зингеровских разностных множеств таких, что

9z(x)sQpN'(x)9Ji(y1)Sxs^(x)0Pi(y2) mod хМ . (2.28) В результате сравнение (2.27) преобразуется в эквивалентное сравнение:

Ч,<*> ePi(^)^xs0J,U) 0Р2СУ2) modxM .

Отсюда, так как у2 = y,?l/?l = yf3, где 4з=^2^1=2Р1 - \/2Pl -1, в итоге получаем:

0р,(У?') 0p,U)-xS0p,(y.) ер>(У.*') modxM. (2.29) Так как Ср1,рг)—I, то можно показать, что (2Pl — 1,2А —= Кроме того степени полиномов 9pj(yfJ) и бр^^) меньше 2Л — 1. Следовательно, полиномы вр,(У?') и вР2(у,§') не содержат членов с целыми степенями уь Независимо от значения s для выполнения сравнения (2.29) необходимо выполнение сравнения: 9Pl (j^i)s х*' 6^ )

mod xv-l. Отсюда следует, что А - зингеровское разностное множество. Поэтому в силу эквивалентности множеств А и В множество В также должно быть зингеровское.

Итак, доказано, что совокупности всех неэквивалентных GMW разностных

множеств {GMW?'} и {GMW?L } не содержат общих элементов, т.е.

Рассмотрим теперь более сложный случай N=pip2P3. Здесь так же, как в предыдущем случае, pt ?3, рг ?3 и рз i>3 есть не равные друг другу простые числа. По

предыдущей теореме {GMW™* }=> (GMW* } u {GMW^ } для i, j=l,2,3 и

Рассмотрим следующие две совокупности GMW разностных множеств GMW{,Psh

GMW?|P' и выясним, что представляет собой их пересечение. Очевидно, что оно не пусто,

так как каждое из них содержит одно и то же зингеровское разностное множество. Предположим, что существует некоторое разностное множество С, отличное от зингеровского и принадлежащее этому пересечению С. Тогда должно выполняться следующее сравнение:

^Г,(х)ер1Р1(у1) = ОГ(х)вР(Р)(у2) modxM , которое, в свою очередь, эквивалентно сравнению:

%^К^)Щ^(УЛ1Рз(У2) modхМ .(2.30)

Здесь 6PlP2(xi) и 0PlPj(х2) - полиномы Холла базисных разностных множеств с параметрами (2.13), соответственно при mi=pip2 и m2=pip3, у|=дг', 4i = ~^Г,—"» У2=*, ^2

у

= — , A 9JLPL(X) и BP|PJ(X) - полиномы Холла зингеровских разностных множеств таких,

что

^^(х)в;,(у3)то<1х2",-,-1 и в^(х) SQ^(x)Qlt(yA)modx2'^-\ , где Уз = х2"' ~тп "1=х4*, и у4 = х2"1 ~т" ~1 = х4* .С учетом этого (2.30) принимает вид

Замечаем, что в левой части полученного сравнения только первый сомножитель содержит целые степени у|. Поэтому для вьшолнения этого сравнения необходимо, чтобы полином Холла вр^р, (yf*) из его правой части раскладывался на следующие множители:

^(yf5) s^*(yh eft(yf).

Приравнивая сомножители с целыми степенями yi, в итоге получаем: ер,Р,(У|) si?U0ri) ^Of5) mod После сокращений, находим, что 0^(yf°') = Я^Су?)-Отсюда, без нарушения общности положим t=l. Таким образом, установлено, что если GMW разностное множество принадлежит С , то его полином Холла имеет вид:

ec^(*)^(y,) 4ktf)-Q9A0Ofi!U&i) modxM,

где ЬЬРЫл и )¦ eft(>f) mod xv-l. Итак, получен следующий результат:

С= {GMWp,Pl}n{GMWp,Pj}={GMWJ5'} .(2.31) Аналогично доказывается, что

{GMW™1} n {GMW™3 }={GMW>' }, (2.32)

{GM WP,P)} n {GMWp,Pj }={ GMWP}} .

Теперь положим N=pip22, т.е. pi=P2 • Учитывая, что при получении предыдущего результата условие строго неравенства pi и р2 нигде не использовалось, находим:

{GMWJ'P'} n {GMWP,J }={ GMW*} . (2.34) Далее, пусть N=pf,p2,...p^', где pi ,p2-..ps есть простые отличные от единицы числа, а

ai,ai...,Os - целочисленные, положительные показатели. Тогда индукцией по s , используя предыдущее, получим:

{GMW,J'}n{GMW^ }={GMW^"Nj)} , (2.35)

где Ni , N2 — некоторые делители N. Этот результат крайне важен для получения аналитического выражения числа GMW разностных множеств и поэтому сформулируем его в виде самостоятельной теоремы.

Теорема 2.8 [14]. Пусть N | Ni и N | Nj и (N„Nj)>3. Тогда

{GMW?'} п {GMW„' }={ GMW^''Nj)}. (2.36)

Введем следующие обозначения. Пусть ЛГ, = N/p^, ?1*1,5, NH = (Л^,Л^) = N/p^p^ , iiii, i2€l,5. Пусть Ni(iiл ={Nii1Nii...9Nik) = N/p,tp,i...pi^ iiN,2 f = (NliN1...yNt) = N/pip2...ps. Тогда {GMWN''} есть совокупность неэквивалентных GMW разностных множеств с параметрами (2.13), построенных на основе базисных разностных множеств с параметрами (2.17) при т= . Аналогично {GMW*'" *} есть совокупность неэквивалентных GMW разностных множеств, строящихся на основе базисных разностных множеств с параметрами (2.17) и m=Niii ik, а {GMW,J'r*}есть

совокупность неэквивалентных GMW разностных множеств, строящихся на основе базисных разностных множеств с параметрами (2.17) и n=Ni2...f.

INI N

Обозначим через I GMWN I мощность множества {GMWN л}, а через Мы ( ^ соответственно мощность класса зингеровских разностных множеств с параметрами (2.13) при N=NM j .

Пусть Nj(jj i >6 и не простое число. Тогда согласно следствию 2.1 и теореме 2.5 имеем:

I GMW>-* | = (| GMWNJIIJ ^ l+l)MN^ % -1 . (2.37)

Действительно, множество {GMW,/1'1 *} строится на основе базисных разностных множеств

с параметрами (2.17) при m=Nn * . Число всех базисных множеств при m=NiiiJkравно

произведению суммы числа неэквивалентных друг другу классов GMW и зингеровского разностного множества на мощность этих классов MNJ| ^ . Отсюда, учитывая, что одно из

базисных множеств соответствует зингеровскому разностному множеству с параметрами (2.13), приходим к формуле (2.37). Рассмотрим случай, когда Ni(jj , есть простое число.

Тогда

I GMW**' Ч = I BNmi J -1 , (2.38) где I BN.(. I - мощность соответствующих базисных разностных множеств с параметрами (2.17) при т=г4^ ^.Очевидно, Bi=B2=l. Обобщая (2.37) и (2.38), получаем:

I GMWNN*'* |= (I GMWNI(II Л 1+1) А^ л -1 , (2.39)

где A v.

N и lj.lt

GMW vt ф О
- в противном случае

Для определения числа неэквивалентных GMW разностных множеств с параметрами (2.13) и ^р^'р"2..^*" воспользуемся известным из комбинаторного анализа принципом включения и исключения [43]. В соответствии с ним множество {GMWN} рассматривается как некоторое множество элементов со свойствами {Р^}, И=1,*, где элемент ВЕ{ОМ>^ы} обладает свойством Р4 , если ge{GMWN', }. Применив теорему 2.8, получаем, что % обладает свойствами Р- ,Р| ...,Р4 , 11 <Т2<...<1к, п,12,.«-1к€ 1,$, если

Отсюда следует, что I GMW*'•,, 4 I есть число элементов со свойствами Р4( ,Р^ ...,Р,к. Применяя принцип включения и исключения, в результате получаем

42_j

I,(2.40)

Подставляя в формулу (2.40) выражение для | ОМ\Ум'А"* I из (2.39) и учитывая, что 0=(1-1)8=1-С] + С) + ...+(-1)* , получаем следующую рекуррентную формулу:

ІGMWN|=E(|GMW +1)А -?(|0М>Ум +1)Аы1,1 +~+

i,+ (-!)*"' ? (|GMWNi,J+1)AN?J^ .(2.41)

i,<»,...Тогда число PN различных ПСП GMW для всех возможных значений N может быть вычислено по формуле:

PN=IGMWN|MN . (2.42) На основе полученных выражений для N<18 в [14] были рассчитаны:

- число I GMW^ 1 неэквивалентных классов ПСП GMW длины 2N-1, строящихся на основе

базисных последовательностей длины w=2m-l;

число I GMWN I всех неэквивалентных классов ПСП GMW длины 2N-1;

мощность MN классов;

общее число PN ПСП GMW.

Результаты вычислений приведены в таблицах 2.3 и 2.4. При этом в качестве базисных разностных множеств наряду с зингеровскими использовались разностные множества Лежандра, Холла, Бомера-Фридриксена [45], а также вМШ. Более подробно свойства последовательностей, полученных на основе разностных множеств Лежандра, Холла и Бомера-Фридриксена будут рассмотрены в 3-й главе настоящей диссертации. Впервые эти результаты были опубликованы в 1979г в работе [14]. К сожалению, полученные в этой работе результаты остались не замеченными ни в нашей стране, ни за рубежом. Всплеск интереса к последовательностям вМАУ в 90-х гт. привлек внимание к проблеме нахождения их численности ведущих ученых мира и, прежде всего, С. Голомба и др. В общем виде эта задача для ц-ичных каскадных ПСП зингеровской природы

Число неэквивалентных классов ПСП СМ\У в зависимости от т.

была решена в работе [52]. Следует отметить, что ее результаты в случае двоичных ПСП вМ>У полностью совпадают с результатами [14].

Теперь настало время сделать одно важное замечание. Формулы (2.39) и (2.41) были получены исходя из предположения, что для не простых N существуют только два типа разностных множеств: зингеровские и СМ>У. Однако недавно опубликованные работы [11,31] показывают, что для таких N могут существовать и другие типы разностных множеств. Краткий обзор получаемых на их основе последовательностей приведен в разделе 1.2. Отсюда следует, что для вычисления общего количества последовательностей можно воспользоваться только формулой (2.40). Формулы же (2.39) и (2.41) в силу последних результатов оказываются не полными, поскольку не отражают все возможные базисные последовательности. Исходя из этого обозначим через {Вм } и | Вм

"».4 -«»

N

множество и соответственно мощность всех базисных последовательностей длины 2 Л -1.

Тогда по-прежнему | СМ\У*% | = | Вм ^ I -1

С учетом этого выражение (2.40) преобразуется к следующему

ь<1,

В таблице 2.5 для всех N^20 представлены скорректированные результаты расчета значений параметров | GMWN I и PN. При этом в качестве базисных наряду с известными последовательностями использовались недавно полученное семейство последовательностей No-Golomb-Gong-Lee-Gaal, а также два класса последовательностей длины 511, найденные Дрейером [31]. В результате число базисных последовательностей для т=8, т=9 и т=10 увеличивается с 31, 95 и 479 до 63, 143 и 599 соответственно.

Таблица 2.5.

Скорректированые значения параметров | GMWN I и PN .
N m Bm-1 IGMWN| MN PN 6 3 1 1 6 6 8 4 1 1 16 16 9 3 1 1 48 48 10 5 7 7 60 420 3 1 12 144 1728 12 4 1 6 11 14 7 79 79 756 59724 15 3 1 8 1800 14400 5 7 16 8 63 63 2048 129024 18 3 1 249 7776 1936224 6 11 9 239 20 4 1 600 24000 14400000 10 599

В заключение следует отметить, что экспериментальная проверка правильности выведенных расчетных формул довольно сложна, а при больших значениях N просто не возможна. И все же для одного частного случая N=12 такая проверка была проведена. С помощью имитационного моделирования на компьютере для т=3, т=4 и т=6 были построены ПСП, являющиеся векторами инцидентности всех GMW разностных множеств с параметрами (4095, 2048, 1024). При этом использовался новый метод генерации [49]. В результате сравнения этих ПСП, было установлено, что ОМ\У|2 с СМ\У,*, тогда как СМ>У4 сгОМ\У,62. При этом І вМ>У4 |=1,а | ОМ\У,62 | =11. Таким образом, ОМ\У,2= I СМ\\',4 | + I ) =1+11=12. Заметим, что аналогичные результаты были получены

при нахождении общего числа последовательностей вГу/Ш каскадного типа [52].

2.4. Статистические свойства

Анализ статистических свойств последовательностей вМ>У будем проводить в сравнении с соответствующими статистическими свойствами порождающих их ш-последовательностей. Согласно широко известной аксиоматики псевдослучайных последовательностей [13] последние в идеале должны удовлетворять следующим критериям случайности:

критерий Ш (свойство сбалансированности): в каждом периоде последовательности число 1 отличается от числа -1 не более чем на единицу, т.е.

<1;

критерий Ю. (свойство серий): в течение периода последовательности половина серий 1 и -1 имеет длину 1, одна четверть - 2, одна восьмая - 3 и т.д.;

критерий Ю ( свойство корреляции): если последовательность почленно сравнивать с любым ее циклическим сдвигом на длине периода этой последовательности, то число совпадений отличается от числа несовпадений не более, чем на единицу. Фактически это

означает, что

С(т) = ±апап

<. 1 для всех 0<Т<У.

Паї

Всем этим критериям в точности удовлетворяют т-последовательности, причем для них

? V

строго выполняются равенства ^а„=-1и С(т) = ^алаяч.г =-1, т.е. автокорреляционная

п-1 л»1

функция является двухуровневой со значениями 2м-1 и -1. Кроме того, т-последовательности обладают важным для практического применения аддитивно-циклическим свойством, состоящим в том, что сумма по модулю два двух любых сдвигов т-последовательности также является ее некоторым сдвигом.

Что же касается нелинейных последовательностей СМ'М, то, как было показано в разделе 2.1, они обладают точно такими же свойствами Ш и ЯЗ, что и родственные им т-последовательности. Однако в отличие от т-последовательностей свойство К2 выполняется лишь для серий длины равной или меньшей к=Ы/т. Это устанавливается следующей теоремой [4].

Теорема 2.9.

Пусть {Ь„} есть последовательность вМ\У периода 2м-1, К=тк. Тогда число Ыа позиции внутри периода {Ь„}, на которых встречается 1-серия а\ &г... aj определяется выражением

2"\ дляд*0, \<>JТак, например, для N=10=5*2, одиночные серии (1) и (0) встречаются на периода.

соответственно 512 и 511 раз, двойные серии (01), (10), (11) - 256 раз, а (00) -соответственно 255 раз. В процессе математического моделирования последовательностей разной д.ші\ы

было установлено, что в частоте появлении более длинных серий нет регулярного порядка как случае т-последовательностей, число их случайно, а вероятность серий длины более N+3, состоящих из одних 1 или нулей равна нулю.

Нетрудно проверить, что последовательности ОМ>У в общем случае не обладают и свойством аддитивно-циклического сдвига. Для последовательностей вМ^У на основе нелинейных базисных последовательностей это утверждение очевидно. В случае же

базисных т-последовательностей это верно лишь частично, поскольку аддитивно-циклическим свойством обладает лишь подмножество, состоящее из равномерно сдвинутых на ?, разрядов копий одной и той же последовательности ОМ\У, которые образуют подгруппу относительно операции сложения по модулю два порядка 2т-1. Причем всего таких подгрупп ровно 4-