<<
>>

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Теорема 2.1 [44].

Пусть 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). Положим v=qN-l/q-l, w=qm-l/q-l и cj=v/w. Пусть а есть примитивный элемент GF(qN) и пусть р=а^. Пусть 0(х) и Оо(у) есть полиномы Холла соответственно разностных множеств D(L,c?) и D(Lo,P). Пусть у=х^. Тогда

П(Х)=][УУ

m,

(2.9)

Суммирование здесь производится по всем i, для которых

L2(ct>0, 0Полином Холла 0о(у) разностного множества D(Lo,p) имеет следующие параметры:

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)

РОССИЙСКАЯ ГОСУДАРСТВЕННА*
41 БИБЛИОТЕКА

является последовательностью GMW длины 2 -1.

Теперь сформулируем условия, при которых два разностных множества В и С с параметрами (2.7), полученные этим способом, являются эквивалентными. Поставим в соответствие каждому (w, /, \х) разностному множеству о с полиномом Холла Эь(у) некоторое (v, k, X) - разностное множество В с полиномом Холла 6в(х)=О(х)0ь(х^) .

Теорема 2.2 [44].

Пусть q есть степень простого числа р, и пусть N есть целое, N>2. Пусть m | N, N>m>2. Пусть v, к, X, w, /, ц определены формулами (2.7) и (2.10), ?=v/w, и пусть Q(x) есть полином, определяемый выражением (2.9). Пусть b и с есть (w, /, ц) разностные множества. Тогда (v, к, X) разностные множества В и С эквивалентны тогда и только тогда, когда b является циклическим сдвигом с.

Заметим, что хотя данная теорема и включает случай 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На втором шаге алгоритма строится таблица представителей элементов D(L,a) [45], которая получила еще название таблицы декомпозиции т-последовательности [14]. Эта таблица состоит из ?=2-1/2-1 строк и w=2 -1 столбцов с элементами, определяемыми

выражением = ¦

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. Соответственно последовательность с элементами bn^by для всех n=i+?j есть последовательность GMW с параметрами (2.13). Рассмотрим пример построения последовательности GMW длины 63. В соответствии с изложенным выше алгоритмом возьмем примитивный многочлен степени 6 над GF(2) вида f(x)=x6+x+l. Пусть а1 =Cio+Ciia+Ci2a2+...+Ci5a5 есть разложение а1 в базисе 1,а, а2,...а5 с коэффициентами (Cio,Cii,.-.,Ci5). Тогда имеем Ца'^ю . Следовательно, ieD(L,a)oL(a')=aio =1. Отсюда имеем, что D(L,a)={0, 6,11, 12, 16, 18, 21, 22, 23, 24, 26, 30, 31, 32, 35, 38, 40, 41, 45, 47, 48, 51, 52, 54, 56, 58, 59, 60, 61, 62}. Далее, так как N=6=3*2 и т=3, то ?,=9. Ниже приводится таблица 2.1 представителей элементов D(L,a), состоящая из 9 строк и 7 столбцов.

Базисные разностные множества состоят из двух изоморфных (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].

Подготовка к ЕГЭ/ОГЭ
<< | >>
Источник: Кренгель Евгений Ильич. ИССЛЕДОВАНИЕ И РАЗРАБОТКА НОВЫХ КЛАССОВ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И УСТРОЙСТВ ИХ ГЕНЕРАЦИИ ДЛЯ СИСТЕМ СКОДОВЫМ РАЗДЕЛЕНИЕМ КАНАЛОВ. 2002

Еще по теме 2.2. Алгебраическо-комбинаторные основания построения ПСП вМУ:

  1. §1. Субъект преступления как критерий классификации посягательств против правосудия
  2. 12. Взаимодействие политики с другими сферами общественной жизни.
  3. Научная новизна исследования
  4. 2.2. Алгебраическо-комбинаторные основания построения ПСП вМУ
  5. 3.4. Взаимно-корреляционные пики последовательностей СМ
  6. Использование задачного подхода
  7. а) Возможность философской антропологии
  8. 21.2.2. Планирование порожнего и общего пробега вагонов
  9.   § 48. Философские основания эпистемологии  
  10.   ЧТО ТАКОЕ АНТРОПОЛОГИЯ   I860 
  11.   ЗАДАЧИ ПОЗИТИВИЗМА И ИХ РЕШЕНИЕ 1868  
  12.   ДАО-ДЭ: ФИЛОСОФСКАЯ РАЗРАБОТКА ПОСЛЕРОДОВОГО МИРОВОЗЗРЕНИЯ
  13. Аналогия и моделирование
  14. ИСТОЧНИКИ И МЕХАНИЗМЫ КУЛЬТУРНОЙ ДИНАМИКИ
  15. И.З. Шишков ФОРМИРОВАНИЕ И ОСОБЕННОСТИ КУЛЬТУРЫ И ФИЛОСОФИИ НОВОГО ВРЕМЕНИ
  16. ГЛАВА II. СЕКУЛЯРИЗМ И ИДЕЙНО-ПОЛИТИЧЕСКИЕ ОСНОВАНИЯ ПОСТРОЕНИЯ ИН ДИЙСКОЙ НАЦИИ
  17. ОСНОВАНИЯ ПОСТРОЕНИЯ СИСТЕМЫ ПРАВА