Генератор случайных чисел Советский патент 1990 года по МПК G06F7/58 

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

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

На фиг.1 изображена структурная схема генератора; на фиг.2 - функциональная схема узла синхронизации; на фиг.З - граф, поясняющий циклическую последовательность выбора команд; на фиг.4 показано содержимое Ячеек, хранящих команды; на фиг.5 изображены временные диаграммы реализации команд; на фиг.6 дана иллюстрация заполнения блока памяти выходными значениями.

Генератор (фиг.1) содержит блок 1 памяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5,эле-, мент 6 задержки, элемент ИЛИ 7, регистры 8-10, блок 11 памяти, узел 12 синхронизации, сумматоры 13, 14, схему 15 сравнения, элемент И 16, блок t7 мультиплексоров, регистр 18, дат-. чик 19 равномерно распределенных случайных чисел, элемент ИЛИ 20, счетчик 21, регистр 22, блок 23 памяти, элемент 24 задержки.

Узел 12 синхронизации (фиг.2) содержит элемент ИЛИ 25, элемент 26 задержки, RS-триггер 27, элемент И 28, генератоп 29 тактовых импульсов, элементы 30, 31 задержки, мультиплексор 32, блок 33 памяти, регистр 34, блок 35 элементов И, элемент 36 задержки .

В основе работы генератора лежат следующие теоретические положения. В генераторе получение текущего случайного числа х для заданного распределения

(1)

15 где Р J - вероятность появления числа

;.и Pi 1) производится с

20

помощью вспомогательного (имплицирующего) распределения (вектора)

р р р г , г,.

(2)

0

5

0

5

0

5

п - число двоичных разрядов для кодирования равномерно распределенных случайных чисел.

На первом шаге формируется значение YV, а на втором производится функциональное преобразование значения у/ в значение х. Выполнение шага 1 для формирования последующего числа совмещено со временем вьтол- нения шага 2, относящегося к процессу формирования теущего числа х.

Имплицирующее распределение (2), соответствующее заданному распределению (1), предварительно вычисляется по известному алгоритму.

Формирование значений у; в генераторе производится по следующему алгоритму, являющемуся модификацией алгоритма Уэлкера. Сначала вычисляются данные, которые заносятся в блок 1 памяти по следующему правилу.

Пусть К n ,(aj - целое, не меньшее а). Разбиваем интервал (0,1) на 2 равных интервалов

О zxj ll

iv 2

24

2 - 1

ТГ-.

пронумеруем их числами О,1,...,2 -1

К

соответственно. Поскольку m 2 , то среди чисел PJР найдется PJ а

- -2-..

Ставим интервалу с номером

О в соответствие число у-.

за

о

1599856

жательно в блоке 1 памяти в ячейку

к

с адресом 7. - t + 1 помещаются ла Z и А, а в ячейках с адресами А и А + 1 - числа У и у

соответt жл л f. - --- - - - D - 4fI

. ственно), РВ заменяется на О, а Р на РВ +

Ре - -рЕсли Pg О, то ос

Изобретение относится к вычислительной технике и может быть использовано в качестве задающего блока в имитаторах случайных процессов, а также в качестве специализированного вероятностного процессора. Цель изобретения - повышение быстродействия. Генератор содержит первый блок памяти, датчик равномерно распределенных случайных чисел, первый сумматор,четыре регистра, четыре элемента ИЛИ, первый элемент задержки, мультиплексор, схему сравнения, узел синхронизации. Дополнительно введены два регистра, блок мультиплексоров, счетчик, второй и третий блоки памяти, элемент И, второй сумматор, второй элемент задержки. Узел синхронизации содержит четыре элемента задержки, Р-триггер, элемент, генератор тактовых импульсов, мультиплексор, блок памяти, регистр блок элементов И. 1 з.п. ф-лы, 2 ил.

меняем на число Р.

- ()

