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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

<н991421 (61) Дополнительное к авт. свид-ву(22) Заявлено 13.07 ° 81 (21) 3316792/18-24 с присоединением заявки MJ

{23) ПриоритетОпубликовано 2301;83. Бюллетень Мо 3

Р М Кп з

G 06 F 7/58

Государственный комитет

СССР но дедам изобретений и открытий (33) УДК 681. 325 (088. 8) Дата опубликования описания 23.01.83

Ъ

А ф. (72) Авторы изобретения

% à

В. М. Тарасов и В. М. Трусфус (71) Заявитель

Казанский ордена Трудового Красного Знамени авиационный институт им. A. Н. Туполева!

{54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

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

Однако данное устройство имеет низкое быстродействие, так как в разрядное случайное число с заданным законом распределения формируется в течение m тактов.

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

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

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

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

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

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

ИЛИ, выходы которых являются выходами преобразователя, первые входы элементов И и элементов И первой и второй групп образуют первую группу входов преобразователя, вторую группу входов которого образуют вторые входы элемента И, элементов И первой и второй групп и первые входы элементов ИЛИ, выход элемента И соеди,нен с вторым входом первого элемен1

5 та ИЛИ, выходи элементов H первой группы соединены с соответствующими входами, кроме первого, второго элемента ИЛИ, выходы элементов И второй группы соединены с соответ- ствующими входами, кроме первого, третьего элемента ИЛИ, На фиг, 1 приведена блок-схема генератора," на фиг. 2 - блок памяти> на фиг. 3 -. стохастический преобра15 зователь.

Генератор случайных чисел содержит генератор 1 тактовых импульсов, генератор 2 равномерно распределенных случайных чисел, блок 3 памяти, блок

4 кодирования, группу 5 элементов И, входы б и 7, группу выходов 8.

Блок памяти- (фиг. 2) содержит группу 9 регистров, группу 10 схем сравнения, вход 11; первую 12 и вторую 13 группу выходов.

Блок 4 кодирования (фиг. 3) содер жит группу 14 элементов И, группу 15 элементов ИЛИ, первую 1б и вторую 17 группы входов, группы выходов 18.

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

После поступления сигнала "Пуск" на вход б происходит запуск генератора 1 тактовых импульсов, который формирует две серии сдвинутых друг

350 относительно друга импульсов. B моменты времени, задаваемые сигналами с первого выхода генератора 1 тактовых импульсов, генератор 2 вырабаты,вает равномерно распределенные в ди4О апазоне (О, 1) случайные числа ф

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

45 По сигналам с выхода блока 3 памяти в блоке 4 кодйрования формируются случайные числа с заданным законом распределения, которые в моменты времени, задаваемые сигналами. со второго выхода генератора 1 тактовых импульсов, через группу 5 элементов И поступают на выход генератора.

В качестве ассоциативных признаков в блоке 3 памяти используются значения заданной Функции распределения F(x). Блок 3 памяти (фиг. 2) состоит из группы 9 регистров и группы

10 схем сравнения. Группа 9 регистров предназначена для хранения ассоциативных признаков (значений заданной фун" о. кции распределения) при этом в первом регистре 9 записано значение F (0 5) функции распределения, во втором 9 и третьем 95 регистрах соответственно

F (0,25) p F (0,75),. в регистрах 94, 65 9, 9 и 9 - соответственно

991421

F (0 125), Р (0,375), 1 (О,б25) и

F (0,875) и т д.

Другими словами, в первом регистре 9 хранится значение функции рас-: пределения, подсчитанное на середине интервала (0,1), т.е. F (0,5), во втором и третьем регистрах — значения F(x), подсчитанные соответствен.но на середине интервалов (0,05) и . (0.5,1), т.е. F (0,25) и F (0,75), в регистрах 94, 9, 9 и 9> — значения F(x), подсчитанные на середине интервалов (0,0.25), (0.25, 0.5), (0.5, 0.75) и (0.75, 1) соответственно, т.е. Р (0.125), Р (0,375), F (0,625), и F (0,875) и т.д. При этом емкость блока 3 памяти равна и = 2 -1, где m - разрядность формируемых случайных чисел с заданным законом распределения ° При поступлении на вход 11 блока 3 памяти равно- мерного распределенного случайного числа происходит сравнение этого числа со всеми значениями F(x) функции распределения одновременно.

Прн этом, если $ li F(x„) то на первом 12„ выходе i-ой схемы сравнения 10„ появится единичный сигнал

b = 1, а на втором выходе 13„ схемы сравнения 10„ будет нулевой сигнал

5„ = О. Аналогично, при ф < F(xÄ ) на первом выходе 12; i-ой схемы сравнения будет нулевой сигнал Ь„. = О, а на втором выходе 13; — единичный сигнал Ь 1. Очевидно, выходы 12, и 13< инверсны по отношению друг к другу. Выходы 12 блока 10 схем сравнения образуют первую группу выходов ассоциативного запоминающего устройства 3, а выходы 13„. — вторую группу выходов. Сформированные таким образом сигналы bÄ. и h„ ïîñòóïàþò на входы блока 4 кодирования.

Блок 4 кодирования (фиг. 3) содержит группу 14 элементов И и группу 15 элементов ИЛИ. При поступлении на его входы сигналов Ь; и Ь блок 4 формирует случайное число с заданным законом распределения. Первый выход

18 блока 4 соединен непосредственно с первым входом 16 . Если первая группа 16 входов блока 4 соединена с первой группой выходов блока 3 памяти, единичный сигнал на выходе 18 появится только в том случае, если сигнал Ь = 1, т.е. если g )r F(x<)

F (0,5)). Так происходит формирование первого (старшего) разряда случай ного числа с заданным законом распре-. деления..

