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

11 Изобретение относится к вычислительной технике и может бьГть исполь зовано при моделировании случайных процессов. Особенно эффективно подобные уст ррйства могут быть использованы для решения задач исследования сложных систем, при создании испытательной аппаратуры, входящей в состав стоха стических моделирующих и вычислител ных комплексов. На выходе такой аппаратуры требуется получать до нескольких десятков потоков случайных величин (чисел), подаваемых на испытуемый объект. . Эффективны датчики случайных чисел и в качестве специализированн го внешнего устройства в ЭВМ. Одним из перспективных направлений в создании датчиков случайных чисел является разработка принципиа но новых схемных решений, позволяюI щих значительно упростить устройство и повысить эффективность функционирования новых разработок по сравнению с известными. Известен датчик случайных чисел, построенный а базе управляемого вероятностного преобразователя, содержащего блок памяти, регистр сдви га, вероятностный (1, h ) полюсник, блок управления, генераторы импульсов, счетчики, триггеры, элементы И и ИЛИ 1 . Этот датчик, реализуя последовательный рекуррентный способ формиро вания случайных чисел, обладает сравнительно невысоким быстродействием, пропорциональным математическ му ожиданию генерируемого числа, что ограничивает возможность его применения. Наиболее быстродействующими являются датчики случайных чисел, реа лизующие метод минимаксных преобраз ваний заключающийся, вчастности, в выделении первого из событий группы потоков случайных событий. Эти датчики содержат в качесуве основных элементов .устройство функции распределения, генераторы потоков случайных событий, логические блоки выделения первого события, дешифратор, регистр и ряд дополнительных блоков для управления испытаниями С2 3 . Недостатком этих датчиков являет ся их значительная сложность, обусло вленная большим (по числу квантилей 1 . 2 количеством генераторов случайных событий. Наиболее близким техническим решением к предлагаемому является управляемый датчик случайных чисел, содержащий датчик равновероятных чисел, устройство ввода функции ра.пределен1 я, схемы параллельного сравнения чисел и выходные устройства, например, регистры, причем схемы сравнения соединены с логическими блоками, включающими по одному триггеру и элементу И, так, что выход каждой из схем сравнения соединен. с единичным входом триггера, единичный выход которого подключен к первому входу элемента И, второй вход которого соединен с нулевым выходом триггера последующего логического блока, а выходы элементов И подключены к выходам соответствующих логических блоков, соединенных с выходными устройствами 33Недостатком датчика является спошность, обусловленная наличием многоразрядного датчика равновероятных чисел и большого количества (по числу)квантилей схем параллельного сравнения многоразрядных чисел. Целью изобретения является упрощение датчика случайных чисел. Эта цель достигается тем, что в датчик случайных чисел, содержащий генератор равномерно распределенных случайных чисел, выход которого соединен с первыми входами блоков сравнения группы, вторьте входы которых подключены к соответствующим выходам блока задания функции распределения, регистр памяти, выход которого является выходом датчика, введены блок задания адреса, шифратор, три элемента И и генератор тактовых импульсов, выход которого соединен с входом генератора равномерно распределенных случайных чисел и с первыми входами первого и второго элементов И, вторые входы которых подключены к выходу третьего элемента И, входы которого соединены с первыми выходами блоков сравнения группы соответственно, втюрые выходы которых соединены с соответствующими входами шифратора, выход которого соединен с информационным входом регистра памяти, синхронизирующий вход которого соединен с выходом первого элемента И, с третьими входами блоков сравнения группы и с первым входом блока задания адреса, второй вход которого подключен к выходу второго элемента И, а выход блока задания адреса соединен с входом блока задания функции распределения. Кроме того, каждый блок сравнения содержит два элемента И, два триггера и элемент ИЛИ, выход которого является первым выходом блока вторым выходом которого является выход первого триггера, соединенный с первым входом элемента ИЛИ, второй вход которого подключен к выходу вто рого триггера и к первому входу первого элемента И, выход которого соединен с единичным входом первого триггера, нулевой вход которого объе динен с нулевым входом второго триггера, выход второго элемента И соединен с единичным входом второго триггера, второй вход первого элемен та И соединен с первым входом второго элемента И и является первым входом блока, третий вход первого элемента И соединен с вторым входом второго элемента И и является вторым входом блока третьим входом которого является нулевой вход первого триггера. На чертеже изображена структурная схема устройства. Датчик случайных чисел содержит генератор 1 равномерно распределенных случайных чисел, блок 2 задания функции распределения, блоки 3-j, 3|g, сравнения, блок t задания адреса генератор 5 тактовых импульсов, третий элемент И 6, первый 7 и второй 8 элементы И, шифратор 9 и регистр 10 памяти, причем блок 2 задания функции распЕэеделения включает 1 элементов 1 Ц ,... ,11(s| памяти с поби товой адресуемой выборкой, а каждый блок 3 сравнения - первый 12-1 и второй 122. триггеры, элемент 3, элемент И l, элемент ИЛИ 15. Генератор 1 равномерно распределенных случайных чисел фо.рмирует первичные случайные числа, используемые для получения выходных случа ных чисел, распределенных по требуемому закону. Блок 2 задания Функции распредел ния служит для хранения и выдачи кодов вероятностей соответствующих квантилей функции распределения. Блоки 3 . . J 3 (Ц осуществляют сра нение первичных случайных чисел, фо мируемых генератором 1, со значениями вероятностей функций распределения, поступающими с выходов бло|Га 2. Блок 4 задания адреса предназначен для определения адреса-очередного разряда каждого из кодов вероятностей функции распределения, хранящихся в блоке 2. Генератор 5 тактовых импульсов обеспечивает синхронность работы всех узлов датчика случайных чисел. Элемент Иб определяет момент окончания операции сравнения разрядов первичного случайного числа с соответствующими разрядами кодов вероятностей функции распределения и разрешения выдачи сформированного случайного числа, распределенного по требуемому закону, на выход датчика случайных чисел. Элемент И 7 вырабатывает сигнал, разрешающий выдачу сформированного случайного числа на выход устройства и подготавливающий необходимые . блоки устройства к формированию следующего случайного числа. Элемент И 8 вырабатывает сигнал, по которому определяется адрес-очередных разрядов кодов вероятностей 4)ункции распределения для осуществления операции сравнения. Шифратор 9 формирует выходное случайное число, распределенное по требуемому закону. Регистр 10 памяти служит в качестве буферного устройства, хранящего выходное случайное число до поступления сигнала, разрешающего выдачу его на выход датчика случайных чисел. Элементы 11,. .., 11 м памяти с по- битовой адресуемой выборкой служат для хранения и выдачи по запросу блока k выбора адреса одного из разрядов соответствующих кодов вероятностей функции распределения. Первый и второй 122 триггеры, элементы И 13 и lA, а также элемент ИЛИ 15 реализуют операцию сравнения i-го разряда первичного случайного числа с соответствующим разрядом соответствующего кода вероятностей функции распределения. В основе работы датчика случайных чисел лежит йетод обратных функций, который заключается в сравнении первичного случайного числа, вырабатываемого генератором с кодами вероятностей функции распределения. Выходное случайное число, распределенное по требуемому закону, получается

510071

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

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

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

14

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

Допуст1/1м, что в i-M и (1+1)-м элементах 11 и 11 памяти с побитовой адресуемой выборкой хранятся следующие коды вероятностей розыгрыша (появления) квантилей функции распределения:

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

Код вероятности, хранящийся 1011 в блоке 1Ь Код вероятности, хранящийся 1 11 0 в блоке 1 Ц Первичное случайное число Ъ 1 1 О Дсэпустим также, что старший разря первичного случайного числа Ь равен едиЯицс; Ъ- 1. В этом случае на выходе элемента И 13 1-го блока 3:: ед ничный сигнал не появляется, так как на третий вход трехвходового элемента И 13, являющийся инверсным поступает единичный сигнал с третье входа блока 3j. На выход элемента И 14 также не проходит единичный сигнал с третьего входа блока 3, так как на первый вход элемента И I являющийся инверсным, подается единичный сигнал с второго входа блока Аналогичная ситуация происходит В (tbi )-м блоке 3 Поскольку на выходах элементов И 13 и 1 присутствует нулевой сигнал, то переключения первого 12,. и второго 129 триггеров в единичное состояние не происходит. Сяедователь но, нулевой сигнал сохраняется и на выходе элемента И 6, Следующий тактовый импульс, выраб тываемый генератором 5 тактовых импульсов, приводит к появлению на выходе генератора 1 второго разряда первичного случайного числа Ь2 Этот 11ОО 1 01 1 же тактовцй импульс вызывает прохождение единичного сигнала на выход второго элемента И 8, так как на его второй вход, являющийся инверсным, поступает нулевой сигнал с выхода элемента И 6. Сигнал с выхода второго элемента И 8 подается на второй вход блока , что приводит к формированию в блоке задания адреса адреса очередного разряда кода вероятности соответствующих квантилей функции распределения и выдаче их на выходы блока 2. Таким образом, начинается следующий этап операции сравнения. Допустим, что второй разряд первичного случайного числа принимает значение единицы 1 Тогда на выходе элемента И 14 i-ro блокаЗ появляется единичный сигнал, переключающий второй триггер 12 2 в единичное состояние. Состояние на выходе элемента И 13 не изменяется, так как на его третий (инверсный) вход поступает единичный сигнал с третьего входа блока В (i+1)-M блоке происходят те же процессы, что и на предыдущем , . такте. /1 Очередной тактовый импульс приводит к формированию в блоке 4 задания адреса адреса третьих разрядов кодов вероятностей всех квантилей функции распределения и выдаче их на соответ ствукхцие выходы устройства 2. ввода функции распределения, а также к появлению на выходе генератора 1 третьего разряда первичного случайно го числа 1)3 , равного, например, нулю. Тогда на выходе элемента И 13 (i+1)-ro блока 3. + - появляется единичный сигнал, так как на его второй вход поступает единичный сигнал с соответствующего выхода блока 2, на третий инверсный вход - нулевой сигнал с выхода генератора 1, а на первый инверсный вход - нулевой сигнал с выхода второго триггера 122 (переключения второго триггера IZo в единичное состояние не происходит поскольку состояние на выходе двухвходового элемента И 14 не изменяется). Единичный сигнал с выхода элемента И 13 вызывает переключение первого триггера 12 в единичное состояние. Переключения первого триггера 12 i-ro блока 3i в единичное состояние не происходит, так как прохождение единичного сигнала па выход элемента И 13 блокируется единичным сигналом с выхода второго триггера 122 . поступающим на первый инверсный вход элемента И 13 1-го блока 3 Операция сравнения ггродолжается до тех пор, пока не сработает хотя бы один из TpVirrepoB 12 или 12 л каж дого блока что означает, -- ЧТО первичное случайное число больше (срабатывает второй триггер 122)яибо меньше (срабатывает первый триггер 12) соответствующих кодов вероятностей функции распределения. После окончания операции сравнения единичные сигналы с выходов одного из триггеров каждого.блока 3-, .,3 проходят через элемент ИЛИ 1 и поступают на входы элемента И 6, W а единичный сигнал с его выхода про ходит через первый элемент И 7, пер водит блок 4 в первоначальное состояние для получения возможности фо 4 8 мирования очередного выходного случайного числа и обнуляет оба триггера 12х,и 122 каждого блока 3-,f . . ,3(М Поскольку значения кодоз вероятностей розыгрыша квантилей функции распределения, хранящиеся в элементах 1Ц,1,.,11 памяти с побитовой адресуемой выборкой, не превышают значения кода вероятности, хранящегося в элементе ll.- памяти, а зна- чения кодов вероятностей, хранящихся в элементах 11 +211fs| памяти, больше значения кода вероятности, хранящегося в элементе П|4- памяти, то на вторых выходах блоков 3,. . . обязательно формируются нулевые сигналы. Интегральный двоичный код с вторых выходов блоков Зх|, .. (Зм поступает, на входы шифратора 9 где происходит формирование дифференциального двоичного кода и выделение интервала, в который попадает первичное случайное число в результате операции его сравнения с кодами вероятностей введенной функции распределения. Выходное случайное число, распределенное по требуемому закону, из регистра 10 подается на выход датчика случайных чисел, так как на втором входе регистра 10 присутствует разрешающий сигнал с выхода двухвходового элемента И 7. Технико-экономическая эффективность предлагаемого датчика случайных чисел определяется значительным упрощением его устройства, заключающимся в упрощении функциональных блоков и уменьшении числа связей схемы при сохранении достаточно высокого быстродействия, превышающего быстродействие последовательных датчиков, не намного более простых, чем предлагаемый. Кроме того, значительно расширяются возможности интегрального исполнения датчика .случайных чисел в виде, например, большой гибридной интегральной микросхемы, вследствие высокой однородности структуры, выполненной на основе цифровой : элементной базы, и относительно малого, по сравнению с известными устройствами, числа межсоединений схемы.