(это соответствует тому, что в блок 1 памяти в ячейку с адресом О записывается число у-). Теперь остается 2-1 интервал и t отличных от нуля чисел в последовательности Р ,.. .,Pr,(t m или t m-D , Если t ё: 2 - 1,

то вновь выбирается Р.

а у

сопоставляется интервалу 1, из Р

вычитается

-|- (т.е.

в блоке 1 памяти устройства число у записывается в ячейку с адресом 1), и так продолжается до тех пор, пока число t не- нулевых чисел в последовательности Р-Ч-.ч не станет больше (ровно

I 14

на единицу) числа интервалов, которым не сопоставлены числа. Без потерн общности считаем, что числа , ненулевые. Интервалы, которым не сопоставлены числа yj, остались с номерами 2 -t+1,...,2 - 1. Далее применяется рекурсивная процедура M(t).

Описание процедуры М(t).

Вход: числа Pj,...,Р, интервалы с номерами 2 -t + 1,..., 2,-1,

1 -р, то

( + 1)-му интервалу

сопоставляется число у.

- (т.е. в блок t памяти в ячейку с номером 2 - t + 1 записывается у), число Р заменяется на О и применяется процедура M(t-1).I ,

нет равных т° выбираются такие

1

Р и Р в е

что Р.

Ре -Гл

а Р, - -i T

(легко увидеть, что такие два числа эеегда найдутся). (2 - t + 1)-му интервалу сопоставляются два числа + 1/2

2 + РЙ и А (содер

талось t-1 число и t-2 интервала. Далее применяется процедура M(t-1). Если Р О, то имеется t-2 ненулевых числа и столько же интервалов. В этом случае делается шаг, описанный ранее.

Далее выполняются процедуры формирования значений у.

Шаг 1. По первьм S разрядам случайного числа , получаемого от датчика 19, считывается из блока 1 памя-; ти слово с адресом (ir), где ( g - двоичный код первых S разрядов , R - двоичный код начальной базы адреса. Если это У , то процесс закончей за одно обращение к памяти.

Шаг.2. Если это слово состоит из чисел Z и А, то производится сравнение: если Z , то считывается число у из ячейки с адресом (А+1), в

противном случае считывается У из ячейки с адресом А, т.е. процесс заканчивается за два обращения к памяти.

Шаг 3. Если же слово с адресом

остоит из базы адреса А, то считывается из ячейки с адресом А + + у (где у - смещение) двоичный код следующих разрядов числа f и повторяется шаг 1. Алгоритм работает, по-

ка не считывается слово .

При работе устройства происходит циклическое считывание из блока памяти команд (к,. К,, Ki,K4) с после. дующей реализацией этих команд. Ал- 45 горитм работы изображен на фиг.З.

Формат вьшолняемых команд показан на фиг.4. Поле 1 содержит код операции, поле 2 команды К - число

; j

5flr Z F(y), поле 3 - тип операнда:

N -«

В командах 1С, - это база относительного адреса (А), в команде К, - это код у ; (значение имплицирующего вектора).

По команде К, определяется отрезок интервала, в который попало число , и формируется адрес команды К2 или команды К, или команды К.

55

По команде К уточняется дальнейшее положение числа на интервале ,и формируется адрес команды К или комавды Kj, или команды К.

По команде К число xj считывается на выход устройства.

По команде К, уточняется интервал и формируется адрес команды К или команды К4

Все команды (К , - К) реализуются с помощью микрокоманд, которые вырабатываются в узле 12. Последовательность выполнения команды К показана в табл. 1 ; команды Кг.- в табл.2;.кбманды К - в табл.3; команды К 4 - в табл.4. I

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

По сигналу Пуск по адресу, определяемому регистром 4, происходит считывание из блока 1 памяти команды К, и запуск датчика 19. Дальнейший алгоритм работы устройства изображен на фиг.З. Управление функционированием генератора осуществляется узлом 12 синхронизации. Работу узла 12 поясняет табл.5. Временные диаграммы управляющий сигналов на выходе узла 12 показаны на фиг.З.

Узел 12 синхронизации начинает работать по сигналу Пуск, посту-, пающему через элемент ИЛИ 25, или по сигналу С . По этому сигналу триггер 27 открывает элемент И 28 через время, определяемое элементом 26 задержки, необходимое для считывания команд в регистры 8-10. Через элемент И 28 с генератора 29 тактовых импульсов поступает серия импульсов, число импульсов в которой зависит от команды К; (i 1,4). Под действием каяздог.о импульса этой серии происходит считывание из блока 33 памяти в регистр 34 одной микрокоманды. Адрес очередной микрокоманды поступает из регистра 34 через мультиплексор 32 в блок 33 памяти под действием управгяющего сигнала С( . Частота импульсов считывания, посту11ающих от генератора тактовых импульсов,определяется быстродействием блока 33 памяти.

Выходные значения считываются из блока 11 памяти. Иллюстрацию заполнения блока 11 значениями х показаны на фиг.6.

1599856

Формула

изобретени

0

5

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

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

10

n

1599856

Таблица

Описание микроопераций

Считьшание случайного числа из датчика 19 в регистр 18

Считывание из блока 23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов управляющих работой блка мультиплексоров 17 (первый номер разбиения отрезка 0,1), и подключение к сумматору 13 адреса первого разбиения Модификация адреса в сумматоре 13 . Считьшание из блока 1 памяти очередной команды по сформированному адресу

Описание микроопераций

Перевод счетчика 21 в значение, соответствующее следующему уровню распределенияСчитывание из блока 23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старике раряды адреса) сигналов , управляющих работой блока 17 (второй номер разбиения отрезка О,1),и подключение к сумматору 13 адреса второго разбиения Модификация адреса в сумматоре 13 Считывание из блока 1 памяти очередной команды по сформированному адресу

12

Управляющие сигналы

б

П

It

С

5

ч

С«

Таблица 2

Управляющие сигналы

Cg, C,j С,,

C-f f С 1(

- с„

5

C,j

с,

Описание микроопераций

из блока 11 памяти значения х.„

Описание микроопераций

Считывание из блока 23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока 17 (текущий уровень распределения) Сравнение в схеме 15 содержимого регистров 9 и 18, вьщача результата сравнения (О или 1) в младшие разряды сумматора 14 и модификация адреса в сзд маторе 13 Считывание из блока 1 памяти следующей команды по сформированному адресу

Управляющие сигналы .

Сг, См

4 с;,,

С( ,С,С 1

Cq, С,

Таблица 4

Управляющие сигналы

7 CK

)(,С ,0

С«, С

15

159985616

Таблица 5

Фиг.З

Фи.6

Регис/пр адреса

1ед-)-Р/ЙЯ--Л

M-PlJfi)Pi

)Рп