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

(54) УПРАВЛЯЕМЫЙ ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

Р-зЕестен управляемый генератор случайных чисел, содержащий датчик равномерно распределенных случайньж чисел, запоминающее устройствоi схемы параллельного сравнения чисел, триггеры, схемы совпадения, выходное устройство и позволяющий получать случайные числа с заданным законом распределения за один такт работы датчика. |l .

Однако устройство имеет высокую сложность.

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

Недостатком устройства является низкое быстродействие, так как т-разрядное с.т1учайное число форми-. руется за vm+1) такт.

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

15 входов запоминающего устройства, второй вход запоминающего устройства подключен к nepEioMy выходу г.енератора тактовых импульсов, входы регистра соединены с выходами первой груп20пы элементов И, ; лервая и вторая группы входов которой подключены к выходам схемы сравнения и генератора тактовых импульсов соответственно, выходы регистра через вторую

25 группу элементов И соединены с выходом устройства, выход генератора тактовых импульсов подключен к второй группе входов второй группы элементов И. В генераторе для получения

30 последовательности случайных чисел

с заданньП законом распределения применяется функциональное преобразование, основанное на кусочно-линейной аппроксимации заданного распределения F(x) ГЗ.

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

Целью изобретения является повышение точности всспроиэнедения распределения F(x) за счет разбиения области значений аргумента х на л неравных интервалов„

