2.5. Структурные свойства
Говоря о структурных свойствах псевдослучайных последовательностей, будем подразумевать, прежде всего, различные типы отношений, связывающих их элементы, а также сами эти последовательности между собой.
Структурные свойства последовательностей СМ\У, равно как и т-последовательностей основываются на рассмотренных в разделах 2.1-2.2 свойствах порождающих их разностных множеств. Исследования структур этих и им подобным математических объектов началось более трех десятилетий назад. Так в начале 70гг. Венгом была сформулирована и доказана следующая замечательная теорема о разложении или декомпозиции т-последовательностей [53].Теорема 2.10.
п_
Пусть {тп} есть двоичная т-последовательность длины 2М-1=П1 х пг , а Мпп есть матрица порядка щ х пг с элементами ау=тп, п=0, 1, 2,..., 2**-2, где 1=п-П1
целые числа, начиная от нуля, и пусть П2~2т-\. Тогда каждая строка матрицы
М есть либо т-последовательность длины 2т-1, либо последовательность из 2т-1
нулей. Причем число таких нулевых строк в точности равно 2К-1/21"-1 _2т>4"т.
Отметим, что полученную теорему Венг применил исключительно к исследованию т-последовательностей, хотя у него и имеется ссылка на известную работу [44]. Почти тогда же Бомер в своей монографии [45], посвященной циклическим разностным множествам, интерпретируя Теорему 2.1, также представил т-последователъность в виде таблицы размером 2т-1х?, назвав ее таблицей представителей элементов т-последовательности (об этом уже говорилось в разделе 2.2). Декомпозиции по Венгу и Бомеру, хотя и обладают одинаковыми с точностью до транспонирования структурными свойствами, вместе с тем являются различными формами представления одной и той же т-последовательности. Заметим, что в силу теоремы 2.1 точно таким же свойством декомпозиции должны обладать и родственные т-последовательностям последовательности вММ. Табличное представление последовательностей по Бомеру, без всякого сомнения, можно считать фундаментальным, поскольку большинство полученных в диссертации результатов в той или иной степени основываются на этом представлении.
Более подробно на этом мы остановимся при рассмотрении вопросов взаимной корреляции (Глава 3) и генерации (Глава 4).Следующее структурное свойство последовательностей связано с понятием
децимации, введенным Голомбом [13], и обозначающим замещение последовательности {а„} последовательностью {а№}, образованной элементами последовательности {ап} с номерами Ш (тос! V). В общем случае с учетом существующей связи между разностными множествами и соответствующими им векторами инцидентности имеет место следующая теорема.
Теорема 2.11.
Пусть {ап} есть последовательность, соответствующая разностным множествам с параметрами (2.13), т.е. разностным множествам типа Адамара. Тогда последовательность {ащ}, где I - есть множитель разностного множества, является сдвигом исходной последовательности {осп}. Если же 1 есть немножитель разностного множества, тогда последовательность {о<п} есть изоморфная {ап} последовательность того же периода.
Во 2-й главе было показано, что множители вМ>У разностных множеств при q=2 являются исключительно степенями числа два и образуют мультипликативную группу г=1, 2, 21д"1 порядка N. Очевидно, что децимации с этими числами последовательности СМУ/ приводят с точностью до сдвига к той же самой последовательности. Причем согласно теореме Манна-Джонса [43] существует единственный циклический сдвиг последовательности GMW, фиксируемый каждым ее множителем. Подобный сдвиг в литературе получил название характеристического сдвига [18]. Заметим, что сказанное в равной степени относится и к семейству т-последовательностей.