Генератор случайных чисел с произвольным законом распределения Советский патент 1989 года по МПК G06F9/50 G06F13/32 

СП

О

со

СХ)

ОС

СдЭ

10

15

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

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

На фиг. 1- представлена структурная схема генератора случайных чисел с произвольным законом распределения; на фиг,2 - алгоритм работы блока управления.

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

Принцип работы основан на кусоч- 25 но-полиноминальной аппроксимации за- даннрй интегральной функции распределения. Интервал значений .заданной случайной BenH4viHH разбивается на п подынтервалов различной дли- ЗО ны. Использование неравномерного разбиения интервала Га,Ъ на подынтервалы позволяет дополнительно повысить точность генерирования случайных чиходе датчика 1/равномерно распределенных случайных чисел устанавливается значение , , которое поступает на первый вход схемы 6 сравнения и на информационный вход регистра 2. Одновременно по сигналу Y. на седь- выходе блока 6 управления происходит начальная установка регистра 7 к счетчиков 11 и 12. Далее начинается цикл работы регистров 7 и 10 и счетчиков 11 и 12, Их задача - определение адреса ячейки блока 5 памяти, содержание которой F( ) удовлетворяет уравнению

F(X,-.) « F(X),

Процесс переборки адресов выполняется с первого адреса нулевой страницы блока 5 памяти, которому соответствует центр исходного интервала.

По сигналу УЗ ка четвертом выходе блока б управления происходит обращение к блоку 5 памяти, на его выходе появляется значение, определяемое адресом начальной установки регистра и счетчика 1, которое через блок 3 элементов ИЛИ попадает на р.торой вход схекь 4 сравнения, где сравнивается со значением i|, , Если на первом входе логических условий Xj блока б З Ттравления появляется 1, т.е. РЧ Х ) - q, , осуществляется выход из числа, так как сел при фиксированном количестве под- -,;.

-з-э адрес на выходе регистра / и счетчи- ынтервалов, т.е. при ограниченном

объеме памяти.

Б качестве аппроксимирующего полинома на подынтервале выбран .полином Бернштейна, который имеет вид:

40

ка 1) является искомым. В противном сл учае и если на втором входе логических условий X. блока б управления присутствует , то по сигналу Y на шестом выходе блока б управотения идет подготовка нового адреса в регистре 7. При наличии сигнала О на третьем входе логических условий Х блока б управления цикл работы повторяется. При наличии сигнала 1 на третьем входе логических условий Xj блока б управления на его восьмом выходе формируется сигнал Yg,, поступающий на вход установки адреса регистра 7. После зтого по сигналу Y на пятом выходе блока б управления происходит увеличение старших разрядов адресов на выходе счетчика 11 и по сигналу Y;5 четвертом выходе блока б управления происходит обращение к блоку 5 памяти. На втором входе блока 3 элементов ШШ появляется значение фу1жций в центре интервала,

BjZ) f:F(j/m)c;|,{l-Z)

m-j

где h; - степень полинома;

Cff, - число сочетаний из m по j- F(,3/in) - значение аппроксимирующей функции в узловых точках; Z - переменная, принимающая зна ;чения на интервале 0,1. Генератор работает следующим образом.

До начала работы в блок 5 памяти заносится информация о значении функции распределения на границах интер- валов, и на середине интервала, длина интервала и значения границ интервалов. При появлении сигнала Y на первом выходе блока 6 управления на вы

5

0

5 О

ходе датчика 1/равномерно распределенных случайных чисел устанавливается значение , , которое поступает на первый вход схемы 6 сравнения и на информационный вход регистра 2. Одновременно по сигналу Y. на седь- выходе блока 6 управления происходит начальная установка регистра 7 к счетчиков 11 и 12. Далее начинается цикл работы регистров 7 и 10 и счетчиков 11 и 12, Их задача - определение адреса ячейки блока 5 памяти, содержание которой F( ) удовлетворяет уравнению

F(X,-.) « F(X),

Процесс переборки адресов выполняется с первого адреса нулевой страницы блока 5 памяти, которому соответствует центр исходного интервала.

По сигналу УЗ ка четвертом выходе блока б управления происходит обращение к блоку 5 памяти, на его выходе появляется значение, определяемое адресом начальной установки регистра и счетчика 1, которое через блок 3 элементов ИЛИ попадает на р.торой вход схекь 4 сравнения, где сравнивается со значением i|, , Если на первом входе логических условий Xj блока б З Ттравления появляется 1, т.е. РЧ Х ) - q, , осуадрес на выходе регистра / и счетчи-

ка 1) является искомым. В противном сл учае и если на втором входе логических условий X. блока б управления присутствует , то по сигналу Y на шестом выходе блока б управотения идет подготовка нового адреса в регистре 7. При наличии сигнала О на третьем входе логических условий Х блока б управления цикл работы повторяется. При наличии сигнала 1 на третьем входе логических условий Xj блока б управления на его восьмом выходе формируется сигнал Yg,, поступающий на вход установки адреса регистра 7. После зтого по сигналу Y на пятом выходе блока б управления происходит увеличение старших разрядов адресов на выходе счетчика 11 и по сигналу Y;5 четвертом выходе блока б управления происходит обращение к блоку 5 памяти. На втором входе блока 3 элементов ШШ появляется значение фу1жций в центре интервала,