Поставленная цель достигается тем что в управляемый генератор случайны чисел, содержащий генератор тактовыу: импульсов, блок памяти, первый дешифратор, первый регистр памяти, выход которого через первый дешифратор соединен с первым нходом блока памяти, блок сравнения, первый и второй блоки элементов И, генератор равномерно распределенных чисел, группа выходов которого соединена с соответствующими входами первой группы 6JiOKa сравнения, выход второго блока элементов И является выходом генер |Тора, введены второй и третий регистры памяти, блок анализа кодов, счетчик, второй дешифратор и элемент ИЛИ, причем первый и второй входы Пуск, а.также гервый к второй входы задания режиь а генератора тактовых импульсов соедшнены с первым и вторья 1 входами генератора f (п - число выходов второго дешифратора) выходом второго дешифратора и первым выходом бло.са анализа кодов соответственно, пер:е-.,гй выход генератора тактовых кмпульсов подключен к первому входу счетчика, к к первому входу второго элементов И, второй и третий входы которого соединены с выходом -трету его регистр;, памяти и выходом 1енерс:торг. равномерно распределенных случайных чисел соответственно, второй выход генератора тактовых импульсоп соединен о перВЕлми входами nepsoio и второго регистров памяти, блока памяти и блока анализа кодов, первый выход блока подключен к второму входу второго регис ра rtaMHTH,, выходы которого соединены ( соответствую ЦИ1Ми входами второй группы блока сравнения, вход которого подключен к третьему выходу геп-ератсра тактовых импульсов, второй выход блока памяти подкл:.:чаи к второму в.оду первого регистра памяти,, третрй вход которого соединек с вторым выходом 5noia анализа кодов, второй и третий входы которого подключены к тоетьему выходу блока памяти и выходу блока ср ;внения соответственно, четвертый т-ыуод генераторе;

тактовых к.-::1ульсов соединен с входном генератора разномерно распоеделенных случайн лх чисел, группа выходов котсрого 11одключена к соответствующим зходг1м первой группы первого блока элементов И, ахо.цы второй группы которого соедиьены с соответствующими выходами второго дешифратора,Г а выхо.аь4 первого блока элементов И соединены с группой входов элемента ИЛИ соответстьенно, вход которого соединен с выходом блока сравнения, а выход элемента ИЛИ соединен с перзглм входом третьего регистра памяти, Бторой вход которого соодинен с пятым выходом генератора тактовых импульсов, шестой и седьмой БУХОДЫ которого подключены к второму входу счетчика и входу второго де:лифратора соответственно, четвертый вход первс:го регистра памяти соединен с п-ьгм выходом ВТО1ЭОГО дешифратора, групгта ВХОДОР которого подключена к аьтходам счетчикг соответственно.

Кроме того, блок анализа кодов содержит четыре группы элементов И, элемент ИЛИ, элемент НЕ и два регистра памяти, пеовые входы которых образуют первый вход блока, второй вход которого соадилен с втор.:-лли входами регистров памяти, тов И первой группы соеди.ен с первым ВХОДОМ 3.j3iv SHTa ИЛИ , выход э;:ементов И второй групта ЛЕ. i первым выходом 6JiOfca, зыходь,: элементов И третьей и чета--его и грул г :;сади1;ены соответственно с -«тог ЫдМ и иретьим входами элемента И.1И, выход которого является BTOpHjx-i выходом бчока, первый выход первого реггютра памяти соединен с первыми входами зламентов И первой и третьей груп;., BJ:Gрой выход первого регистра памяти соединен с первыми входами элементов И второй и четвертой групп, первый выход второго регистра памя1 г соединен с втсрыми входг гли элег.ьч-. тов И первой и второй групп, второй выход, второго регистра .ч соединен с STOpBiviH Ехола -:Н элементов И третьей к четвертой групп, трс-тии вход блока соединен с третьими входами элементов И второй и третьей 1рупп и с нходом элемента Hi-, зьход которого соединек с третьим входом элгм&:чта И четвертой групга,

Нэ фиг, приведена структурная схама управляемого гекератора случайных чисел; на фиг «2 - функцислгальная схема блока анализа; на фьг.Г функцкональне я схема генерглтора -;-;: тоЕЫХ импульссз; на фиг. 4 - грем;;-:ные диаграмрды работы управляемого генератора случайных чиса..; на фиг. 5 :уоочно-;ннейНЕл атроксима;; - ; jfдапного расггределени.ч pixi . Управляемый генератор содержит первый 1 памяти, первый деши фратор 2, блок 3 памяти, генератор 4 тактовых импульсов, второй регистр 5 памяти, блок 6 сравнения, блок 7 анализа кодов, генератор 8 равномерно распределенных случайных чисел, первый блок 9 элементов И, элемент ИЛИ 10, счетчик 11, второй дешифратор 12, третий регистр 13, второй блок 14 элементов И, входы 15 и 16 генератора и -выход 1.7 генератора. Выход первого регистра 1 через первый дешифратор 2 соединен с первым входом блока 3 памяти, первый, второй и третий выходы которого под ключены к первым входам регис5тро.в 5 и 1 блока 7 анализа соответственно. Первый, второй, третий и четвертый входы генератора 4 тактовых импульсов подключены к первому 15 и второ му 16 входам устройства, последнему выходу второго дешифратора 12 и к второму выходу блока 7 анализа соответственно. Первый выход генера тора 4 тактовых импульсов соединен с первым входом счетчика 11 и с тре тьим входом второго блока 14 элементов И-, первый и второй входы блока 14 подключены к выходу регист ра 13 и к второму выходу генератора 8 равномерно распределенных случайных чисел соответственно, а выход блока 14 соединен ,с выходом 17 устройства. Второй выход генератора 4 тактовых импульсов соединен с вторыми входами регистров 1 и 5, блока 3 па мяти и блока-7 анализа, первый выхо блока 7 анализа подключен к четвертому входу регистра 1. Третий выход генератора 4 подключен к третье му входу блока 6 сравнения, первая вторая группы входов которого соеди нены соответственно с первой группо выходов генератора 8, с выходами ре гистра 5, а выход блока 6 оравнения подключен к третьему входу блока 7 анализа и к первому входу элемента ИЛИ 10. Четвертый выход генератора 4 тактовых импульсов подключен к входу генератора 8 равномерно распр деленных случайных чисел, первая группа выходов которого соединена с с первой группой входов блока 9 эле ментов И, вторая группа входов блока 9 подключена к выходам дешифрато ра 12, а выходы блока 9 соединены с второй группой входов элемента ИЛИ Выход элемента ИЛИ 10 соединен с пе вым входом регистра 13, второй вход которого подключен к седьмому выход генератора 4 тактовых импульсов, а пятый и шестой выходы генератора 4 соединены с вторыми входами счетчика 11 и дешифратора I. соответствен Третий вход регистра 1 подключен к последнему выходу дешифратора 12, входы которого соединены с выходами счетчика 11. Блок 7 анализа (фиг.2) содерукнт двухзарядный регистр 18 памяти, блок 19 элементов И, элемент НЕ 20, элемент ИЛИ 21, входы 22-24 и выходы 26 и 25, причем первая и вторая группы входов регистра 18 соединены соответственно с входами 22 и 23 блока 7 анализа, а выход 24 блока 7: подключен к третьему входу элементов И 1Э и 19з и к входу элемента НЕ 20, выход которого соединен с третьим входом элемента И 19д , первый выход первого разряда регистра 18 подключен к первым входам элементов И 19 и 19, а второй выход первого разряда регистра 18 соединен с первыми входами элементов И 19д. и 19, первый выход второго разряда регистра 18 соединен с вторыми входами элементов И 19 и 194, а второй выход второго разряда регистра 18 подключен к вторь1М входам элементов И 19 и 19,, выход элемента И 1 соединен с первым выходом 25 блока 7 анализа, а выходы элементов И 19 , 19 и 19 через элемент ИЛИ 21 подключены к второму выходу 26 блока 7 анализа. Генератор 4 тактовых импульсов (фиг.З) содержит элементы И 27 и ИЛИ 28, триггеры 29, генератор 30 импульсов, триггер 31, элемент НЕ 32, блок 33 элементов И, входы 1516, 34 и 35 и группу выходов 36, причем первый и второй входы генератора 30 импульсов соединены с первым 15 и вторым 16 входами устройства соответственно, а первый выход генератора 30 импульсов подключен к вторым входам элементов И 33 , 332, 334. и 335-, вторые входы элементов И 33j и 33, седьмой выход 36-, генератора 4 тактовых импульсов, второй и третий входы триггера 29 и второй вход триггера 31 соединены с вторым выходом генератора 30 импульсов, третий 34 и четвертый 35 входы генератора 4 соединены соответственно с первым и третьим входами триггера 31, а также с первыми входами элементов ИЛИ 28 и И 27 соответственно, первый выход триггера 31 подключен к третьему входу элемента И 33, к первым входам элементов И 33 и к второму входу элемента И 27, выход которого соединен с вторым входом элемента ИЛИ 28,а выход элемента ИЛИ 28 подключен к первому входу триггера 29, второй выход триггера 31 подключен к первому входу элемента И 33, а первые входы элементов И 33 и 33д соединены с выходом-триггера 29,выход элемента И 33 через элемент НЕ 32 подключен к первому вхоцу элемента, И 33 , выходы блока 33 элементов К соединены с соответству ющими выходами 36 генератора 4 -такт вых импульсов. Управляемый генератор случайных чисел работает следующим образом. Получение случайных чисел (i l п) с заданным законом распределения F{x) основано на сравнении равномер но распределенных случайных чисел , снимаемый с выхода генератора 8. со значениями F (к .} и отыскании интервала, где выполняется ус ловие р / V- - I V 1 т При попадании числа в интерва/ F(X,-) ; F(. ) управляемый генератор выдает число х., подчиненное закону F(х). Будем считать, что в запоминающем устройстве 3 записаны значения функции F(x,), а в регистре 1 находится адрес ячейки памяти, в которо хранится значение функции F(x) при X 0,5. При поступлении сигнала Пуск по входу 15 происходит запуск генер тора 4 тактовых импульсов, который вырабатывает серии импульсов, управ ляющие работой устройства (фиг,4), По сигналу с первого выхода генератора 4 счетчик 11 устанавливается S начальное состояние, а по сигналу со второго выхода генератора тактовых импульсов происходит чтение пер вого слова из блока 3 памяти и прием этого снова в регистры 1 и 5 и в блок 7 анализа. По сигналу с четвер .сго выхода генератора 4 производит ся запуск генератора 8 равномерно распределенных случайных чисел. Каждое слово,- хранящееся в запом ка;о2ам устройстве 3, состоит из тре частей: в старших разрядах слова за писаке значение функции распределения F(x:),, а в мла,Д1г.:их разрядах адрес ячейки пга-мяти. р которой хранится следующее слово и двухразрядньгЛ код Z ,. При чтении очередного слова из памяти Б адресный регистр поступает алрес следующего слова, в pet-KCTp 5 - значение функции F;x. а в Iблок 7 анализа - код , ои чтении из памяти первого сло ва & регистр 5 поступает значечие орункции Р{х-0,5), которое в момент времени, задаваемый сигналом с третьего выхода генератора 4 тактовых импульсов, сравнизается в блоке 6 сравкекия с числом s , снимаекшм с выхода генератора. 8 равномерно распреде.кенкых случайных чисел„ Если F(x,;)r на выходе схемы сравнения формируется единичный сигнал (), в противном случае - нулевой ) . Сигнал Ь с выхода схемы срав.чения поступает в блок 7 анализа, а через элеменТ ИЛИ 10 записывается в младший разряд регистра 13, На этом формирование старшего разряда случайно- , го числа заканчивается. Дальнейшая работа генератора зависит от значения кода Z.; , поступившего в предыдущем такте в регистр 18 блока 7 анализа, схема которого приведена на фиг.2. В этой схеме первая группа входов 22; блока 7 соединена с третьей группой выводов блока 3 памяти. Поэтому код Z. из запоминающего устройства 3 записывается в регистр 18 в моменты времени, задаваемые управляющим сигналом, поступипшим на второй вход 23 блока 7 анализа. Сигнал Ь с выхода схемы 6 сравнения поступает на третий вход 24 блока 7 анализа,, .Первый выход 25 блока 7 соединен с входом установки в единичное состояние младшего разряда регистра 1 , nosTOf iy, если на первом выходе 25 блока 7 анализа формируется единичный сигнал, в младшем разряде регистра 1 записывается единица, в противном случае в этом разряде сохраняется ранее записанное значение. Рассмотрим работу управляемого генератора случайных чисел при ,,-00 на примере формирования р.э.эряда числа х . На походе элемеьгсИ 192 (т.е. на первом ЕЬходе 25 блока 7) единичный сигнал может ппязи ь ся только при и , так как выходы элемента И 1 5;,, соедиие;{ы с вто-. рыми (инверсными) выходами ps::- Jгpa 18 и с третьим входом блока , Поэтому при на выходе 25 блока 7 еи-ли за формируется единичный сигнал и D мла.иший разряд регистра 1 запис: ;вастср единица. По сформированному таким образом Е. регистре 1 адресу 1 кз памяти считывается слово, з старших разрядах которого записано значение функции F(,75), Здесь А,,- код, хранящийся в (1.) старши.: разрядах регистра 1; (f - разрядность р гистра 1; А - исполнительный адрес,. Если Ь-О, на выходе 25 блока 7 формируется нулевой сигнал и в м.падшем рааряде регистра 1 сохраняется прежнее нулевое значение, т.е. , При формировании второго разряда числа по адресу в памяти хранится слово, в старших разрядах которого записано зна-1е:ние функции F(.25). Таким образом получается, что в зависимости от значенияЬ. ;-:з памяти считывается либо значение функции F(,25), либо F(,5;, Поскольку при F (х 0 ,-5 ) , то Б этом случае из памяти считывается значение F(,,25), т.е. значен.-:: функции F(x) на середин- имт( рваа OixsO,5, Если же (,5) ,. то и из памяти считывается значение функции F(x) при ,75, т.е. ри значении аргумента, на середине интервала 0,. Аналогичным образом происходит формирование адресов и выбор срединных значений функции F(x) и при формировании остальных разрядов случайного числа , если . Случайное число формируется в регистре 13 сдвига, в мла:дший разряд которого по сигналу с выхода блока б сравнения записывается единица, если F(), и ноль - в противном случае. Сдвиг в сторону старших разрядов ранее 15 сформированных разрядов числа х осуществляется в регистре 13 по сигналу с седьмого выхода генератора 4 тактовых импульсов.

Рассмотрим работу управляемого 20 генератора случайных чисел при . В этом случае работа генератора зависит от значения сигнала q, формируемого на втором выходе 26 блока 7 анализа. Если , форми- 25 рование старших разрядов числа к заканчивается, а в младшие разряды числа X. , -начиная со следующего , такта с вероятностью 0,5, записываются единицы. Сигнал q формируется на выходе элемента ИЛИ 21, входы ко- ., торого соединены с выходами элементов к 19. , 19-3 и Поэтому сигнал q равен единице, если , илр Z 11, а b 1, или 01, а 35 , В остальных случаях /см. схему блока 7, приведенную на фиг.2),

Сигнал q поступает на четвертый вход 35 генератора 4 тактовых импульсов, схема которого приведена 40 на фиг.З. В этой схеме генератор 30 импульсов формирует на первом и втором выходах непрерывные последовательности тактовых импульсов, следующие с одинаковой частотой и сдви- 45 нутые друг относительно друга на половину периода. Поэтому такт работы предлагаемого генератора состоит из двух микротактов. До поступ- , ления на вход 35 генератора 4 сигнала 50 , генератор 4 в каждом такте (кроме первого) в первом микротакте формирует сигналы на втором 36 и пятом 365- выходах, а во втором микротакте - сигналы на выходах 36 и 36- . jj В первом такте каждого цикла формируются все названные сигналы за исключением сигнала на пятом выходе. В первом такте также формируются сигналы на первом 36 и четвертом л Збд выходах генератора 4 (см.временную диаграмму, изображенную на фиг.4). По сигналам с второго выхода генератора 4 осуществляется чтение информации из блока 3 памяти и ее прием в регистры 1 и 5 и в 5

блок 7 анализа.По сигналам с третьего и четвертого выходов генератора 4 осуществляется срабатывание блока 6 сравнения и генератора 8 случайных чисел соответственно. Для увеличения содержимого счетчика 11 на единицу и сдвига содержимого регистра 13 используются управляющие сигналы, формируемые на пятом и седьмом выходах генератора 4 тактовых импульсов соответственно. Сигнал с первого выхода генератора 4 необходим для установки счетчика 11 в исходное состояние и выдачи сформированного в предыдущем цикле случайного числа на выход 17 генератора. Все названные сигналы формируются генератором 4 как в случае , так и в случае Z 00 при . Заметим, что в случае Z. сигнал на первом выходе блока 7 анализа всегда равен нулю иследовательно исполнительный адрес А равен адресу, поступающему в регистр 1 из запоминающего устройства 3. Поэтому в этом случае возможен переход к чтению из памяти только одной узловой точки F(), а не выбор одной точки из двух, как в случаеZ - 0€. При поступлении сигнала на четвертый вход генератора 4 тактовы импульсов триггер 29 переходит в единичное состояние, а триггер 31 в нулевое. Считаем, что в схеме используются двухступенчатые синхронные 1К-триггеры, на второй вход (вход синхронизации) которых поступает сигнал-с второго выхода генератора 30 (фиг.З). Поэтому триггеры 29 и 31 сменяют свои состояния по заднему фронту импульса, снимаемого со второго выхода генератора 30, и разрешают тем самым появление импульсов на четвертом 36 и шестом 36g выходах- генератора 4. При этом прохождение сигналов на первый 36 , второй 36 2 и третий 36. выходы блока 4 запрещено. В следующем такте по сигналу с второго выхода генератора 30 триггер 29 возвращается в нулевое состояние, запрещая там самым дальнейшее прохождение импульсо на четвертый выход блока 4. Поэтому после поступления сигнала на четвертом 36 выходе блока 4 может появиться только один импульс, который запустит генератор 8 равномерно распределенных случайных чисел.

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

Формирование очередного случайного числа заканчивается в тот момент времени, когда счетчик 11 п-ереходит в,(т-1)-ое состояние и на последнем выходе дешифратора 12 появ/ яется импульс, который устанавливает в регистре 1 начальный адрес - адрес ячейки памяти, в которой хранится значение F(,5). Здесь т-разрядность случайного числа х . Импульс с последнего выхода дешифратора 12 поступает также на третий вход 34 блока 4 и переводит триггеры 29 и 31 в единичное соетояние, запрещая тем самым прохождение сигнала на шестой выход 36 генератора 4, так как первый вход элемента И 33g соединен с вторым (инверсным) выходом триггера 31, и разрешая прохождение сигналов с выхода генератора 30 на первый 36 , второй Зб2, третий 36 и четвертый Збд выходы блока 4, Поскольку в следующем такте по сигналу с второго выхода генератора 30 импульсов триггер 29 возвращается в нулевое состояние, а выход триггера 29 соединен с первыми входами элементов И 33 и 33j, то на первый 36 и четвертый 36 выходы блока 4 проходит только один импульс. По импульсу с первого выхода блока 4 происходит установка в начальное (нулевое) состояние счетчика 11, считывается сформированноев предыдущем цикле случайное число х с регистра 13 и начинается цикл формирования следующего случайного числа. При необходимости разрядность формируемых случайных чисел может быть увеличена за счет добавления к числу равномерно распределенного числа с генератора 8 (рыходы генератора 8 через элементы ii 14 соединены с выходами 17 устройства). Поскольку первый вход, элемента И 33. через элемент НЕ 3,2 соединен с первым выходом 4, то на пятом выходе 36. сигнал «может появиться только в тс моменты времени, когда отсутствует сигнал на выходе элемента И 33. Седьмой выход блока 4 соединен непосредственно с вторым выходом генератора 30, поэтому сигналы на выходе 36 ге нератора 4 появляются в каждом такте.

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

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

Способом повышения точности воспроизведения распределения F(x) является увеличение количества п интервалов аппроксимации за счет меньшения длин h этих интервалов. Получаемая при этом погрешность аппроксимации функции F(x) в случае кусочно-линейной интерполяции определяется по известной формуле Ньютона

е 1;|рЧЧ)|ллс,кс,

где h

- длина 1-го участка аппроксимации; )/MCiKc-- значение модуля

второй производной функции F(x) Б точке т, где погрешность аппроксимаци максимальна,

В известном устройстве область значений аргумента х разбивается на п равных интервалов, длина которых в случае формирований исел X.. равна где m - раэрг-.дность чисел. При этом количество участков аппроксимации определяется ПО формуле п l/h 2. Таким образо при увеличении разрядностк m формируемых чисел уменьшается погре иност воспроизведения распределения Fix) за счет уменьшения длины h y iacTков аппроксимации, т.е. за счет увеличения количества узлов аппроксимации F() .

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

