Генератор случайных чисел

 

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

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

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

РЕСПУБЛИК

5(59 6 F 7/58

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

:В

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1) 3348457/18-24 (22) 06. 10.81 (46) 30.03.83. Бюл. № 12 (72) О. И.Далин и И.К.Галеев (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР

¹ 309356, кл. Cj 06 F 7/58, 1968.

2. Авторское свидетельство СССР № 378826, кл. С 06 F 7/58, 1970 (прототип) . (54)(57) ГЕНЕРАТОР СЛУЧАЙНЫХ

ЧИСЕЛ, содержащий генератор равнрмерно распределенных случайных чисел, первая группа выхоцов которого соединена с первой группой входов схемы срав. кения, вторая группа входов которой соединена с группой выхоцов первого блока памяти, а выход схемы сравнения соецинен с вхоцом блока элементов И, группа выходов которого соединена с группой вхоцов регистра памяти, группа выходов которого соединена с первой группой входов дешифратора, вторая группа вхоцов которого объединена с группой

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

1 1008

Изобретение относится к вычислительной технике и h:îæåò быть использовано при статистическом моделировании в щтфровых вычислительных машинах.

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

Недостатком этого генератора явля- !О ется низкая точность формирования закона распределения случайных чисел.

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

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

11ель изобретения - повышение точности формирования одномерного закона распределения случайных чисел за счет не- 30 ревномерного разбиения заданного интегрального закона распределения Г (х) при том же самом количестве интервалов разбиения.

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

737 2 памяти и с второй группой выходов генератора равномерно распределенных случайных чисел соответственно, группа выходов дешифратора соединена с группой входов второго блока памяти, группа выходов которого соединена с группой входов первого блока памяти, а выход второго блока памяти соединен с входом генератора тактовых импульсов и с входом коммутатора, группа выходов которого является группой выходов генератора.

На фиг. 1 приведена блок-схема генератора; на фиг. 2 — схема генератора тактовых импульсов; на фиг. 3 - схема дешифратора; на фиг. 4 — схема комму- татора; на фиг. 5 - диаграмма работы генератора тактовых импульсов; на фиг. 6 ° пример разбиения кривой закона распределения.

Генератор случайных чисел содержит генератор 1 тактовых импульсов, блок 2 элементов И, дешифратор 3, генератор 4 равномерно распределенных случайных чисел, схему 5 сравнения, первый блок 6 памяти, регистр 7 памяти, второй блок 8 памяти, коммутатора 9 и выход 10.

Генератор 1 тактовых импульсов со.держит источник 11 импульсов, элемент

И 12,вход 13 Пуск, вход 14 от блока 8 памяти, выход 15 элемента И 12,счетчик

16, вход 17 Установка дешифратор . 18, выходы 19-22, последний выход 23 дешифратора, элемент .

ИЛИ 24, выход 25 элемента ИЛИ 24, элемент 26 задержки, выход 27 элемента 26 задержки.

Дешифратор 3 содержит элементы

ИПИ 28, элементы И 29, элементы ИЛИ

30-33, входы 34-38 от регистра 7 памяти, выходы 39-43, входы 44-49 от генератора 1 тактовых импульсов.

Коммутатор 9 содержит элементы

И 50, элементы ИЛИ 51-56; вход 57; от второго блока 8 памяти, входы 58-63 от генератора 1 тактовых импульсов, входы 64-69 от регистра 7 памяти, входы 7()-74 от генератора 4 равномерно распределенных случайных чисел, выходы

75 80.

Приндип работы генератора состоит в следующем.

Область возможных значений случайных чисел (0 х с 1) разбивается на за. данное число неравномерных интервалов причем минимальный интервал равен

2 (hl — число разрядов регистра 7 паП) мяти). Алгоритм получения случайных чисел состоит в том, что исходное случайное равномерно распределенное число

008737 . 4

3 1 сравнивается- со значением функпии в

- узлах разбиения. Отыскиваются соседние значения функции распределения (исполь зуя метод логарифмического перебора аргументов функции распределения) j .à asтервал аргумента которого попало случайное число. Если интервал / a(x )

-Ю

-F(st ) j = 2, то выиоииым числом ивляется аргумент функции распределения.

