Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В

Приводится правило гомоморфного отображения для получения последовательностей Лежандра и М-последовательностей, а также структурные схемы устройств их формирования.

В этой главе рассматривается изоморфное отображение последовательностей, когда порядок поля не меняется, а меняется нумерация элементов поля. Изоморфным отображением является децимация, заключающаяся в построении новой последовательности путем выбора q·i-х элементов исходной последовательности, i=1, 2, …N-1, q – целое число. Рассмотрены децимации последовательностей Лежандра и M- последовательностей, определены номера сдвигов результирующей ПСП. Определен характер изменения корреляционных функций и спектра при децимациях любых последовательностей.

3.3.1. Псевдослучайные двоичные последовательности

иих корреляционные свойства

Врадиотехнических системах часто используются сигналы, для формирования которых применяются псевдослучайные последовательности, В этом случае основными характеристиками сигналов являются их корреляционные свойства. Оказывается, на основе конечных полей можно синтезировать псевдослучайные последовательности, которые обладают хорошими корреляционными свойствами. Здесь ограничимся рассмотрением так называемых фазоманипулированных сигналов, когда в соответствии с символами псевдослучайной двоичной последовательности (ПСП) изменяется фаза гармонической несущей сигнала, принимая два значения: 0 или π. Огибающая корреляционной функции фазоманипулированного сигнала совпадает с корреляционной функцией (КФ) ПСП. Элементами ПСП в этом случае должны быть +1 и -1. ПСП именно с такими элементами нас будут интересовать. Но для простоты записи элементы ПСП будем обозначать 1 и 0.

Построение ПСП с элементами +1 и -1 на основе конечных полей Галуа сводится к гомоморфному отображению группы поля GF(p) или GF(рm) в груп-

пу (+1, -1). Отображение G→H элементов группы G на элементы группы Н называется гомоморфным, если из g1→h1 и g2→h2 следует, что g1*g2→h1*h2 (* обозначает групповую операцию). Иными словами, при гомоморфизме соотношения между элементами сохраняются. В общем случае гомоморфное ото-

бражение сопровождается укрупнением элементов: в один элемент группы Н отображаются целые классы, подгруппы или другие множества элементов группы G. Гомоморфное отображение, которое не сопровождается укрупнением элементов, называется изоморфным. Изоморфизм сводится к изменению порядка следования элементов конечного поля, к перенумерации его элементов. Порядок поля не меняется.

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

95

Обозначим k-й элемент ПСП через μk, k=0,1,…N-1, N - длина последовательности, число элементов в ней. Тогда автокорреляционная функция, которую далее будем называть корреляционной, определяется выражением

k 0

где l означает сдвиг одной копии ПСП относительно другой при вычислении КФ. Значение l выражается целым числом.

КФ R(l) можно определить, не вычисляя произведение элементов в соответствии с формулой (59). Если используются двоичные ПСП, то для заданного l достаточно определить в двух копиях ПСП число А элементов одного знака (произведение этих элементов равно 1) и число D элементов различных знаков (их произведение равно -1). Здесь следует еще раз обратить внимание на то, что хотя ПСП записываются элементами 1 и 0, но под 0 подразумевается -1, что и учитывается при вычислении произведения элементов с разными и одинаковы-

ми знаками: (-1)·(+1)=-1 и (-1)·(-1)=1 (а не 0). Тогда R(l)=A–D=2A–N=N–2D. (60)

В этой формуле учитывалось, что А+D=N.

Формулу (60) рекомендуется использовать при вычислении КФ на ЭВМ, так как операции сравнения на ЭВМ выполняются значительно быстрее, чем умножение. Можно представить и еще одну формулу для вычисления КФ

в которой К+ - число единиц в последовательности, а λ - число произведений вида (1,·1) в формуле (59) для заданного l.

Приведем некоторые свойства периодических КФ псевдослучайных последовательностей, представленных элементами (1,-1).

