<<
>>

4.4. Генератор последовательностей GMW на основе сдвигов т-последовательностей.

Касаясь практической реализации генератора [46], надо отметить, что, несмотря на свою достаточно простую и компактную структуру, его разработчику предстоит решить целый ряд далеко не тривиальных задач, обусловленных особенностями данного метода.

Остановимся на этом вопросе более подробно.

Первая задача, которую необходимо решить, связана непосредственно с выбором примитивного полинома степени к над GF(2m). Ведь

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

Следующая задача связана с построением самого генератора q-ичной т-последовательности по имеющемуся примитивному полиному. Возникающие здесь трудности обусловлены необходимостью использования нетривиальных арифметических операций над GF(q). Очевидно, что и в этом случае также не обойтись без написания специальных компьютерных программ.

И, наконец, последняя по порядку, но не по сложности задача связана с разработкой ПЗУ генератора. Дело в том, что в силу метода построения структура ПЗУ полностью определяется элементами подполя GF(2m) поля GF(2N), представленного в базисе 1, р, р2,..., Р"1*1, где р - примитивный элемент подполя GF(2m). Трудности, возникающие в связи с решением перечисленных задач, в значительной мере ограничивают практическое использование последовательностей GMW в технике связи. Поэтому вполне своевременным представляется нахождение такого метода генерации, который бы способствовал более широкому их практическому применению. Предлагаемый новый, более простой метод генерации последовательностей GMW основан на формировании сдвинутых копий двоичной m-последовательности значности v. При рассмотрении этого метода будем опираться на известные свойства линейных функционалов над полями Галуа [45].

Пусть L-линейный функционал из GF(2N) в GF(2) такой, что Ц1)=1. Соответственно, пусть Lo-сужение L до подполя GF(2m), а Ьг-линейный функционал из GF(2N) в GF(2m) такой, что для VxeGF(2N) выполняется условие:

L0(L2(x)P)=L(xp) для VpeGF(2m). (4.2)

Обозначим через {CJ}, 0^j<2m-l, базисную последовательность длины 2т-1, образованную на основе некоторого разностного множества с параметрами (2.17). Тогда, используя результаты [14], можно показать, что любая последовательность GMW с точностью до сдвига может быть представлена в следующем виде:

b„=f(L2(an)) , (4.3)

где a - примитивный элемент GF(2N), 0f(PJ)=Cj для всех 0^<2т-1 и f(0)=0 . (4.4)

Заметим, что при f==Lo последовательность {Cj} уже сама определяется условиями (4.4), при этом последовательности {bn} и {Cj} являются ш-последовательностями со значностями соответственно V и w. Рассмотрим теперь последовательность {mn}, определяемую условием:

m„=L2(an), 0Согласно [4,13] последовательность {mn} является q-ичной т-последовательностью злачности 2N-1. Представим последовательность {т„} в виде двумерной таблицы размерности EXW, в которой каждый элемент т„ СТОИТ на пересечении і-ой строки и j-ro столбца, где.

0<і<є и 0{pSl+J} ,(4.5) где 0<і<є, 0?jНетрудно убедиться, что все такие ненулевые строки являются циклическими сдвигами друг друга и могут быть получены из первой строки с і=0 вида {р-1}, 0^=Ь0(Р3)для всех 0Согласно построению последовательность {d,} есть m-последовательность значности 2т-1. Введем теперь функционал L\: GF(2m) -> GF(2m), определяемый из следующих условий:

