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

 

1. ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор равномерно распределенных случайных чисел, выход которого соединен с первыми входами блоков сравнения Круппы, вторые входы которых подключены к соответствующим выходам блока задания функции распределения, регистр памяти, выход которого является выходом датчика, отличающийся тем, что, с целью упрощения датчика, он содержит блок задания адреса, шифратор, три элемента И и генератор тактовых импульсов, выход которого соединен.с входом генератора равномерно распределённых случайных чисел и с первыми входами первого и второго элементов И, вторые входы которых подключены к выходу третьего элемента И, входы которого соединены с первыми выходами блоков сравнения группы соответственно, вторые выходы которых соединены с соответствующими входами шифратора, выход которого соединен с информационным входом регистра памяти, синхронизирующий вход которого соединен с выходом первого элемента И, с третьими входами блоков сравнения группы и с первым входом блока задания адреса, второй вход которого подключен к выходу второго элемента И, а выход блока задания адреса соединен с входом блока задания функции распределения. 2. Датчик по п. 1,отличаю щ и и с я тем, что каждый блок сравнения содержит два элемента И, (О два триггера и элемент ИЛИ, выход которого является первым выходом блока, вторым выходом которого явля а ется выход первого триггера, соедие . ненный с первым входом элемента ИЛИ, второй вход которого подключен к , выходу второго триггера и к первому входу первого элемента И, выход которого соединен с единичным входом первого триггера, нулевой вход которого объединен с нулевым входом второго триггера, выход второго элемента И соединен с единичным входом второго триггера, второй вход первого элемента И соединен с первым входом второго элемента И и-является первым входом блока, третий вход первого элемента И соединен с вто рым входом второго элемента И и яв ляется вторым входом блока, треть 1М входом которого является нулевой вход первого триггера. .

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

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

РЕСПУБЛИК всю G 06 F 7/58

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21 ) 3292011/18-24 (22) 25 05. 81 (46) 23.03.83. Бюл. и 11 (72) М.А. Орлов, 8.Н. Орлова, Л. А. Смирнова и А. 8. Соколов (71) Минский радйотехнический институт (53) 681 325 (088.8) (56) 1. Авторское свидетельство СССР 638995, кл. О 06 F 7/58, 1978.

2. Четвериков В.Н., Баканович 3.А., Меньков А.Б. 8ычислительная техника для статистического моделирования.

М., "Советское радио ", 1978, - с. 234-244, рис. У.6.1.У.6.3, У.6.4.

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

М 213424, кл. G 06 F 1/02, 1968 (прототип). (54)(57) 1. ЛАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор равномерно распределенных случайных чисел, выход которого соединен с первыми входами блоков сравнения группы, вторые входы которых подключены к соответствующим выходам блока задания. функции распределения, регистр памяти, выход которого является выходом датчика, отличающийся тем, что, с целью упрощения датчика, он содержит блок задания адреса, шифратор, три элемента И и генератор тактовых импульсов, выход которого соединен, с входом генератора равномерно распределенных случайных чисел и с первыми входами первого и второго элементов .И, вторые входы которых подключены к выходу третьего элемента И, входы которого соединены с первыми выходами блоков

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

2. Датчик по и. 1, о т л и ч аю шийся тем, что каждый блок сравнения содержит два элемента И, два триггера и элемент ИЛИ, выход которого является первым выходом блока, вторым выходом которого явля . ° ется выход первого триггера, соеди. ненный с первым входом элемента ИЛИ, второй вход которого подключен к выходу второго триггера и к первому входу первого элемента И, выход которого соединен с единичным входом первого триггера, нулевой вход которого объединен с нулевым входом второго триггера, выход второго weмента И соединен с .единичным входом второго триггера, второй вход первого элемента И соединен с первым входом второго элемента И и -является первым входом блока, третий вход первого элемента И соединен с вторым входом второго элемента И и является вторым входом блока, третьим входом которогоявляется нулевой вход первого триггера..

7104 - 2 количеством генераторов случайных событий.

Наиболее близким техническим решением к предлагаемому является уя1$ разрядного датчика равновероятных чисел и большого количества (по числу)квантилей схем параллельного сравнения многоразрядных чисел.

