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

Изобретение чтю итст t ггчно Мтель- ои техчики и Пить L t o .O при решонии ,здпч стагистич (от но т (;о

Р }(,1Я

Цель изоОрек ния раплирес ш ;,,IK цмона 1 з(|Ых DOCMPYiicc 1гй та CMi1 ой iu

Г Н раЦПИ 1ИГР СО ГМеИ1,}ННЫГ/И

Элтонами .РДРПОНИЛ. п()рдс1ярнг чми о

PN(X) -f I -re ;К,:х) ( Г Р,(л) (t) ГЦеГ(;) Ф/НКЦ1 1 рТСПрРДСМ Ш 1 rrprjii Р-ЫХОДНОГО rnv ITIHOi )

ш 1 rf чератор i () J-yifunq рагпрсдр if i i 1 нпо

кого сг ju - O i иг нала

Г(/1 ф И I,,, I jj jullpf /if, ДОПОЛ- 1- ИТОТс-1 1Г I lOl TTO S

t п ри и о гиги i i i

7 - тпьм i, з(.-.егр еричующии гопен. ,5Рr,ji3i с НОРНОГО

Г1Ч id/ir4 /I)

I н чг по -э Tirj г i.jyT ; rxi-ча

ГРНСРГПО 1 1 Г Г ПИННХЧИГ r

Опэ год Пжит гснерсзтин i-fr r,ii им и.льсоч i г- и ьюрои j K,TX -ч- лнг°ль ir CtOTt л первый счетчик Ь /| г зрпую схему сраиирния / ,niiTiiiK р вномерн 4 гтС федг

...j

iO.

ос

-|

4s|

о

О,

ленных случайных чисел 8, триггер 9, второй счетмик 10, регистр 11, блок синхронизации 12, элемент ИЛИ 13, элемент задержки 14, формирователь импульсов 15, К групп элементов Л 16, коммутатор 17, первую 18 и вторую 19 группы элементов ИЛИ, второй датчик равномерно распределенных случайных чисел 20, вторую схему сравнения 21, первую 22 и вторую 23 дополнительные группы элементов И, выход генератора 24.

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

Предварительно на первой группе выходов блока синхронизации 12 устанавливается код, соответствующий параметру а ; на двух выходах третьей группы выходов этого блока (например, нз -м и j-м, i , j - 1, К, lipj) появляются единичные сигналы, указы- пающие смесь каких распределений из общего числа К возможных распределений будет формироваться; на одном из 1-го и j-ro выходов, например на i-м, появляется единичный сигнал, указывающий какое из распределений (в данном случае 1-е) является основным распределением FX|(x), а какое (в данном случае j-e) является засоряющим распределением FXj(x).

Формирование случайных чисел, подчиняющихся любому из К возможных функций распределения вероятностей, осуществляется с помощью одного и того же метода, основанного на преобразовании равномерно распределенных случайных чисел Z в случайные числа с заданным интегральным законом распределения вероятностей FX|(x); I в соответствии с формулой

Fxi(xn) Zn.(2)

Числа с заданным законом распределения образуются на разрядных выходах счетчика 5. Принцип реализации преобразования (2) базируется на вариации частоты импульсов на входе счетчика 5. При этом воспроизводимая нелинейная зависимость аппроксимируется кусочно-линейной функцией, а каждый линейный участок - кусочно-ступенчатой функцией. Делитель частоты 4 с переменным коэффициентом деления обеспечивает необходимую частоту для каждого участка ломаной линии. Значения, получаемые на выходе счетчика 5. сравниваются схемой сравнения 7 со значением случайного числа Zn на выходе датчика 8. В момент их равенства в счетчика 10 оказывается записанным число Хп с заданным законом распределения вероятностей. Требуемые функции распределения задаются соответствующим соединением полного дешифратора 6, элементов И, входящих в одну из К групп элементов И 16 и управляющих выбором одного из К возможных распределений, коммутатора 17, первой группы элементов ИЛИ 18. Настройка генератора на формиро- вание определенныЈ законов распределения FX|(x); I - 1, К осуществляется

коммутатором 17, куда по управляющему входу, являющемуся входом задания коэффициентов линейной аппроксимации

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

При начальном запуске генератора по5 дается запускающий сигнал Пуск, открывающий ключ 2, и сигнал Сброс, устанавливающий в исходное (нулевое) состояние делитель частоты 4, первый счетчик 5, регистр 11 и - через элемент ИЛИ 13 0 второй счетчик 10 и триггер 9 (в единичное состояние). Кроме того, осуществляется первоначальный запуск первого 8 и второго 20 датчиков равномерно распределенных случайных чисел (цепи первоначального за5 пуска не показаны).

Случайное число Y, образовавшееся на

выходе второго датчика 20, сравнивается со

значением параметра а. Если Y а, то на

.выходе второй схемы сравнения 21 появля0 ется сигнал, который открывает 1-й элемент И первой дополнительной группы 22; в результате единичный сигнал появляется на выходе 1-го элемента ИЛИ второй группы 19, который подается на вторые входы эле5 ментов И i-й группы 16. Тем самым схема подготавливается к генерации очередного случайного числа, с функцией распределения FXI(X), являющейся основной в смешанном распределении (1), Если же а, то сигнал на выходе схемы сравнения 21 не появляется и поэтому по своему первому инверсному входу открывается j-й элемент И второй дополнительной группы 23; в результате единичный сигнал возникает на выходе j-ro элемента ИЛИ второй группы 19, который подается на вторые входы элементов И j-й группы 16. Тем самым схема подготавливается к генерации очередного случайного числа с функцией распределения Fxj(x), являющейся засоряющей в смешанном распределении (1). В обоих случаях формирование очередного случайного числа осуществляется аналогичным образом.

Импульсы с генератора тактовых импульсов 1 через открытые ключи 2 и 3 поступают на делитель частоты 4 и второй счетчик 10, Выходные импульсы делителя частоты 4 начинают поступать на вход

0 Y

5

0

первого счетчика 5. По цепи обратной спязи через дешифратор 6, включенную группу (1-ю или j-ю) элементов И 16, коммутатор 17 и элементы ИЛИ первой группы 18 производится управление коэффициентом деления делителя частоты 4, обеспечивающим необходимую частоту для каждого участка аппроксимированной зависимости. В момент времени, когда число на разрядных пы- ходах счетчика 5 станопится равным случайному числу на выходе первого датчика 8 равномерно распределенных случайных чисел, с выхода первой схемы сравнения поступает импульс, перебрасывающий триггер 9 в нулевое состояние. В результате закрывается ключ 3; число, оказавшееся в этот момент записанным во втором счетчике 10, является искомым числом хп и фиксируется о нем. После переполнения первого счетчика 5 сигнал с выхода переполнения осуществляет очередной запуск второго счетчика 20 и поступает на вход формирователя импульсов 15. Выходной импульс с формирователя 15 переписывает число с выходов второго счетчика 10 в регистр 11. В результате полученное число хп поступает на выход (енератора 24. Одновременно импульс выхода формирователя 15, задержанный элементом задержки 14 на время установки числа в регистре 11, осуществляет очередной запуск первого датчика 8;одновременно ом проходит через элемент ИЛИ 13 производя сброс второго счетчика 10 в нулевое состояние и перевод триггера 9 в единичное состояние. В результате начинается формирование очередного случайного числа. Поскольку с вероятностью о. каждое генерируемое случайное число подчиняется функции распределения FX), (

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

Формула изобретения Генератор случайных чисел, содержащий генератор тактовых импульсов, первый и второй ключи, делитель частоты, первый и второй счетчики, регистр, первую группу элементов ИЛИ, коммутатор, первый датчик равномерно распределенных случайных чисел, первую схему сравнения, дешифратор, элемент задержки элемент ИЛИ, формирователь импульсов, триггер, К групп элементов И (К - число задаваемых законов распределения вероятностей 5Л01 МИПЧЦИИ РЫ- чод р нРрагора г.чкн.иш-. нчпу/. соеди- ноч г информационным чхо,)м . управляющий ,j югоэого соод л- НРН со в.одо№ Пуск ге чч 4 ор-j, Р пы од - со счетным входом де/нчечм и с информационным аховом D jputo ,

уПраГ ЛЯЮЩПЙ ВХОД КОТОрОГО С.ЦИ -ЧЗн Г.

единичным выходом триггера, едини шый

0 вход которою соединен с установочным входом первого счетчика и подключен к выходу элемента ИЛИ, выход второго ключа соединен со счетным входом первого счетчика, разрядные вычоды котооо с соедине5 ны с ииформациог 1 ми входами разрядов регистра разрядник выходы которо с являются выходом генератора, элементов И каждой j-й группы у 1, К) соединены с J-й группой информационных входов ком0 мутатора, управпяющий вход которого является входом задания коэффициентов линейной аппроксимации интегральной функции распределения вероятностей, каждая j-ая ipynna выходов коммутатора

5 соединена с входами j го элемента ИЛИ первой группы выходы элементов ИЛИ первой группы соединены с разрядными входами делителя частоты выход которого соединен со счетным входом глорого счет0 чика, выход переполнения которого соединен с входом формирования импульсов, выход которого соединен с син,ронизиру- ющим входом регистра и входом элемента задержки, выход которого соединен с вто5 рым входом элемента ИЛИ и со входом запуска перпого датчика равномерно распределенных случайных чисел, разрядные выходы которого соединены с первой труппой входов схемы сравнения, вторая

0 группа входов которой соединена с разрядными выходами второго счетчика и с входами дешифратора, выходы которого соединены с перовыми входами элементов И j-й группы 0 1, К), выход Равно схемы

5 сравнения соединен с нулевым входом триггера, вход Сброс генератора соединен со входами начальной установки делителя частоты, регистра второго счетчика и вторым входом элемен га ИЛИ о i л и ч а ю0 щ и и с я тем, чю, с целпю расширения функциональных оозмо- ностеи за счет обеспечения генерации чисел со смешанными распределениями вероя ностей в него введены второй датчик равномерно

5 распределенных случайных чисел вторая схема сравнения, вторая группа из К элементов ИЛИ и две дополнительные группы из К элементов И, выходы каждого j-ro элемента которых (j - 1. К) соединены со входами- -го элемента ИЛИ второй труппы, а выходы этого элемента ИЛИ - со вторыми входами элементов И J-й группы, вход запуска второго датчика равномерно распределенных случайных чисел соединен с выходом переполнения второго счетчика, а разрядные выходы второго датчика - с первым разрядным входом второй схемы сравнения, второй разрядный вход которой соединен с первой группой выходов блока синхронизации, а выход - с первыми прямыми входами элементов И первой дополнительной группы и первыми инверсными

входами элементов И второй дополнитель- нной группы, j-й выход (J ) второй группы выходов блока синхронизации соединен со вторым прямым входом j-ro элемента И первой дополнительной группы и вторым инверсным входом J-ro элемента И второй дополнительной группы, J-й выходО fTK)третьей группы выходов блока синхронизации соединен с третьим прямым входом J-ro элемента И первой дополнительной группы и первым прямым входом J-ro элемента И второй дополнительной группы.