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

Размещено на http://www.allbest.ru/

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

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

Псевдослучайные последовательности (ПСП) представляют собой периодически повторяющиеся кодовые двоичные последовательности определенной длины, которые широко используются для передачи дискретных сообщений. Наилучшей с точки зрения помехозащищенности средств радиосвязи (СРС) с фазоманипулированными широкополосными сигналами (ФМШПС) является случайная последовательность. Однако для осуществления сжатия спектра сигнала такая последовательность не может быть использована, так как на приемной стороне СРС необходимо иметь точную копию передаваемой последовательности. Поэтому для формирования ФМШПС используется ПСП.

К множеству ПСП предъявляются следующие требования:

1) каждый из сигналов данного множества легко отличим от своей сдвинутой во времени копии, то есть должен иметь автокорреляционную функцию (АКФ) с малыми значениями боковых выбросов;

2) каждый из сигналов данного множества легко отличим от любого другого сигнала этого множества, то есть взаимно-корреляционная функция (ВКФ) любой пары несовпадающих сигналов множества должна быть минимальной;

3) множество, используемых ПСП, должно составлять достаточно обширный ансамбль.

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

Возможны 2 варианта включения сумматоров по модулю 2 для формирования ПСП (рисунок 1):

а) со встроенными сумматорами по модулю 2 (форма Галуа);

б) с вынесенными сумматорами по модулю 2 (форма Фибоначчи).

Схемы рисунков 1 а) и б) эквивалентны. Генерируемые линейные ПСП имеют одинаковую форму.

Рис. 1. Генераторы ПСП: а) со встроенными сумматорами по модулю 2: б) с вынесенными сумматорами по модулю 2.

генератор псевдослучайный регистр

Обозначим состояние -ой ячейки РСЛОС через , тогда регистр сдвига будем считать линейным, если функция цепи обратной связи будет для схемы рисунка 1,б состоять из сумматоров по модулю 2, которая выражается как

где ; знак «+» означает суммирование по модулю 2.

Для ЛРП состояние ячейки определяется как

где принимает значение «1», если существует контакт с цепью обратной связи, и принимает значение «0», если соединение с цепью обратной связи отсутствует.

Следует заметить, что математическое описание генераторов ПСП со встроенными сумматорами по модулю 2 и с вынесенными сумматорами по модулю 2 эквивалентно (рисунок 1), они воспроизводят одинаковые ПСП. Обратимся к рисунку 1, а (схема Галуа), где состояния определяются как , где является индексом состояния, а является индексом времени.

Рассматривая выход схемы Галуа РСЛОС (рисунок 1,а), получим следующее выражение

Это следует из того, что состояние на выходе состоит из суммы выхода предыдущего каскада (ячейки) , умноженного на , и (состояния на выходе каскада, расположенного на две ячейки ранее), умноженного на , и т. д., пока не достигнута первая ячейка. Первая ячейка регистра имеет задержку на единиц и в итоге получаем (3). Результат представим в виде

.

Из рисунка 1, а следует, что

.

Обозначим и , затем подставим в (5) и (4). В результате получим

так как

.

Таким образом,

,

В результате мы видим, что для РСЛОС, построенных по схеме Галуа или Фибоначчи, результирующая ПСП получается одинаковой.

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

Рис. 2. Схема РСЛОС, соответствующая характеристическому многочлену .

Рассмотрим схему, соответствующую рисунку 2. Если состояние регистров в момент времени представляется вектором размера , то состояние регистров в момент времени по отношению к моменту времени определяется как , где ? матрица соединений порядка , имеющая блочно-диагональный вид.

Указанные многочлены сведены в таблицы, которые можно найти в [1, 2]. Генераторы ПСП на сдвиговых регистрах описываются с помощью матрицы соединений -ного порядка.

Детерминант матрицы соединений (? единичная матрица порядка ) представляет собой искомый характеристический многочлен матрицы . В этом случае характеристический многочлен можно представить как

,

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

Генераторы ПСП на сдвиговых регистрах описываются с помощью характеристического многочлена, который обозначен (9). Следовательно, схема рисунка 1, б, соответствующая (1), производит ту же выходную последовательность, как и схема рисунка 1, а. Матрица соединений рисунка 1 является дополнительной матрицей для .

Обратным многочленом для будет . Его удобно представлять многочленом задержки.