Целью изобретения является упрощение датчика случайных чисел.

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

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

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

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

Эффективны датчики случайных чисел и в качестве специализированного внешнего устройства в ЭВМ.

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

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

И и ИЛИ (1 3 .

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

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

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

И подключены к выходам соответствующих логических блоков, соединенных с выходными устройствами (3 ) .

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

Кроме того, каждый блок сравнения содержит два элемента И, два триггера и элемент ИЛИ, выход которого является первым выходом блока, вторым выходом которого является выход 10 первого триггера, соединенный с первым входам элемента ИЛИ, второй вход которого подключен к выходу второго триггера и к первому входу перaoro элемента И, выход которого 15 соединен с единичным входом первого триггера, нулевой вход которого объединен с нулевым входом второго триггера, выход второго элемента И соединен с единичным входом второго р0 триггера, второй вход первого элемента И соединен с первым входом второго элемента И и является первым входом блока, третий вход первого элемента И соединен с вторым входом второго элемента И и является вторым входом блока третьим входом которого является нулевой вход первого триггера.

На чертеже изображена структурная схема устройства.

Датчик случайных чисел содержит генератор 1 равномерно распределенных случайных чисел, блок 2 задания функции. распределения, блоки 3.1,.

3g, сравнения, блок 4 задания адреса, 1 35 генератор 5 тактовых импульсов, третий элемент И 6, первый 7 и второй

8 элементы И, шифратор 9 и регистр

10 памяти, причем блок 2 задания

40 . функции распределения включает М элементов 11.,...,11@ памяти с побитовой адресуемой выборкой, а каждый блок 3 сравнения - первый 12 1 и второй 12ъ триггеры, элемент И 13, элемент И 14, элемент ИЛИ 15.

Генератор 1 равномерно распределенных случайных чисел формирует первичные случайные числа, используемые для получения выходных случайных чисел, распределенных по требуемому закону. .Э

Блок 2 задания фУнкции Распределе" ния служит для хранения и выдачи кодов вероятностей соответствующих квантилей функции распределения.

Блоки 3„,...,31 1осуществляют сравнение первйчных случайных чисел, фор-. мируемых генератором 1,,со значени04 4 ями вероятностей функции распределе" ния, поступающими с выходов блока 2.

Блок 4 задания .адреса предназначен для определения адреса .очередного разряда каждого из кодов вероятностей функции распределения, хранящихся в блоке 2.

Генератор 5 тактовых импульсов обеспечивает синхронность работы всех узлов датчика случайных чисел.

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

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

Шифратор 9 формирует выходное случайное число, распределенное по требуемому закону.

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

Элементы 1 1<,..., 11 памяти с побитовой адресуемой выборкой служат для хранения и выдачи по запросу блока 4 выбора адреса одного из разрядов соответствующих кодов вероятностей функции распределения.

Первый 12 и второй 12 триггеры, элементы И 13 и 14, а также элемент

ИЛИ 15 реализуют операцию сравнения >

i-го разряда первичного случайного числа с соответствующим разрядом соответствующего кода вероятностей функции распределения °

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

1 2 3

5 6 7 8

Разряды

Код вероятности, хранящийся в блоке 11 °

1 0 0

1 0 1

Код вероятности, хранящийся в блоке 11;

Первичное случайное число Ь

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

Устройство работает следующим образом.

При включении датчика случайных чисел генератор 1 по сигналу гене- ф ратора 5 тактовых импульсов вырабатывает первый (старший) разряд первичного случайного числа, который

Допустим также, что старший разряд первичного случайногочисла % равен едиНиц Ъ1=1. В этом случае на выходе элемента И 13 i-го блока 3 ° еди1 ничный сигнал не появляется, так как на третий вход трехвходового элемента И 13, являющийся инверсным, поступает единичный сигнал с третьего входа блока 3 . На выход элемента

И 14 также не проходит единичный сигнал с третьего входа блока 3 1, так как на первый вход элемента Й 14 являющийся инверсным, подается единичный сигнал с второго входа блока

3) °

Аналогичная ситуация происходит в (<+1)-м блоке 3 ° +1 .

Поскольку на выходах элементов

