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

ел к

NU

о 4

00

3152

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

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

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

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

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

Сумматор 15 (фиг. 6) содержит ком- бинационньш сумматор 37 и регистр 38, Регистр 17 сдвига содержит старшую часть - (п-двухразрядный) регистр 39 сдвига и младшую часть,- двухразрядный регистр 40 сдвига (п - число разрядов для представления случайного числа).

«

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

В генераторе реализуется метод обратных функций, основанный на сравнении равномерно распределенных случай- ных чисел со значениями F(x) воспро- изводк ой Функции распределения, отыскании интервала, для которого выполняется условие

F(X;)F(X.,,),

и выдаче соответствующего данному интервалу значения х;. Поиск интервала производится логарифмическим перебором интервалов с основанием а логарифма перебора, равным целой степени два, т.е. , где 1 - любое целое положительное число. На каждом шаге перебора величина 1 может быть программно изменена с целью достижения оптимального компромисса между скоростью генерации случайных чисел и объемом требуемой памяти. Реализация алгоритма поиска требует проведения подготовительных операций (по подготовке данных н юс организации в памяти), которые могут быть прот- граммно стандартизованы.

Работа устройства сводится к циклической выборке из блока памяти команд (К,-Kg) в соответствии с переходами (фиг. 3), где пунктиром обозначено начало циклов более длинных, но и маловероятных. Код х считывается на выход устройства после выполнения команды К| или Kg, или Kj. Иллюстрации алгоритма поиска даны в приложении.

Содержимое ячеек, соответствующее командам, показано на фиг. 4, где поле 1 содержит четырехразрядный код операции, поле 2 - двоичный код величины 1, поле 3 - тип операнда: для команд К,, К - база (А) относительного адреса, для К- - код х; , для

е

К,.- число (x;). j

По команде К, по 1 старшим разрядам числа определяется тот отрезок (из 2 равновероятных отрезков интервала О, 2, где п - разрядность чисел ), в KOTopHii попало число , По команде К производится дальнейшее уточнение места расположения числа на интервале О, 2 J по следующим 1 старшим разрядам числа , где 1 может быть меньше, равно или больше 1. По команде К производится считывание кода х ; из регистра команд на выход устройства и пуск датчика случайных чисел ц для нового цикла. По команде К производится пересыпка базы адреса из регистра команд в регистр адреса. По команде К реализуется указа1шое соотношение.

Команды выполняются с помощью элементарных операций (микроопераций),

5I52A048

которые определяются микрокомандами, поступающими из блока 33 памяти. Микрокоманды задают последовательность управляющих сигналов (синхросигналов), которые обеспечивают выполнение микроопераций (С,-С,).

Микрооперации, которые выполняются по команде К представлены в табл. I. Таблица

10

Продолжение табл.2

Считывание из блока памяти команды К, по адресу, хра10

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

Микрооперации в команде К

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

Пересыпка содержимого из регистра 10 в счетчик 23 блока управления

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

Сдвиг содержимого 1-стар- шях разрядов регистра 18 в младшую часть регистра 17 Образование адреса в сумматоре 15 путем суммирования в сумматоре содержимого регистров 10 и 57 Считывание из блока памяти очередной команды по сформированному в регистре 14 адресу

Операция формирования адреса при выполнении команды К, производится по формуле , где А - база адреса, хранимого в регистрах 14 или 10, Jl - смещение - двоичный 1-раз- рядньй код, хранимый в регистре 17.

Результ;ат суммирования записьта- ется в регистр 40 сумматора.

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

По команде Kg, К, К вьшолняются микрооперации, представленные в

табл. 2-4.

IТаблица

Микрооперации в команде К,

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

Считывается содержимое регистра 10 на выход устройстваЗапуск датчика 19 случайных чисел

J-5 Пересьшка содержимого регистра 10 в регистр 14 памяти .

Считывание из блока памяти команды К .17.

С 1 С 2

20

Таблица 4

25

Микрооперации в команде К,

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

