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

ОП ИСАНИЕ

И ЗОБРЕТЕ Н ИЯ

К АВТОРСКОМУ СВИ ВТИЛЬСТВУ

Союз Советскик

Социалистическии

Республик (iii 942013 (6l ) Дополнительное к авт. сема-ву -. (22) Заявлено 17. 11.80 (21) 3005800/18-24 (51)М. К,п. с прнсоеанменнеы заявки №G 06 F 7/58

3Ъоуаоротоаиыб комитет

СССР аэ дилан изобрвтеиий и открытий

{23) Прноритет(53) УДК 681.325 (088.8) Опубликовано 07.07.32. 61оллетемь № 25

Дата опублмковання описания 07. 07. 82 (72) Автор изобретения

М,М.Юрцевич

1

Р

Минский радиотехнический институт (7l ) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

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

Известен генератор псевдослучайных последовательностей, содержащий регистр сдвига и сумматор по модулю два в цепи обратной связи, позволяющий. получить псевдослучайную последова.тельность максимальной длительности с периодом 2" 1 Г13 ° го

Недостатками данного устройства являются узость класса формируемых псевдослучайных последовательностей, а также невозможность получения неби2 нарной псевдослучайной последовательностии °

Известен генератор псевдослучайных последовательностей, содержащий иразрядный регистр сдвига с с.мматором по модулю два в цепи обратной связи и r дополнительных сумматоров по модуле два на выходах которых формируются псевдослучайные последовательности, причем гоп/2. Дополнительные сумматоры по модулю два позволяют получить псевдослучайные последовательности с различным фазовым сдвигом со спектром, близким к равномерному f2J.

Однако это устройство позволяет формировать узкий класс последовательностей с символами + 1. Наиболее близкин к предлагаемому по технической сущности является генератор псевдослучайных последовательностей (ПСП), содержащий генератор тактовых импульсов, выход которого соеди,нен со входом генератора М-последо3 -94 вательности, а выход генератора Мпоследовательности через последовательно соединенные фазовращатель, дополнительный генератор М«последовательности и блок сравнения связан с блоком вычисления разности, причем выход генератора тактовых импульсов соединен с другим входом фазовращателя, а другой выход генератора Мпоследовательности связан с вторым входом блока сравнения.

Сущность работы генератора заключена в том, что основной и дополнительный генераторы M-последовательностей формируют псевдослучайные последовательности максимального периода М2 .-1 различной фазовой структуры, т.е. на основе различных неприводных и примитивных полиномов, причем фаза дополнительного генератора М-последовательности сдвигается на один символ после каждого периода псевдослучайной последовательности, формируемой основным генератором М-последовательности. 3а период ПСП вычисляется число совпадающих и число несовпадающих символов этих IlCll. Разность между числом совпадающих и числом несовпадающих символов этих ПСП дает значение символа новой псевдЬслучайной последовательности, значение символа в параллельном коде снимается с блока вычисления разности(3).

Основным недостатком известного генератора псевдослучайной последовательности является низкое быстродействие, Это объясняется тем, что время формирования одного символа псевдослучайной последовательности является результатом вычисления периодической функции взаимной корреляции между двумя М-последовательностями одинакового периода в точке, т.е. за

2"-1 тактов генератора тактовой частоты. Следовательно, длительность одного символа многоуровневой последовательности в 2 -1 раэ больше пеП» риода. тактовой частоты, а быстродействие в 2 -1 раз меньше. Кроме того, и класс формируемых псевдослучайных последовательностей в этом генераторе достаточно узок.

Цель изобретения - повышение быстродействия генератора.

Поставленная цель достигается тем, что в генератор псевдослучайных последовательностей, содержащий генера тор тактовых импульсов, выход кото2013 4

5 о

30 м

4$ ю

55 рого соединен со входом генератора

M-последовательности, введены сумматор и блок динамической памяти, входы которого подключены к выходам генератора И-последовательности соответственно, а выходы блока динамической памяти соединены с соответствующими входами сумматора, выход которого является выходом генератора.

На чертеже изображен предлагаемый генератор псевдослучайных последовательностей, Генератор псевдослучайных последовательностей содержит последовательно соединенные генератор 1 тактовых импульсов, генератор 2 M-последовательности, блок 3 динамической памяти и сумматор 4.

Устройство работает следующим образом.

В момент включения состояние генератора 2 М-последовательности может быть любым, кроме состояния ивсе нули". После включения начинают формироваться символы М-последовательности в блоке 3 динамической памяти. Эти символы поступают на сумматор 4. Результат суммы есть символ образуемой таким образом псевдослучайной последовательности. При этом за каждый период тактового генератора 1 образуется один символ выходной-ПСП на выходе сумматора 4, Сущность работы предлагаемого устройства основана на том, что ряд псевдослучайных последовательностей (М-последовательности, последовательности Гордона-Милса-Велча, последовательности Якоби) имеют составной период, т.е. N=t - t ... где t<,t<,.. °,t " значения простых множителей, на которые разлагается такая псевдослучайная последовательность; S — число простых (возможно повторяющихся) множителей. Для определенности будем рассматривать все для М-последовательности, Если осуществить суммирование символов М-последовательности через интервал, равный одному из множителей или произведению ряда множителей, на которые разлагается такая последовательность, то получится другая псевдослучайная последовательность, каждый символ которой определяется выражением с(; -Е - =,}„ „Х °

1 (i+ e 0 ) rn Ocj г1 i

Формула изобретения

R(k) =N- dphil, R(k) =-са, k: — 0 mod В;

МО mod 2. (2) 5 9420 где j - определяет номер образуемой

ПСП;

I - текущий символ образуемой

ПСП;

"(q+mg)(mod м) - значение символа

М-последовательности по модулю N;

aL - число суммируемых символов

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

=N/ P., 10

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

Период псевдослучайных последовательностей (у„.) равен E. Из соотношения Р=Й1с . нетрудно видеть, что

20 число ПСП, формируемых по выражению (1) будет больше, чем это можно достичь в известном генераторе, где

7=2"- 1. Так как за каждый такт гене25 ратора тактовой частоты 1 формируется один символ выходной ПСП, то бастродействие предлагаемого генератора псевдослучайной последовательности в 2 -1 раз выше, чем в извести ного.

Таким образом, предлагаемое устройство имеет высокое быстродействие

13 6 и позволяет получить больший ансамбль формируемых псевдослучайных последовательностей.

Генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов„ выход которого соединен с входом генератора И"поспедовательности, о т л и ч а ю щ и йс я тем, что, с целью повышения быстродействия генератора, он содер" жит.сумматор и блдк динамической памяти, входы которого подключены к выходам генератора И-последовательности соответственно, а выходы блока динамической памяти соединены с соответствующими входами сумматора, выход которого является выходом генератора, 1

Источники информации, принятые во внимание при экспертизе

Патент США N 3700869, кл. C 235-152, опублик.1972.

2. Яковлев В.В., Федоров P.Ô.

Стахостические вычислительные машины. Л., "Машиностроение". 1974, с.253.

3. Авторское свидетельство СССР .N 524174, кл. ч 06 F 1/02, 1974 (прототип) .

ВНИИПИ Заказ 4841/39

Тираж 731 Подписное

Филиал ППП "Патент", г.ужгород,ул.Проектная,4