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

Изобретение относится к вычислительной технике и может быть исполь зовано при моделировании случайных процессов. Особенно: эффективны подобные устройства при пост эоении испытательной аппаратуры, входящей в состав вычислительно-моделирующих комп лексов. На выходе такой аппаратуры требуется получать до нескольких де сятков потоков случайных величин (чисел), подаваемых на испытуемый объект. Эффективны аппаратурные датчики случайных чисел и в качестве специализированного внешнего устройств к ЭВМ. При этом к датчикам предъявляется ряд часто противоречивых тре бований, например, необходимость достижения требуемого быстродействи и достаточно простая схемно-констру тивная реализация. Одним из перспективных направлений в создании датчиков случайных чисел является разработка принципиально новых схемных решений, позволяющих снять противоречия в техни ческих требованиях и повысить эффек тивность новых решений по сравнению с известными . Известны датчики случайных чисел, основными узлами которых являются блок памяти, генератор первичных равновероятностных двоичных чисел, вероятностные вентили, схемы сравнения, схемы дешифрации, элементы И и ИЛИ, реализующие для получения чисел с требуемым распределением метод обратных функций, методы рекуррентного и минимаксного преобразований. Эти датчики, работающие по параллельному способу формирования всех цифр выходного случайного числа, сложны, хотя и обеспечивают наибольшее быстродействие. Более просты схемы датчиков случайных чисел,реализующие метод условных вероятностей,по которому цифры выходного случайного числа формируются последовательно, начиная со старшей. Рассмотрим эти схемы более детально. Известен датчик случайных чисел, содержащий мультивибраторы и генератор случайных импульсов, подключенные через элементы И к первым .входам соответствующих триггеров, образующих регистр хранения случайных чисел, причем вторые входы триггеров подключены к установочному входу

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

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

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

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

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

Поставленная цель достигается тем что датчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий N основных триггеров и М дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равйовероятных двоичных чисел, выход котцррго соединен с вторым входом (Первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов , выход которого подключен к выходу генератора равновероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, снабжен дополнительными (N-1)

регистрами хранения случайного числа разрядность которых возрастает соответственно на один от 1 до (N-1)-, (N,-1) блоками памяти и (N-1) ключами первые входы которых подключены к выходам соответствующих блоков памяти, вторые входы - к выходу генератора равновероятных двоичных чисел, треть входы - к выходу генератора тактовых импульсов и ко входам синхронизации регистров хранения случайных чисел соответственно. Выход каждого из вероятностных вентилей подключен к установочному входу триггера младшего ;разряда соответствующего регистра хранения случайного числа. Выходы рарядных триггеров каждого предыдущего регистра хранения случайного числа, расположенного в порядке возрастания числа разрядов, подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа и к адресным входам последующего блока памяти.

На чертеже изображена структурная схема датчика,

датчик содержит N блоков памяти ((), f/ ключей (), регистры хранения случайного числа (3 -3jjj ), генератор равновероятных двоичных чисел 4 и генератор тактовых импульсов 5.

Первые входы ключей подключены к выходам соответствующих блоков памяти , . вторые входы - к выходу генератора 4 и установочным входам дополнительных триггеров ((N+1) ...,(N+M)) регистра Зу, третьи входы - к выходу генератора 5 и ко входам синхронизации регистров 3 -Зц, выходы разрядных триггеров каждого предыдущего 3 из которых подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа и к адресным входам последующего L(VH блока памяти.

Блок памяти 1 служит для хранения и выдачи кодов вероятностей появления единичного значения соответствующей разрядной цифры выходного случайного числа с требуемым законом распределения. Ключи 2 реализуют поразрядное логическое перемножение кодов с выходов генератора 4 и блоков памяти 1 и выделения хотя бы одного единичного результата. Регистры 3 реализуют хранение частично сформированных случайных чисел, полностью сформированное (N+M)-разрядное число, распределенное по требуемому закону, образуется на N-M регистре 3. Генератор 4 формирует первичные слу чайные числа, используемые для формирования разрядных цифр выходного случайного числа с требуемым законом распределения. Генератор 5 вырабатывает поток импульсов, синхронизиру щих работу всего устройства. Устройство функционирует следую щим образом. Для получения на выходе датчика первого полностью сформированного случайного числа, распределенного по требуемому закону, при запуске датчика случайных чисел необходимо N тактов, после чего числа .с требу мым распределением получают на выходах датчика в каждом такте. Например, при на выходе дат .ка с заданной вероятностью появля ется одно четырехразрядное число и 16 возможных. Каждому двоичному числу соответ ствует вероятность Р его появлени которая определяется, исходя из тр буемого закона распределения. В соответствии с этим вероятност «оявления единицы в старшем разряде выходного случайного числа равна Р(а 1),, н-Р,о , +Р,2. +Р, +Р,4 -f Вероятность появления нуля в старше разряде равна Р (а 0) Р .+Рз+Р4 I Вероятность появления единицы во втором разряде выходного числа зави сит от того, какое значение принял старший разряд. Например, при P.,.+P,.4R +Р. Р()(а,м)- .. S Р(а,-1) при а 0 РС + P(q,-H)V-o)- Аналогично вероятности., появления нуля во втором разряде РК-«, Р(а,.о.с,.о,- ТаУоУ Для нормального функционирования датчика Достаточно хранить в блоках памяти следующие условия вероятности:в первом блоке памяти - Р(), во втором блоке памяти - Р()гР( 0) в третьем блоке памяти - Р ( 1 ,) Р(аз ,а,0) .Р(,а2 1) Р(,) в четвертом блоке памяти - Р(.1,а 1,а.1) Р(а.1/а%1,а2 1,а,0) Р(.1,,) Р(а4 ,,а,0) Р(а,1/а 0,,а,1) Р(а4 ,,) Р(а4 1/а 0,а,,а, 1) Р(,а2.0,) . Итого в блоках памяти хранится 15 значений вероятности вместо 16 (т.е. (N-1) значений вместо N). Значения уже сформированных старших разрядов выходного случайного числа служат адресом выборки из i-ro блока памяти вероятности появления единицы в очередном i-м разряде выходного случайного числа. Таким образом, значительно упрощена система адресации блоков памяти. Рассмотрим функционирование устройства в динамике. Двоичное число с выхода генератора 4 поступает на вторые входы ключей , на первый вход первого из которых (2) поступает код вероятности появления единицы в старшем разряде выходного случайного числаNP(aiM)--s р где PI безусловная вероятность появления 1-го числа на выходе датчика. содержащего в старшем разряде, В результате этого на выходе вероятностного вентиля появляется сигнал либо О,который поступает на установочный вход старшего триггера первого регистра 3.

Ко второму такту информация, хранящаяся в старшем триггере первого регистра 3 , подается на установочный вход старшего триггера второго регистра Ъ и на адресный вход второго блока памяти 1,, что вызывает появление на его выходе кода вероятности появления единицы во втором разряде выходного случайного числа (с учетом условия, что , либо ). Такие вероятности определяются следующими выражениями:

- PCcia- fa.o)- (а,-Ь),

i-N|4+)

P(ai-o)-f-P(a,-i) PCao-H/QiH)-S p IP (a,--/).

