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

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

Пусть 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.

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'=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. Заметам, что одновременно этим доказывается и псевдослучайность последовательности

Таким образом, последовательности {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-подобных последовательностей.

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.

Для построения псевдослучайного генератора для 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