,

где представляет собой задержку одного каскада сдвигового регистра.

В таком виде каждый каскад сдвигового регистра схемы может прямо соответствовать одному члену . Процедура нахождения соответствующей схемы, таким образом, состоит из преобразования в . Далее производится разложение на члены , и . Типовые структуры схемы приведены на рисунке 3, которые следует определить. Любые и можно свести к этим схемным конфигурациям, разлагая и на члены и , где и ? положительные целые числа.

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

Рис. 3. Типовые конфигурации частей схемы. а) D+1; б) D2+1; в) Dn+1; г) x+1; д) x2+1 е) xn+1.

Для описания выходной последовательности сдвигового генератора используют производящую функцию.

Определим выходную ПСП в виде

где нижний индекс означает момент времени; то есть, сначала появляется , затем и так далее.

Тогда производящая функция выходной ПСП задается в виде

Начальное состояние регистра сдвига определяется как . Тогда выходная ПСП определяется линейным рекуррентным соотношением

, ,

Так что последовательность определяется начальными условиями при синхронизации регистра. Подставляя (12) в (11), получим

Изменяя порядок суммирования, получим

Или

.

Подставляя (13) в (15), получим

.

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

Рассмотрим основные правила, по которым должны формироваться ПСП. На рисунке 4 приведено устройство генерации кодов Голда. Производящая функция последовательности Голда определяется как сумма производящих функций двух М-последовательностей:

,

где и ? производящие функции М-последовательностей верхнего и нижнего сдвигового регистра, соответственно; «+» ? знак суммирования по модулю 2.

Рис. 4. Схема формирования ПСП Голда из двух М-последовательностей

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

,

.

Подставляя выражения (19) и (20) в (18), получим

В результате получается та же самая М-последовательность, но начальная установка определяется как поразрядная сумма по модулю 2 начальных установок двух РСЛОС.

Когда направление цепи обратной связи взаимно изменяется, то получается конфигурация, представимая обратным многочленом. Это позволяет расширить поиск более простых матриц соединений по сравнению с уже найденными. Последнее означает, что разложению на множители подвергается не только , но также и . Это часто позволяет получать более экономичные схемы. Части схем, полученные из этих форм, приведены на рисунке 3.

Только что описанный метод можно использовать для создания генераторов ПСП, используя минимальное число сумматоров по модулю 2. Показана возможность уменьшения количества сумматоров по модулю 2 генераторов псевдослучайных последовательностей вплоть до трех. Выигрыш при использовании указанного метода возрастает, когда количество ненулевых членов примитивного многочлена становится больше. Значительная экономия аппаратных средств, при построении генератора псевдослучайных последовательностей, может быть достигнута использованием предложенного метода по сравнению с методами, основанными на использовании сопровождающей матрицы. Многочлены, получаемые в этом случае, примитивные и неприводимые. Номера неприводимых многочленов приведены в [1, 2]. На основе этих данных построена таблица 1. В таблице 1 приведены матрицы соединений для всех примитивных многочленов степени 9, к которым применимы формулы (1) и (2), и которые должны использовать меньшее количество сумматоров по модулю 2, чем определяется сопровождающей матрицей. Многочлены степени менее 5 таким свойством не обладают. В таблице 1 использована следующая система обозначений:

1) коэффициенты многочленов указываются в восьмеричной системе, причем старшая степень предшествует младшей;

2) соединения описываются двумя множествами чисел, разделенных чертой. Каждое число , предшествующее черте, указывает направление линии обратной связи в каскаде ; каждая цифра , следующая за чертой, указывает направление, по которому выход каскада подключается к петле обратной связи;

3) каскады пронумерованы, слева направо. Это означает, что обратная связь, начинающаяся в каскаде , направлена из каскада.

Таблица 1. Построение РСЛОС

Заключение

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

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

Литература

генератор псевдослучайный регистр

1.Бессарабова А. А. М-последовательности. Воронеж: АО «Концерн «Созвездие», 2010. ? 223с.

2.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. / Под ред. Р. Л. Добрушина, С. И. Самойленко. М.: Мир, 1976. ? 594 с.

3.Варакин Л. Е. Системы связи с шумоподобными сигналами. М.: Радио и связь, 1985. ? 384 с.

Размещено на Allbest.ru