1. Разность N-R(l) всегда делится на 4, то есть N-R(l)≡0(mod 4). Максимальное значение КФ будет при l=0: R(0)=N, а возможные боковые уровни КФ могут принимать дискретный ряд значений с интервалом 4. Это свойство можно использовать для проверки правильности вычисления периодических КФ.

2. Нижняя оценка максимальных боковых выбросов. Минимальное значение максимальных (по модулю) боковых выбросов определяется соотношениями

-1 при N 3(mod 4),

Пример 1. Определить возможные уровни КФ последовательностей дли-

ны N= 4, 10, 11, 13.

ПСП длины 4 может иметь только 3 уровня КФ; 4, 0 и -4. ПСП длины 10 может иметь КФ с уровнями: 10, 6, 2, -2, -6, -10. ПСП длины 11 может иметь КФ с уровнями: 11, 7, 3, -1, -5, -9, а длины 13: 13, 9, 5, 1, -3, -7, -11.

96

Для рассмотрения 3-го свойства надо ввести следующие понятия. Периодическая КФ называется одноуровневой, если R(l), l≠0, принимает

одно и только одно значение. Если R(l), l≠0, принимает два различных значения,

то периодическая КФ называется двухуровневой. Аналогичным образом определяются многоуровневые КФ.

3. Необходимым условием получения одноуровневой КФ является

То есть произведение K+(K+-1) должно делиться без остатка на (N-1). Частное от деления и будет равно λ (целое число), которое входит в формулу (61):

Решая совместно уравнения, можно определить число единиц в ПСП, при котором ее корреляционная функция будет одноуровневой с минимально возможными уровнями выбросов, определяемыми (61). Результаты расчетов, а также примеры приведены в табл.3.3.1.

В таблице приведено число единиц К+ в ПСП, при котором возможно получение одноуровневых КФ с минимальными боковыми выбросами, определяемыми выражением (59). К сожалению, это только необходимые условия, и не все последовательности, приведенные в таблице в качестве примеров, будут иметь одноуровневые КФ.

Таблица 3.10 Длина N ПСП и число единиц К+ в ней, необходимые для получения

одноуроневой КФ с минимальным выбросом

Достаточным условием получения одноуровневых КФ является существование разностного множества D(N, K+, λ), при этом λ зависит от значений N и K+ и определяется формулой (2.6). Разностное множество определяет номера позиций в ПСП, на которых стоят 1. Разностное множество D(N, K+,λ) содержит числа от 1 до N-1 (всего K+ чисел), такие, что разности между ними (по модулю N) принимают каждое из значений 1, 2,..., (N-1) ровно λ раз. Верно и обрат-

97

ное утверждение: если получена ПСП с одноуровневой КФ (не обязательно с минимальным значением Rmax ()), то позиции единичных элементов составляют разностное множество D(N,K+,λ) при λ, удовлетворяющем условию (61).

Существуют также разностные множества, которые соответствуют ПСП с двухуровневыми КФ. Подробнее с известными разностными множествами можно познакомиться в работах [22,23].

Двоичные последовательности с минимальными боковыми выбросами КФ можно построить на основе конечных полей. К таким последовательностям относятся М-последовательности длины N=2m-1, последовательности Лежандра, длина которых равна простому числу N=p. Длина М-последовательностей может быть представлена в виде N=2m-1=2m-22+3=24(22m-2-1)+3≡3(mod 4) и в соответствии с (59) боковой выброс КФ может иметь значение -1. Последовательности Лежандра имеют длину N≡3(mod 4) либо N≡1(mod 4). В первом случае они также будут иметь одноуровневые КФ с R(l)=-1, l≠0. Во втором случае одноуровневой КФ получить нельзя, так как число 1 в последовательности Лежандра равно К+=(N+1) ∕ 2, то есть не соответствует числу К+, приведенному в табл.1.7. В этом случае получаются двухуровневые КФ с выбросами 1 и -3, Причем половина боковых выбросов будет иметь уровень 1, а другая половина -3. Это следует из того, что при таких значениях числа К+ расчеты по формуле (63) дадут значение λ, равное нецелому числу, дробная часть его равна 0,5. Поэтому половина значений может быть равна целой части числа, полученного по формуле (63), а половина - на 1 больше. На рис. 3.10 представлены корреляционные функции M-последовательности длины 15 (а), последовательностей Лежандра длины 11 и 13 (соответственно б и в).