Li(W*dj + +... + а<і+т.,РпИ и L,(0)=0 . (4.7)

Покажем, что Li есть взаимно однозначное отображение GF(2m)—>GF(2fn). Воспользуемся для этого известным свойством m-последовательности, иногда называемым свойством окна. Согласно этому свойству любой ненулевой набор из m последовательных символов т-последовательноста значности 2т-1, встречается на ее периоде ровно один раз, причем число различных таких наборов равно 2т-1. А поскольку коэффициенты при степенях р в правой части выражения (4.7) образуют именно такие наборы, то Li - взаимно однозначное отображение.

Обозначим через g: GF(2m)-> GF(2) функционал, определяемый следующими условиями:

gOLiWOHd и g(0)=0. Тогда в силу построения последовательность {bn } вида:

Ь„Ч(Ьі(Ь2(ап))) . (4.8) оказывается эквивалентной последовательности {b,,}, определяемой (4.3). Подставляям (4.7) в (4.8) с учетом (4.2), (4.5) и (4.6), в итоге получаем:

bo'=g(L(an)+ ЦОР+...+ ЦоҐ*"1'1^"1-1) . (4.9) Из анализа (4.9) видно, что коэффициенты L(an), L(an+t),... L(an+€(m",)) представляют собой сдвинутые на є чипов копии m-последовательности {Ца")}. С другой стороны эти коэффициенты могут быть интерпретированы как m-разрядные адреса, по которым в ПЗУ записаны символы последовательности {CJ}, причем по нулевому адресу в ПЗУ всегда должен находиться символ "О". В результате построенный в соответствии с (4.9) генератор

128

последовательностей GMW будет состоять из последовательно включенных генератора сдвинутых копий m-последовательности злачности v и ПЗУ базисной ПСП, состоящего из 2Ш однобитных слов. Функциональная схема этого генератора представлена на Рис.4.6.

Рис. 4.6.

Генератор ПСП GMW по схеме Кренгеля-Мешковского.

Сопоставление нового генератора с генератором [46] показывает, что, несмотря на почти одинаковую элементную сложность, новый генератор оказывается более предпочтительным в виду явно очевидной простоты его реализации. Главным неоспоримым преимуществом предлагаемого генератора является то, что все арифметические операции выполняются в нем исключительно по правилам двоичной логики над GF(2). Это, очевидно, значительно упрощает его разработку по сравнению с генератором [46], в котором используется более сложная арифметика над GF(q). В отношении генерации сдвинутых копий двоичной т-последовательности следует сказать, что этот вопрос в литературе [24] освещен достаточно подробно и никаких трудностей здесь не возникает. Предлагаемый метод может быть также эффективен и в случае его программной реализации. Особенно это относится к генерации

сверхдлинных последовательностей, применяемых для защиты передаваемых по каналам связи данных. Следует отметить, что область применения этого метода не ограничивается только последовательностями GMW. Данный метод может быть также использован для генерации и других двоичных последовательностей, ооразованных на основе 2 -ичнои т-последовательности и разностных множеств [18].

В заключении в качестве примера рассмотрим генерацию последовательности GMW

12 12

значности v=2 -1=4095,где N=12 и ш=3. Пусть примитивный элемент а поля GF(2 )

является корнем неприводимого примитивного полинома [68]:

X^+X'^X'+xVl. (4.10)

Тогда генератор сдвинутых копий m-последовательности должен формировать т=3 сдвинутых последовательностей bn, bn+585, bn+ii70 , где bn=L(an). Нетрудно убедиться, что

последовательности b„+ss5 и bn+ii70 являются задержанными соответственно на 3510 и 2925 чипов копиями m-последовательности bn. Формирование задержанных копий т-последовательносги наиболее просто осуществить суммированием по модулю два соответствующих разрядных выходов регистра сдвига генератора m-последовательности Ь„, выполненного по схеме с вынесенными сумматорами. Однако вид обратной связи при этом будет уже определяться полиномом:

X^+X^XVX+I , (4.11) двойственным к полиному (4.10). Пусть у корень примитивного полинома (4.11), а bn, b„-i, ...,bn^N.i) - последовательности, образующиеся на разрядных выходах регистра сдвига генератора m-последовательности. Тогда последовательность Ь„.і для всех 0^1bn-i=lobn+l і bn. і,... ,+1N- І b„-где вектор двоичных коэффициентов (координат) lo, li,..., 1N-I ИЗ GF(2) численно совпадает с соответствующими коэффициентами в разложении элемента у1 по базису 1, у, у2,...,)^"1. В результате для bn+585=bn-3Sio и bn+ii70=bn-2925 с помощью компьютера находим, что:

