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

 

К псевдослучайным последовательностям предъявляются следующие требования:

· хорошие авто- и взаимнокорреляционные характеристики;

· сбалансированность структуры;

· высокая эквивалентная линейная сложность;

· большой ансамбль сигналов;

· простота генерации.

Автокорреляционные и взаимнокорреляционные функции

Пусть - кодовая последовательность, - длительность единичного элемента ПСП, - период ПСП.

Периодическая ВКФ кодовой последовательности будет определяться соотношением

,

(3.1)

где , . ПВКФ является мерой соответствия двух различных кодовых последовательностей.

При получаем периодическую АКФ:

.

(3.2)

ПАКФ показывает связь сигнала со своей копией, смещенной во времени на величину .

Пусть - пиковое значение бокового лепестка ВКФ; - пиковое значение бокового лепестка АКФ; наибольшее пиковое значение бокового лепестка корреляционной функции. Качество корреляционных характеристик определяется наименьшим значением .

Корреляционные свойства кодовых последовательностей, используемых в широкополосных СПИ, зависят от типа кодовой последовательности , ее длины , частоты следования символов , посимвольной структуры [25-32].

Сбалансированность структуры

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

Эквивалентная линейная сложность

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

Ансамбль сигналов

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

Все перечисленные параметры играют важную роль при выборе того или иного семейства последовательностей. Основные характеристики хорошо известных и новых двоичных ПСП представлены в табл.3.1.

Таблица 3.1

Семейство	Период	Объем	Линейная сложность	Максимальное значение боковых пиков
М-последователь-ности
Голда	, -нечетно
, -четно
Касами Малое	-четно
Касами Большое	-четно
Бент-после-довательности
Мак Элис
GMW
Де Брейна
Холла
Лежандра
Последовательности No	,
Норм-следовые последовательности TN	,
Последовательности Кердока	-четно
QF- последовательности	,
IM^Y ^tr (Y =3)	, -нечетно
IM^Y ^tr(Y =3)	, -четно
IM^Y ^tr(Y) =0

 

М-последовательности

 

М-последовательности, известные еще как последовательности Хаффмена, относятся к линейным рекуррентным последовательностям максимального периода.

Значение каждого текущего символа в M-последовательности зависит от значений предыдущих символов и определяется рекуррентным правилом:

(3.3)

где и могут принимать значение 0 или 1; Å - знак сложения по модулю два; число называется памятью последовательности . Из выражения (3.3) следует, что устройство, вырабатывающее двоичную линейную рекуррентную последовательность, должно помнить последних символов последовательности и складывать их по модулю два с весами задаваемыми правилом кодирования.

M-последовательности строятся на основе неприводимых примитивных двоичных многочленов. Общее число возможных различных M-последовательностей максимального периода в ансамбле определяется из выражения [26,27]

,

(3.4)

где - функция Эйлера, - степень неприводимого примитивного многочлена

M-последовательности обладают следующими свойствами:

· являются периодическими с периодом , где - длина регистра, с помощью которого формируется M-последовательность;

· все импульсы в периоде распределены равновероятно;

· сумма двух M-последовательностей, сдвинутых относительно друг друга, также является M-последовательностью;

· в M-последовательности длиной содержатся все n -значные комбинации двоичных символов кроме нулевой;

· в каждом периоде общее число единиц отличается от общего числа нулей не более чем на единицу.

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

Формируются M-последовательности с помощью сдвиговых регистров и схем суммирования по модулю два. Структура цифрового автомата для формирования М-последовательности полностью определяется видом неприводимого примитивного многочлена.

М-последовательности служат основой для формирования других многочисленных ансамблей ПСП: последовательностей Голда, Касами, Бент-последовательностей, последовательностей GMW.

Пример. Построить М-последовательность над полем Галуа , схему формирования и АКФ.

Выберем из табл.3.2 неприводимый двоичный многочлен .

Пусть начальное состояние регистра 1000.

Тогда формирование -го элемента последовательности будет определяться выражением (3.3):

. (3.5)

В неприводимом двоичном многочлене коэффициенты , , следовательно,

. (3.6)

Тогда, ;

;

….

Таким образом, получим последовательность: 100011110101100 1000111101….

На рис.3.1 приведена схема формирования М-последовательности, в которой число элементов задержки и количество сумматоров определяется выражением (3.6).

 

 

Рис.3.1. Схема формирования М-последовательности

 

Периодическая АКФ М-последовательности рассчитана в пакете Matcad по формуле (3.2) и показана на рис.3.2.

 

 

Рис.3.2. Периодическая АКФ М-последовательности

 

Задание к лабораторной работе «Построение и расчет