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

 

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

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

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

РЕСПУБЛИН

„„SU„„152 04

А1 (50 4 G 06 F 7/58

Р". 6:: ."Р

ПАП-:! . ;.. th:

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4375983/24-24 (22) 25.12.87 (46) 23.11.89. Б)ол. Н 43 (71) Казанский государственный университет им. В.H.Óëüÿíîâà — Ленина (72) Р,Г.Бухараев, Г.Г.Баранов, В.М.Захаров, С.Е.Кузнецов, Ю.С.Комаров, И.И.Макарон и В.И.Пермитин (53) 681.3(088.8) (56) Авторское свидетельство СССР

h- 378826, кл. G 06 F 7/58, 1973.

Авторское свидетельство СССР

hÔ 1008738, кл. G 06 F 7/58, 1983. (54) ГЕНЕРАТОР СЛУЧА1БЬ!Х ЧИСЕЛ (57) Изобретение относит; я к вычислительной технике и может быть испольэоваио в качестве специализированного вероятностного процессора.

Цель изобретения — повьппение быстродействия. Генератор содержит блок

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

7 ил., 5 табл.

1524048

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

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

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

Генератор (фиг. 1) содержит блок 1 памяти, элемент ИЛИ 2, мультиплексор

3, регистр 4, элемент ИЛИ 5, элемент

6 задержки, элемент ИЛИ 7, регистры

8-10, блок 11 элементов И, узел 12 управления, мультиплексор 13, регистр

14, сумматор 15, схему 16 сравнения, регистры 17 и 18 сдвига, датчик 19 30

paaHbMepHo распределенных случайных чисел, элецент ИЛИ 20.

Узел 12 управления (фиг. 2) содержит элемент ИЛИ 21, расширитель

22 импульсов, счетчик 23, элемент

24 задержки, триггер 25, генератор

26 тактовых импульсов, элементы И 27 и 28, делитель 29 частоты, элементы

30 и 31 задержки, мультиплексор 32, блок 33 памяти, регистр 34, блок 35 40 элементов И, элемент 36 задержки.

Сумматор 15 (фиг. 6) содержит комбинационный сумматор 37 и регистр 38.

Регистр 17 сдвига содержит старшую часть — (п-двухразрядный) регистр 39 45 сдвига и младшую часть. — двухразрядный регистр 40 сдвига {n — число разрядов для представления случайного числа).

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

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

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

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

1 выход устройства после выполнения команды К, или К, или К,. Иллюстрации алгоритма поиска даны в приложении.

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

В

К вЂ” число Е= Р(х, ) °

j-1

