Управляемый генератор случайных чисел

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик н>960812 (61) Дополнительное к авт. свид-ву (22) Заявлено Об. 03. 81 (21) 3253046/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 230982. Бюллетень ¹ 35

Дата опубликования описания 23.09.82 (51) М. Кл.з

G Об F 7/58

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

СССР по делам изобретений и открытий

153) УДК 88 .325 (088.8) (72) Авторы изобретения

В.М.Тарасов и В.М.Трусфус (71) Заявитель

Казанский ордена Трудового Красного Знамени авиационный институт им.A.Н.Туполева (54) УПРАВЛЯЕМЫЙ ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

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

Однако устройство имеет высоY ую еложн о ть, Известен также генератор, содержащий генератор равномерно распределенных случайных чисел, схему срав20

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

Недостатком устройства является низкое быстродействие, так как

m-разрядное случайное число форми-. руется за (m+1) такт.

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

960с>1 2 с заданным законом распределения применяется функциональное преобразование, основанное на кусочно-линейной аппроксимации заданного распределения Р (х) Г 3 1.

Однако известный гене >атор имеет низкую точность, .-!оскольку обBBсть возмож1!Ых значений аргумента х ра=биваетс я н а и рави:>1!x иH т-ipçàëîB .

Целью изобретения является говы- 10 шение точности всспроиз Ведения р спределения F (X) за счет pa!IáèåíèB области зна:ений аргуме;!та х ча неравных интервалов.

Поставле1:ная цель дост-iiается тем,! ; что в управляемый генератор случайных чисел, содержащий генератор тактовы)с импульсов, блок памяти, гервый дешифратор„ г!ервый регистр памяти, выход которого через первый дешифратор соединен с первым !ходом бло с) ка памяти, блок сравнения, первый и второй блоки элементов И, генератОр равномерно расгределенных чисел, группа выходов которого соединена с соответствующим? входами первой группы блэка сравнения, выход второГ.) блока элементов И является выхо— дом генер;тора, введены второй и третий ре!истры памяти, блок анализ, кодов, счетчик, второй дешифратор и элемент ИЛИ, причем первый и второй входы Пуск, а.также первый и второй входы задания режима

С "HÅPà TOI)c) TàÊ TОВЫХ ИМПУЛЬСОВ Сое-динены с первым и вторым входами З5

ГЕ!."--PcITOPa. и-ЫМ (П вЂ” ЧИСЛО ВЫХО,цов вто о О де!1!Ифратора} Выходом второго дешифратора и первым выходом бл">;.а анализа кодов соответственно, !

ep:» iIé выход генератора тактовых 4О импульсоэ подключен к первому входу счетчика и к первому входу второго бло<а элементов H, "-торой и третий входы которого соединены с выходом третьего регис,p пам !TH H выходом генер;.Тор=-.. р=. -.Померно распределенных случай!?:=;X чисе:-. ОоотBeTOTBCHHQ c B TOPO B ХОП ЯН ЕГатОРа так ТС)

РЫХ ИМПУЛЬСОР СОЕДЧ!1 Н ПС .РвсЛМИ ВХО— ,;ами первого >и зтOp„-Го р::-!строэ памяти, блска :-.ам. т и б.-ока а1-:.Пиза

КО>!Оэz ПЕРВЫЙ ВЫХОД ОЛОКа ПРМ ТИ ПОД— ключен к второму Входу вт-ооогс рег IcTра памяти„ Выходы !=! 1:ci«BTIi, б третий вхоц которого соединен с: Рта

Рым выхсДом б ло. a aHc!r:"!=-a кодов,. вто1 ой и трет?;й входы кс:тсpo»0 Iio - .>! л -! ч "1 K т )з е т ь см" ы ?с ОД у блока и ам;-;— ти и э1>ходу блока ср"-BHс ния соответ-" стэенHQ четвертый .-..;.)сс г генератор,. тактовых >1.:I ?!.I,c. н соединен с нходоM Гpнс)pатoра разномерно гасп0 =.

?IFë0H HI Ix слу !ай нюх чисел, группа выходов котс рогo i.одк)!юче:.а к соответстьующим входам первой группы первого блока элементов И, Bx0>„-ы второй гругr!h; котор;=0 соединeH j с сООтВетствующими выходами ьторого дешифратс— а Выходы !!- )ОВОГО бло с!а элемеч тов

H co rrHHeHHI c групгой входов элемента ИЛИ соответстнен О в од которого соединен с выходом блока -, равнения, а выход э:-емента. ИЛИ с.)ед «jeH " перзым входом третьегс- рег::; тра 1!амяти, второй вход которого сс .динен с:1ятым эыходсм -.ене=атора ак.-свых и1«пульсов, ше-тсй и седьмой B-сходы которого подключены к второму входу счетчика и входу B-,орогс де.1!1фрас-ора соответственн, чеTB. =.pTûé вход

-первс:ГО регистра памяти соединен

