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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советскик Социалистических Республик(61) Дополнительное к авт. свид-ву- (22) Заявлено 13,07. 81 (21) 3316792/18-24 с присоединением заявки М(23) ПриоритетОпубликовано 2301;83. Бюллетень Мо 3 РМ Кп з С 06 Р 7/58 Государственный комитет СССР но дедам изобретений и открытийДата опубликования описания 23,01.83(71) Заявитель Казанский ордена Трудового Красного Знамени авиационный институт им. А. Н. Туполева(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может найти применение при статистическом моделировании в цифровых вычислительных машинах.Известен генератор случайных чисел с заданными законами распределения, содержащий генератор тактовыхимпульсов, генератор равномерно распределенных случайных чисел, запоминающее устройство, схему сравнения,первую и вторую группы элементов И,дешифратор, регистр 1 1.Однако данное устройство имеетнизкое быстродействие, так как аразрядное случайное число с заданнымзаконом распределения формируетсяв течение щ тактов,Известен также генератор, содержащий датчик равномерно распределенных случайных чисел, запоминающееустройство, схемы сравнения, триггеры, схемы совпадения выходное устройство 2.Данное устройство позволяет получать случайные числа с заданным законом распределения за один такт рабо ты датчика, но имеет высокую сложность.Наиболее близким техническим реше"нием к изобретению является генератор случайных чисел, содержащий генератор равномерно распределенныхслучайных чисел, генератор тактовыхимпульсов, регистр признака опроса,первый и второй входы которого соединены с выходом генератора равно"мерно распределенных случайных чисели со вторым выходом генератора тактовых импульсов соответственно апервый выход генератора тактовых импульсов подключен к входу генератораравномерно распределенных случайныхчисел, ассоциативное запоминающееустройство, индикаторное устройство,логический блок, состоящий иэ элементов И и ИЛИ, выходное устройство,причем выход регистра признака опроса соединен со входом ассоциативногозапоминающего устройства, первая ивторая группы выходов которого подключены к первой и третьей группам входом индикаторного устройства соответ"ственно, а вторая. группа входов индикаторного устройствасоединена стретьим выходом генератора тактовыхимпульсов первый выход каждого индикатора индикаторного устройства соединен через соответствующие элементы И и ИЛИ логического блока .с однимиз входов выходного устройства, вто 991421рой выход каждого индикатора подключен к первому входу соответствующеГоэлемента ИЛИ логического блока, атретий выход индикатора соединен совторым входом элемента И предшествующего разряда, четвертый выход генератора тактовых импульсов подключенк первому входу выходного устройствами Однако известный генератор имеет низкое быстродействие, так как в каждом такте для формирования одного случайного числа необходимо совершить последовательно ряд действий, такихкак установка в исходное состояниеиндикаторного устройства и запускгенератора равномерно распределенныхслучайных чисел, формирование токовопроса ассоциативного запоминающегоустройства, выполненного на ферритовых сердечниках, чтение из выходного устройства по сигналу, сформированному в логическом блоке случайногочисла, Кроме того, известное устрой" ство имеет высокую сложность, Поскольку содержит индикаторное и выходноеустройства. Цель изобретения - повышение быстродействия генератора случайных чисел путем устранения непроизводительныхзатрат времени на установку в нужноесостояние индикаторного устройстваи чтения случайного числа из выходного устройства, а также сокращениеаппаратурных затрат,Поставленная цель достигается тем,что в генератор случайных чисел, содержащий генератор тактовых импульсов, первый выход которого соединенс входом генератора равномерно распределенных случайных чисел, блок памяти, введены стохастический преобразователь и группа элементов И, вы"ходы которых являются выходом генера.тора, выход генератора равномернораспределенных случайных чисел соеди.нен с входом блока памяти, первая ивторая группы выходов которых соединены соответственно с первой и второй группами входов стохастическогопреобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, вторыевходы которых соединены с вторым выходом генератора тактовых импульсов,Рпервый и второй входы которого являются соответственно входами "Пуск"и "Стоп" генератора, выход блока памяти соединен с входом блока элементов И,Кроме того, стохастический преобразователь содержит элемент И, двегруппы элементов И и три элементаИЛИ, выходы которых являются выходами преобразователя, первые входы элементов И и элементов И первой и второй групп образуют первую группувходов преобразователя, вторую группу входов которого образуют вторые входы элемента И, элементов И первойи второй групп и первые входы элементов ИЛИ, выход элемента И соеди,нен с вторым входом первого элемен 15 та ИЛИ, выходи элементов И первойгруппы соединены с соответствующимивходами, кроме первого, второгоэлементаИЛИ, выходы элементов Ивторой группы соединены с соответ-1 О ствующими входами, кроме первого,третьего элемента ИЛИ,На фиг, 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 относительно друга импульсов. В моменты времени, задаваемые сигналамис первого выхода генератора 1 тактовых импульсов, генератор 2 вырабаты,вает равномерно распределенные в ди 40 апазоне (О, 1) случайные числа фЭти числа поступают на вход блока 3памяти, который предназначен для.хранения ассоциативных признаков исравнения этих признаков с числами45 По сигналам с выхода блока 3 памятив блоке 4 кодирования формируютсяслучайные числа с заданным закономраспределения, которые в моменты времени, задаваемые сигналами, со второго выхода генератора 1 тактовых импульсов, через группу 5 элементов Ипоступают на выход генератора.В качестве ассоциативных признаков в блоке 3 памяти используютсязначения заданной Функции распределения Р(х). Блок 3 памяти (фиг, 2) состоит из группы 9 регистров и группы10 схем сравнения. Группа 9 регистровпредназначена для хранения ассоциативных признаков (значений заданной фун"бо. кции распределения) при этом в первомрегистре 91 записано значение Е (0,5)функции распределения, во втором 9и третьем 95 регистрах соответственноР (0,25) и Р (0,75),. в регистрах 9,659 , 9 и 9 - соответственноР (0,125),. Р (0,375), Р (0,625) и Р (0,875) и т,д.Другими словами, в первом регистре 9 хранится значение функции рас-: пределения, подсчитанное на середине интервала (0,1), т.е. Р (0,5), во втором и третьем регистрах - значения Р(х), подсчитанные соответствен.но на середине интервалов (0,05) и . (0.5,1), т.е. Р (0,25) и Р (0,75), в регистрах 94, 9, 9 и 9) - значения Р(х), подсчитанные на середине интервалов (0,0.25), (0.25, 0.5), (0.5, 0.75) и (0.75, 1) соответствен. но, т,е, Р (0.125), Р (0,375), Р (0,625), и Р (0,875) и т.д, При этом емкость блока 3 памяти равна и = 2"д, где в - разрядность Формируемых случайных чисел с заданным законом распределенияПри поступлении на вход 11 блока 3 памяти равно- мерного распределенного случайного числапроисходит сравнение этого числа со всеми значениями Р(х) функции распределения одновременно, Прн этом, если) Р(х) то на первом 12 выходе -ой схемы сравнения 10 появится единичный сигнал Ь = 1, а на втором выходе 13 схемы сравнения 10 будет нулевой сигнал Ъ = О. Аналогично, при фР(х ) на первом выходе 12; 1"ой схемы сравнения будет нулевой сигнал Ь = О, а на втором выходе 13; - единичный сигнал Б = 1, Очевидно, выходы 12, и 13 инверсны по отношению друг к другу, Выходы 12 блока 10 схем сравнения образуют первую группу выходов ассоциативного запоминающего устройства 3, а выходы 13- вторую группу выходов, СФормированные таким образом сигналы Ь и Ь поступают на входы блока 4 кодирования.Блок 4 кодирования (Фиг. 3) содержит группу 14 элементов И и группу 15 элементов ИЛИ. При поступлении на его входы сигналов Ь; и Ь блок 4 формирует случайное число с заданным законом распределения, Первый выход 18 блока 4 соединен непосредственно с первым входом 16, Если первая группа 16 входов блока 4 соединена с первой группой выходов блока 3 памяти, единичный сигнал на выходе 18 появится только в том случае, если сигнал Ь = 1, т.е. если)/ Р(х)Р (0,5), Так происходит Формирование первого (старшего) разряда случай ного числа с заданным законом распре-. деленияНа втором выходе 18 блока 4 (на выходе элемента 15 ИЛИ) единичный сигнал появится только при Ь Ь МЬ = 1, что следует из схемы блока 4,приведенной. на фиг. 3. Но Ь, ЬЬ = 1, ес.и равномерно распределенное случайное число попало в интервал Р(х )ф Р(0,25) е 4 ас Р(х ) = Р (О 5) илив интервал 1 1 Щ Р(4) = Р (0,75) .Поэтому второй разряд формируемогослучайного числа с заданным заковомраспределения примет единичное значение только при попаданиив названные интервалы, что и необходимо дляправильной работы предлагаемого ге-,нератора случайных чисел. АналогичноФормируются и осталвные разряды слу чайного числа с заданным законом рас.пределения.П Р и м е р. Пусть генератор 2равномерно распределенных случайных 15 чисел сформировал число , котороеудовлетворяет следующим условиямР(9/16)Р (10/16). учитывая,что фукнция распределения Р(х) неубывающая, имеем, что сигнал Ь 1,так как М Л (0,5), а сигналы Ь. = 1 20 и Ьз= О, так как )г Р (0,25) йс Р (0,75). Аналогично Ь 4= Ь 1,ьь ь) О, Ьз ь 9 ЬЮ Ьи Ь 4 УЬ 4 э,= Ь- Ь=.О, гпе Ь; - сигналы сйервой;группы вкходов ассоциативного запо минающего устройства, поступающиена первую группу входов 16 блока 4.Отсюда имеем, что первый разряд формируемого случайного числа равенединице, так как единичный сигнал З 0 Ь = 1 происходит непосредственно навыход 18 блока 4. Очевидно, второйразряд случайного числа равен нулю,так как сигналы Ь 1, Ь и Ь, посту"пающие на входы элементов 14 И и 1 35 ИЛИ, равны Ь, = Ь О, Ь 1. Аналогично на выходе элемента 15 ИЛИбудет сформирован нуйевой сигнал,так как сигналы, поступающие на входы элементов 14 И, 14 И, 14. И и 40 15 а ИЛИ, равны Б Ъ =Ь = Ь э Ои Ьь = Ь 4 = Ь= 1; Наконец, на выходеэлемента 15 з ИЛИ будет сФормированединичный сигнал, так как Ь = 1 и 45 - Ьв- Ь 9= Ь = Ь - Ь 1 здесь Ьсигналы со второй (инверсной) группыпы выходов ассоциативного запоминающего устройства 3, йоступающие навторую группу входов 17 блока 4. Таким образом, на выходах блока 4 будетсформирован код 1001. Будем считать,что запятая в случайном числе фиксирована перед старшим разрядом, Тогдана выходах предлагаемого генератораслучайных чисел будет сформировано 55 число 0,1001 .9/16, что соответствует исходным данным. При поступлении сигнала на вход 17 предлагаемыйгенератор заканчивает свою работу.Рассмотрим, как достигается поставленная цель - повышение быстродействия и сокращение аппаратурныхзатрат. В известномустройстве случайное число с заданным законом распределения формируется в течение одного 65 такта, причем каждый такт состоит изтрех микротактов. В первом микротакте по сигналам с выходов генератора тактовых импульсов формируется равномерно распределенное числои происходит установка в исходное состояние индикаторного устройства. Во втором микротакте случайное число з заносится в регистр, который вырабатывает импульсы токов опроса, под действием которых происходит сравне". ние числас ассоциативными призна" ками, хранящимися в ассоциативном запоминающем устройстве (АЗУ). Кроме того, во втором микротакте по сиг. налам с выходов АЗУ индикаторное устройство переводится в нужное состояние. В третьем микротакте посигналам, сформированным в логическом блоке, происходит чтение из рабочей части АЗУ случайного числа с заданным законом распределения. Заметим, что все названные микротакты следуют друг за другом последовательно без перекрытий. В данном генераторе равн мерно распределенное случайное числосра-. зу подается йавсоды АЗУ, в котором происходит одновременное сравнение числас ассоциативными признаками. Через время, равное времени срабатывания комбинационной схемы срав-. нения, на выходе АЗУ появятся .сигналы Ь и Ь, которые поступают в блок 4, являющийся двухуровневой комбинационной схемой. С выходов блока 4 случайное число с заданным законом распределения поступает через блок 5 элементов И непосредственно на выход устройства, Таким образом, в предлагаемом устройстве в отличие от известного отсутствуют потери времени на формирование токов опроса, уста-, новки в исходное и нужное состояние индикаторного устройства, чтение из памяти чисел, что и позволяет повысить скорость формирования случайных чисел с заданным законом распределения не менее чем в 1,5 раза.Сравнение известного и предлага" емого генераторов показывает, что в последнем отсутствуют такие блоки., как регистр признака опроса, индикаторное устройство и рабочая часть АЗУ (выходное устройство), которое 1 служит для хранения случайных чисел с заданным законом распределения, Суммарная сложность блока формирования случайных чисел и блока элементов И примерно равна сложности логического блока, который используется в известном устройстве в качестве дешифратора адреса рабочей части АЗУ. Кроме того, в известном устройстве используется АЗУ на ферритовых сердечниках, которое сложно в изготов-лении и эксплуатации, В предлагаемом, устройстве АЗУ может быть реализова-.но в интегральном исполнении ввиде БИСа, Поэтому использование предлагаемого устройства позволит резко сократить аппаратурные затраты по сравнению с известным при генериро вании случайных. чисел с заданным законом распределения без снижения функциональных возможностей.3Использование новых элементов =блока формирования случайных чисел и блока элементов И выгодно отличает предлагаемый генератор случайных чисел от известного, так как позволяет повысить скорость формирования случайных чисел и уменьшить аппаратурные затраты на изготовление генератора,формула изобретения2 С1. Генератор случайных чисел, содержащий генератор тактовых импульсов, первый выход которого соединенс входом генератора равномерно распределенных случайных чисел, блокпамяти, о т л и ч а ю щ и й с я тем,что, с целью повышения быстродействия, он содержит стояастическийпреобразователь и группу элементов И, ЗС выходы которых являются выходом генератора, выход генератора равномерно распределенных случайных чиселсбединен с входом блока памяти, первая и вторая группы выходов которого Зф соединены соответственно с первойи второй группами входом стохастического преобразователя, выходы которого соединены с первыми входамисоответствующих элементов И группы, 40 вторые входы которых соединены с вторым выходом генератора импульсов, первый и второй входы которого являютсясоответственно входами "Пуск" и "Стоп"генератора, выход блока памяти соеди нен с входом блока элементов И.2, Генератор по и, 1, о т л ич а ю щ и й с я тем, что стохастический преобразователь содержит элемент И, две группы элементов И и триэлемента ИЛИ, выходы которых являются выходами преобразователя, первыевходы элемента И и элементов И первой и второй групп образуют первуюгруппу входов преобразователя, вто,рую группу входов которого образуютвторые входы элемента. И, элементовИ первой и второй групп и первыевходы элементов ИЛИ, выход элементаИ соединен с вторым входом первогоэлемента ИЛИ, выходы элементов И первой группы соединены с соответствующими входами, кроме первого, второго элемента ИЛИ, выходы элементов Ивторой .группы соединены с соответствующими входами, кроме первого, 65 третьего элемента ИЛИ.991421 1 О Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 378826, кл. С 06 Г 7/58, 1971,2. Авторское 9 21324, кл. С 3Авторское 9 351207, кл. С тотип), свидетельство СССРОб Р 7/58, 1966свидетельство СССРОб Р 7/58, 1971 (про991421 1 б Составитель А. Карактор С. Патрушева Техред Т.Фанта Корректор М. Н 1 арош з 135/67 Тираж ВНИИПИ Государственн по делам изобретен 113035, Москва, Ж, дпис иал ППП "Патент", г. Ужгород, ул. Проектная, 4 Гб 17 704 Пого комитета СССРй и открытийаушская наб., д, 4/5