По команде К, по 1 старшим разрядам числа определяется тот отрезок (из 2 равновероятных отрезков интерС вала ГО, 2" j где и — разрядность чисел ), в который попало число

1»

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

По команде К производится пересылка базы адреса иэ регистра команд в регистр адреса. По команде К реализуется указанное соотношение.

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

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

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

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

Таблица l

Таблица 3

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

С8,С„

Таблица 4

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

С,о,сп

Сравнение в схеме 16 содержимого регистров 10 и !8 и

30 запись результата сравнения в регистр 17, при этом результат сравнения "меньше, равно" — единичный сигнал— поступает в первый разряд регистра 17, а результат

35 11больше" — единичный сигналпоступает во второй разряд регистра 17 С,С

Модификация адреса путем суммирования содержимого ре40 гистров 14 и 17 фф

Считывание из блока памяти следующей команды по сформированному адресу С,,С

45 Генератор начинает работать по и налу "Пуск™, поступ щему на элементы ИЛИ 2, S 7 и узел 12.

Под действнем этого сигнала производится считывание из блока 1 памяти команды K и включение датчика 19 случайных чисел. Дальнейшая выборка в соответствии с переходами (фиг.3) производится с помощью узла 12 управления, процесс выборки микрокоманд

55 которого описывается в табл. 5. Временные диаграммы появления управляющих импульсов на выходе блока 35 элементов И при реализации команд

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

Микрооперации в команде К, Управляющие сигналы

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

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

Сдвиг содержимого 1-старших разрядов регистра 18 в младшую часть регистра 17

Образование адреса в сумматоре 15 путем суммирования в сумматоре содержимого регистров 10 и 17

Считывание из блока памяти очередной команды по сформированному в регистре 14 адресу

Операция формирования адреса при выполнении команды К, производится по формуле 8=A+ (Ij, где А — база адреса -хранимого в регистрах 14 или

l0, (I) — смещение — двоичньм 1-разрядный код, хранимый в регистре 17.

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

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

ПО кОманде КЭ К4 К5 ВЫПОлнЯютсЯ микрооперации, представленные в табл. 2-4.

I Таблица 2

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

Считывается содержимое регистра 10 на выход устройства С,,С„

Запуск датчика 19 случайных чисел С,,сы

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

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

Пересылка содержимого регистра 10 в регистр 14 памяти . С,C„2

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

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

152 4048

КоманСодержимое ячейки

Адрес микроко манды ды

Управляющие импульсы

Адрес следующей микрокоманды

001 I

001 0

0011

0001

00ll

0001

0101

К 001

0010

55

К,-К „ показаны на фиг ° 5. Узел 12 управления начинает работать по сигналу "Пуск", поступающему через элемент ИЛИ 21 или синхроимпульсу С .

По этому импульсу триггер 25 открывает элемент И 28, (через промежуток времени, определяемый величиной задержки элемента 24. Эта величина определяется временем считывания команды К;, i l 5 в регистрах 8, 9, l0 памяти).

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

И 28, определяется быстродействием блока 33 памяти.

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

Таблица 5

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

КоманАдрес микроко манны

Содержимое ячейки

Адрес Управляющие следую- импульсы щей мнкрокоман0001

01!О

100!

0!Ii

0001 !

0001

100!

0001

00!О

0001

0000

С 12

фф

С, С„ с, C„7

c„

C„2

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

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

S-входом RS-триггера, R-вход которо!

524048

ro соединен с выходом элемента ИЛИ узла управления, прямой выход RS-триггера соединен с первым входом перво-

i.o элемента И, выход которого через

5 второй элемент задержки соединен с входом синхронизации регистра узла управления, старший разрядный выход которого соединен с первым информационным разрядным входом мультиплексора узла управления, выход которого соединен с адресным входом блока памяти узла управления, выход которого соединен с информационным входом регистра, вход синхронизации 15 блока памяти соединен с выходом первого элемента И, выход расширителя импульсов соединен с первым входом второго элемента И, второй вход которого соединен с выходом генератора Zp тактовых импульсов и подключен к входу делителя частоты, выход которого соединен с вторым входом первого элемента И, выход счетчика соединен с третьим входом второго элемента И, 25 выход которого соединен с счетным входом счетчика, выход второго элемента задержки через третий элемент задержки соединен с первым входом блока элементов И узла управлепл», второй 30 вход которого соединен с соответствующими младшими раз рядными выходами регистра узла управления, первый вход первого эг мента ИЛИ соединен с первыми входами второго, третьего и 35 четвертого элементов И. П1, с первым входом элемента ИЛИ узла управления и является входом Пуск" генератора, выход первого элемента ИЛИ соединен с входом разрешения чтения блока па- 40 мяти, первый, второй и третий информационные выходы которого соединены соо гвет-.твенно с информационными входами первого, второго и третьего регистров, входы синхронизации кото- 45 рых соединены с выходом элемента задержки, вход которого соединен с выходом третьего элемента ИЛИ, адресный вход блока памяти соединен с выходом первого мультиплексора, первый

50 информационный вход xoTopoI о соединен с выходом четвертого регистра, выход н i îðoão элемента ИЛИ соединен с управляющим входом первого мультиплекеора, второй информационньй вход

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

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

12 !

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

524048

Поле 1 7ппе 2 Полюс

"Ю

1524048

Рт dn.17

Составитель И.Столяров

Техред Л. Олийнык Корректор Т. Палий

Редактор Л.Зайцева

Заказ 7044/50 Тираж.668 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул, Гагарина, 101