П-ЫМ ВЫХОДОМ НтОРОГО ДЕШИфс)атОРа,.

1 РУПIIа ВХсЗДОР КОТОРОГО ПОДКЛЮЧЕНа !<

Э Ь! Х Од аМ С -I E".T "Õ È Ê cj ": О О Т В Е Т С Т !3 Е и Н О „

КРОМЕ ТОГО бдок аиаЛИЗ ci КОДОВ содержит четыре группы элем !TQB И. элемент ИЛИ, элемен: ИЕ :.. два реГИСтРа ПаМЯТИ, ПCQВЫЕ ВХС>ДЫ !сОТОРЫХ

06Рс 3 ßt пеРВый ВХОД блс)ка,. В TQPÎ!-1

ВХОД KOTCPQI Ci СО Д?I. BН B,".:.. М! ВХОдами регис Г? Ов памят и, зь. хо," зле!". ентов И первой гр ппы соед?:.- :. с пе„-ВЫМ ВХОДОМ Э;:-:М-. - та ИЛ.", ".ЫХОд Э.rBВЬIМ ВЫХОДОМ б) О!Са, Rr>XOE(!c ЭЛЕ,:c--1 ТOB

И третьей и чет!з, ;-..=, -.,",;: -,,и;еНЫ СООтВЕтСтВЕННО С. - тс .",Ы;-.-; )! Т РЕ ЬИМ входами элемента . !.:!. Выхо,.:, которо:— го является вторьтч выходом б ê, первый выход перзогс рег:.Стрса гам -".: соединен с первыми входами :-.лэмен-. тов И первой и третьей груп;., в .ОРОй ВЫХОД ПЕРВОГО РЕГИСТPci Памэти соединен с первыми входам!- элементов И второй и четвертой групп, перВый ВыхОд ВтОрОГО р1гистp. I.амяIи

СОЕДИНЕН С ВТСрнс1И Входа 1И Э.).=.=-1тов И первой и в;орой групп„ этсрой выход з-Qpoãñ Ое. Hcто:- -а:-. -!т соеди>1ен с вторыми Exода! ;:> э е! IRH тов И -ipñ :1-.0!й Iи гетвертсй групп, тр )т. :.и Вход блока соединен с уретьим. .1 13ходам?! злее >ен тон И в эрой и 1pе " тьей руп: и с >И!одом элемент!а и . ., выход которогî -.Оединен с трет =-м

"-ходам элемс=нта И четвертой Грулпы.

На фиг.3 .Приведена структурная с!? .. .==..Ма ">гравляемого генератора. сл,-1айных н я схем блока ана. IHB!.; а, . г, функ иональная схем:-. генератор. :-,стовых импульссз;.:-.а фи!.. 4 — —.с.:

Hb>cc ДнаFPcc!.ММЫ РаботЫ УГРВВЛЯЕ::10>" 3

l "i нератора случайных > ис . -, H:j 11Г . з

c0! Но .инейна: а-: Ipo и1!а ... да!. «Огс) рас предел H ив,, >с 1

960812

Управляемый генератор содержит первый регистр 1 памяти, первый дешифратор 2, блок 3 памяти, генератор 4 тактовых импульсов, второй регистр

5 памяти, блок б сравнения, блок 7 анализа кодов, генератор 8 равномерно распределенных случайных чисел, первый блок 9 элементов И, элемент

ИЛИ 10, счетчик 11, второй дешифратор 12, третий регистр 13, второй блок 14 элементов И, входы 15 и 16 генератора и .выход 1.7 генератора.

Выход первого регистра 1 через первый дешифратор 2 соединен с первым входом блока 3 памяти, первый, второй и третий выходы которого подключены к первым входам регистров 5 и 1 блока 7 анализа соответственно.

Первый, второй, третий и четвертый входы генератора 4 тактовых импульсов подключены к первому 15 и второму 16 входам устройства, последнему выходу второго дешифратора 12 и к второму выходу блока 7 анализа соответственно. Первый выход генератора 4 тактовых импульсов соединен 25 с первым входом счетчика 11 и с тре- . тьим входом второго блока 14 элементов И., первый и второй входы блока 14 подключены к выходу регистра 13 и к второму выходу генератора

8 равномерно распределенных случайных чисел соответственно, а выход блока 14 соединен,с выходом 17 устройства.

Второй выход генератора 4 такто- 35 вых импульсов соединен с вторыми входами регистров 1 и 5, блока 3 памяти и блока.7 анализа, первый выход блока 7 анализа подключен к четвертому входу регистра 1. Третий вы- 49 ход генератора 4 подключен к третьему входу блока б сравнения, первая и вторая группы входов которого соединены соответственно с первой группой выходов генератора 8, с выходами ре- 45 гистра 5, а выход блока б оравнения подключен к третьему входу блока 7 анализа и к первому входу элемента

ИЛИ 10. Четвертый выход генератора