30

40

Сравнение в схеме 16 содер- ташого регистров 10 и 18 и запись результата сравнения в регистр 17, при этом результат сравнения меньше, равно - единичный сигнал - поступает в первый разряд регистра 17, а результат 35 больше - единичный сигнал- поступает во второй разряд регистра 17С,С

Модификация адреса путем cy миpoвaния содержимого регистров 14 и 17 Считывание из блока памяти следующей команды по сформированному адресу

С $ С ,2.

С,,С

г

45

50

55

Генератор начинает работать по сигналу Пуск, поступающему на элементы ИЛИ 2, 5, 7 и узел 12. Под действием этого сигнала производится считывание из блока 1 памяти команды К, и включение датчика 19 случайных чисел. Дальнейшая выборка в соответствии с переходами (фиг.З) производится с помощью узла 12 управления, процесс выборки микрокоманд которого описывается в табл. 5. Временные диаграммы появления управляющих импульсов на выходе блока 35 элементов И при реализации команд

к,-к jj показаны на фиг. 5. Узел 12 управления начинает работать по сигналу Пуск, поступающему через элемент ИЛИ 21 или синхроимпульсу С. По этому импульсу триггер 25 открывает элемент И 28, (через промежуток времени, определяемый величиной задержки элемента 24. Эта величина определяется временем считывания ко- манды К;, ,5 в регистрах 8, 9, 10 памяти).

Через открытьш элемент И 28 от генератора 26 через делитель 29 поступает серия импульсов. Длина серии зависит от команды К;, (фиг. 5), каждый импульс в этой серии считывает из блока 33 памяти в регистр 34 одну микрокоманду. Адрес очередной микрокоманды поступает из регистра 3 через мультиплексор 32 в блок 33 памяти под действием синхроимпульса С,. Содержимое микрокоманд отражено в табл. 5, Каждому импульсу синхронизации С;, ,12 соответствует код 1 в i-ом разряде регистра 34. Частота импульсо считывания, поступающих из элемента И 28, определяется быстродействием блока 33 памяти.

Блоки 23, 24, 27 и 28 формиру- ют на выходе элемента И 27 серию (длины 1 тактовых импульсов сдвига, поступающих в регистры сдвига 18 и 17 По синхроимпульсу С, производится запись в счетчик 23 содержимого регист- ра 9 (двоичный код величины 1). По синхроимпульсу С расширитель 22 формирует импульс длительностью, равной периоду считывания микрокоманд из блока памяти 33. Появление импульсов на выходе элемента И 27 прекращается в момент обнуления счетчика 23.

Таблица 5

Cg С,, с,2

о i С 5 С ia

С

11

С 1( С 10 С 11 С «г С cj

Продолжение табл.5

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

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

Генератор случайных чисел, содержащий блок памяти, датчик равномерно распределенных случайных чисел, сумматор, первый регистр сдвига, о т-- личающийся тем, что, с целью повьпнения быстродействия, он содержит пять регистров, второй регистр сдвига, схему сравнения, два мультиплексора, четыре элемента Ш1И, элемент задержки, блок элементов И и узел управления, который содержит элемент ИЛИ, два элемента И, расширитель импульсов, счетчик, генератор тактовых импульсов, RS-триггер, делитель частоты, четыре элемента задержки, мультиплексор, блок nat-шти, регистр и блок элементов И, выход элемента ИЛИ узла управления через первый элемент задержки соединен с S-входом RS-триггера, R-вход которо

915

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

10

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

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

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

с.а.

JU

21

К

OcmOHol

vS

25

Фаг. 2

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

т-

о

Фиг.З

I52A048

Поле 1 Лоле 2 ПолеЗ

-П.

Сз

с

5

Сг-П rrLJlJT

«3

С

С

Cs-

Сб-П

rOirui

Фие.

С,

c,JT

rrLJUT

L

Фиг. 5

Фм.6

CSpoc

Сб

От Л1./7

Фие.7