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

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

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

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

Генератор 1 тактовых импульсов содержит источник 11 импульсов, элемент И 12,вход 13Пуск,вход 14 от блока 8 памяти,выход 15 элемента И 12,счетчик 16, вход 17 Установка деши4 ратор .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 372 памяти и с второй группой выходов генератора равномерно распределенных случайных чисел соответственно, группа выходов дешифратора соединена с группой входов второго блока памяти, группа выходов которог-о соединена с группой входов первого блока памяти, а выход второго блока памяти соединен с входом генератора тактовых импульсов и с входом коммутатора, группа выходов которого является группой выходов генератор)а. На фиг. 1 приведена блок-схема генератора; на фиг. 2 - схема генератора тактовых импулЕгСОв; на фиг. 3 - схема дешифратора; на фиг. 4 - схема коммутатора; на фиг. 5 - диаграмма работы генератора тактовых импульсов; нафиг. 6пример разбиения кривой закона распределешга, , Генератор случайных чисел содержит генератор 1 тактовых импульсов, блок 2 элементов И, дешифратор 3, генератор 4 равномерно распределенных случайных чисел, схему 5 сравнения, первый блок 6 памяти, регистр 7 памяти, второй блок 8 памяти, коммутатора 9 и вых,од 1О. от генератора 1 тактовых импулг сов. входы 64-69 от регистра 7 памяти, входы 70-74 от генератора 4 равномерно распределенных случайных чисел, выходы . Приншш работы генератора состоит в следующем. Область возможных значений случайных чисел (О X i 1) разбивается на заданное число неравномерных интервалов щжчем минимальный интервал равен т ( Т1 - число разрядов регистра 7 памяти). Алгоритм получения случайньос чисел состоит в том, что исходное случайное равномерно распределенное число 31 срввнива€ тся со значением функции в узлах раЬбиения. Отыскиваются соседние значения функции распределения (испояЕхзуя логарифмического nepe6ojpa аргументов функции распределения ) ;в ин тервал аргумента которого попало случайное число. Если интервал / F { х ) -Р(Ч)/ то выходным числом яв- ляется аргумент функции распределения. Бели интервал I Р(ХЧ+) - F(X)/. 2(т.е. интервал определился за & тактов рабозъ генератора), старшие разрядов Еьдходного числа являются старшик)и разрядами аргумента распределения а младшие разряды выходного числа .6 +1,..., (П заполняются символами с вероятносгьюГ Р 0,5, Генерато 1 тактовых импульсов вы.рабатывает серию из ffl сигналов, необ ходимьк. для формирования m разрядов случайного числа .и можетбыть выполнен, , как показано на фиг. 2. Временные диaгpaм vn)I работы представлены на фиг. 5 .(обозначение сигналов соответствует нумерации на фиг. 2). Сигнал по входу 13 разрешения работы генератора случайных чисел позволяет прохождение тактовых импульсов от изт&чника 11 импульсов на вход счетчика 16. На выходах дешифратора 18последовательно появляются сигналы, управляющие работой генератора,случайных чисел. Сигнал с выхода 23 (1ти-1)-й выход детЬифратора} и сигнал по входу 1 .(от второго блока 8 памяти) устанавлива.ет в начальное состояние счетчик 16. Блок 2 элементов И представляет со- бой набор из ТП элементов И, которые в каждый такт работы генератора случайны чисел подключают выход схемы 5 сравнения к соответствующему входу разряда регистра 7 памяти, ршзрёшая этим запис в разряд регистра результат сравнения случайного числа, поступающего от генератора случайных чисел, с числом, поступающим из первого блока 6 памяти. Дешифратор 3 реализует режим логарифмического перебора данных, записанных во втором блоке 8 памяти в з;ависи- мости от сформированных старших разрядов регистра 7 памяти сигналов управления от генератора 1 тактовых импульсов и можетбыть выполнен, например, как показано на фиг. 3. На выходах 39-43 каждьгй такт времени появляется адрес О , а t...OIrn Нформадии, записанной во втором блоке 8 памяти. В первый такт времени формируется адрес 1 О О ...О, во второй . 4 . 37 такт времени - V, 1 О ... О (где J, содержание первого, только что сформи- Ковавшегося разряда регистра 7 памяти), в третий такт времени - у ,„ О, и т.д. В такт времени ГП формируется адрес tj y z-Чтч ,. Генератор случайных чисел преаставпяет собой первичный источник равноме яю распределенньрс случайных чисел Е Схема 5 сравнения представляет собой схему сравнения двоичных чисел и формн- рует сигнал 1, если на ее входах равномерно распределенное случайное число от датчика 4 случайных чисел будет болыце иди равно числа поступающего от первого запоминающего устройства 6, то есть F(JC). Первый блок 6 памяти представляет собой запоминающее устройство на S чисел, каждое из которых является координатой интегрального закона распределения F(x).. Регистр 7 памяти представляет собой . набор из гп триггеров, в которые записываетсн информация по сиг налам, из блока 2 элементов И. Второй блок 8 памяти : хранит разрядных чисел. В -м разряде хранится информация, сигнализирующая окончания формирования случайного числа, т.е. говорящая о TOI, что равномерно распределенное случайное число попало в интервал Р(х;), Г(х,). .В первых (Г - 1) разрядах хранятся адреса ячеек первого блока 6 памяти. Так как то во многих ячейках второго блока 8 памяти хранится одинаковая информаи. Содержимое второго блока 8 памяти вы- бираетсяпо сигналам с выхода дешифра- тора 3, т.е. фактически по аргументу х функции распределения Р(х). Следовательно, на нескольких разшых (не рядом расположенных на числовой оси) аргументах X в первом блоке 6 памяти хранятся одинаковые значения Р (х). На фиг. 6 представлена иллюстрация вышесжазанного Аргумент X представлен в двоичной-форме 5 6, Ш 4. . F (ООН) Р (O1QO); F (Q101) F (оно) F (0111) в Р UOOOO); F (10OJ.) Р (1010) F (1011) Р (1100) F (1101) Р (НЮ). , Коммутатор 9 служит для выдачи на выходы устройства случайного числа по окончании его формирования по сигналам с генератора 1 тактовых импульсов. Т.е. после m тактов работы генератора 1 t тактоеых импульсов на выходы устройст5100ва выдается содержимое первых 2 разрядов регистра 7 памяти, а на остальные I + l...f М выходы устройства подается случайное число с генератора 4 случайных чисел. Одно из возможных технических решений коммутатора 8 представлено йа фиг, 4. Генератор работает следующим образом. Предварительно в первый и второй бло ки памяти заносится информация о законе распределения. По команде Пуск происходит запуск генератора 1 тактовых импульсов, который вырабатътает серию импульсных сигналов. Первый из этих сигналов производит опрос генератора 4 случайных чисел, а также через дешифратор 3 производит опрос второго блока 8 памяти, который в свою очередь, опрашивает первый блок 6 памяти, осущест влдя выбор значения функции распредепе«ния заданного закона К(1РЮ,5) при Ot х4 1. Значение функтаи распределения Р(,5) подается на схему 5 сравнения, где сравнивается с равномерно pac.iпределенным случайным числом , резупьтат сравнения с помошью блока 2 элементов И записывается в регистр 7 памяти. Если в результате сравнения ока яжтся, что F(,5), то в первый разряд регистра 7 памяти записан символ О, Во второй такт работы генератора 1 тактовых икгаульсов иа первого блока б памяти будет выбрано анйче76ние F(,25), т.е. середины интервала ,5. Если окажется, что F(x),5} то в первый разряд регистра 7 будет за- писан символ 1, и в результате этого второй такт работы генератора 1 тектовых импульсов из первого блока 6 памяти будет выбрано значение F (,75) т.е. середины интервала 0,5 х 1, Процесс выбора серединных значений соответствующих интервалов по резупьтатам сравнения и с учетом ранее сформированной части числа продолжается цо тех пор, пока исходное случайное число не попадет в интервал по условию F(x:)i F(x), о чем покажет сигнал с выхода г -го разряда второго блока 8 памяти. В этот момент времени в регистре 7 памяти будет сформировано t разрядов случайного числазаданного закона распределения, остальные 8 + 1,..., m разряды заполняются с вероятностью FM3,5 символами , поступающими из гене ратора 4 случайных чисел с помощью коммутатора 9. Затем цикл формирования случайного числа повторяется снова, Использование новых блоков: второго запоминающего устройства и коммутатора выгодно отличает предлагаемое устройство от прототипа, так как при том же самом количестве интервалов разбиение хгозволяет повысить точность формирования заданного закона распределения.

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

iL

/7

фиг.1

M

Г

У

t.. .

NI

«41

о 5

&

фие.З /У-ГиТП-ГЪ- lJnLrTrLrL.. 0 -1 .

..

.-.

.

fft/f.S rLrLrLn