4 тактовых импульсов подключен к 50 входу генератора 8 равномерно распределенных случайных чисел, первая группа выходов которого соединена с с первой группой входов блока 9 элементов И, вторая грУппа входов блока 9 подключена к выходам дешифрато ра 12, а выходы блока 9 соединены с второй группой входов элемента ИЛИ 10, Выход элемента ИЛИ 10 соединен с первым входом регистра 13, второй вход которого подключен к седьмому выходу генератора 4 тактовых импульсов, а пятый и шестой выходы генератора 4 соединены с вторыми входами счетчика ll и дешифратора 1? соответственно

Третий вход регистра 1 подключен к последнему выходу дешифратора 12, входы которого соединены с выходами счетчика 11.

Блок 7 анализа (фиг.2) содержит двухзарядный регистр 18 памяти, блок

19 элементов И, элемент НЕ 20, элемент ИЛИ 21, входы 22-24 и выходы

26 и 25, причем первая и вторая группы входов регистра 18 соединены соответственно с входами 22 и 23 бло. ка 7 анализа, а выход 24 блока 7. подключен к третьему входу элементов И 19 и 19 и к входу элемента

НЕ 20, выход которого соединен с третьим входом элемента И 19А, первый выход первого разряда регистра

18 подключен к первым входам элементов И 19 и 199, а второй выход первого разряда регистра 18 соединен с первыми входами элементов И 19 и

194, первый выход второго разряда регистра 18 соединен с вторыми входами элементов И 19> и 194, а второй выход второго разряда регистра 18 подключен к вторым входам элементов И 19. и 19,, выход элемента И 1 соединен с первым выходом 25 блока 7 анализа, а выходы элементов

И 19,, 19 и 19 через элемент ИЛИ

21 подключены к второму выходу 26 блока 7 анализа.

Генератор 4 тактовых импульсов (фиг.З) содержит элементы И 27 и ИЛИ 28, триггеры 29, генератор 30 импульсов, триггер 31, элемент НЕ

32, блок 3.3 элементов И, входы 1516, 34 и 35 и группу выходов 36, причем первый и второй входы генератора 30 импульсов соединены с первым

15 и вторым 16 входами устройства соответственно, а первый выход генератора 30 импульсов подключен к вто.рым входам элементов И 33, 33, 334 и 33, вторые входы элементов

И 33 и 336, седьмой выход 36 генератора 4 тактовых импульсов, вто рой и третий входы триггера 29 и второй вход триггера 31 соединены с вторым выходом генератора 30 импульсов, третий 34 и четвертый 35 входы генератора 4 соединены соответственно с первым и третьим входами триггера 31, а также с первыми входами элементов ИЛИ 28 и И 27 соответственно, первый выход триггера 31 подключен к третьему входу элемента И 33 к первым входам элементов И 33 и 33 и к второму входу элемента И 27, выход которого соединен с вторым входом элемента ИЛИ

28, а выход элемента ИЛИ 28 подключен к первому входу триггера 29, второй выход триггера 31 подключен к первому входу элемента И 33,, а первые входы элементов И 33„ и

33 соединены с выходом триггера

29, выход элемента И 33 через эле960812 мент НЕ 32 подключен к первому входу элемента, И 33-, выходы блока 33 элементов И гоедииеиы с соответствующими выходами 36 генератора 4 та:<товых импульсов.

Управляемый генератор случайных чисел работает следующим образом.

Получение случайных чисел x„ (i.=Ã, и) с заданным законом распределения

F(х) основано на сравнении равномерно распределенных случайных чисел <<1 снимаемых с Выхода генератора <, <.о значениями функции F(х „.) и отыс— кании интервала, где выполняется условие

