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

 

О П И С А Н И Е,,1ц 552629

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 24.12.75 (21) 2308547/24 с присоединением заявки № (23) Приоритет

Опубликовано 30.03.77. Бюллетень № 12

Дата опубликования описания 15.04.77 (51) М. Кл. G 07С 15/00

G 06F 1/02

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.3(088.8) (72) Авторы изобретения

В. Ф. Герасимов и А. Н. Гаркуша (71) Заявитель

Московский ордена Трудового Красного Знамени инженернофизический институт (54) ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ

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

Известны датчики случайных чисел.

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

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

Недостатком этого датчика является его аппаратурная избыточность.

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

«Сброс» счетчика подсоединен к выходу элемента ИЛИ, а разрядные выходы — к первым входам группы элементов И соответственно, выходы которых являются выходами датчика и подключены к входам элемента ИЛИ.

Однако такой датчик не обеспечивает высокой точности формирования случайных чисел.

Цель изобретения — повышение точности формирования случайных чисел.

5 Для этого в датчик дополнительно введены циклический регистр сдвига, делитель частоты, первый и второй элементы И и триггер, нулевой вход которого соединен с выходом генератора случайных импульсов, а выходы—

)О с первыми входами первого„и второго элемепгоп И соответственно, вторые входы этих элементов И связаны с выходами циклического регистра сдвига и делителя частоты соответственно, входы которых подключены к выхо15 ду генератора тактовых импульсов, выход первого элемента И подключен к счетному входу счетчика, выход второго элемента И— к единичному входу триггера и к вторым входам группы элементов И.

20 Блок-схема датчика приведена на чертеже.

Датчик содержит циклический регистр 1 сдвига, вход которого соединен с выходом генератора 2 тактовых импульсов и с входом делителя 3 частоты. Выход циклического ре25 гистра 1 сдвига подключен к входу первого элемента И 4, выход делителя 3 частоты — к входу второго элемента И 5. Выход элемента

И 4 соединен со счетным входом счетчика 6.

Вторые входы элементов И 4 и 5 подключены

30 к выходам триггера 7, нулевой вход которого

552629

15

65 соединен с выходом генератора 8 случайных импульсов, а единичный — с выходом элемента И 5. Разрядные выходы счетчика 6 подключены к первым входам группы элементов

И 9, вторые входы которых соединены с выходом элемента И 5, а выходы являются выходами датчика и связаны с входами элемента

ИЛИ 10, выходом соединенного с входом

«Сброс» счетчика б.

Работает датчик следующим образом.

В циклический регистр 1 сдвига заносится вся информация о законе распределения в виде двоичного числа. Число единиц в нем равно числу интервалов дискретности, а число нулей между единицами пропорционально значениям вероятностей соответствующих узловых точек ступенчатой аппроксимации настраиваемого закона распределения. При этом оощее число разрядов в регистре принимается за 1. Содержимое циклического сдвигового регистра 1 периодически сдвигается на один разряд в направлении от единицы, обозначающей конечную узловую точку к начальной импульсами стабильной частоты генератора 2 тактовых импульсов, которые одновременно поступают на делитель 3 частоты, пропускающий каждый N-й импульс. Импульсы с выхода регистра 1 попадают на счетчик 6, предварительно пройдя через элемент И 4, открытый по второму входу потенциальным сигналом с единичного выхода триггера 7, на нулевой вход которого потупают случайные импульсы пуассоновского потока с выхода генератора 8, таким образом, что хотя бы один импульс появляется в течение времени, равного периоду следования импульсов генератора 2, с вероятностью, равной обратной величине числа разрядов регистра 1. Как только на нулевой вход триггера 7 поступает случайный сигнал, элемент И 4 закрывается, а элемент И 5 открывается. Код в регистре 1 сдвигается, а код в счетчике б сохраняется до тех пор, пока импульс с выхода делителя 3 частоты, пройдя элемент И 5, не выдаст его в выходной канал через группу элементов И 9ь 9>,..., 9>. При этом выходной импульс элемента ИЛИ 10 устанавливает счетчик 6 в нуль. К этому времени импульс с выхода элемента И 5 уже переводит в единичное состояние триггер 7, который этим самым открывает элемент И 4 для импульсов с выхода циклического сдвигового регистра для прохождения в счетчик б, после чего процесс генерирования случайного числа начинается вновь. Примерно в 36 случаях из 100 случайных импульсов не проходит на нулевой вход триггера 7 с выхода генератора 8 в течение цикла обращения кода в циклическом сдвиговом регистре. Тогда элемент

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

Разрядность кодов формируемых случайных чисел, точность воспроизведения произвольного закона распределения, а также число настраиваемых законов распределения зависят от числа разрядов циклического сдвигового регистра 1. Для нормальной ее работы необходимо удовлетворить лишь одно условие: — л е =1 — —.

Р 1V

Такой датчик при небольших изменениях может работать и в режиме датчика случайных интервалов. Для этого достаточно между выходом источника случайных сигналов и нулевым входом триггера подключить еще один элемент И, на второй вход которого подается единичный выход еще одного дополнительного триггера, а на нулевой вход последнего— ответвление с выхода элемента ИЛИ 10. Входом датчика или шиной опроса служит единичный вход дополнительного триггера. На основе этой схемы также можно построить широкий класс генераторов случайных процессов несмотря на то, что моменты появления случайных чисел в выходном канале случайны. В большинстве практических случаев ошибка, возникающая вследствие этого, компенсируется простотой и дешевизной конструкции.

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

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

Датчик случайных чисел, содержащий генератор тактовых импульсов, генератор случайных импульсов, счетчик, вход «Сброс» которого подключен к выходу элемента ИЛИ, а разрядные выходы — к первым входам группы элементов И соответственно, выходы которых являются выходами датчика и подключены к входам элемента ИЛИ, отличающийс я тем, что, с целью повышения точности формирования случайных чисел, датчик дополни552629

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

Редактор И, Грузова Техред А. Камышникова Корректор А. Степанова

Заказ 756/14 Изд. ¹ 333 Тираж 769 Подписное

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

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

Типография, пр. Сапунова, 2 тельно содержит циклический регистр сдвига, делитель частоты, первый и второй элементы

И и триггер, нулевой вход которого соединен с выходом генератора случайных импульсов, а выходы — с первыми входами первого и второго элементов И соответственно, вторые входы которых соединены с выходами циклического регистра сдвига и делителя частоты соответственно, входы которых подключены к выходу генератора тактовых импульсов, выход первого элемента И соединен со счетным

5 входом счетчика, выход второго элемента И подключен к единичному входу триггера и к вторым входам группы элементов И.