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

 

Изобретение относится к импульсной технике. Цель изобретения расширение функциональных возможностей и снижение уровня корреляции формируемых чисел. Генератор содержит генератор 2 импульсов, элемент 3 ЗАПРЕТ, делитель 4 частоты, матор 7, регистр 8 адреса и блок 9 памяти. Для достижения поставленной цели в устройство введены регистр 5 сдвига и блок 6 памяти с образованием новых связей между элементами устройства. 1 з.п. ф-лы, 2 ил. Q S tc ел О5 05 -; фиг.1

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„Я0„„1256161

А1 (дц 4 Н 03 К 3/84

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц д, И1 .:Ф. 7а4

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3842075/24-21

° °

22) 07.01.85

46 07.09.86. Бюл. У 33 (71) Ленинградский институт инженеров железнодорожного транспорта им. акад, В,Н,Образцова (72) Г.В.Добрис (53) 621,374,2(088.8) (56) Билинский И.Я., 11икелсон А.К.

Стохастическая цифровая обработка непрерывных сигналов. — Рига: Зинатне, 1983, рис. 5.2а.

Авторское свидетельство СССР

В 1223350 кл. Н 03 К 3/84,28,06.84. (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к импульсной технике. Цель изобретения расширение функциональных возможностей и снижение уровня корреляции формируемых чисел. Генератор содержит генератор 2 импульсов, элемент

3 ЗАПРЕТ, делитель 4 частоты, -сумматор 7, регистр 8 адреса и блок 9 памяти. Для достижения поставленной цели в устройство введены регистр

5 сдвига и блок 6 памяти с образованием новых связей между элементами устройства. 1 g,ï. ф-лы, 2 ил.

1?56161

40

Изобретение относится к импульсной технике.

Цель изобретения — расширение функциональных возможностей и снижение уровня корреляции формируемых 5 чисел.

На фиг. 1 представлена структурная схема генератора псевдослучайных чисел", на фиг. 2 — схема регистра сдвига. 10

Генератор псевдослучайных чисел содержит шину 1 "Пуск", генератор 2 импульсов, элемент ЗАПРЕТ 3, делитель 4 частоты, регистр 5 сдвига, второй блок 6 памяти, сумматор 7, регистр 8 адреса, первый блок 9 памяти. Шина l "Пуск" соединена с первыми входами элемента ЗАПРЕТ 3, делителя 4 частоты и регистра 8 адреса, второй вход которого соединен с вторым входом делителя 4 частоты и выходом элемента ЗАПРЕТ 3, второй вход которого соединен с выходом генератора 2 импульсов. Входы первого блока 9 памяти соединены с первой группой входов сумматора 7 и выходами регистра 8 адреса, разрядные входы которого соединены с выходами сумматора 7, выход переноса и вход переноса которого соединены между собой, Первый вход регистра 5 сдвига соединен с выходом делителя 4 частоты. Шина 1 "Пуск" соединена с вторым входом регистра 5 сдвига, выходы которого соединены с входами второго блока 6 памяти, выходы которого соединены с второй группой входов сумматора 7.

Регистр 5 сдвига содержит Е последовательно соединенных счетных триггеров 10, -10, n- I последовательно соединенных D-триггеров 11, ll выход последнего из.которых (ll„-го) соединен с входом первого счетчика триггера 10„. Выход Й-го 45 счетного триггера 10 соединен с входом первого D-триггера 10 .,1.Входы синхронизации всех счетных триггеров 10 -10 и D-триггеров 11 т ck1

11„ объединены и являются первым вхо- 0 дом регистра 5 сдвига, второй вход которого соединен с входами установки всех счетных триггеров 10 и Dтриггеров 11.

Генератор псевдослучайных чисел работает следующим образом.

tn

В ? -1 ячейках первого блока 9 памяти записана последоватепьность равномерно распределенных псевдослучайных m-разрядных чисел с периодом повторения M=2 -1, соответствующая одному из примитивных характеристических полиномов степени m. Bo второй блок 6 памяти записано 2 констант q, взаймно простых к периоду M=2 -1 и не удовлетворяющих уравнению (q)mod M тп, где т =1,2,...,К, Например при тп=5, M=31 и К=2 из

2 -2=30 возможных значений должны быть исключены значения q=l,2,3,4, 27, 28, 29 и 30, являющиеся решениями уравнения при т =1, значения q=

=14, 15, 16 и 17, полученные при

i =2. Для получения общего числа 2

=16 констант могут быть исключены еще два значения q=9 и 22, дающие максимальный уровень корреляции псевдослучайных чисел Х и X +1. при < =3.

Для улучшения взаимно корреляционных свойств последовательностей

К псевдослучайных чисел Х, получаемых в отдельных циклах, где К вЂ” номер цикла, из множества допустимых значений q могут быть исключены также

J все значения q =2 q mod М и значения

I 1 т1 =И-т1, где q — множество исполь1 i f зуемых значений q, j=1,2...,,m-l, При этих условиях все последова(к} тельности (X. 1 оказываются независи3 мыми, т.е. не содержат одинаковых разрядных последовательностей (M-последовательностей, и не включают взаимно обратных к себе последовательностей (последовательностей с взаимно обратным порядком следования чисел), отличающихся большими выбросами взаимно корреляционной функции.

Если период М=? -1 является составным числом, то число допустимых констант q уменьшается. При малых значениях периода M (m=5- 8) общее число констант q целесообразно взять равным 2 или 2, При большем периоде (тп) 9 ) с целью улучшения корреляционных свойств генерируемых последовательностей это число может быть уменьшено до значений 2 или 2

Для увеличения полного периода последовательности псевдослучайных чисел, формируемых на выходах, в устройстве ист ользуется вспомогательный генератор псевдослучайных чисел, представляющий собой регистр 5 сдвига с обратной связью (фиг. 2), состоящий из f счетных триггеров 10 и (и1256161

f) D-триггеров !1. Если числа и и соответствуют параметрам примитивного характеристического полинома е

X +X +1, то регистром 5 сдвига генерируется последовательность псевдог случайных чисел периода N=? — I. При этом полный период последовательности псевдослучайных чисел, получаемых на выходе устройства, равен произведению периодов N M=(2 — 1)(2 — 1). Та 11

Pq IO ким образом, параметры вспомогательного генератора псевдослучайных чисел (регистра 5 сдвига) и и. I определяются соответственно требуемым периодом вьгходной последовательности и числом г

2 констант q записанных в блок 6 памяти.

Условием случайности следования отдельных циклов в последовательности псевдослучайных чисел периода N

И=(2 — 1).(2 -1) является отсутствие корреЛяции между последовательными индексами децимаций q u q, где

К К+L

=l,N — номер цикла, 1. =1,2,... Так как последовательность индексов децимаций q" хранимых в блоке 6 памяти, полностью определяется последовательностью адресов, формируемых в первых разрядах регистра 5 сдвига, требование некоррелированности отдельных циклов последовательности полностью переносится на последовательность адресов, причем последовательные адреса А„ и А „,-, должны быть некоррелированны на максимально возможном интервале задержки, Этому условию удовлетворяет последовательность псевдослучайных чисел, получаемая на выходах счетных триггеров 10 в регистре 5 сдвига. 4О

Минимальные фазовые сдвиги S бинарных последовательностей (М-последовательностей), получаемых на выходах этих триггеров, определяются и-Х неравенством m/71-(— — )

E-разрядными псевдослучайными числами А„ и А практически отсутству-

K%I. ет. 55

Делитель 4 частоты выполнен с Ъ коэффициентом деления, равным 2 -1, и фиксирует момент окончания очередного цикла генерации М=2 "-1 непонторяющихся псевдослучайных чисел Х (KI

Работа устройства инициируется сигналом по шине 1 "Пуск". По этому сигналу прекращается прохождение тактовых импульсов с выхода генератора

2 импульсов на выход элемента ЗАПРЕТ 3, делитель 4 частоты, регистр

5 сдвига и регистр 8 адреса устанавливаются в исходное состояние. Для регистра 8 адреса исходным состоянием является нулевое, а для регистра

5 сдвига — любое, отличное от нуля, например, все единицы (фиг. 2), По окончании сигнала на шине 1 "Пуск" тактовые импульсы начинают управлять работой устройства.

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

Этот результат является очередным адресом, по-которому из блока 9 памяти считывается очередное псевдослучайное число. В следующем такте содержимое регистра 8 адреса снова увеличивается на величину 11, I

В поле допустимых адресов блока

9 памяти отсутствует один адрес, соответствующий нулевой ячейке, поэтому при переходе через граничное значение адреса А=2 — 1 в результате очередного прибавления константы необходима коррекция адреса, Эта коррекция выполняется с помощью обратной связи с выхода переноса сумматора 7 на его вход переноса. Когда результат суммирования вьгходит за границу допустимых адресов, на выходе переноса сумматора 7 образуется единичный сигнал (единица переноса).

Этот сигнал по цепи обратной связи поступает на вход переноса сумматора 7 в младший разряд, в результате чего значение суммы на выходах сумматора 7 увеличивается на единицу. Та-,, ким образом, при переходе через границу адресов А=2 -1 к очередному адресу прибавляется константа q+1 в остальных случаях адрес модифицируется на величину q. Этим обеспечивается работа сумматора 7 по модулю ? -1 с исключением нулевого адреса из поля допустимых адресов.

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

Союз

ЩЮ

Улц юбит

Составитель IO.Áóðìèñòðîâ

Редактор В..Петраш Техред M.Õîäàíè÷ Корректор М.Максимишинец

Заказ 4834/55

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1)3035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4

5 12561

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

5 сдвига устанавливается в новое состояние, в результате чего из блока 6 памяти считывается новая константа q. По окончании Н2 -1 циклов работы регистр 5 сдвига устанав- . ливается в исходное состояние, после чего процесс генерации псевдо- !О случайных чисел повторяется.

1, Генератор псевдослучайных чи- 15 сел, содержащий шину "Пуск", соединенную с первыми входами элемента

ЗАПРЕТ, делителя частоты и регистра адреса, второй вход которого соединен с вторым входом делителя часто- 2О ты и выходом элемента ЗАПРЕТ, второй вход которого соединен с выходом генератора импульсов, первый блок памяти, входы которого соединены с первой группой входов сумматора и выходами регистра адреса, разряднйе входы которого соединены с выходами сумматора, выход переноса и вход переноса которого соединены между собой, отличающийся тем, что, с целью расширения функциональных возможностей и снижения уровня корреляции формируемых чисел, он содержит второй блок памяти и регистр сдвига, первый вход которого соединен с выходом делителя частоты, шина "Пуск" соединена с вторым входом регистра сдвига, выходы которого соединены с входами второго блока памяти, выходы которого соединены с второй группой входов сумматора.

2. Генератор по п ° 1, о т л и.ч а ю шийся тем, что регистр сдвига содержит E последовательно соединенных счетных триггеров, n-I последовательно соединенных D-триггеров, выход последнего иэ которых соединен с входом первого счетного триггера, выход Е-го счетного триггера соединен с входом первого Этриггера, входы синхронизации всех счетных триггеров и D-триггеров объединены и являются первым входом регистра сдвига, второй вход которо" го соединен с входами установки всех счетных триггеров и D-триггеров.