F(x.) (1(Р(x4Ô1) . 5

При попадании числа в интервал (F(x;); F(х,+1 )j управляемый генератор выдает число х., подчиненное

1 закону F (х) .

Будем считать, что B запоминаю- у() щем устройстве 3 записаны значения функции F(х,), а в регистре 1 находится адрес ячейки памяти, в которой хранится значение функции F(х) при х = 0,5.

При поступлении сигнала Пуск по входу 15 происходит запуск генератора 4 тактовых импульсов, который

Вырабатывает серии импульсов, управляющ::е работой устройства (фиг.4). 30

По сигналу с первого выхода генератора 4 счетчик 11 ycтанавливается

В нача .=-Hoå состояние, а по сигналу со втсрого выхода генератора тактовых импульсов происходит чтение пер- 35 вого слова из блока 3 памяти и прием "-.òîãî с -;ова в регистры 1 и 5 и в блок 7 анализа. По сигналу с четвер="o Выхода генератора 4 производится эапуск генератора 8 равномерно QQ расг.ределеиных случайных чисел. (аждое слово,. х анящееся в запомиl аю-";ем устройстВе 3„ осТОНТ из трсх частей: в старших разрядах слова записано =-начини" Функции распределения F(х:),, а в младших разрядах .аДРЕС :ЧЕйКИ ПаМЯтИ,. В КатОРОЙ ХРаиится следующее слово и двухразрядны код Е .. При чтении очередного

1 слова из памяти в адр"-сный регистр 1 поступ;.ет адрес следующег cлова, В регистр 5 — значение Функции Г х ), 1 а В блок 7 анализа — код Е

f 1

)DpI чтении из памяти первого слс5 ва В реl !и тр 5 поступа T значение функции Г(х==-0,5), которое В момент времени, задаваемый сигналом с тре тьего выхода генератора 4 тактовых импульсов, сравиива""-тс †. в блоке 6 11 < сравнения с числом q, caимаемым с выхода генер-тора 8 равномерно ра"пределеиных случайных чисел. Если

Ь Е(х:,),. на выходе схемы сравнения

Формируется един H÷и ый сиги ал (Ь=-1 ), в противном <..лучае — нулевой (b=-0) . 65

< игнал Ь с Выхода схемы сравнения поступает В блок 7 анализа, а <ерез элемент ИЛИ 10 .=:аписывается В младший разряд регистра 13. Иа этом формирование старшего разряда случайного числа х„ заканчивается.

Дальнейшая работа генератора заВисит от значения кода Е,;, пос:упившсго В предыдушем такте в реги<"тр 8 блска 7 анализа, схема: оторо-.о приведена на фиг.2. Б этой схеме первая группа входов 22 блока 7 соедин"=на с третьей группой выводов бло«a 3 и мяти. Поэтому код Z. и;. за:.:сминаю1 щего jcTpoAcTH а 3 3 аписыв< ется в ре

= HcTp 18 в моменты време.-";1, задаваемые управляющим сигналом, пост,— пившим на второй вход 23 блока 7 анализа. CHrHaл b с выхода схемы 6 сравнения поступает на третий Вход

2; блока 7 анализа, Первый Выход 25 блока 7 соединен с входом установки в единичное состоя:;ие младшего р.-;.зряда регистра 1 . Поэто:y aci H Ha r! epI вом выходе 25 блока 7 анализа формируется единичиый сигнал, в младшем разряде оегистоа 1 записывает< н единица, в противном случае и этом разряде сохраняется ранее =:àïè< анное значение.

Рассмотрим работу управля=-мого генератора ст:учай .Вых .- сел пр; 7*=00 иа примере формирования :Tc.<. . o p ряда числа х . Иа В -ходе элем;=ь

И 19 (т. е. на первом Выходе 2 5 блока 7) единичный сигнал моя,=т ся только при Г =00:. b=, т=- «:ак

1, выходы элемента И 19-. =оеди: е:<ы с вто-рыми (инверсными) выходами р=-. . ":pa 18 и с третьим входом блока . Пс.= To! !ó при b=l иа выходе 25 Ioaa 7 =-,i I!Hза формируется единичный сигнал и: —:-. лà lший разряд регистра 1 зап .г:1вас;ся единица. По сформированному таким образом ь регистре 1 адресу А-"Л 1 из памяти считывается слово, . арш=х разрядах которого записано значение функции F(x=0,75). Здесь и код, хранящийся В (Р-1) старши.: раз— рядах регистра 1; Š— разрядность гистра 1; A — - исполнительный адрес ., Если b=0, на выходе 25 блока 7 формируется нулевой сигнал и в младшем раз,-яде регистра 1 сохраняетс=. про:..«нее нулевое значение,. т.е. A=)!10

При Формировании второго разряда .числа х по адресу А=А <". в памяти

1 1

PaHNTCH СЛОВО В CTBPL3ИХ РаЗРЯДак которого записано зна ..ение функ<.;ии

F(х=-О,.25). Таким образом получасT H. что В зависимости <т зиаче:.ия b. .з памяти считывается либо значение функции F(х=0.25), либо F(х=Î, 5

По< кольку при < F,х=0,. 5) Ь=- °, To в этом случае э памяти < !Hтываес;.". зна <ение F!x-=-О,. 25), т.е,,иаче:-:.

Фуикции Е (х) на сеоеди.,: и:т";;-- a—

960812

10 ла 0 х 0,5. Если же gwiF(х=0,5),. то

b=l и из памяти считынается значение функции F(x) при x=0,75, т.е. при значении аргумента на середине интервала 0,5i

10 младший. разряд которого по сигналу с выхода блока б сравнения записывается единица, если (7iF(x ), и ноль — в противном случае. Сдвиг в сторону старших разрядов ранее 15 сформированных разрядов числа х; осуществляется в регистре 13 по сигналу с седьмого выхода генератора 4 тактовых импульсов.

Рассмотрим работу управляемого 20 генератора случайных чисел при

Z; f00. В этом случае работа генератора зависит от значения сигнала q формируемого на втором выходе 26 блока 7 анализа. Если q=l, форми- 25 рование старших разрядов числа х„ заканчинается, а в младшие разряды числа х,.начиная со следующего

1 К такта с вероятностью 0,5, записываются единицы. Сигнал q формируется на выходе элемента ИЛИ 21, входы которого соединены с выходами элемен тон К 19, 19 3 и 194. Поэтому сигнал q ранен единице, если Е =10, или Е„-= 11, à b= 1, или Е„ = 01, а З5

Ь=О, В остальных случаях q=0,(см. схему блока 7, приведенную на фиг.2) °

Сигнал а поступает на четвертый .вход 35 генератора 4 тактовых импульсов, схема которого приведена Ю на фиг.Ç. В этой схеме генератор 30 импульсон формирует на первом и втором выходах непрерывные последовательности тактовых импульсов, следующие с одинаковой частотой и сдви- 45 нутые друг относительно друга на по- . лонину периода. Поэтому такт работы предлагаемого генератора состоит из двух микротактов. До поступления на вход 35 генератора 4 сигнала 50

q=l, генератор 4 н каждом такте (кроме первого) в первом микротакте формирует сигналы на втором 36 и пятом 36 выходах, а во втором микротакте — сигналы на выходах 36 и 36> . 55

В первом такте каждого цикла формируются все названные сигналы за исключением сигнала на пятом выходе.

В первом такте также формируются сигналы на первом 36 и четвертом

364 выходах генератора 4 (см.временную диаграмму, изображенную на фиг.4). По сигналам с второго выхода генератора 4 осуществляется чтение информации из блока 3 памяти и ее прием в регистры 1 и 5 и н блок 7 анализа.По сигналам с третьего и четвертого выходов генератора

4 осуществляется срабатывание блока б сравнения и генератора 8 случай ных чисел соответственно. Для увеличения содержимого счетчика 11 на единицу и сдвига содержимого регистра 13 используются управляющие сигналы, формируемые на пятом и седьмом выходах генератора 4 тактовых импульсов соответственно. Сигнал с первого выхода генератора 4 необходим для установки счетчика 11 в ис>одное состояние и выдачи сформированного в предыдущем цикле случайного числа х .на выход 17 генерато4 ра. Все названные сигналы формируются генератором 4 как в случае

Е =00, так и в случае Е„-) 00 при

q=0 Заметим, что в случае Z, фОО сигнал на ервом выходе блока 7 анализа всегда равен нулю и следовательно исполнительный адрес A равен адресу, поступающему в регистр 1 из запоминающего устройства 3. Поэтому в этом случае возможен переход к чтению из памяти только одной узловой точки F(х„), а не выбор одной точки иэ двух, как в случае Z OO.

При поступлении сигнала q=l на четвертый вход генератора 4 тактовых импульсов триггер 29 переходит н единичное состояние, а триггер 31 в нулевое, Считаем, что в схеме используются двухступенчатые синхронные IK-триггеры, на второй вход (вход синхронизации) которых поступает сигнал с второго выхода генератора 30 (фиг„З). Поэтому триггеры 29 и 31 сменяют свои состояния по заднему фронту импульса, снимаемого со второго выхода генератора

30, и разрешают тем самым появление импульсов на четвертом 364 и шестом

366 выходах генератора 4. При этом прохождение сигналов на первый 36, второй 36 и третий 36> выходы блока 4 запрещено. В следующем такте по сигналу с второго выхода генератора 30 триггер 29 возвращается в нулевое состояние, запрещая тем самым дальнейшее прохождение импульсов на четвертый выход блока 4. Поэтому после поступления сигнала q=l на четвертом 364 выходе блока 4 может появиться только один импульс, который запустит генератор 8 равномерно распределенных случайных чисел.

Опрос разрядов генератора 8 происходит по сигналам с выходов дешифратора 12 в моменты времени, задаваемые сигналами с шестого выхода генератора 4. Сформированный таким образом поток импульсов с выходов генератора 8 через элемент ИЛИ 10 поA 1

960812

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

Формирование очередного случайного числа х заканчивается в тот

1 момент времени, когда счетчик 11 переходит в,(m-1)-ое состояние и на последнем выходе дешифратора 12 появляется импульс, который устанавливает в регистре 1 начальный адрес — адрес ячейки памяти, в которой хранится значение F(x=0,5). 15

Здесь m-разрядность случайного числа х„ . Импульс с последнего выхода дешифратора 12 поступает также на третий вход 34 блока 4 и переводит триггеры 29 и 31 в единичное сос- 2G тояние, запрещая тем самым прохождение сигнала на шестой выход 366 генератора 4, так как первый вход элемента И 336 соединен с вторым (инверсным) выходом триггера 31, и раз- 25 решая прохождение сигналов с выхода генератора 30 на первый 36, второй 36>, третий 36З и четвертый

36, выходы блока 4. Поскольку в следующем такте по сигналу с второго ЗО выхода генератора 30 импульсов триггер 29 возвращается в нулевое состояние, а выход триггера 29 соединен с первыми входами элементов И 33(и

33,1, то на первый 36.(и четвертый 364 3S выходы блока 4 проходит только один

1 импульс. По импульсу с первого выхода блока 4 происходит установка в начальное (нулевое) состояние счетчика 11, считывается сформиронан-40 ноев предыдущем цикле случайное число х с регистра 13 и начинает1 ся цикл формирования следующего случайного числа ° При необходимости разрядность Формируемых случайных 45 чисел может быть увеличена эа счет добавления к числу х: равномерно распределенного числа с генератора 8 (выходы генератора 8 через элементы И 14 соединены с выходами 50

17 устройстна). Поскольку первый вход. элемента И 33 через элемент

НЕ 32 соединен с первым выходом

l блок(а 4, то на пятом выходе 36 сигнал может появиться только в те мо- -5 менты времени, когда отсутствует сигнал на выходе элемента И 33 . Седьмой выход блока 4 соединен непосредственно с вторым выходом генератора

30, поэтому сигналы на выходе 36> re-60 нератора 4 появляются н каждом такте.

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

При поступлении этого сигнала генератор 30 импульсов прекращает формировать импульсные последовательности и работа управляемого генератора случайных чисел на этом заканчивается.

Способом повышения точности воспроизведения распределения F(x) является увеличение количества и интервалов аппроксимации за счет уменьшениядлин Ь этих интервалов.

Получаемая при этом по;.решность О аппроксимации функции F(х) н случае кусочно-линейной интерполяции определяется по известной формуле

Ньютона — „) " Ю ) мокс, где длина i-го участка аппроксимации; (I F") Ч)/мокс — значение модуля второй производной функции F (х) н точке Т, где погреш-ность аппроксимации максимальнаВ известном устройстве Область значений аргумента х разбиваетгя на и равных интервалов, длина которых в случае формиров ния д:Ои н;»х — })1

