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

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

Иллюстрации

Показать все

Реферат

 

»ес?с?к?зни.я

"ЛМ к

"ч | i тюка IVI + иц 572823

ОП ИСАН И Е

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ <ВИДЕTEJIbCYBY

Ооюа Советскик

"-оциалистическик

Республик (61) Дополнительное к авт, свпд-ву (22) Заявлено 09.09.75 (21) 2173579/24 (51) М. Кл.2 G 07С 15,. 00

G 06F 1/02 с присоединением заявки М

Государственный комитет

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

Опубликовано 15.09.77. Б:оллетсиь Х 34

Дата опубликования описания 28.09.77 (53) УДК 681.325(088.8) (72) Авторы изобретения A. E. Леусенко, В. H. Ярмолик, A. H. Морозевич и В. М. Цуриков (71) Заявитель

Минский радиотехнический институт (54) ГEHEPATOP IICEBglOCJI YЧАйНЫХ ЧИСЕЛ

Изобретение относится к вычислительной технике и мо?кет быть использовано для повышения эффективности больших ЦВМ, для расширения возможностей — малых при вероятностном моделировании, à также:в качествс основного блока стахостических ЭВМ.

Известны генераторы псевдослучайных чисел, основанные на применении регистров сдвига. Простейшим генератором псевдослучайных чисел .на базе регистра сдвига является последовательный генератор псевдослучайных чисел,,в котором очередное двоичное число образуется на выходе l,разрядов регистра сдвига через каждые N)l импульсов сдвига. Частота выборки псевдослучайных чисел Е в N раз меньше, чем тактовая частота. Для достижения максимального быстродействия ГПСЧ обычно используют параллельный принцип формирования разрядов псевдослучайного двоичного числа, что приводит к усложнению генератора (1). Другой генератор псевдослучайных чисел соде р?кит регистр сдвига и блок сумматоров по модулю, что так?ке обуславливает большие аппаратуриые затраты (2), Наиболее близким к изобретению техническим решением является генератор псевдослучайных чисел, содер?кащий m триггеров, входы которых подключены к тактовому входу генератора, а выходы являются выходами генератора, и (m — i) сумматоров по модулю два. В этом генераторе на один разряд формируемого числа приходится 0,5 сумматора по модулю два, что больше минимально возможной величины (3). Целью изобретения является упрощение схемы. В описываемом генераторе это достигается тем, что в нем единичные выходы (т — /) -х триггеров соединены со счетными

10 входами (m — j) -х триггеров, а единичные выходы (2т — j) -х и (т+т — j ) -х триггеров подключены к первому и второму входам сумматоров по модулю два соответственно, выходы которых подключены к счетным входам (т—

15 — j) -х триггеров.

На чертеже приведена блок-схема описываемого генератора для случая т-5.

Он содержит т триггеров 1, выходы которых соединены со счетными входами тригге20 ров других разрядов и входами j сумматоров

2 по модулю два соответственно, выходы которых соединены со счетными входами первых (m — -j) триггеров.

25 Количество сумматоров по модулю два и связи в генераторе определяется ключевым числом 1 по табл. 1.

Количество сумматоров j =m — i,для различных т приведены в табл. 2.

Таблица 1

Е nëï (m — l) rn и1 Е или (m — Е) Е илn (rn i) 22

1,4 или 7

11

17

IS

1

1

1 или 3

4

Г>

9

5 или 9

3 или 7

3,9 или 13

З,Г>,7 или 13

31

Таблица 2

1 1 3 7 3

Подписное

Тира>к 738

Изд. № 776

Заказ 2146/1

Типография, пр. Сапунова, 2

4 6 10 18 20 22

В исходном состоянии хотя бы один триггер должен находиться в ненулегом со тоянии.

Это требование справедливо для всех ГПСЧ на базе регистра сдвига. При поступлении синхросигнала СИ1 код, соответствующий состоянию (Š— j) -х триггеров, поступает на счетные входы соответствующих (т — j) триггеров (где i —; т — номер старшего из:используемых триггеров, который определяется разрядностью выходного псевдослучайного числа (j=0, 1, 2, ... i — 1).

Таким образом, информация, хранящаяся на (i — j)-x триггерах, суммируется по модулю два на (т — j)-х триггерах с информацией, сформированной в предыдущем такте и хранящейся на (m — j)-x триггерах. 1-1а сумматорах по модулю два формируются суммы содержимого (т+г — j)-х разрядов с содержимым (2i — j) -х разрядов (j =i, i+1, i+2, ... т--1). При поступлении СИ1 эти суммы суммируются по модулю два с содержимым (m — j)-x разрядов и окончательная сумма остается на (т — j)-x разрядах (j=i, i+1, i+2, ... m — 1).

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

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

Генератор псевдослучайных чисел, содержащий m триггеров, входы которых подключены к тактовому входу генератора, а выходы являются выходами генератора, и (m — i)

20 сумматоров по модулю два, отличаю щи йся тем, что, с целью упрощения генератора, единичные выходы (i,— j)-х триггеров соединены со. счетными входами (m — j)-х триггеров, а единичные выходы (2i — j)-x и (m+i—

25 — j) -х триггеров подключены к первому и второму входам сумматоров по модулю два соответственно, выходы которых подключены к счетным входам (m — j)-x триггеров.

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

1. Яковлев В. В. и Федоров P. Ф., Стахостические вычислительные машины, Л., Машиностроение, 1974, с. 246.

2. Кирьянов Б. Ф. Многоканальный генера35 тор псевдослучайных символов. Известия АН

СССР, «Техническая кибернетика», 1970, №4, с. 107.

3. «Датчик псевдослучайных чисел». ЭИ приборы и элементы автоматики и вычисли40 тельной техники, 1973, № 7,