На втором выходе 1.8 блока 4 (на выходе элемента 15 ИЛИ) единичный сигнал появится только при Ь Ь g= 1, что следует из схемы блока 4,приведенной. на фиг. 3. Но Ь,, b vb> = 1, ес .и равномерно распределенное случайное число попало в интервал Р(х ) F(0 25) Е g ас F(x ) = F (0,5) или в интервал 125 Ft4 ) = F (0,75).

Поэтому второй разряд формируемого случайного числа с заданным законом распределения примет единичное значение только при попадании в названные интервалы, что и необходимо для правильной работы предлагаемого ге- . нератора случайных чисел. Аналогично формируются и осталвные разряды слу10 чайного числа с заданным законом распределения.

П Р и м е р. Пусть генератор 2 равномерно распределен них случайных

15 чисел сформировал число, которое удовлетворяет следующим условиям

F(9/16) g + F (10/16). учитывая, что фукнция распределения F{x) неубывающая, имеем, что сигнал Ь 1, так как М Л (0,5), а сигналы b. = 1

20 и Ьз= О, так как )>j F (0,25) и

М F (0,75). Аналогично Ь, = Ь 1, b = b = О, Ь = Ь9= Ь = Ь = Ь,„=УЬ ,= b - Ь„ =-О, гпе Ь; — сигналы сйервой; группы вкходов ассоциативного запо25 минающего устройства, поступающие на первую группу входов 16 блока 4.

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

З0 Ь = 1 происходит непосредственно на выход 18 блока 4. Очевидно, второй разряд случайного числа равен нулю, так как сигналы Ь, Ь и Ь, поступающие на входы элементов 14„ И и 1g

35 ИЛИ, равны Ь, = Ь О, Ь 1. Аналогично на выходе элемента 15 ИЛИ будет сформирован нулевой сигнал, так как сигналы, поступающие на входы элементов 14ц И, 14 И, 14». И и

40 15я. ИЛИ, равны Б Q =.Ь = Ь 0 и Ьь = Ь4 = Ь = l. Наконец, на выходе элемента 15 ИЛИ будет сформирован единичный сигнал, так как Ь

5 = b<= Ь = Ь,, Ъ= Ьш» 1. Здесь Ь сигналы со второй (инверсной) группы пы выходов ассоциативного запоминающего устройства 3, йоступающие на вторую группу входов 17 блока 4. Таким образом, на выходах блока 4 будет сформирован код 1001. Будем считать, что запятая s случайном числе фиксирована перед старшим разрядом. Тогда на выходах предлагаемого генератора случайных чисел будет сформировано

55 число 0,1001 .9/16, что соответствует исходным данным. При поступлении сигнала на вход 17 предлагаемый генератор заканчивает свою работу.

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

65 такта, причем каждый такт состоит из

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

В данном генераторе равн мерно распределенное случайное число g сра-. зу подается rrai входы АЗУ, в котором происходит одновременное сравнение числа с ассоциативными признаками. Через время, равное времени срабатывания комбинационной схемы срав-. нения, на выходе АЗУ появятся .сигналы b. и Ь„, которые поступают в блок

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

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

АЗУ (выходное устройство), которое .служит для хранения случайных чисел с заданным законом распределения.

Суммарная сложность блока формирования случайных чисел и блока элементов И примерно равна сложности логического блока, который используется в известном устройстве в качестве дешифратора адреса рабочей части АЗУ.

Кроме того, в известном устройстве используется АЗУ на ферритовых сердечниках, которое сложно в изготов- лении и эксплуатации. В предлагаемом, устройстве АЗУ может быть реализова-. ! но в интегральном исполнении в виде

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

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

2С

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

Зф соединены соответственно с первой и второй группами входом стохастического преобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, 40 вторые входы которых соединены с вторым выходом генератора импульсов, первый и второй входы которого являются соответственно входами "Пуск" и "Стоп" генератора, выход блока памяти соеди45 нен с входом блока элементов И.

2, Генератор по и, 1, о т л ич а ю шийся тем, что стохастический преобразователь содержит элемент И, две группы элементов И и три элемента ИЛИ, выходы которых являются выходами преобразователя, первые входы элемента И и элементов И первой и второй групп образуют первую группу входов преобразователя, вто>5,pyro группу входов которого образуют вторые входы элемента И, элементов

И первой и второй групп и первые входы элементов ИЛИ, выход элемента

И соединен с вторым входом первого элемента ИЛИ, выходы элементов И пер.вой группы соединены с соответствующими входами, кроме первого, второго элемента ИЛИ, выходы элементов И второй .группы соединены с соответствующими входами, кроме первого, 65 третьего элемента. ИЛИ.

991421

Источники информации, принятые во внимание при экспертизе

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

М 378826, кл. f 06 Г 7/58, 1971.

2. Авторское

9 213С24 кл. G

3 ° Авторское

9 351207, кл. G тотип). свидетельство СССР

06 F 7/58, 1966 ° свидетельство СССР

06 F 7/58, 1971 (про991421

Составитель A. Карасов

Редактор С. Патрушева Техред Т.Фанта

Корректор M. лароши

Подписное

Заказ 135/б 7 Тираж 704

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4