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

 

О П И С А Н И Е <,1оо1ои

ИЗОБРЕТЕНИЯ Союз Советских

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 20.10.81 (2I ) 3348025/18-24 (5l)M. Кл. (06 F 7/58 с присоединением заявки №

Государственный комитет (23) Приоритет оо делам изобретений и открытий

Опубликовано 28.02.83. Бюллетень № 8

Дата опубликования описания 02.03.83 (53) УДK 681.325 (088.8) (72) Автор изобретения (1"

А. Н. Морозевич

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

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

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

; чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи 1

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

Известен также генератор псевдослучайных чисел, содержащий группу сумматоров по модулю два и грушту триггеров, выходы синхронизации которых подключены к выходу генератора тактовых импуль го

cos (2g.

В данном генераторе псевдослучайных чисел повышено быстродействие, но пери од генерируемой последовательности сохранен таким же как в f 1 ).

Наиболее близким к предлагаемому по технической сущности является генератор псевдослучайных чисел, содержащий две группы сумматоров по модулю два, две группы элементов И, группу алементов ИЛИ, группу триггеров, входы синхронизации которых подключены к выходу генератора тактовых импульсов и входу генератора равновероятной дво ичной цифры, причем к первым входам т -ых сумматоров по модулю два подключены единичные выходы т -ark триггеров, к вторым входам j старших сумматоров по модулю два подключены выходы ) младших триггеров, к вторым входам ттт- j младших сумматоров по модулю два

4 подключены выходы m- $ старших сумма оров по модулю два 1 3 j.

В известном устройстве при высоком быстродействии практически отсутствует период последовательности, кодов формиЭ 10010 руемых псевдослучайных чисел. Недостатком этого устройства является большой объем используемого оборудования.

Цель изобретения — сокращение обч ема используемого оборудования, т.е, упрощение генератора.

Поставленная цель достигается тем, что в генераторе псевдослучайных чисел, содержашем две группы из rn суммато- ров по модулю два и группу из гп триг 10 геров, синхронизирующие входы которых подключены к выходу генератора тактовых импульсов и входу генератора равновероятной двоичной цифры, а выходы триггеров группы подключены к первым 15 входам соответствующих сумматоров по модулю два первой группы, причем выходы j (f (m) младших триггеров группы подключены к вторым входам j старших сумматоров по Модулю два первой группы,20 а вторые входы п — j младших сумматоров по модулю два первой группы под-! ключены к выходам m - старших сумматоров по модулю два первой группы, ин формационные входы триггеров группы 25 подключены к выходам соответствующих сумматоров по модулю два первой группы, третьи входы которых подключены к первому выходу генератора равновероятностной двоичной цифры, второй выход кото- Зр рого подключен к первым входам сумматоров по модулю два второй группы, вторые входы которых подключены к выходам соответствующих сумматоров по модулю два первой группы.

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

tv=5; на фиг. 2 - функциональная схема генератора при m=3; на фиг. 3 — пример временной диаграммы сигналов, фор

40 мируемых на выходе генератора тактовых импульсов (точка а), по приходу которых триггеры устройства меняют свое состояние, и на в1ором (прямом) выходе генератора равновероятной двоичной цифры

45 (точка в); на фиг. 4 - граф состояний и последовательности переходов элементов памяти (триггеров) генератора псевдослучайных чисел при т = 3 для порождающего полинома У (Х ) = Х +X +1 определенный начальным состоянием 101 и временной диаграммой (фиг. 3) °

Генератор псевдослучайных чисел со» стоит из тп сумматоров 1 по модулю два первой группы, rn сумматоров 2 по модулю два второй группы, гп триггеров

3, генератора 4 тактовых импульсов, генератора 5 равновероятной двоичной циф4 ры. Причем входы сумматоров 1 по модулю два первой группы подключены к выходам триггеров 3 и генератора 5 равновероятной двоичной цифры таким образом, что на выходе сумматоров 1 формируются сигналы в соответствии со следуюшей системой логических уравнений: п ) t1l-1О j i OЪ у 1=-0i, jm i Е мm+1- О+а, ь),3+1,...tel ю

r äå Ъ „- единичный выход (rn -1 )-го триггера;

g „- выход (m + j — 1 )-го сумматора по модулю два первой, группы; — первый (инверсный) выход генератора 5 равновероятной двоичной цифры; знак 9 — означает операцию суммирования по модулю два; — номер разряда регистра сдвига, выход которого вместе с выходом

tn -го разряда соединен с входами сумматора по модулю два в последовательных структурах.

Если m =5, j =3 и Ь =О, то система (1) примет вид

Оъ, 4- „О, а =ь (-+.)- „

2 3 3

@ = О+ " > - Ь1 ® а следовательно, при Ъ =0 пРедлагае» мое устройство (фиг. 1) позволяет генерировать пятиразрядные коды псевдослучайных чисел М -последовательности, порождаемой полиномом Ч (х) = х + х +

+1 (как в устройстве-прототипе). При

Ь =1 система (1) принимает вид а =Ъ ОЪ +-Ь,О+ЪД а5=ЪЗ8 1

5 3 О,; „=ü„Î+.

Очевидно, что М последовательности, генерируемые при Ь =0 и b l, будут иметь одинаковые периоды, но очередность появления кодов и их состав различны (фиг. 4).

