<<
>>

5.4. m-подобные последовательности над GF(2m) и их применение в широкополосных системах связи

На сегодняшний день существует достаточно хорошо развитая теория и практика как двоичных, так и q-ичных m-последовательностей. Бесспорно, двоичные т-последовательности являются наиболее простыми с точки зрения генерации, так как в отличие от q-ичных используют обычную булевую логику.

Вместе с тем в достаточно большом числе приложений, связанных с кодированием, модуляцией по закону прыгающей частоты и др., применяются q-ичные m-последовательности. Известны исследования, в которых генерация q-ичных m-последовательностей сводится к генерации двоичных [75,76]. Из них наибольший интерес представляет работа [76], касающаяся выявления связей между m-последовательностями над GF(qm) и GF(q). Согласно [76] любой элемент m-последовательности над GF(qm) длины qnm-l может быть представлен в виде линейной комбинации элементов m-последовательности над GF(q) в базисе GF(qm). Недостатком работы [76] является то, что, доказывая существование такого представления, она в то же время не содержат явного указания на то, как следует выбирать эти q-ичные m-последовательности. Действительно, в [76] в начале строится m-последовательность над GF(qm), а уже потом с ее помощью строится m-последовательности над GF(q). В настоящей диссертации предпринята попытка обойти эту трудность за счет построения нового класса q-ичных последовательностей длины 2N-1, где q=2m, N=mk, m>2, k^2, обладающих статистическими свойствами класса m-последовательностей над GF(2m) и формирующихся на основе сдвинутых копий двоичных m-последовательностей той же длины.

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

функционал из GF(2N) в GF(2m) такой, что для VxeGF(2N) справедливо Lo(L.2(x)y)=L(xy) для VyeGF(2m) . Тогда согласно [45] последовательность {Ь„} с элементами вида:

bn= L2(an) , (5.7) где а есть примитивный элемент GF(2N) и 0сп= Ца") (5.8)

есть двоичная m-последовательности длины 2N-1.

Пусть р=а8, где e=2N-l/2m-l. Тогда Р есть примитивный элемент поля GF(2m). Пусть {dn} последовательность над GF(2m ) с элементами вида:

