2.1. Разностные множества и последовательности с двухуровневой ПАКФ
Множество D, состоящее из к вычетов d], d2,. ..,dK по модулю v, называется (v, к, X) - циклическим разностным множеством, если для каждого d*0 mod v существует
точно X упорядоченных пар (dj, dj), dj, dj eD таких, что dj - dj =d mod v.
Легко проверить, что сложение по модулю v элементов разностного множества D с некоторой константой приводит к образованию нового разностного множества с теми же самыми параметрами.
При этом разностное множество С называется сдвигом разностного множества D={di>d2, ...Дс}, если C={d|+s d2+s, ....dk+sjmod v.Параметры циклического разностного множества связаны следующим соотношением:
к(к-1)=Цу-1).
Полином Холла разностного множества D={di,d2, ...,dK} есть
со свойством [43]
e(x)9(x*>k-^ + A.Tv(x)modxv-l , (2.2)
где Tv(x)=l + х + х2 +... + xv*1.
Вектор инцидентности b разностного множества определяется следующим образом:
0,ntD \,neD
Последовательность {Ьп}, образованная повторением вектора инцидентности с периодом V, имеет двухуровневую периодическую автокорреляционную функцию (ПАКФ) РььСО» задаваемую выражением:
V-I
п=0
к, т = 0 mod v [Л, T*0modv
И, наоборот, если задана периодическая двоичная последовательность {bn} с двухуровневой ПАКФ, то один период {Ь„} является вектором инцидентности разностного множества. Последовательность квадратных корней из единицы {а,,}, основанная на разностном множестве D, определяется следующим выражением:
v-l
=(-!)'¦ =l-2*„ . (2.3) ПАКФ Раа(т) последовательности {ап} также двухуровневая с
v, т=о mod V
п=0
у-4к+4Л, T^omodv ' (2'4)
Из выражения (2.4) следует, что любой двоичной последовательности с двухуровневой ПАКФ может быть поставлено в соответствие циклическое разностное множество. Иными словами методы построения циклических разностных множеств одновременно являются и методами построения последовательностей с двухуровневой ПАКФ и наоборот.
Два разностных множества D={diid2, ...,dK} и €={01,02, ...,ск} эквивалентны, т.е.
D~C, если существуют такие взаимно простые целые s и t, что во(х) =xs 9c(xt) mod xv -1.Если существуют такие целые s и t, где (t, v)=l, что множества {tdi, td2, ...,tdk} mod v и {di+s d2+s, ...,dk+s} mod v совпадают в каком-либо порядке, т.е. выполняется сравнение GD(X)Xs = бо(х1) mod xv -1, то t называется множителем разностного множества D={dit d2, ...,dk}. С алгебраической точки зрения множитель разностного множества t является автоморфизмом соответствующей циклической блок-схемы [43]. Множители образуют группу, называемую группой множителей блок-схемы. Если D ~ С и Б не является сдвигом С, то в соответствии с изоморфизмом блок-схем, В и С есть изоморфные разностные множества, а коэффициент X - немножитель разностного множества С. Все изоморфные друг другу разностные множества образуют класс разностных множеств, а множество всех неэквивалентных классов, имеющих сходную природу, - семейство разностных множеств. Из существующего разнообразия разностных множеств наибольший интерес представляют разностные множества типа Адамара, к числу которых относятся разностные множества Зингера (класс ?) и Гордона, Милза, Велча (ОМ\У) с параметрами [14,44]
у=2*-1, к=2ы"'-1, А.=2м"2-1 , (2.5) числовые разностные множества Лежандра (класс Ь), Холла (класс Н) и Якоби (класс Т) с параметрами у=4Ы, к=21-1, Я.=1-1 [10], а также целый ряд новых недавно открытых разностных множеств [39]. При этом последовательности, соответствующие зингеровским разностным множествам, оказываются хорошо известными ш-последовательностями со значением бокового выброса ПАКФ, равным -1 [45]. Очевидно, что двоичные последовательности, соответствующие другим классам разностных множеств с параметрами (2.5), имеют точно такие же ПАКФ. В 1962г. Гордоном, Милзом и Велчем [44] на основе зингеровских разностных множеств были открыты и построены новые классы разностных множеств с параметрами (2.5), где N=1^4, т>3, к>2. В литературе эти разностные множества получили название вМ\У разностных множеств [47].
За рубежом первое упоминание, касающееся прикладного аспекта этих разностных множеств, можно встретить в работе [10]. И то лишь косвенным образом в библиографии раздела, посвященного псевдослучайным последовательностям типа Адамара. Далее следует почти двадцатилетний период молчания, конец которому положила вызвавшая широкий отклик статья Велча и Шольца [46], посвященная последовательностям ОМ\У. К сожалению, по не известным причинам авторы ограничились рассмотрением лишь некоторых классов разностных множеств,определив при этом соответствующие этим классам последовательности как последовательности ОМ\У. Это внесло определенную путаницу при дефиниции последовательностей, получаемых на основе других, не рассмотренных в [46] классов СМ\У разностных множеств. В результате многие такие последовательности без должного на то основания получили название т-подобных, каскадных, расширенных, геометрических, новых последовательностей и т.д. [31,34,36,47,48]. Заметим, что десятилетием позже Шольц снял эту неоднозначность, определив все соответствующие вМ>У разностным множествам последовательности уже как последовательности [46]. В нашей стране
первые работы по исследованию последовательностей, на основе ОМ\У разностных множеств появились в середине 70гг. [21,22]. Правда, в отличие от [46], они получили название последовательностей Гордона, Милза и Велча, и это название относилось к последовательностям, получаемым на основе всех вМ\^ разностных множеств. Более подробно история этого вопроса изложена в [49,50]. Рассмотрим теперь математические аспекты построения этих новых классов последовательностей.