Входы сумматоров 2 по модулю два второй группы подключены к сумматорам

1 по модулю два первой группы и второму выходу генератора 5 в соответствии со следующей системой уравнений: и = с1.(+)ф, 1=,2,..., m {2) где с11 - выход i -го сумматора по мо1 дулк два второй группы; — второй (прямой) выход генератора 5.

5 1ОМО

Кроме того, выход генератора 4 тактовых импульсов подключен к входу генератора 5 равновероятных двоичных цифр и первым входам триггеров 3.

Устройство функционирует следующим 5 образом.

Исходное состояние триггеров — произволвное. В зависимости от значения двоичной цифры, сформированной генератором 5, на выходах сумматоров 1 по- 10 является ачередной код первой или второй М-последовательности. По переднему фронту тактового импульса в триггеры 3 записывается код с выходов сумматоров

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

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

Более подробно процесс генерирования псевдослучайных чисел поясним на конкретном примере. Пусть в первоначаль- 25 ный момент времени на триггерах 3 (фиг. 2) записан код 101 и пусть генератор 5 на своем втором (прямом) выходе формирует сигнал, как это представле» но на фиг. 3. Тогда до прихода первого З0 тактового импульса на выходах сумма1 торов 1 в соответствии с (1) формируется код $ =010, а на выходах сумматоров 2 в соответствии с (2) — код

101. По переднему фронту первого так-M тового импульса, пришедшего с выхода генератора 4 на первые (синхро-) входы триггеров 3, в триггера 3 записывается код 010. По заднему фронту первого тактового импульса (фиг. 3) значение, 40 сигнала на выходах генератора 5 меняется на противоположное. После окончания переходных процессов на выходах сумматоров 1 устанавливается код 100, на выходах сумматоров 2 - также код 4s

100. Подобным образом триггеры меняют свое состояние в зависимости от значения сигналов на выходе генератора

5 и по приходу последующих импульсов.

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

Из вышеприведенного описания функционирования генератора псевдослучайных

55 чисел следует, что значения > форматер > руемые на выходах сумматоров 1 по модулю два первой группы, в каждый кон97 6 кретный такт являются значениями кодов двух различающихся между собой

М-последовательностей. Каждое последующее значение „ является следующим. значением либо одной и той же М-после довательности, либо. другой М»последовательности, что определяется значением двоичной цифры, формируемой на выходе генератора 5 равновероятной двоичной цифры. Нетрудно замеФить, что при фиксировании на первом выходе генератора

5 значений 1 или 0" предлагаемый генератор генерирует одну из двух М-последовательностей, представленных на фиг. 4. На фиг. 4 пунктирами показчны для сравнения направления изменения состояний регистра сдвига последовательного генератора псевдослучайных чисел, типа (1).

Преимущества предлагаемого генератора псевдослучайных чисел по сравнению с прототипом заключаются в сокращении объема используемого оборудования. Так удельные аппаратные затраты на один разряд псевдослучайного числа в прототипе составляют один сумматор по моду лю два, один элемент И, 1/2 элемента

ИЛИ, D -триггера, 1/2 генератора рав новероятной двоичной цифрь и 1/2 генератора тактовых импульсов. В предлагаемом.же устройстве для этих целей требуется лишь один сумматор по модулю два, 1/2Э -триггера, 1/2 генератора равновероятной двоичной цифры и 1/2 генератора тактовых импульсов. Следует. заметить, что в прототипе и предлагае- мом устройстве значения е и корт релированы, так как порождаются одним состоянием триггеров (в предлагаемом устройстве зависимость меньше, так как одно и тоже состояние триггеров может породить два значения (1, два значения.

, в прототипе — только по одному) .

B ряде случаев наличия корреляции огра-.

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

Кроме того, как это следует из (1) и (2) и видно из фиг. 4 в устройстве

7 1001 генерируются последовательности из 2 и чисел (включая нулевую комбинацию), а не 2 -1. Последнее также является отличительным положительным свойством устройства.

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

Предлагаемое устройство отличается высоким быстродействием: скорость формирования о -разрядного числа в и раз выше.

Формула изобретения два первой группы, причем выходы

j (1 (Р1 ) младших триггеров группы подключены к вторым входам $ старших сумматоров по модулю два первой группы, 5 а вторые входы тп - j младших суммато ров по модулю два первой группы подипочены к выходам Ф -1 старших сумматоров по модулю два первой группы, о тличающийся тем,что,сцелью

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

20 соответствующих сумматоров по модулю два первой группы.

Генератор псевдослучайных чисел, содержащий две группы из rn сумматоров по модулю два и группу из rn триггеров, синхронизирующие входы которых подключены к выходу генератора тактовых импульсов и входу генератора равновероятной двоичной цифры, а выходы тригге- ЗО ров группы подключены к первым входам соответствующих сумматоров по модулю

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

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

Вероятностные вычислительные машины, Л., Машиностроение", 1974, с. 344.

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

¹ 634329, кл. С, 06 F 7/58, 1976, 3. Авторское свидетельство СССР

¹ 708381, кл. 5 06 F 7/58," 1978. (прототип) .

1001097

0 12 Ю Ф 5 Е 7 85

RHHHllH Закаэ 1 397/5б Тираж 704 Поцпнсное

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