Если интервал g F ()r„,. ) - F (Х;) (ъ 2- (т.е. интервал опрецелйлся за 6 тактов работы генератора), старшие 3 разрядов вйхоцного числа являются старшими разрядами аргумента функции распределения, а младшие разряды выходного числа .3 + 1,...,lA заполняются символами "1" с вероятностью Р =0,5.

Генератоф 1. тактовых импульсов вы.рабатывает серию иэ f0 сигналов, необ- ходимых для формирования rri разрядов . слунайного числа .и может быть выполнен, .например, как показано на фиг. 2.

Временные диаграммы работы представлены на фиг.. 5 .(обоэначение сигналов соответствует нумерации на фиг. 2).

Сигнал по входу 13 разрешения ра боты генератора случайных чисел позволяет прохождение тактовых импульсов or источника 11 импульсов на вход счетчика 16. На выхоцах цешифратора 18 послецоватепьно появляются сигналы, уп равляющие работой генератора случайных чисел. Сигнал с выхода 23 ((N+ 1)-йвыход цешифратора) и сигнал по входу 14 .(от второго блока 8 памяти) устанавливает в начальное состояние счетчик 16.

Блок 2 элементов И представляет со- . бой набор из Ф элементов И, которые в кажцый такт работы генератора случайных чисел подключают выхоц схемы 5 сравнения к соответствующему входу разряца . регистра 7 памяти, .разрешая этим запись в разряд регистра результат сравнения случайного числа, поступающего от генератора случайных чисел, с числом, поступающим из первого блока 6 памяти.

Дешифратор 3 реализует режим логарифмического перебора данных, записанных во втором блоке 8 памяти в зависимости or сформированных старших разря» дов регистра 7 памяти сигналов управления от генератора 1 тактовых импульсов и можетбыть выполнен, например, как показано на фиг. 3.

На выходах 39-43 кажцый такт времени появляется адрес Q и д ° (3pq ин формации, записанной во втором блоке 8 памяти. В первый такт времени формируется андрес 1 0 0 ... О, во второй такт времени.- у; 1 0 ... 0 (гце )< содержание первого, только что сформи».. ровавшегося разряда регистра 7 памяти), в третий такт времени -, ) 1 ... О, и т.д. В такт времени Щ формйруется адрес (,1 еее р, 1е

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

10 Схема 5 сравнения представляет собой. схему сравнения двоичных чисел и формирует сигнал 1, если на ее входах равно- . мерно распределенное случайное число от . датчика 4 случайных чисел будет больше

35 ass равно числа поступающего от нерво-. го запоминающего устройства 6, то есть

P)F(x) °

Первый блок 6 памяти представляет собой запоминающее устройство íà 5 чи20 сел, каждое из которых является координатой интегрального закона распределения

F(x) .

Регистр 7 памяти прецставляет собой набор иэ rn триггеров, в которые запи25 сываетсн информация по сигналам из блока 2 элементов И.

Второй блок 8 памяти: хранит 2 ь. рюряцных чисел. В с -м разряде хранится информация, сигнализирующая окон30 чания формирования случайного числа, т.е, говорящая о том, что равномерно распределенное случайное число F попало в интервал F (х;), Г(х;,<)....В первых (l" — 1) разрядах хранятся адреса ячеек

35 первого блока 6 памяти. Так как 2+WG и то во многих ячейках второго блока 8 памяти хранится одинаковая информация.

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

45 представлена иллюстрация вышесказанного.

Аргумент х представлен в двоичной .форме5 =6,ф4.

F (0011) = F (0100); (0101) - F (0110) - К (0111)= F (10000);

У (1001) = F (1010) = (1011) =

- F (1100) = F (1101) = F (1110).

Коммутатор 9 служит для выдачи на выходы устройства случайного числа но окончании его формирования по сигналам с генератора 1 тактовых импульсов. Т.е. после гй тактов работы генератора 1 тактовых импульсов на выходы устройся

5 10087 ва выдается соцержимое первых 3 разряцов регистра 7 памяти, а на остальные

+ 1,..., l5 выхоцы устройства поцается случайное число с генератора 4 случайных чисел. Одно из возможных технических решений коммутатора 8 прецставлено на фиг. 4.

Генератор работает следующим образом.

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

8 памяти, который в свою очередь, опрашивает первый блок 6 памяти, осущест 20 вляя выбор начения функции распределе ния заданного закона Р(х0,5) прн 04 ха 1. Значение функции распрецеления

F(x=0,5) подается на схему 5 сравнения, гце сравнивается с равномерно рас 25 прецеленным случайным числом $, результат сравнения с помощью блока 2 элементов И записывается в регистр 7 памяти, Если в результате сравнения окажется, что g c F (xW,5), то в первый зо разряд регистра 7 памяти записан символ 0 "» Во второй такт работы генератора 1 тактовых импульсов из nepsoro блока 6 памяти будет выбрано знйче37 6 ние F (х=0,25), т,е. середины интервала

О» х< -0,5. Если окажется, что, Р(х=0,5) то в первый разряц регистра 7 буцет за- . писан символ "1", и в результате этого во второй такт работы генератора 1 актовых импульсов из первого блока 6 памяти будет выбрано значение F (х=0,75) т.е. серецины интервала 0,5& x 1.

Процесс выбора серединных значений соответствующих интервалов по результатам сравнения и с учетом ранее сформированной части числа процолжается цо тех пор, пока исходное случайное число не попадет в интервал по условию Г(х. М

c pc F(xite) о чем покажет сигнал с выхода г -го разряда второго блока 8 памяти. В этот момент времени в регист ре 7 памяти буцет сформировано 6 разрядов случайного числа зацанного закона распределения, остальные 3 + 1, ..., П1 разряды заполняются с вероятностью Р=0,5 символами "1, поступающими из гене ратора 4 случайных чисел с помощью коммутатора 9.

Затем цикл формирования случайного числа повторяется снова.

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

1008737

100973 7

1008737

1008737

И

7f

62

09

1008737

22 фис..У

Fy н

° Ф ch ц % ф 4и Ъ ф ар ф е а в - "- а@ а а

Ф» Cb а а

Ю

ВНИИПИ Заказ 2339/59 Тираж 704, Подписное

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