Рис. 3.10. Корреляционные функции М-последовательности длины 15 (а), последовательностей Лежандра длины 11 (б) и 13 (в)

3.3.2. Последовательности Лежандра

Эти последовательности называют последовательностями квадратичных вычетов. Число элементов в последовательности равно простому числу, они строятся на основе простого поля GF(р). Как было указано выше, все ненулевые элементы простого поля составляют мультипликативную группу и могут быть представлены как степени первообразного элемента θ. Для каждого простого р существует φ(p-1) первообразных элементов.

В мультипликативной группе простого поля можно выделить подгруппу,

98

образующим элементом которой будет θ2. Элементами этой подгруппы будут все четные степени первообразного элемента { θ0, θ2, θ4, θ6,…}={θ2k}, k=0, 1,

...(p-3)/2.. Покажем, что {θ2k} является подгруппой. Подгруппа должна обладать всеми свойствами группы: иметь единичный элемент (θ0); каждый элемент должен иметь обратный, принадлежащий этой же подгруппе; на элементах подгруппы должна быть определена групповая операция (умножение). Покажем, что обратный к элементу θ2k является квадратичным вычетом, то есть представляется четной степенью первообразного элемента θ: θ2k θ 2k θp 1 2k . Здесь учитывалось, что первообразный элемент имеет период (p-1) и θp-1. Значение (p-1- 2k) всегда четно, так как (р-1) четно. Следовательно, θ2k - квадратичный вычет, то есть принадлежит подгруппе {θ2k}. Произведение любых элементов подгруппы дает элемент, принадлежащий подгруппе θ2k·θ2l=θ2(k+l), показатель степени 2(k+l) всегда четен, поэтому θ2(k+l) принадлежит подгруппе {θ2k}. Все нечетные степени первообразного элемента составляют смежный класс по подгруппе {θ2k} с образующим элементом: каждый элемент смежного класса может быть получен умножением на θ элементов подгруппы {θ2k}.

Синтез последовательностей Лежандра сводится к гомоморфному отображению мультипликативной группы простого поля GF(р) в мультипликативную группу {-1, 1}. При этом отображении все элементы одного смежного класса переходят в один элемент. Схематично это можно представить следую-

щим образом:

{θ2k}→1, {θ2k+1}→ -1.

Образом класса {θ2k} является 1, а -1 – образом класса {θ2k+1}. Соответственно классы {θ2k} и {θ2k+1} являются прообразами элементов 1 и -1.

При гомоморфном отображении групп нулевой элемент поля не определен. Ему можно поставить в соответствие -1 или 1. Число элементов мультипликативной группы равно р-1 или через длину ПСП N-1. Следовательно, подгруппа квадратичных вычетов даст (N-1)/2 единичных элементов в ПСП. Если нулевому элементу поля GF(p) будет присвоена 1, то число единиц в ПСП увеличится на 1. Поэтому число единиц в последовательностях Лежандра, как было указано выше, определяется выражением

K+=(N+1)/2.

В дальнейшем элемент -1 будет обозначен 0.

Пример 2. Построить последовательность Лежандра для N=7. Последовательность Лежандра длины N=7 строим на основе простого конечного поля GF(7), первообразным элементом которого, как следует из табл.2.2, является θ=3. Представим ненулевые элементы этого поля, то есть его мультипликативную группу, степенями первообразного элемента: 1=30 , 2=32, 3=31, 4=34 , 5=35 , 6=33 . Напоминаем, что все операции в этом поле проводятся по модулю N=7. Квадратичными вычетами, то есть четными степенями первообразного элемента, являются элементы: 2=32, 4=34, 1=30. Следовательно, 1, 2 и 4-й элементы ПСП будут представляться 1, а 3, 5 и 6-й -1, для простоты записи -1 заменим на

99