5

соответствующего адресу на выходе регистра 7 и счетчика 11. Это значение сравнивается с величиной i в схеме 4 сравнения. Появление I на выходе Больше схемы 4 сравнения означает, что слу-гайная величина находится в левой половине подынтервала, появление О - з правой. По сигналу Y,f на левом выходе блока б управления на выхода датчика 1 равномерно распределенных: случайньгк чисел появляется значение , которое поступает на ин -орма дионный вход регистра 2. По сигналу Yg на втором выходе блока б упра:,(0 ия значение записывается в регистр 2, Снова по сигналу Y, с перв.-лтчэ выхода блока 5 ут:равления на выходе датчик-а I равномерно par птJeдeлeк ыx случайных чисел попв.лкетс.я числе .-j i nocTViiasc- пдее на первый вход схемы 4 cpaBHeHHSi по сигналу YQ с третьег о выхода блока 6 управления число S , с выхода регистра. 2 Crepes блок 3 элементов ИЛИ поступает на второй вход

4сравнения.. Далее в зависимости от нахождения случайггого числа ( в левом или п равом подыктервалеJ. т. е„ от состоянкя на втором ких услов лй Xj блов:а б т1равления, выбирается мвг ынее или большее со- ответстБенно из двух чисел и , , п.олученмое число- запомнится в регистр 2.

Далее по сигналу Y., на пятом выходе блока 6 управления происходит увеличение старшего разряда адреса ка выходе счетчика 1, по сигналу Y, на четвертом выходе блока 6 управления происходит обращение к блоку 5 памяти, в результате мношгмое из блока 5 памяти появляется на соответствующем входе блока 8 умножения, а множитель поступает из регистра 2 по сигналу YP на третьем выходе блока б управления. Занесение множимого и множителя в блок 8 умножения происходит по сигналу Y,j на десятом выходе блока 6 управления, а операция умножения по сигналу Y на одиннадцатом выходе блока б управления. Снова происходит увеличение старшего раз ряда адреса на выходе счетчика 11 и по соответствующим сигналам блока 6 управления обращение к блоку 5 памяти в результате одно слагаемое из блока

5памяти, а другое из блока 8 умножения поступают на вход сумматора 9. .

098836

По си1 налу Y,2 на двенадидтом выходе блока 6 управления происходит суммирование и на выходе генератора появляется первое слу .айное число X, При генерированной массива случайнь г чисел весь процесс повторяется..

В счетчик 12 по сигналу Y запи- , сывается колтгчество подынтервалов,

jQ его содержимое у еньгаается на единицу сигналом YJ на девятом выходе блока 6 упрявлекия. Состоягше счет- чгжа 12 определяет состояние на третьем выходе логт .ческих условий

15 Xj блока 6 управления. Регистр iO хранит предыдущее состояние регистра 7, с помощь регистра 10 формируется новое состояние ре гистра 7, т.е. новое состояние адресных вхо20 дов блока 5 памяти.

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

Генератор сл айных чисел с про- 25 HSBOJfbi-ibuM saTcoHOM распре/.еления, со- де.ркащ1-гй датчик равномерно распределенных: случайных чисел, блок памяти, схему сравмерлгя, причем выход датчика равномерно распределенньк чисе.п соеди- 30 f-sii i-- iiepBttti входом схемы сравнения, о л ч а га и; и и с i тем, что, с целью повышения точности формирования случайных , в него введены блок ртравлекия, три регистра,

два счетчика, блок элементов ПИИ,- j5

олок ум южения и с тчматор, причем

вход опроса датчика равномерно распределенных спз 1глгштх чисел соединен с первым выходом блока з правлеAQ НИН, И1-1сЪормационгемй вход первого регистра соединен с выходом датчика равномерно распределенных случайных чисел, вход записи и вход разрешения первого регистра соединены с втодд рым и третьим выходами блока управ- . ления соответственно, выход первого регистра соединен с входом множителя блока умножения и с первьЕМ входом блока элементов ИЛИ, второй вход

50 которого соединен с выходом блока

памяти, с входом множимого блока умножения и с первым информационньпч вхо-г дом сумматора, выход блока элементов VUTK соединен с вторым информационным

гг входом схемы сравнения, выход Рав- но которой соединен с первым входом лоп-сческих условий блока управления, второй в:ход логических условий которого соедин(:Н с входом запрета приема

кода второго регистра и с выходом Болъгае схемы сравнения, третий вход логических условий блока управления соединен с выходом первого счетчика, четвертый выход блока управления соединен с входом чтения блока памяти, адресные входы которого соединены с выходами второго регистра и третьего счетчика, пятый выход блока управления соединен с тактовым входом - третьего счетчика, вход разрешения третьего регистра соединен с шестым выходом блока управлеьюя, седьмой выход которого соединен с входами на- чальной установки второго регистра, первого и второго счетчиков, вход разрешения второго регистра соединен с восьмым выходом блока управления.

HavaAJj

LiJ

ys

Уз

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

С Конец J

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