i- N|4ti

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

Двоичное одноразрядное число, полученное в результате поразрядного логического перемножения во втором вероятностном ключе 2,когда условна вероятность появления единицы во втором разряде выходного случайного числа и случайного числа с выхода генератора 4, поступает на установочный вход второго триггера, второго регистра Зз..

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

Следовательно, до окончания первых N тактов работы датчика на выходе его отсутствует случайное число, а в регистрах 3 - 3 , хранятся k(j+i)-My такту .частично сформированные случайных числа разрядностью соответстненно от 1 до .

Процесс распространяется по регистрам 3/1 - 3 |ij аналогично до тех пор, пока не будет сформирован младший разряд первого (с момента запуска) выходного случайного числа. Затем после окончания первых N тактов случайные числа поступают на выход устройства на каждом такте, так как старшие (N-1) разрядов формируются параллельно на предыдущих тактах и поступают в N-й регистр, хранения случайного числа 3 из предыдущего {N-1)го регистра, N-й разряд формируется путем поразрядного логического перемножения кода условной верояности появления единицы в младшем разряде выходного случайного числа из блока памяти Ifj и случайного числа, поступающего с выхода генератора 4.

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

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

В последние М (младших) разрядов выходного регистра Зщ могут быть двзаписаны равномерно распределенные числа, формируемые генератором 4, для уменьшения дискретности квантования по аргументу, при воспроизведении случайных величин с непрерывными функциями распределения.

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

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

Структура высокорегулярна, чтодела.ет перспективным выпуск датчика в виде интегральной схемы специального назначения.

Формула изобретения

Датчик случайных чисел, содержащий первый ключ, к первому входу которого подключен выход первого блока памяти, первый регистр хранения случайного числа, включающий N основных триггеров и М дополнительных триггеров, выходы которых являются выходом датчика случайных чисел, генератор равновероятных двоичных чисел, выход которого соединен с вторым входом первого ключа и установочными входами М дополнительных триггеров первого регистра хранения случайного числа, а также генератор тактовых импульсов, выход которого подключен к входу генератора равновероятных двоичных чисел, к третьему входу первого ключа и входу синхронизации первого регистра хранения случайного числа, отличающий с я тем, что, с целью повышения быстродействия датчика, он содержит дополнительные (N-1) регистры хранения случайного числа, разрядность которых возрастает соответственно на один от 1 до {N-1), (N-1). блоков памяти и (N-1) ключей, первые входы которых подключены к выходам соответствующих блоков памяти, вторые входы - к выходу генератора равновероятных двоичных чисел, третьи входы - к выходу генератора тактовых импульсов и ко входам синхронизации регистров хранения случайных чисел соответственно,. а выход каждого из вероятностных вентилей подключен к установочному входу триггера младшего разряда соответствующего регистра хранения случайного числа, выходы разрядных триггеров каждого пре дыдущёго регистра хранения случайного числа, раоположенного в порядке возрастания числа разрядов, подключены к установочным входам старших разрядных триггеров последующего регистра хранения случайного числа и к адресным входам последующего блока памяти.

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

0

1.Авторское свидетельство СССР № 351209, кл.;: G 06 F 7/58, 1970.

2.Авторское свидетельство СССР № 430368, кл. G Об F 7/58, 1972.

3.Авторское свидетельство СССР 5 185569, кл, G 06 F 7/58,1964 (прототип) .