4исел х. равна h=2, где m — раз",:.:д1 нОсть чисел. При этом колк: Рс: BG участков аппроксимации огре.=,:=;яется по формуле n = 1!h=2 . Так::*;и Образом при увеличении разрядности в формируемых чисел уменьшается ..Огре.ино ть воспроизведения распределения Fi») за счет уменьшения длины )1 у :астков аппроксимации, т,е. за счет увеличения количества узлов аппрок- . симации Г(х„).

ПоскОльку ДлЯ хранения у .=.лОных. ТОчек Г(х„ ) необходимо использовать запоминающее устройство емкостью и-1 чисел, то такой способ говышения точности воспроизведения сопряжен со значительными аппаратурн,лми затратами. Действительно, увеличение разрядности формируемых чисел х всегда на один разряд требует уне. личения в два раза объема запоминающего устройства, "гак как количество п участков аппроксимации возрастает в два раза.

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

F(x) при разбиении области значений аргумента х на и неравных интерналон. Длина h каждого интервала выбирается при этом таким Образом, чтобы погрешность ; аппроксим.=,ции не !.

960812

13

14 превышала заданной величины. Поэтому на тех участках, на которых модуль второй производной ) F"() воз-, растает, следует уменьшить длину интервала, а при уменьшении (V )Jìàêñ длину h„ Monaco увеличить °