bn+585==bn+bn-|+bn.2+bn.3+bn-5+bn.7+bn.io, а Ьп+1170=bn.i+b,v2+bn-8+bn-9+bn-10.

Образуем теперь 7-ми элементную ненулевую последовательность {dj}, где в соответствии с (4.6) dj=b585j , 0^j<7. Это всегда можно сделать путем соответствующего выбора начального состояния генератора последовательности bn . Тогда при начальном состоянии So=l последовательность {dj} имеет вид: {dj}=l 101001. Для построения ПЗУ в соответствии с (4.7) образуем таблицу 4.1, в которой каждому 3-х элементному набору символов последовательности {dj} ставится в соответствие его порядковый номер j, а наборы при этом рассматриваются как двоичные адреса.

Таблица 4.1. Взаимосвязь адреса и j.

АДРЕС J 1 1 0 0 1 0 1 1 0 1 0 2 1 0 0 3 0 0 1 4 0 1 1 5 1 1 1 6

Для генерации последовательности GMW выберем теперь в качестве базисной последовательность {CJ}=1 001011, обратную к {dj}. Заметим, что для рассматриваемого

случая существует всего только одна базисная последовательность. Затем поместим символы последовательности {CJ} по адресам Таблицы 4.1 в соответствие со значениями индекса j. Тогда, учитывая, что по нулевому адресу всегда находится символ 0, после упорядочения таблицы по возрастанию адресного параметра получаем таблицу 4.2, полностью определяющую структуру ПЗУ генератора.

Таблица 4.2

Структура ПЗУ генератора ПСП GMW длины 4095.

АДРЕС символ 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1

После этого не представит особого труда построить и сам генератор, функциональная схема которого изображена на Рис.4.7.

В Приложении 2 представлены тексты программ вычисления координат векторов сдвигов, используемых для построения генераторов ПСП GMW для N=12, 14, 15, 16, 20, 32, 48 и 63. Здесь же приведены тексты программ, моделирующие его работу.

Выводы

1. Проведен сравнительный анализ известных схем генераторов последовательностей GMW.

2. Предложен новый простой метод генерации двоичных последовательностей GMW, на основе генерации сдвинутых копий двоичной m-последовательности той же длины. Показано преимущество данного метода по сравнению с известным методом Велча-Шольца, основанного на генерации q-ичной m-последовательности.

І

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

Еще по теме 4.4. Генератор последовательностей GMW на основе сдвигов т-последовательностей.:

  1. Целью диссертационной работы является конструирование новых классов ПСП
  2. Основные положения, выносимые на защиту.
  3. Краткое содержание работы.
  4. 1.2. Последовательности для систем связи по технологии DS-CDMA
  5. Глава 2. Математические основы построения классов ПСП GMW и их свойства
  6. 2.6. Линейная сложность
  7. З.5. Последовательности
  8. Глава 4. Генераторы последовательностей GMW
  9. 4.1 Краткая историческая справка
  10. 4.2. Декомпозиционные генераторы последовательностей GMW
  11. 4.3. Генератор последовательностей GMW на основе следов полей Галуа
  12. 4.4. Генератор последовательностей GMW на основе сдвигов т-последовательностей.
  13. 5.1. Ортогональные производные системы сигналов на основе ПСП GMW
  14. 5.2. Применение последовательностей GMW для повышения безопасности CDMA систем на основе стандарта IS-95
  15. 5.4. m-подобные последовательности над GF(2m) и их применение в широкополосных системах связи
  16. Заключение
  17. Приложение 1 Тексты программ расчета координат векторов сдвигов генераторов ПСП GMW
  18. МЕСТО РЕНЕССАНСА B СРЕДНЕВЕКОВОЙ ИСТОРИИ ЗАПАДА
  19. ОСТРОУМИЕ И ЛОГИКА КОГНИТИВНОГО БЕССОЗНАТЕЛЬНОГО [48]