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

(54) ГЕНЕРАТОР СЛУЧАЙНЬК НИСЕЛ

Изобретение относится к вычислительной технике и может найти применение при статистическом моделировании в цифровых вычислительных машинах. Известен генератор случайных чисел с заданными законами распределения, содержащий генератор тактовых импульсов, генератор равномерно распределенных случайных чисел, запоминающее устройство, схему сравнения, первую и вторую группы элементов И, дешифратор, регистр. Однако данное.устройство имеет низкое быстродействие, так как рядное случайное число с заданным законом распределения формируется в течение m тактов. Известен также генератор, содержащий датчик равномерно распределенных случайных чисел, запоминающее устройство, схемы сравнения, триггеры, cxeNw совпадения,- выходное устройствоДанное устройство позволяет получать случайные числа с заданным зако ном распределения за один такт работы датчика, но имеет высокую сложнос Наиболее близким техническим реше нием к изобретению является генератор случайных чисел, содержащий генератор равномерно распределенных случайных чисел, генератор тактовых импульсов, регистр признака опроса, первый и второй входы которого соединены с выходом генератора равномерно распределенных случайных чисел и со вторьам выходом генератора тактовых импульсов соответственно/ а первый выход генератора тактовых импульсов подключен к входу генератора равномерно распределенных случайных чисел, ассоциативное запоминающее устройство, индикаторное устройство, логический блок, состояпщй из элементов И и ИЛИ, выходное устройство, причем выход регистра признака опроса соединен со входом ассоциативного запоминающего устройства, первая и вторая группы выходов которого подключены к первой и третьей группам входом индикаторного устройства соответственно, а вторая группа входов индикаторного устройствасоединена с третьим выходом генератора тактовых импульсов., первый выход каждого индикатора индикаторного устройства соединен через соответствующие элементы И и ИЛИ логического блока с одним из входов выходного устройства, второй выход каждого индикатора подключен к первому входу соответствующего элемента ИЛИ логического блока, а третий выход индикатора соединен со вторым входом элемента И предшествующего разряда, четвертый выход генератора тактовых импульсов подключен к первому входу выходного ycтpoйcтвafЗf Однако известный генератор имеет низкое быстродействие, так как в каж дом такте для формирования одного случайного числа необходимо совершит последовательно ряд действий, таких как установка в исходное состояние/ индикаторного устройства и запуск генератора равномерно распределенных случайных чисел, формирование токов опроса ассоциативного запоминающего устройства, выполненного на ферритовых сердечниках, чтение из выходного устройства по сигналу, сформированному в логическом блоке случайного числа. Кроме того, известное устройство имеет высокую сложность, роскол ку содержит индикаторное и выходное устройства. Цель изобретения - повышение быст родействия генератора случайных чисе путем устранения непроизводительных затрат времени на установку в нужное состояние индикаторного устройства и чтения случайного числа из выходного устройства, а также сокращение аппаратурных затрат. Поставленная цель достигается тем что в генератор случайных чисел, содержащий генератор тактовых импульсов, первый выход которого соединен С входом генератора равномерно распроделанных случайных чисел, блок па мяти , введены стохастический преобразоватёль и группа элементов И, выходы которых являются выходом генера тора, выход генератора равномерно распределенных случайных чисел соеди нен с входом блока памяти, первая и вторая группы выходов которых соединены соответственно с первой и второй группами входов стохастического преобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, вторые входы которых соединены с вторым выходом генератора тактовых импульсов, первый и второй входы которого являются соответственно входами Пуск и Стоп генератора, выход блока памяти соединен с входом блока элементов И. Кроме того, стохастический преобразователь содержит элемент И, две группы элементов И и три элемента ИЛИ, выходы которых являются выходами преобразователя, первые входы эле ментов Н и элементов И первой и второй групп образуют первую группу входов преобразователя, вторую группу входов котррого образуют вторые входы элемента И, элементов И первой и второй групп и первые входы элементов ИЛИ, выход элемента И соединен с вторым входом первого элемента ИЛИ, выходы элементов И первой группы соединены с соответствующими входами, кроме первого, второго элементаИЛИ, выходы элементов И второй группы соединены с соответствующими, входами, кроме первого, третьего элемента ИЛИ. , На фиг. 1 приведена блок-схема генератора; на фиг. 2 - блок памяти; на фиг. 3 г- стохастический преобразователь. Генератор случайных чисел содержит генератор 1 тактовых импульсов, генератор 2 равномерно распределенных случайных чисел, блок 3 памяти, блок 4 кодирования, группу 5 элементов И, входы 6 и 7, группу выходов 8. Блок памяти (фиг. 2) содержит группу 9 регистров, группу 10 схем сравнения, вход 11,- первую 12 и вторую 13 группу выходов. Блок 4 кодирования (фиг. 3) содержит группу 14 элементов И, группу 15 элементов ИЛИ, первую 16 и вторую 17 группы входов,группы выходов 18. Генератор случайных чисел работает следующим образом. После поступления сигнала Пуск на вход б происходит запуск генератора 1 тактовых импульсов, который формирует две серии сдвинутых друг ртносительно друга импульсов. В моменты времени, задаваемые сигналами с первого выхода генератора 1 тактовых импульсов, генератор 2 вырабатывает равномерна распределенные в диапазоне (О, 1) случайные числа . . Эти числа поступают на вход блока 3 памяти, который предназначен для хранения ассоциативных признаков и сравнения этих признаков с числами По сигналам с выхода блока 3 памяти в блоке 4 кодирования формируются случайные числа с заданным законом распределения, которые в моменты времени, задаваемые сигналами, со второго выхода генератора 1 тактовых импульсов, через группу 5 элементов И поступают на выход генератора. В качестве ассоциативных признаков в блоке 3 памяти используются значения заданной функции распределения F(x). Блок 3 памяти (фиг. 2) состоит из группы 9 регистров и группы 10 схем сравнения. Группа 9 регистров предназначена для хранения ассоциативных признаков (значений заданной функции распределения) при этом в первом регистре В записано значение F (0,5) функции распределения, во втором 9 и третьем 9з регистрах-соответственно F (0,25) и F (0,75),. в регистрах 9, 9 , 9(, и 9-J - соответственно F (ОД25),- F (0,375), F (0,625) я F (0,875) и т.д. Другими словами, в первом регистре 9 хранится значение функции расг пределения, подсчитанное на середине интервала (0,1), т.е. F (0,5), во втором и третьем регистрах - значения F(x), подсчитанные соответствен.но на середине интервалов (0,05) и (0.5,1), т.е. F (0,25) и F (0,75), в регистрах 94 f 9, 9 и 9, - значения F(x), подсчитанные на середине интервалов (0,0.25), (0.25, 0.5), (0.5, 0.75) и (0.75, 1) соответствен но, т.е. F (0.125), F (0,375), F (0,625), и F (0,875) и т.д. При этом емкость блока 3 памяти равна п , где m - разрядность формируемых случайных чисел с заданным законом распределения. При поступлении на вход 11 блока 3 памяти равномерного распределенного случайного числа происходит сравнение этого числа со всеми значениями F(x,) функции распределения одновременно. При этом, если 7/ F() то на пер вом выходе i-ой схемы сравнения 10 появится единичный сигнал Ц 1, а на втором выходе схемы сравнения 10: будет нулевой сигнал Ъ- 0. Аналогично, при F(XJ) на первом выходе 12 i-ой :хемы сравнения будет нулевой сигигш Ц- О, а на втором выходе единичный сигнал Ь 1. Очевидно, выходы и 13{ инверсны по отношению друг к другу. Выходы 12 блока 10 схем срав нения образуют первую группу выходов ассоциативного запоминающего устройства 3, а выходы вторую группу выходов. Сформированные таким образо сигналы и li поступают на входы блока 4 кодирования. Влок 4 кодирования (фиг. 3) содержит группу 14 элементов И и группу 15 элементов ИЛИ. При поступлении на его входы сигналов Ь и Ь; блок -4 формирует случайное число с заданным законом распределения. Первый выход 18 блока 4 соединен непосредственно с первым входом 16 . Если первая группа 16 входов блока 4 соединена с первой группой выходов блока 3 памяти, единичный сигнал на выходе 18 появится только в том случае, если сигнал К 1, т.е. если 7/ F(x) F (0,5). Так происходит формирование первого (старшего) разряда случа ного числа с заданным законом распре деления. . На втором выходе 1.8 блока 4 (на выходе элемента 15, ИЛИ) единичный сигнал появится только при что следует из схемы блока 4,,приведенной на фиг. 3. Но Ь 1 ecjiH равномерно распределенное случайное число попало в интервал Р(Х4) F(0,25) : F(xJ F (0,5) или в интервал 1. F(}J,,) F (0,75). Поэтому второй разряд фop iиpyeмoгo случайного числа с заданным законом распределения примет единичное значение только при попадании Ч в назван:ные интервалы, что и необходимо для правильной работы предлагаемого генератора случайных чисел. Аналогично формируются и осталвные разряды случайного числа с заданным законом распределения. | .. П 1 и м е р. Пусть генератор 2 равномерно распределенжлх случайных чисел Сформировал число , которое удовлетворяет следукивдм условиям F(9/16) i F (10/16-). Учитывая, что фукнция распределения F(x) неубывающая, имеем, что сигнал Ц 1, так как (0,5), а сигналы Ь 1 и Ьз О, так как / F (0,25) и F (0,75). Аналогично Ь bg 1, bfe О, be b b b«. 1 b b 0 , где сигналы с первой ; группы выходов ассоциативного запоминакнцего устройства, поступающие напервую группу входов 16 блока 4. Отсюда имеем, что первый разряд формируемого случайного числа равен единице, так как единичный сигнал Ь; 1 происходит непосредственно на выход 18 блока 4. Очевидно, второй разряд случайного числа равен нулю, так как сигналы Ь , Ъ и bj , поступающие на входы элементов И и 1 ИЛИ, равны Ь Ь О, Ь 1. Аналогично на выходе элемента 15;. ИЛИ будет сформирован нулевой сигнал, так как сигналы, поступающие на входы элементов . И, , И и 15а ИЛИ, равны Ъ Е Ь Ь О и Ц t b Т. Наконец, на выходе элемента 15 ИЛИ будет сформирован единичный сигнал, так 4 Jn 4 0. Ч Ч Ь, bg b l 1. Здесь сигналы со второй (инверсной)группы пы выходов ассоциативного запоминающего устройства 3, йоступающие на вторую группу входов 17 блока 4. Таким образом, на выходах блока 4 будет сформирован код 1001. Будем считать, что запятая в случайном числе фиксирована перед старшим разрядом. Тогда на выходах предлагаемого генератора случайных чисел будет сфорлмровано число 0,1001 9/16, что соответствует исходным данным. При поступлении сигнала на вход 17 предлагаемый генератор заканчивает свою работу. Рассмотрим, как достигается пог ставленная цель - повтаение быстродействия и сокращение аппаратурных затрат. В известном устройстве случай ное число с заданным законом распределения формируется в течение одного такта, причем каждый такт состоит из

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

В данном генераторе равн мерно распределенное случайное число сра ЗУ подается на I рходы АЗУ, в котором происходит одновременное сравнение числа с ассоциативными признаками. Через время, равное времени срабатывания комбинационной cxeNta сравнения, выходе АЗУ появятся сигналы Ц и Ь , которые поступают в блок 4, являющийся двухуровневой комбинационной схемой. С выходов блока 4 случайное число с задгшным законом распределения поступает через блок 5 элементов И непоср дственно на выход устройства. Таким образом, в предлагаемом устройстве в отличие от известного отсутствуют потери времени на формирование токов опроса, уста- . новки в исходное и нужное состояние индикаторного устройства, чтение из памяти чисел, что и позволяет повысить скорость формирования случайных чисел с заданным законом распределения не менее чем в 1,5 раза.

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

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

-..

Использование новых элементоЪ

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

изобретения

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

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

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

свидетельство СССР Об F 7/58, 1966.

свидетельство СССР

Об F 7/58, 1971 (про