dn=L(a>pL(an+€)+p2L(an+2e)+....+pm-,L(an+*(m-,)) . (5.9) Покажем, что последовательность {dn} имеет период 2N-1 и не совпадает с классом m-последовательностей GF(2m). Первое утверждение тривиально и следует из того, что период последовательностей (L(an)}{L(an+(m",)c)} есть 2N-1. Для доказательства второго утверждения представим последовательности {bn}, {Cn}, {d„} в виде двумерных таблиц Ть, Тс, Td размерности exw, в которых каждый n-ый элемент последовательности стоит на пересечении і строки и j столбца, где 0^і<є, 0? jДалее замечаем, что в силу построения последовательности {dn} нулевые строки таблицы Td оказываются расположенными на тех же местах, что и в таблицах Ть и Тс.

Кроме того, в силу свойства «окна» m-последовательности любые ненулевые строки таблицы Td будут состоять из w различных ненулевых элементов GF(2m) и являться сдвигами друг друга.

Предположим теперь, что для некоторого і-ого элемента последовательности {d„} dpi. Тогда Ца')=1, Ца'^)=Ца*2б)=....Ца'+в(пИ))=0. Рассмотрим строку таблицы Td, содержащую элемент dj. В соответствие с (5.9) следующим элементом в этой строке будет

d1^=L(ai+>pL(ai+2>p2L(ai+V----+Pm'1Uai+em)=Pm',L(ai+?m). Данная строка не содержит нулевых элементов, поэтому L(a,+cm)=l и d^p"1"1. Таким образом, установлено, что в ненулевой строке Td за элементом поля 1 всегда следует элемент pml. Отсюда следует, что последовательности {Ь„} и {d„} суть различные последовательности, не являющиеся сдвигами друг друга. Рассуждая аналогично, можно показать, что последовательность {dn} не совпадает также ни с одной другой q-ичной ш-последовательностью той же длины. Данное утверждение справедливо применительно к любой другой последовательности {dn'}, элементы которой определяются выражением

dn'=L(yn)^-ЩY^)+X2L(y^2c)+....+Xm•,L(yn+eЧисло различных последовательностей {d„} совпадает с числом ш-последовательностей степени N над GF(2), равным (p(2N-l)/N, что меньше общего числа ш-последовательностей степени N над GF(2m) в к раз.

Согласно [4,13] псевдослучайный характер последовательностей целиком определяется ее статистическими свойствами. При исследовании статистических свойств последовательностей {dn} будем опираться на известные статистические свойства ш-последовательностей {bn} в том виде, как они даны в [4].

Свойство Цбалансное). Число Nb появления ненулевого символа b на периоде m-последовательности {bn} на 1 превышает число No появления символа 0 на этом периоде, т.е. Nb=No+l.

153 Свойство 2.

Число Na позиций внутри периода последовательности, на которых встречается J-строка a=aia2...aj, определяется выражением

2N-mJ , дляа*0, lОилиі, kСвойство 3 (аддитивно-циклическое).

Разность между т-последоватсльностью {Ь„} и ее т-сдвигом {bn+t} есть другой v-сдвиг {bn+v} той же самой m-последовательности. При этом выполняется

Ьп+у=Ьп+х - Ьп для всех п. Свойство 4.

Пусть {in} есть последовательность целых чисел таких, что

где (bn> bn+i,..., bn+j-i) есть J-строка m-последовательности {bn}, a lПусть і, есть последовательность длины 2N-1, образованная из элементов {i„}, начиная с s-ro. Тогда для T*0mod(2N-l) расстояние по Хэммингу между ii и ±1+х вычисляется по формуле

H(il,il+т)=2N(l-2¦да,).

V

Здесь H(x,y)=^th(xnyl) есть метрика Хэмминга, где h(xi,yi) есть 0,если Xi=yi и 1 в і-\

противном случае.

Теперь покажем, что свойствами 1-4 обладают также построенные выше последовательности {dn}. Действительно, выполнение свойств 1-2 для {dn} следует из взаимной однозначности элементов строк таблиц Td и Ть. Справедливость свойства 3 вытекает из справедливости этого свойства для компонент Ца")},.... ,{Цап+<ш"1)с) элемента dn. Доказательство свойства 4 для последовательности {dn} вытекает из свойств 2 и

3. Заметам, что одновременно этим доказывается и псевдослучайность последовательности

Таким образом, последовательности {dn}, обладая всеми свойствами т-послсдоватсльностей, по-суидеству, являются m-подобными последовательностями меньшей мощности. Поэтому в дальнейшем последовательности {dn} будем называть т-подобными. Можно построить и другие классы m-подобных последовательностей, получаемых, например, перестановкой компонент в символах {dn} или {Ь„}. Очевидно, такие последовательности также будут обладать свойствами 1-4.

В соответствие с (5.9) генератор m-подобных последовательностей может быть представлен в виде формирователя m сдвинутых друг относительно друга на є разрядов копий двоичной m-последовательности. Генератор сдвинутых копий достаточно подробно рассмотрен во многих работах, например, в [24]. Он состоит из последовательно соединенных генератора двоичной m-последовательности и блока сумматоров по модулю два (Рис.5.3). Можно указать на две возможные области применения m-подобных последовательностей.

Это широкополосные системы многостанционного доступа с модуляцией прямыми последовательностями (DS-CDMA) и широкополосные системы многостанционного доступа с модуляцией прыгающей частотой (FH-CDMA). Применение m-подобных последовательностей в DS-CDMA носит косвенный характер, выражающийся в том, что основу генератора ПСП GMW (Рис.4.6.) составляет генератор m-подобных последовательностей длины 2N-1. Кроме того, генератор m-подобных последовательностей может быть использован для получения других семейств нелинейных последовательностей, строящихся на основе m-последовательностей над GF(2m) и разностных множеств [18].

m-подобные последовательности могут найти применение и в системах с кодовым разделением и модуляцией с прыгающей частотой, закон изменения которой определяется m-последовательностью над GF(2m) [4]. Очевидно, в этом случае генераторы ш-последовательностей также можно безболезненно заменить более простыми генераторами m-подобных последовательностей. Однако, как справедливо отмечено в [4], недостатком этих последовательностей является их малая линейная сложность, численно равная к. Поэтому в тех случаях, когда требуется большая линейная сложность, используются довольно сложные конструкции, например, обобщенные бент-последовательности [77]. Ниже будет показано, как на основе m-подобных последовательностей за счет незначительного усложнения конструкции могут быть получены последовательности с большей линейной сложностью. Для этого рассмотрим последовательность {zn} длины 2N-1 с элементами вида

2„=[Ь2(ап)]' , (5.11)

где lПусть Tz - двумерная (є,\у)-таблица последовательности {г,,}. Тогда в силу того, что отображение PJ->PJT, где 0Lpk" , (5.12) где u-число единиц в двоичном представлении числа t.

При этом максимальное значение L2=km"1 достигается при t=(2m"I-l)2s mod (2N-1), где 0(Pj)"' ^Mat(2m"2-J)) + p-^(c^ и 0->0 ,(5.13)

где 0Это отображение взаимно однозначное, так как {Ь(сг*(2"~г~0)} , где 0m-последовательность длины 2т-1 и, следовательно, любой ненулевой набор из m последовательных ее символов встречается на ее периоде ровно один раз, причем число различных таких наборов равно 2ш-1. Если теперь в ПЗУ по тем же самым адресам вместо элементов (р*)"1 разместить соответствующие им согласно (5.13) элементы, то в результате на выходе такого генератора образуется последовательность с элементами zn=L3([L2(an)]"1), которая имеет такие же статистические свойства и линейную сложность, что и последовательность {[L2(an)]" }. Нетрудно заметить, что элементы последовательности {zn} обладают следующим замечательным свойством. Согласно (5.10), (511) двоичные координаты ее элементов в рассмотренном базисе GF(2m) представляют собой сдвинутые на є разрядов копии последовательности GMW с базисной m-последовательностью {Ца"4)}, т-е. zn'=(gmwn,gmwn+e,...,gmwn+€(ia.i,). Основное преимущества данного генератора перед генератором последовательности {^(а")]*1} состоит в том, что для построения его ПЗУ необходимо лишь знать обратную к {L(ctCJ)}, где 0^j<2m-l, последовательность {L(ct'ej)}, для получения которой достаточно использовать двоичную арифметику над GF(2).

Для построения псевдослучайного генератора для FHMA поступим следующим образом. Пусть zn J-строка последовательных элементов из {Zn}. Кроме того, пусть s(x) произвольное взаимно однозначное отображение zn' в множество 2Jm различных частот. Рассмотрим последовательность fn=s(zn'). Тогда для всех т*0 будет выполняться равенство H(fn,fn+t)=2N-2N"Jm. Это следует из свойства (5.10) и взаимно однозначности отображения s.

На Рис.5.4. изображена блок-схема такого псевдослучайного генератора для случая J-1. В качестве примера рассмотрим генерацию 23-ичной последовательности {ЬзАЪгСа")]"1)} длины 4095 на основе генератора m-подобной последовательности с параметрами N=12,

1"У
т=3 и J=l. Пусть примитивный элемент а поля GF(2 ) является корнем неприводимого примитивного полинома:

Х,2+Хп+Х8+Х6+1 . (5.14) Тогда в соответствие с [49] генератор m-подобной последовательности должен формировать т=3 сдвинутых последовательностей {с„}, {Сп+585}. {Сп+іпоЬ где cn=L(an). Очевидно, последовательности с„+585 и Сп+1170 являются задержанными соответственно на 3510 и 2925 чипов копиями m-последовательности Сп. Формирование задержанных копий т-последовательности наиболее просто осуществить с помощью суммирования по модулю два соответствующих разрядных выходов регистра сдвига генератора m-последовательности по схеме Фибоначчи. Пусть Cn,Cn-h...,Ci,.(N-i) - последовательности, образующиеся на выходах разрядов регистра сдвига этого генератора. Тогда для Сп+585=с,кшо и Сп+п7о=Сп-2925 с помощью компьютера находим, что:

Cn+SeS^^-l+Cn^+CnO+Cn-S+Cn-T+Cn-IO И Сщ-] |70^-1+Сп-2-^п-8+Сп-9+Сп-10 .

Образуем 7-ми элементную ненулевую последовательность {ej}, где ej=L(a585j) . Это всегда можно сделать путем соответствующего выбора начального состояния генератора последовательности св. При Ц1)=1 эта последовательность имеет вид: 1101001. Тогда обратная к ней последовательность есть 1001011. Для построения ПЗУ образуем таблицу

5.3, в которой наборам из 3-х подряд идущих символов последовательности {ej}, рассматриваемым как двоичные адреса, ставятся в соответствие 3-х разрядные элементы L3(P'J).

158

Рис.5.4.

-ичной псевдослучайной последовательности повышенной линейной сложности для FHMA .

С учетом того, что по нулевому адресу всегда находится символ 0, после упорядочения таблицы по возрастанию адресного параметра в результате получаем таблицу 5.4, полностью определяющую структуру ПЗУ генератора. Функциональная схема генератора представлена на Рис.5.5. Формируемая последовательность имеет параметры: L=16 и Н=3584. Однако, задержав zn всего на один разряд и переходя к случаю J=2, можно существенно улучшить параметр Н до 4032. При этом число различных частот составит 64. Отметим, что такой же результат можно получить посредством генератора с параметрами N=12, т=6,к=2иЛ=1.

К сожалению, генератор на основе последовательности {zn } позволяет получать только сдвинутые копии последовательности {fn}. В то же время описанный в [4] псевдослучайный генератор FH на основе 2га-ичной m-последовательности обеспечивает генерацию целого семейства последовательностей с элементами fnv=s(x+v), где v -произвольная J-строка, с хорошими Хэмминговыми расстояниями. Анализ показывает, что на основе последовательности (5.11) с помощью преобразования s(x+v) также могут быть получены последовательности с такими же Хэмминговыми расстояниями, но значительно большей линейной сложностью.

Адреса элементов L3(p"J).

Таблица 5.4.

Структура ПЗУ генератора m-подобной последовательности над GF(8).

АДРЕС СИМВОЛ GF(23) 0 0 0 ООО 0 0 1 011 0 1 0 010 0 1 1 111 1 0 0 101 1 0 1 001 1 1 0 100 1 1 1 по

Выводы

Построенные на основе m-последовательностей и последовательностей GMW ортогональные производные системы сигналов характеризуются большой линейной сложностью и удовлетворительными корреляционными параметрами и могут быть использованы в системах связи с CDMA, требующих повышенную имито и криптозащиту.

Предложенный генератор длинного кода на основе последовательности GMW длины 242-1 позволяет существенным образом повысить безопасность CDMA систем по технологии IS-95 и cdma2000.

3. Найденные закономерности взаимно-корреляционных спектров пар последовательностей со сверхвысокими пиками взаимной корреляции позволяют производить отбор последовательностей для систем связи с CDMA среди всего класса последовательностей, увеличивая тем самым число последовательностей с приемлемыми корреляционными свойствами. Причем на этапе поиска сигнала знание периода появления сверхвысоких пиков взаимной корреляции может быть использовано для уменьшения вероятности ложного захвата за любой из этих пиков. 4. Построенные новые семейства m-подобных последовательностей высокой

линейной сложности могут найти применение в широкополосных системах

многостанционного доступа с прыгающей частотой (FHMA).

Рис.5.5

Генератор последовательности над GF(8) длины 4095

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

Еще по теме 5.4. m-подобные последовательности над GF(2m) и их применение в широкополосных системах связи:

  1. 48. Пополнение недостатка законов
  2. 101. Детерминистическая формула вменяемости
  3. § 4. Преступления, посягающие на финансово-кредитные | отношения
  4. 11.5. Психологические основы веденияпереговоров с преступниками
  5. §3. Особенности символического освоения социальных изменений посредством моды
  6. Поиск в Яндексе
  7. 8.1.3 Дальние корреляции в первичной структуре нуклеотидных последовательностей
  8. 1.1. Особенности построения широкополосных систем связи на базе технологии СОМА
  9. 1.2. Последовательности для систем связи по технологии DS-CDMA
  10. 1.3. Критерии выбора ансамблей псевдослучайных последовательностей для систем с CDMA
  11. 2.6. Линейная сложность
  12. З.5. Последовательности