График на фиг.5 иллюстрирует принятйй при построении генератора метод аппроксимации заданного распределения

F(x) .

При формировании первого разряда числа х равномерно распределенное случайное число g сравнивается со значением Р (х=О, 5) . Если f Г (х= О, 5), то формируемое число х может при1 нять значение из интервала 0,5 х<1. 35

Если >

F (õ4) 1F (x„..„). (2)

Однако в силу разбиения области изменения х íà и неравных интервалов число может попасть в интервал 30

<2) не эа к шагов (как в известном устройстве), а раньше. Здесь m как и прежде разрядность формируемых èoåë х, \

U p H M е р 1. Пусть )гг(х=0,75) 35

Тогда в силу монотонности функции

F(x) имеем $7F(x=0,5) и следовательно в результате первого испытания получаем, что х„.Е(0,5;1) . На втором шаге (такте) число сравнивается с 40

F(x=0,75), в результате чего получаем x„e(0,75;1). Поскольку дальнейшее разбиение интервала (0,75;1) пополам в данном случае не предусмотрено (фиг.5), то выдачей числа х из

4 найденного интервала и заканчивается цикл формирования очередного числа (недостающие m-2 разряда числа х. снимаются с генератора равномерно распределенных случайных чисел). Таким образом в рассматриваемом примере за два такта формируются два старших разряда числа х

1 Г а в младшие разряды, начиная с третьего, с вероятностью 0,5 заносятся единицы (в предлагаемом устройстве два старших разряда Формируются с помощью схемы сравнения, а мла.цшие разряды — путем опроса значений разрядов генератора 8 дешифратором 60

12 с последующим занесением результата в младший разряд регистра 13 сдвига, содержимое которого в каждом такте сдвигается на один разряд) . 65

Пример 2. Пусть F(x=3/16)

<5