И 13 и 14 присутствует нулевой сигнал, то переключения первого 12 и

50 второго 12 триггеров в единичное состояние не происходит. Следователь но, нулевой сигнал сохраняется и на выходе элемента И 6.

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

04 6 поступает на третьи входы всех блоков

3,,...,3ы. Одновременно на вторые входы блоков 3,,,..., 3 подаются старшие разрядй кодов вероятностей для соответствующих квантилей функции распределения с соответствующих выходов блока 2.

Допустим, что в i-м и (i+1)-м элементах ll„ и 11 +, памяти с побитовой адресуемой выборкой хранятся следующие коды вероятностей розыгрыша (появления) квантилей функции распределения: же тактовый импульс вызывает прохождение единичного сигнала на выход второго элемента И 8, так. как на его второй вход, являющийся инверсным, поступает нулевой сигнал с выхода элемента И 6. Сигнал с выхода второго элемента И 8 подается на второй вход блока 4, что приводит к формированию в блоке 4 задания адреса, адреса очередного разряда кода вероятности соответствующих квантилей функции распределения и выдаче их на выходы блока 2.

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

Допустим, что второй разряд первичного случайного числа принимает значение единицы ф2 =1, Тогда на выходе элемента И 14 i-го блока31 появляется единичный сигнал, переключающий второй триггер 12 у в единичное состояние. Состояние на выходе элемента

И 13 не изменяется, так как на его третий (инверсный) вход поступает единичный сигнал с третьего входа блока 31.

В (i+1 )-м блоке 3; 1 происходят те же процессы, что и на предыдущем такте.

I 10071

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

Тогда на выходе элемента И 13 (i+1)-го блока 3. +1 появляется единичный сигнал, так как на его второй вход поступает единичный сигнал с >s соответствующего выхода блока 2, на третий инверсный вход — нулевой сигнал с выхода генератора 1, а на первый инверсный вход — нулевой сигнал с выхода второго триггера 122 (переключения второго триггера 12 2 в единичное состояние не происходит, поскольку состояние на выходе двухвходового элемента И 14 не изменяется). Единичный сигнал с выхода эле- 2s мента И 13 вызывает переключение первого триггера 12 1 в единичное состояние.

Переключения первого триггера 12

i-го блока 3 „. в единичное состояние не происходит, так как прохождение единичного сигнала яа выход элемента

И 13 блокируется единичным сигналом с выхода второго триггера 12, поступающим на первый инверсный вход элемента И 13 i-ro блока 3 ° .

Операция сравнения продолжается до тех пор, пока не сработает хотя бы один из триггеров 12 или 122 каж1 дого блока 31,...,3 1, что означает, что первичное случайное число больше (срабатывает второй триггер 122)либо меньше (срабатывает первый триггер

121) соответствующих кодов вероятностей функЦии распределения.

После окончания операции сравне45 ния единичные сигналы с выходов одного из триггеров каждого. блока 31, ...,3„ проходят через элемент ИЛИ 15 и поступают на входы элемента И 6, а единичный сигнал с его выхода проходит через первый элемент И 7, переводит блок 4 в первоначальное состояние для получения возможности формирования очередного выходного случайного числа и обнуляет оба триггера

121 и 122 каждого блока 31,...,3 .

Поскольку значения кодов вероятностей розыгрыша квантилей функции распределения, хранящиеся в элементах 11.. .11 .. памяти с побитовой адресуемой выборкой, не превышают значения кода вероятности, хранящегося в элементе 11„ памяти, а значения кодов вероятностей, хранящихся в элементах 11-+2,...,111,1 памяти, больше значения кода вероятности, хранящегося в элементе 1li4.11 памяти, то на вторых выходах блоков

3,...,3 обязательно формируются нулевые сигналы.

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

Выходное случайное число, распределенное по требуемому закону, из регистра 10 подается на выход датчика случайных чисел, так как на втором входе регистра 10 присут" ствует разрешающий сигнал с выхода двухвходового элемента И 7.

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

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

1007104

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

Редактор Т. Кугрышева Техред Q. Неце

Корре ктор 6. Ма карен ко

Подписное

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

Заказ 2140/72 Тираж 704

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

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