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

О П И С А Н И Е п11 „ цгд1

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) ЗаявлЕно14.09,73 (21) 1961299i18-24 (51) М. Кл. 6 Ob j 1702 с присоединением заявки ¹ —Государственный комитет

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

Опубликовано 25.04.75. Бюллетень № 15 (53) УДК 681.3(ОЯВ.Е)

Дата опубликования описания 1О.04.7 5 (72) Авторы изобретения

Г, В, Добрис и В. В. Яковлев (71) Заявитель Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. акад. В. Н. Образцова (54) ГЕНЕРАТОР РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ

ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ индекс 1. - указывает на номер разряда.

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

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

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

Это достигается тем, что первые tn раз- 10 рядов регистра сдвига выполнены на триггерах со счетным входом, а осталькые

{П -%) разрядов — на триггерах с установочными входами, причем счетные входы первых тг1 триггеров соединены с единич- 15 ными входами соответствуюлпгх (1\ -ttl) триггеров, установочные входы которых подключены к выходам первых tel тригге- . ров соответственно.

Схема генератора изображена на чертеже.

Генератор псевдослучайных чисел представляет собой tl -разрядный регистр сдвига, обхваченный цепью обратной связи и содержшпий группу триггеров 1 со счет- х5

2 ным входом 1, 2, ..., 11 и группу триггеров П с шинами установки в "0" и "1"

ГП + 1,..., fl Коммутация разрядов регис ра сдвига выполнена следующим образом: счетный вход - любого из триггеров 1, 2 ..., тг 1, например с номером L, соединяется с единичным выходом триггера, имеющего комер { И, -tn + { ), а единичный и нулевой установочные входы любого из триггеров N + 1, ...,11,, например с номером ), — с соответствующими выходами триггера, имеющего номер (j — tn)

: Цепи синхронизации работы триггеров и

:установки их в на гальное состояние на

:схеме не показаны, хотя их наличие, как и в любой схеме с элементами памяти,, обязательно.

Рассмотрим принцип работы обычного

: генератора псевдослучайных чисел в тече ние tlat тактов.

Начальное состояние разрядов регистров сдвига обозначим символами 0

à2 0 атт, где йi (- Q. a после второго такта

001 01 1 101

010110001

011101100 35,....

1) числа Щ и и должны соответство1

: вать индексам единственных единичных коэффициентов неразЛожимого и примитивного многочлена степени t1

40.

Если указанные операции выполнять на каждом такте работы схемы, от некоторо, го К-того состояния регистра за один такт можно будет перейти к (K + fA ) состо-. янию, минуя промежуточные, т. е, путем изменения логики работы регистра сдвига можно достичь Щ -кратного ускорения .работы генератора псевдослучайных чисел.

Такой алгоритм работы генератора и реа лизуется схемой, показанной на чертеже.

В этой схеме триггеры со счетным входом выполняют операцию суммирования по мо, дулю "2 в соответствии с уравйением, : а триггеры с установочными входами— функцию хранения предшедствующих состо агний первых (1 -Щ) разрядов регистра, Генератор псевдослучайных чисел рабо тает следующим образом.

В исходном состоянии в регистр сдвига заносится произвольное, но не нулевое

Поскольку каждое последующее састояние регистра образуется в результате сдвига вправо на один разряд содержимого ре гистра,в предыдущем такте и записи в освободившийся разряд символа О или

1" с выхода сумматора цепи обратной связи, в результате действия Щ тактовых импульсов получим следующую после1довательность состояний регистра сдвига: .после первого такта сдвига (т(И) «l

Здесь знак + означает суммирование по модулю "2".

Ф

Сравнивая конечное состояние регистра сдвига с исходным, затем, что оно полу; чается путем суммирования по модулю

"2" начальных состояний собственного т -того и К -foal+ l. разрядов для первых д разрядов ретистра сдвига и перезаписью в остальные начальных состояний первых (tl — t7l) разрядов регистра. д -разрядное двоичное число. Нулевое со.стояние регистра запрещено. Если нри эксплуатации: устройства не требуется .точного повторения генерируемой последовательности, достаточно установить в единичное состояние один из разрядов регистра. Под действием тактовых импульсов в регистре формируется последовательность Я -разрядных двоичных чисел, представля:1О ющая собой результат выполнения последо. вательности операций, описываемых урав: нением. Эта последовательность будет ко« лией последовательности псевдослучайных

; чисел, генерируемой обычным генератором, 5 если в последнем чтсло сдвигов Я выб, рать равным tel .

Пример. Если в исходном состоя,.нии в генераторе записано число

1017.00111, последующими числами . : последовательности будут:

Для генерирования схемой последовательности равномерно распределенных псевдослучайных чисел с максимальным перио, дом Я = 2 -1 необходимо выполнение

YL следующих условии:

2) чисти fA и И = 2 -1 должны

tl быть взаимно простыми.

Для получения последовательности пеев; дослучайных чисел с большим числом ста45 тистически независимых разрядов желатель-, но также, чтобы величина tA была какможно ближе к tl .

"з

Ниже приводится таблица значений и

, и ttl, составленная с соблюдением перечисленных условий. Пользуясь этой табли, цей, по .заданному периоду последователь55; ности Х и разрядности псевдослучай . ных чисел . fA, можно выбрать необ, ходимую структуру предложенного генера; тора псевдослучайных чисел, 5

Я, И, Значения fl1

Значении tl

1023

l5

20

25

28

20

Предмет изобретения

Генератор равномерно распределенных псевдослучайных чисел, содержащий ?1разрядный регистр сдвига с сумматором по модулю "2" в цепи обратной связи, отличающийся тем, что, с ! целью повышения быстродействия, первые ф разрядов регистра сдвига выполнены

2047

32767

131071

262143

2097151

4194303

8388607

33554431

2147483647

8589934591 на триггерах со счетным входом, а остальные (И вЂ” Al) разрядов — на триггерах с установочными входами, причем счетные входы первых Щ триггеров соединены

30,с единичными выходами соответствующих (tl — Ф) триггеров, установочные входы

° которых подключены к выходам первых fll триггеров соответственно.