Датчик случайных чисел

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 100 у(51 С 06 Г 7/ ПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОМУ ЕТЕЛЬСТ сравнения группы соотверые выходы которых соедответствующими входамивыход которого соединенционным входом регистрасинхронизирующий вход кодинен с выходом первогос третьими входами блокогруппы и с первым входомзадания адреса., второйго подключен .к выходу втта И, а выход блока задасоединен с входом блокафункции распределения. о, вто сора,Л. А. См,А.,а 6.4СР 2. Датчик по и. 1, о т л и ч а - дю щ и й с я тем, что каждый блокесравнения содержит два элемента И,два триггера и элемент ИЛИ, выходкоторого является первым выходомблока, вторым выходом которого явля.ъется выход первого триггера, соединенный с первым входом элемента ИЛИ,второй вход которого подключен квыходу второго триггера и к первомувходу первого элемента И, выход которого соединен с единичным входомпервого триггера, нулевой вход которого объединен с нулевым входом второго триггера, выход второго эле- фмента И соединен с .единичным входомвторого триггера, второй вход первого элемента И соединен с первымвходом второго элемента И и -являетсяпервым входом блока, третий вход .,фЬпервого элемента И соединен с вторым входом второго элемента И и является вторым входом блока, третьимвходом которогоявляется нулевойвход первого триггера ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(72.) М.А. Орлов, В.Н. Орлова,ирнова и А.В. Соколовинский радйотехнический итут(56) 1. Авторское свидетельствоМ 638995, кл. О 06 Р 7/58, 19782. Четвериков В.Н., БакановиМеньков А.Б. Вычислительная техдля статистического моделированМ., "Советское радио", 1978,с. 234-244, рис. У.6.1.У,6.3, У3. Авторское свидетельство СМ 213424, кл. С 06 Р 1/02, 1968(54)(57) 1 ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ,содержащий генератор равномерно распределенных случайных чисел, выходкоторого соединен с первыми входамиблоков сравнения группы, вторыевходы которых подключены к соответствующим выходам блока задания. функции распределения, регистр памяти,выход которого является выходомдатчика, о т л и ч а ю щ и й с ятем, что, с целью упрощения датчика,он содержит блок задания адреса,шифратор, три элемента И и генератор тактовых импульсов, выход которого соединен, с входом генератораравномерно распределенных случайныхчисел и с первыми входами первогои второго элементов .И, вторые входыкоторых подключены к выходу третьего элемента И, входы которого соединены с первыми выходами блоков ственненыифратос инфопамятторогоэлемев сраблокаход косрогония адзадани7104 . 2количеством генераторов случайныхсобытий,Наиболее близким техническим решением к предлагаемому является упразрядного датчика равновероятныхчисел и большого количества (почислу)квантилей схем параллельногосравнения многоразрядных чисел,Целью изобретения является упрощение датчика случайных чисел.Эта цель достигается тем, что вдатчик случайных чисел, содержащийгенератор равномерно распределенныхслучайных чисел, выход которого сое- З . динен с первыми входами блоков сравнения группы, вторые входы которыхподключены к соответствующим выходамблока задания функции распределения,регистр памяти, выход которого является выходом датчика, введены блокзадания адреса, шифратор, три элемента И и генератор тактовых импульсов, выход которого соединен с входом генератора равномерно распредеф ленных случайных чисел и с первымивходами первого и второго элементовИ, вторые входы которых, подключенык выходу третьего элемента И, входыкоторого соединены с первыми выходами 6 блоков сравнения группы соответственно, вторые выходы которых соединеныс соответствующими входами шифратора,выход которого соединен с информационным входом регистра памяти, син- Я хронизирующий вход которого соединенс выходом первого элемента И, с третьими входами блоков сравнения группыи с первым входом блока задания100Изобретение относится к вычислительной технике и может бь 1 ть использовано при моделировании случайныхпроцессов.Особенно эффективно подобные уст"ройства могут быть использованы длярешения задач исследования сложныхсистем, при создании испытательнойаппаратуры, входящей в состав стохастическим моделирующих и вычислительных комплексов. На выходе такой аппаратуры требуется получать до нескольких десятков потоков случайныхвеличин (чисел ), подаваемых на испытуемый объект, 1Эффективны датчики случайныхчисел и в качестве специализированного внешнего устройства в ЭВМ.Одним из перспективных направлений в создании датчиков случайных щчисел является разработка принципиально новых схемных решений, позволяющих значительно упростить устройство и повысить эффективность функционирования новых разработок по 2спавнению с известными,Известен датчик случайных чисел,построенный на базе управляемоговероятностного преобразователя, содержащего блок памяти, регистр сдвига, вероятностный (1,11) полюсник,блок управления, генераторы импульсов, счетчики, триггеры, элементыИ и ИЛИ 1 ,Этот датчик, реализуя последовательный рекуррентный способ формирования случайных чисел, обладаетсравнительно невысоким быстродействием, пропорциональным математицес,кому ожиданию генерируемого числа,что ограничивает возможность егоприменения.Наиболее быстродействующими являются датчики случайных чисел, реализующие метод минимаксных преобразований заключающийся, вчастности, ввыделении первого из событий группыпотоков случайных событий. Эти датчики содержат в качестве основныхэлементов, устройство ввода функциираспределения, генераторы потоковслучайных событий, логические блокивыделения первого события, дешифратор, регистр и ряд дополнительныхблоков для управления испытаниями 23.Недостатком этих датчиков является их значительная сложность, обусловленная большим (по числу квантилей) равляемый датчик случайных чисел,содержащий датчик равновероятныхчисел, устройство ввода функции рэ.пределенйя, схемы параллельного сравнения чисел и выходные устройства,например, регистры, причем схемы сравнения соединены с логическимиблоками, включающими по одному триггеру и элементу И, так, что выходкаждой из схем сравнения соединен.с единичным входом триггера, единичный выход которого подключен кпервому входу элемента И, второйвход которого соединен с нулевымвыходом триггера последующего логического блока, а выходы элементов И подключены к выходам соответствующих логических блоков, соединенных с выходными устройствами3 ) .Недостатком датчика является сложность, обусловленная наличием много1 2 3 5 6 7 8 Разряды Код вероятности, хранящийсяв блоке 11 1 О О 1 О 1 Код вероятности, хранящийсяв блоке Первичноеслучайноечисло Ъ О 5 1 ООУ 1как результат. выделения интервала,в который попадает первичное случайное число после выполнения операции его сравнения с кодами вероятностей розыгрыша соответствующих кван-тилей Функции распределения,Устройство работает следующимобразом,При включении датчика случайныхчисел генератор 1 по сигналу гене оратора 5 тактовых импульсов вырабатывает первый (старший) разряд первичного случайного числа, который Допустим также, что старший разряд первичного случайногочисла % равен едиНиц 1=1. 8 этом случае на выходе элемента И 13 -го блока 3 единичный сигнал не появляется, так как на третий вход трехвходового элемента И 13, являющийся инверсным, поступает единичный сигнал с третьего входа блока 3 . На выход элемента И 14 также не проходит единичный сигнал с третьего входа блока 3 так как на первый вход элемента И 14 являющийся инверсным, подается единичный сигнал с второго входа блока 3.4Аналогичная ситуация происходитв (9-1)-м блоке 3;1Поскольку на выходах элементов И 13 и 14 присутствует нулевой сигнал, то переключения первого 12 и50 второго 12триггеров в единичное состояние не происходит. Следовательно, нулевой сигнал сохраняется и на выходе элемента И 6.Следующий тактовый импульс, вырабатываемый генератором 5 тактовых импульсов, приводит к появлению на выходе генератора 1 второго разряда первичного случайного числа Ь, Этот 04 6поступает на третьи входы всех блоков 3 31. Одновременно на вторые входы блоков 3,31 подаются старшие разряды кодов вероятностей для соответствующих квантилей функции распределения с соответствующих выходов блока 2.Допустим, что в 1-м и (+1)-м элементах 11 и 11+памяти с побитовой адресуемой выборкой хранятся следующие коды вероятностей розыгрыша (появления) квантилей Функции распределения: же тактовый импульс вызывает прохождение единичного сигнала на выход второго элемента И 8, так. как на его второй вход, являющийся инверсным, поступает нулевой сигнал с выхода элемента И б. Сигнал с выхода второго элемента И 8 подается на второй вход блока 4, что приводит к формированию в блоке 4 задания адреса, адреса очередного разряда кода вероятности соответствующих квантилей функции распределения и выдаче их на выходы блока 2.Таким образом начинается следующий этап операции сравнения.1Допустим, что второй разряд первичного случайного числа принимает значение единицыЬ 2 =1, Тогда на выходе элемента И 1 Ь 1-го блока 31 появляется единичный сигнал, переключающий второй триггер 12в единичное состояние. Состояние на выходе элемента И 13 не изменяется, так как на его третий (инверсный) вход поступает единичный сигнал с третьего входа блока 31.В (1+1)-м блоке 3; 1 происходят те же процессы, что и на предыдущем такте.I 10071Очередной тактовый импульс приводит к формированию в блоке 4 заданияадресаадреса третьих разрядов кодоввероятностей всех квантилей функциираспределения и выдаче их на соответствующие выходы устройства 2. вводафункции распределения, а также кпоявлению на выходе генератора 1третьего разряда первичного случайного числа Ъ , равного, например, 1 онулю.Тогда на выходе элемента И 13(+1)-го блока 3. +1 появляется единичный сигнал, так как на его второйвход поступает единичный сигнал с15соответствующего выхода блока 2,на третий инверсный вход - нулевойсигнал с выхода генератора 1, а напервый инверсный вход - нулевой сигнал с выхода второго триггера 122 2 о(переключения второго триггера 12 2в единичное состояние не происходит,поскольку состояние на выходе двухвходового элемента И 14 не изменяется). Единичный сигнал с выхода элемента И 13 вызывает переключениепервого триггера 12в единичноесостояние.Переключения первого триггера 1211-го блока 3в единичное состояниене происходит, так как прохождениеединичного сигнала яа выход элементаИ 13 блокируется единичным сигналом с выхода второго триггера 12 ,поступающим на первый инверсный входэлемента И 13 1-го блока 3.Операция сравнения продолжаетсядо тех пор, пока не сработает хотябы один из триггеров 12 или 12каж 1дого блока 3,131, что означает,что первичное случайное число больше(срабатывает второй триггер 122)либоменьше (срабатывает первый триггер121) соответствующих кодов вероятностей ФункЦии распределения.После окончания операции сравне 45ния единичные сигналы с выходов одного из триггеров каждого. блока 3.1,,3 проходят через элемент ИЛИ 1и поступают на входы элемента И 6,а единичный сигнал с его выхода проходит через первый элемент И 7, переводит блок 4 в первоначальное состояние для получения возможности формирования очередного выходного случайного числа и обнуляет оба триггера 12и 122 каждого блока 33 ц.Поскольку значения кодов вероятностей розыгрыша квантилей функции распределения, хранящиеся в элементах 11 .11 . памяти с побитовой адресуемой выборкой, не превышают значения кода вероятности, хранящегося в элементе 11 памяти, а значения кодов вероятностей, хранящихся в элементах 11 +2 111,1 памяти, больше значения кода вероятности, хранящегося в элементе 1114.11 памяти, то на вторых выходах блоков 33,1 обязательно Формируются нулевые сигналы.Интегральный двоичный код с вторых выходов блоков 3, :.,3 д поступает.на входы шифратора 9, где происходит формирование дифференциального двоичного кода и выделение интервала, в который попадает первичное случайное число в результате операции его сравнения с кодами вероятностей введенной функции распределения.Выходное случайное число, распределенное по требуемому закону, из регистра 10 подается на выход датчика случайных чисел, так как на втором входе регистра 10 присут" ствует разрешающий сигнал с выхода двухвходового элемента И .Технико-экономическая эффективность предлагаемого датчика случайных чисел определяется значительным упрощением его устройства, заключающимся в упрощении функциональных блоков и уменьшении числа связей схемы при сохранении достаточно высокого быстродействия, превышающего быстродействие последовательных датчиков, не намного более простых, чем предлагаемый.Кроме того, значительно расширяются возможности интегрального исполнения датчика .случайных чисел в виде, например, большой гибридной интегральной микросхемы, вследствие высокой однородности структуры, выполненной на основе цифровой элементной базы, и относительно малого, по =равнению с известными устройствами, числа межсоединений схемы.1007104 Составитель А, КаРедактор Т, Кугрышева Техред О.Неце Зак Филиал ППП фПатент", г. Ужгород, ул, Проектн 140/72 ВНИИПИ Гос по дела