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

 

Изобретение относится к вычислительной технике и может быть использовано при решении задач методом Монте-Карло, статистическом моделировании и т.д. Целью изобретения является повышение быстродействия. Генератор содержит группу Д-триггеров 1, коммутатор 2, генератор равновероятного бинарного сигнала 3, генератор тактовых импульсов 4, сумматор по модулю два 5, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6. Генератор позволяет получать псевдослучайную апериодическую последовательность независимых равномерно распределенных M-разрядных случайных чисел X в соответствии с рекуррентным соотношением, приведенным в описании изобретения. 1 ил, 1 табл.

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

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

РЕСПУБЛИК

„„SU„„1529218 (584 06F 7 58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTQPCHOMV СВИДЕТЕЛЬСТВУ

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4346651/24-24 (22) 22.12.87 (46) 15.12.89. Бюл. № 46 (71) Томский политехнический институт им. С. М. Кирова (72) Ю. К. Рыбин и А. М. Носов (53) 681.3(088.8) (56) Авторское свидетельство СССР № 634329, кл. G 07 С 15/00, 1976.

Авторское свидетельство СССР № 924706, кл. G 06 F 7/58, 1980. (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использова2 но при решении задач методом МонтеКарло, статистическом моделировании и т. д.

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

D-триггеров I, коммутатор 2, генератор равновероятного бинарного сигнала 3, генератор тактовых импульсов 4, сумматор по модулю два 5, блок элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 6. Генератор позволяет получать псевдослучайную апериодическую последовательность независимых равномерно распределенных m-разрядных случайных чисел Х в соответствии с рекуррентным соотношением, приведенным в описании изобретения. 1 ил, 1 табл.

1529218

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

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

На чертеже представлена структурная схе— ма генератора.

Генератор содержит группу D-триггеров 1, коммутатор 2, генератор 3 равновероятного бинарного сигнала, генератор 4 тактовых импульсов, сумматор 5 по модулю два, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6.

Генератор работает следующим образом. 15

Пусть на и-м такте его работы в груп-! пе 0-триггеров 1 записано двоичное m-разрядное число Л,. Соответствующий этому числу двоичный код подается на информационные входы коммутатора 2. Коммута-! тор 2 передается на выход сигналы Х(1)„,...X(k). лишь с определенных D-триггеров группы, выбранных исходя из условия получения псевдослучайной последовательности максимальной длины при определенном виде порождающего полинома. В результате форми- 25 руется определенная структура обратной связи. Изменение этой структуры, т. е. переход к другому режиму работы генератора, отвечающему иному порождающему полиному, осуществляется после подачи соответствующего сигнала на управляющий вход коммутатора, являющийся тем самым входом задания режима работы генератора. Число выходных шин коммутатора 2. может изменяться от 1 до 3 в зависимости от используемого порождающего полинома.

Сигналы Х(I)„,...Х(k)n с выхода коммутатора 2, а также сигнал Q с выхода. генератора равновероятного бинарного сигнала 3 поступают на входы сумматора 5 по модулю два. Генератор равновероятного бинарного сигнала формирует случайную 40 последовательность, принимающую в произвольный момент времени с равной вероятностью два возможных значения: Q=O или

Q=1, причем средняя частота изменений этих значений должна быть несколько большей, чем период М-последовательности, рав- 45 ный 2л — 1. На выходе сумматора по модулю два образуется двоичный сигнал

Z=X1)Р ... + Х(),О+ Q, подаваемый на 0вход первого триггера группы D-триггеров 1.

Двоичный код, соответствующий записанному в группе 0-триггеров 1 числу

Л ., подается также на входы блока ИСКЛЮЧАЮЩЕЕ ИЛИ, реализующего в обратном коде кусочно-линейную зависимость: д »j(2 — 1) — 2Хл при Х„(2 2Хл — (2 — 1) и р и Хл) 2л

Действительно, пусть Մ— двоичный код, снимаемый с инверсных выходов D-триггеров на и-м такте работы: Л.=(X(m)nlX(m l)nl".IX(l)nj где X(;)n — значение, имеющее место в

i-м разряде кода, i=1,2,...,т; X(»„=0 или

Х(;)л=1. Если X(m)n=0, что соответствует выполнению условия Х„(2, то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ блока 6 появится нулевой сигнал.

Вследствие этого сигналы на выходах этих элементов будут повторять сигналы на их первых входах. Если пренебречь пока воздействием сигнала с выхода сумматора 5 по модулю два, это означает, что на D-входах

0-триггеров будет иметь место кодовая комбинация: (Л()„IX(m ).1...1Х(0„!О). В момент появления тактового импульса от генератора 4 на тактовых входах D-триггеров все они установятся в состояния, соответствующие сигналам на D-входах. В результате на инверсных выходах D-триггеров образуется кодовая комбинация (F(X ) =,тХ(,) Х

Х! Х(,>„j...)Õ(ó)„(1), которую можно также представить в виде разноса двух кодов:

F(x ) = (1i1...(1) — (x, „„) х „ /.../Х(,)ÄIO).

Так как первый.код соответствует значению

2 — 1, а второй 2Л„, то получаем, что в данном случае F(Xn)=2 — 1 — 2Лл.

Если же Y()„=1, что соответствует выполнению условия Хл)2, то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 6 появится единичный сигнал. Вследствие этого сигналы на выходах этих элементов будут инверсными по отношению к сигналам на их первых входах. Опять временно пренебрегая сигналом с выхода сумматора 5 по модулю два, получим, что с приходом тактового импульса от тактового генератора 4 на инверсных выходах Dтриггеров образуется кодовая комбинация

F(Xn)=(Л(тл — !)л1Л(ле — 2)л! ° ° ° IX(1)nl 1)в,KoTopy(o no бавляя еще один (т+ ) разряд можно также представить в следующем виде: (Л л)=(Л(лт)л1Л(ле — >)nIX(m — 2)лl ° "1Л(1)л10) (Х(.,„IOI". 10)+(OIOI" !1).

Так как первая кодовая комбинация соответствует значению 2Л „„вторая равна 2, а третья — единице, то в итоге получаем

F(Xn)=2Xn — (2 — 1) .

Учитывая сигнал с выхода сумматора

5 по модулю два, получаем, что в момент появления очередного тактового импульса с генератора 4 тактовых импульсов на инверсных выходах D-триггеров группы 1 формируется очередное псевдослучайное число в соответствии с соотношением J. =F(X,)— — +n+1= F(Xn) — (X(l)nO ... X(k)n Qn+ l i ГДЕ

F(Xn) определяется указанной формулой.

В результате на инверсных выходах

D-триггеров образуется псевдослучайная апериодичная последовательность независимых равномерно расположенных т-разрядных двоичных чисел.

Ниже приведены некоторые варианты подключения обратной связи.

1529218

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

Генератор псевдослучайных чисел, содержит группу D-триггеров, инверсные выходы которых соединены с информационными входами коммутатора, управляющий вход кото- 5 рого является входом задания режима работы генератора, выход коммутатора подключен к первому входу сумматора по модулю два, генератор равновероятного бинарного сигнала и генератор тактовых импульсов, выход которого соединен с тактовыми входами D-триггеров группы, отличающийся тем, что, с целью повышения быстродействия, в него введена группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый вход каждого i-го элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ группы соединен с инверсным выходом i-го 0-триггера группы, а выход с D-входом (i+1) -го D-триггера группы (i=1 2, т — 1) группы, т — число разрядов формируемого числа, вторые элементы

ИСКЛЮЧАЮЩЕЕ ИЛИ групп соединены с инверсным выходом m-го D-триггера группы, D-вход первого триггера группы соединен с выходом сумматора по модулю два, второй вход которого соединен с выходом генератора равновероятного бинарного сигнала.

1 -У разрядов подключения обратной связи

И=2 — 1

4или 2

4или1, 2, Зили4или1, 2, 5 били2или2, 4, 6

1, 4, 5или1, 3, 4или2или4

5 или 1, 4, 7 или 3, 7, 8

6 или 1, 4, 5 или 7

8или1, 2, Зили8

10или1, 2, Зили5

9 или 5, 8, 9 или 5, 6, 9

5или1, 2, 13или12

13 или 9, 12, 13 или 6, 8, 14

15 или 1, 7, 8 или 1, 4, 5 или 1, 8, 9 или

14

16илибили3, 6, 15или4, 6, 12

15 или 1, 3, 4 или 7

11 или 1, 7, 8 или 12

7илиЗ, 5, билиб

18 или 1, 3, 4или2, 16, 18

20 или 1, 2, 3 или 4, 16, 20

22 или 2

19 или 1, 14, 15 или 1, 9, 10 или 1, 5, 6

8или2, 3, 5

4или1, 18, 19или1, 7, 8или4

9 или 3, 5, 6 и20или1,9или1,7,8или1,3,4

28 или 1, 2, 3

17 или 3, 23, 24

1,7,8или1,6,7или1,3,4

29 или 3, 22, 23

21 или 1, 13, 14

31

63

127

511

1023

2047

8191

16383

Составитель Г. Филаретов

Редактор О. Спесивых Техред И. Верес Корректор А. Обручар

Заказ 7642 44 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при I ÊÍÒ СССР

l 13035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат «Патент», г. Ужгород, ул. Гагарина, 10!

1, 3, 1, 3, 1, 5, 7 или

1, 2, 1, 5, 1, 7, 1, 9, 4, 8, 2, 3, 2, 11, 1, 14, 2 или

1, 11, 1, t4, 1, 10, 2, 5, 1, 17, 1, 19, 1, 21, 1, 18, 3, 7, 1, 3, 2, 7, 2, 7, 1, 19

1, 27, 2, 15, 4 или

2, 27, 1, 20, 32767

131071

262143

524287

2097151

4194303

8388607

16777216

33554431

67108863

134217727

536870911

1073741823

2 147483647

8589934591