1/4), которому должно принадлежать формируемое число х-, будет найден ( за четыре шага (в первом такте) сравнивается с F(x=0,5), во второмс F(x=1/4), в третьем — с F(x=1/8), в четвертом — с F(х=3/16). Таким образом в зависимости от значения поиск интервала (2) происходит за

К шагов (тактов), где К вЂ” случайная величина, меньшая или равная m. Поэтому устройство, реализующее рассматриваемый способ генерирования случайных чисел х, должно функционировать таким образом, чтобы в процессе работы на каждом шаге определялось попало ли число в интервал (2) или нет. С этой целью предлагаемое устройство содержит блок 7 анализа, который определяет .момент попадания числа в интервал (2) °

При попадании в.интервал (2) блок 7 анализа формирует сигнал q=l и предлагаемый генератор переходит в режим занесения в младшие разряды выходного регистра 13 с вероятностью

0,5 единичных сигналов. После завершения формирования m-разрядного случайного числа х. по сигналу с последнего выхода дешифратора 12 генератор переходит к формированию следующего случайного числа, а число х;, сформированное в предыдущем цикле, с выходов регистра 13 и генератора 8 через блок 14 элементов И подается. на выход 17 устройства.

С целью определения момента попадания числа (в интервал (2) в запоминающее устройство 3 в период настройки генератора на реализацию заданного закона распрецеления записываются не только значения функции

F(x() и адреса следующих узловых точек, но и двухразрядный код Z.. Этот f код в каждом такте поступает в блок анализа,.который в зависимости от значения Z и значения сигнала b c выхода схемы 6 сравнения формирует сигнал q.

В предлагаемом устройстве принято, что при Е,=-OO генератор формирует следующий разряд числа х обычным образом, т.е. после деления пополам очередного интервала и сравнения с

F(x„) в следующей такте делятся пополам оба полученных полуинтервала, а выбор узловой точки происходит в зависимости от значения сигнала b: при b=O иэ памяти считывается значение функции, подсчитанное на середине левого полуинтервала, а при Ь=1 — на середине правого полуинтервала.

Поступление в блок 7 анализа ко-, да Z, =10 означает, что искомый нн15

960812. тернал (2) найден и генератор начи- ная со следующего такта по сигналу

q=l, сформированному в блоке 7, формирует оставшиеся младшие разряды числа х„, занося в регистр 13 равновероятные дноичные сигналы.

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

В этом случае определение момента попадания н искомый интервал проис- 0 ходит по сиГналу с последнего выхода дешифратора 12, а формирование сигнала q=l блокируется путем поступления иэ памяти в блок 7 анализа кода Е =00, исключая тем самьм воз- (5 можность занесения в младшие разряды регистра 13 раннонероятных двоичных сигналов.

При работе генератора возможна ситуация, когда после деления попо- QQ лам очередного интервала в следующем такте необходимо делить пополам только один из двух полученных полуинтервалов. С целью определения полуинтервала, подлежащего делению, 25 вводятся следующие значения управляющего сигнала: Z<=01 Z; =11. Если

2. =Ol, в следующем такте делится по1 полам только правый полуинтервал, а при попадании - в левый не подлежа- З0 щий делению полуинтервал (т.е. при

Ь=О) в блоке 7 формируется сигнал

q=l и генератор переходит к формированию младших равновероятних разрядов числа х.. Если Z =11, в следую1 1 щем такте делится пополам левый полуинтернал, а при попадании . в правый полуинтервал (т,е. при b=l) Т а б л и ц а 1

0,000122

0,125

0,0313

0,0078 0,00195 0,00049

255

31 63

127

Т а б л и ц а 2

m 3 4 5 6 7 8

О,125 О,О313 О,OO78 О,OO195 О,ООО49 О,OO0122

7 12 23 46 89 рядности регистра 1 и ко.ичества ныM -ходов дешифратора 2.

Предлагаемое устройс.во позноляс". уменьшить погрешность F аппроксимации заданного распределения, сохраняя примерно одинаковые с известным устройЯ ством аппаратурные затр=ты, Например, Из сраннения таблиц видно, что предлагаемое устройство н зависимости от разрядности формируемых чисел позволяет сократить объем памяти н

2,1-2,9 раза при сохранении точности аппроксимации. Сокращение объема памяти ведет также к уменьшению раэн блоке 7 формируется сигнал q=1.

Поэтому блок 7 анализа формирует сигнал q=l не только при ZÄ =10, но и при Z =01, если b=o, и при Е =11, если b=l.

Таким образом, предлагаемый генератор позволяет воспроизводить заданное распределение F(х) при разбиении области х на п неравных интервалов, определяя в каждом такте выполняется ли условие (2) или нет.

Поскольку в известном устройстве ределение момента попадания в интервал (2) проис .-одит только в m-ом такте, то известное устройство не позволяет делить область значений х íà и неравных интервалов, и следовательно, требует дополнительного объема памяти для достижения тех же точностных характеристик, которые имеет предлагаемое устройство.

C целью сравнения точностных характеристик предлагаемого устройства и известного был проведен по формуле (1) расчет погрешности $ аппроксимации показательного распределения

F(x)=1 -ехр(-Х"х) при Р- =8. В табл.l и 2 приведены полученные при этом значения погрешности Я аппроксимации и объема памяти N н зависимости от разрядности m формируемых ;-исел х . Объем памяти определяется. по формуле N = n-l, где n — количество интерналов аппроксимации, обеспечивающих точность 6.. B т"абл.1 привел ны характеристики известного устройства, а в табл.2 — характер-:.;"тики -редлагаемого устройства.

960812

18

17 при формировании случайных чисел, закон распределения которых отличается от показательного распределения не ,)более чем íà f =0,00195, в известном устройстве требуется объем памяти

N=63>a в предлагаемом устройстве погрешность Е= 0,00049 достигается прй

N = 46 (см. табл.1 и 2). Таким образом предлагаемое устройство несмотря даже на некоторое уменьшение объема памяти (с 63 до 46) позволяет поч- о ти В четыре раза повысить точность воспроизведения показательного распределения. Аналогичные характеристики предлагаемое устройство имеет и при воспроизведении других законов 15 распределения.

Использование новых элементов регистров, счетчика, дешифратора, блока анализа, элемента ИЛИ выгодно отличает предлагаемый генератор от 20 ,известного, так как позволяет повысить точность воспроизведения заданного распределения.

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

1. Управляемый генератор случайных чисел, содержащий генератор тактовых импульсов, блок памяти, первый де:шифратор, первый регистр памяти, вы- 3Q .;Од котоpoгo через первый дешифратор соединен с первым входом блока памяти, = ло:. сравнения, первый и второй блоки элементов И, генератор равно. ер о распределенных случайных вели- 35 чин, группа выходов которого соединена с соответствующими входами первой

1руппы блОка сраВнения ВыхОД ВтОрОго блока элементов И является выходом генератора, о т л и ч а ю щ и йтем, что, с целью повышения

".Очности, Он содержит второй и третий регистры памяти, блок анализа . :.Одоз, счетчик, второй дешифратор и элемент ИЛИ, причем первый и

zтОрой входы впуск .1ервый и Второй входы задания режима генератора тактовых импульсов соединены с первым и вторым входамл генератора, и-ым (n — число выходов второго дешифратора) выходом второго дешифратора и первым выходом блока анализа кодов соответственно, первый выход генератора тактовых импульcoâ подключен к первому входу счетчика и к первому входу второго блока элементов И, второй и третий входы которого соединены с выходом третьего регистра памяти и выходом генератора равномерно распределенных случайных чисел соответственно, второй выход генератора тактовых им пульсов соединен с первыми входами первого и второго регистров памяти, блока памяти и блока анализа кодов, первый выход блока памяти подключен 45 к второму входу второго регистра памяти, выходы которого соединены с соответствующими входами второй группы блока сравнения, вход которого, подключен к третьему выходу генератора импульсов, второй выход блока памяти подключен к второму входу первого регистра памяти, третий вход которого соединен с вторым выходом блока анализа кодов, второй и третий входы которого подключены к третьему выходу блока памяти и выходу блока сравнения соответственно, четвертый выход генератора тактовых импульсов соединен с входом генератора равномерно распределенных случайных чисел, группа выходов которого подключена к соответствующим входам первой группы первого блока элементов И, входы второй группы которого соединены с соответствующими Выходами второго дешифратора, а выходы первого блока элементов И соединены с группой входов элемента ИЛИ соответственно, вход которого соединен с выходом блока сравнения, а выход элемента ИЛИ соединен с первым входом третьего регистра памяти, второй вход которого соединен с пятым выходом генератора тактовых импульсов, шестой и седьмой выходы которого подключены к второму входу счетчика и входу второго дешифратора соответственно, четвертый вход первого регистра памяти соединен с и-ым выходом второго дешифратора, группа входов которого подключена к выходам счетчика соответственно.

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

960812

19

20 третьей и четвертой групп, третий вход блока соединен с третьими входами элементов И второй и третьей групп и с входом элемента НЕ, выход которого соединен с третьим входом элементов И четвертой группы.

Источники информации, принятые во внимание при экспертизе

Авторское свидетельство CCCP

9 213424, кл, С 06 F 1/02, 1966.

2. Авторское

9 309356, кл. G

3. Авторское

9 337788882266, кл. G (прототип} . свидетельство СССР

06 F 1/02, 1969. свидетельство СССР

06 F 1/02, 1971

960 В12

1 !

Я/. 7 ф/

Редактор А.Минкина

Заказ 7283/59 Тираж 731 Подписное

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

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

Филиал ППП Патент, г. ужгород, ул. Прсектна.,, 4 ( /I I

У/р / р 1ф а

L 1

Составитель A.Êàðàñîý

Техред М.Тенер Корректор К. Рокко