Предлагаемое устройство реализует способ получения случайных чисел х, , основанный на кусочно-линейной аппроксимации функции распределения F(x) при разбиении области значений аргумента х на п неравных ино:ервалов. Длина h каждого интервала выбирается при этом таким образом, чтобы погрешность аппроксимдции не превышала заданной величины. Поэтом на тех участках, на которых модуль второй производной I F (f) возрастает, следует уменьшить длину h{ интервала, а при уменьшении |Р() длину h можно увеличит График на фиг.5 иллюстрирует принят при построении генератора метод аппроксимации заданного распределения F(x). При формировании первого разряда числа равномерно распределенное случайное число сравнивается со значением F(,5) . (х 0,5 то формируемое число х - может принять значение из интервала 0,. Если (,5), то число х оказыва ся в интервале ,5. При форми ровании второго разряда в зависимос ти от результата первого испытания число сравнивается либо со значением F(, 25) . если х,-€{0,0, 5), л бо со значением F(,75) если (О, 5,1) . Процесс сравнения Ч со срединными значениями функции F(x) продолжается до тех пор, пока не попадает ц интервал F(Xj)( ), .(2) Однако в силу разбиения области изменения х на п неравных интервало число %, может попасть в интервал (2) не за m шагов (как в известном устройстве), а раньше. Здесь m как и прежде разрядность формируемых чисел X,о Пример 1. nycTb 7/F(,75) Тогда в силу монотонности функции F{x) имеем 7F(,5) и следователь но в результате первого испытания получаем, что (0,5;1). На втором шаге (такте) число сравнивается с F(,75), в результате чего получа ем (0,75;1). Поскольку дальнейше разбиение интервала (0,75;1) попо-лам в данном случае не предусмотрено (фиг. 5), то выдачей числа-х из найденного интервала и заканчивается цикл формирования очередного числа (недостающие т-2 разряда числа х снимаются с генератора равномерно распределенных случайных чисел) . Таким образом в рассматриваемом примере за два такта формируются два старших разряда числа , а в младшие разряды, начиная с третьего, с вероятностью 0,5 заносятся единицы (в предлагаемом устройстве два старших разряда формируются с помощью схемы сравнения, а младшие разряды - путем опроса значений разрядов генератора 8 дешифр атором 12 с последующим занесением результата в младший разряд регистра 13 сдвига, содержимое которого в каждом такте сдвигается на один разряд) . п р и м е р 2. Пусть F(): F() . Тогда интервал (3/16 1/4), которому должно принадлежать формируемое число , будет найден за четыре шага (в первом такте) сравнивается с F(,5), во втором с F(), в третьем - с F(), в четвертом - с F(). Таким образом в зависимости от значения поиск интервала (2) происходит за К шагов (тактов), где К - случайная величина, меньшая или равная т. Поэтому устройство, реализующее рассматриваемый способ генерирования случайных чисел х, должно функционировать таким образом, чтобы в процессе работы на каждом шаге определялось попало ли число в интервал (2) или нет. С этой целью предлагаемое устройство содержит блок 7 анализа, который определяет .момент попадания числа в интервал (2). При попадании в.интервал (2) блок 7 анализа формирует сигнал и предлагаемый генератор переходит в режим занесения в младшие разряды выходного регистра 13 с вероятностью 0,5 единичных сигналов. После завершения формирования т-разрядного случайного числа X, по сигналу с последнего выхода дешифратора 12 генератор переходит к формированию следующего случайного числа, а число х, сформированное в предыд тцем цикле, с выходов регистра 13 и генератора 8 черезблок 14 элементов И подается, на выход 17 устройства. С целью определения момента попадания числа в интервал (2) в запоминающее устройство 3 в период настройки генератора на реализацию заданного закона распределения записываются не только значения функции F() и адреса следующих узловых точек, но и двухразрядный код Z. Этот код в каждом такте поступает в блок 7 анализа,.который в зависимости от значения Z и значения сигнала Ь с выхода схемы 6 сравнения формирует сигнал q. . В предлагаемом устройстве принято, что при Z.00 генератор формирует следующий разряд числа х обычным образом, т.е. после деления пополам очередного интервала и сравнения с F(x) в следующем такте делятся пополам оба полученных полуинтервала, а выбор узловой точки происходит в зависимости от значения сигнала Ь: при из памяти считывается значение функции, подсчитанное на середине левого полуинтервала, а при - на середине правого полуинтервала. Поступление в блок 7 анализа ко- , да означает, что искомый ин. тервал (2) найден и генератор начиная со следующего такта по сигналу , сформированному в блоке 7, формирует оставшиеся младшие разряды числа х , занося в регистр 13 равновероятные двоичные сигналы. Очевидно возможен и такой случай, когда все m разрядов числа формируются с помощью схемы сравнения. В этом случае определение момента попадания в искомый интервал проис ходит по сигналу с последнего выхода дешифратора 12, а формирование сигнала блокируется путем поступления из памяти в блок 7 анализа кода , исключая тем самым возможность занесения в младшие разряды регистра 13 равновероятных двоичных сигналов.

При работе генератора возможна ситуация, когда после деления пополам очередного интервала в следующем такте необходимо делить пополам только один из двух полученных полуинтервалов. С целью определения полуинтервала, подлежащего делению, вводятся следующие значения управляющего сигнала: и . Если Z. 01, в следующем такте делится пополам только правый полуинтервал, а при попадании - в левый не подлежащий делению полуинтервал (т.е. при ) в блоке 7 формируется сигнал и генератор переходит к формированию младших равновероятных разрядов числа . Если , в следующем такте делится пополам левый полуинтервал, а при попадании . в правый полуинтервал (т.е. при )

Из сравнения таблиц видно, что предлагаемое устройство в зависимости 60 От разрядности формируемых чисел позволяет сократить объем памяти в 2,1-2,9 раза при сохранении точности 6 аппроксимации. Сокращение объема памяти ведет также к уменьшению раз- 65

в блоке 7 формируется сигнал . Поэтому блок 7 анализа формирует сигнал не только при , но и при Z 01, если , и при Z 11, если .

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

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

Таблица 1

Таблица 2

рядности регистра 1 и количества выходов дешифратора 2.

Предлагаемое устройство позволяе1 уменьшить погрешность аппроксимации заданного распределения, сохраняя примерно одинаковые с известным устройством аппаратурные затраты. Например, при формировании случайных чисел, з кон распределения которых отличаетс от показательного распределения не J6oлee чем ,00195, в известном устройстве требуется объем памяти в предлагаемом устройстве погрешность 6 0,00049 достигается при N 46 {см. табл. и 2). Таким обра зом предлагаемое устройство несмотря даже на некоторое уменьшение объ ма памяти (с 63 до 46) позволяет по ти в четуре раза повысить точность воспроизведения показательного распределения. Аналогичные характерист ки предлагаемое устройство имеет и при воспроизведении других законов распределения. Использование новых элементов регистров, счетчика, дешифратора, блока анализа, элемента ИЛИ выгодно отличает предлагаемый генератор от I известного, так как позволяет повысить точность воспроизведения задан ного распределения. Формула изобретения 1..Управляемый генератор случайны чисел, содержащий генератор тактовых импульсов, блок памяти, первый дешифратор, первый регистр памяти, выход которого через первый дешифратор соедк;;ен с первым входом блока памятн, 2лог: сраБЕ)ения, первый и второй бло:-:и элементов И, генератор равномерно расгфеделенных случайных величин, группа выходов которого соедине на с соответствующими входами первой группы блока сравнения, выход второго блока элементов И является выходом генератора, отличающийс я тем, что, с целью повышения точности, он содержит второй и третий регистры памяти, блок анализа г;.одоз, счетчик, второй дешифратор и элемент ИЛИ, причем первый и второй входы Пуск, а также первый и второй входы задания режима генератора тактовых импульсов соединены с первым и вторым входами генератора, п-ым (п - число выходов второго дешифратора) выходом второго дешифратора и первым выходом блока анализа кодов соответственно, первый выход генератора тактовых импульсов подключен к первому входу счетчика и к первому входу второго 5лока элементов И, второй и третий входы которого соединены с выходом третьего регистра памяти и выходом генератора равномерно распределенны случайных чисел соответственно, вто рой выход генератора тактовых импульсов соединен с первыми входами первого и второго регистров памяти, блока памяти и блока анализа кодов, первый выход блока памяти подключен к второму входу второго регистра памяти, выходы которого соединены с соответствующими входами второй группы блока сравнения, вход которого подключен к третьему выходу генератора импульсов, второй выход блока памяти подключен к второму входу первого регистра памяти, третий вход которого соединен с вторым выходом блока анализа кодов, второй и третий входы которого подключены к третьему выходу блока памяти и выходу блока сравнения соответственно, четвертый выход генератора тактовых импульсов соединен с входом генератора равномерно распределенных случайных чисел, группа выходов которого подключена к соответствующим входам первой группы первого блока элементов И, входы второй группы которого соединены с соответствующими выходами второго дешифратора, а выходы первого блока элементов И соединены с группой входов элемента ИЛИ соответственно, вход которого соединен с выходом блока сравнения, а выход элемента ИЛИ соединен с первым входом третьего регистра памяти, второй вход которого соединен с пятым выходом генератора тактовых импульсов, шестой и седьмой выходы которого подключены к второму входу счетчика и входу второго дешифратора соответственно, четвертый вход первого регистра памяти соединен с п-ым выходом второго дешифратора, группа входов которого подключена к выходам счетчика соответственно. 2. Генератор по п.1, отличающийся тем, что блок анализа кодов содержит четыре группы элементов И, элемент ИЛИ, элемент НЕ и два регистра памяти, первые входы которых образуют первый вход блока, второй вход которого соединен с вторыми входами регистров памяти, выход элементов И первой группы соединен с первым входом элемента ИЛИ, выход элементов И второй группы является первым выходом блока, выходы элементов И третьей и четвертой групп соединены соответственно с вторым и третьим входами элемента ИЛИ, выход Которого является вторым выходом блока, первый выход первого регистра памяти соединен с первыми входами элементов И первой и третьей групп, второй выход первого регистра памяти соедийен с первыми входами элементов И второй и четвертой групп, первый выход второго регистра памяти соединен с вторыми входами элементов И первой и второй групп, второй выход второго регистра памяти соединен с вторыми входами элементов И

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

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

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

63

.-Ll