Вероятностное устройство для моделирования сложных стохастических систем Советский патент 1983 года по МПК G06F7/58 G06F15/173 G06F7/70 

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

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

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

Наиболее близким к предлагаемому является устройство для вероятностного моделирования, содержащее устройство (блок / управления, датчик (генератор ) равномерно распределенных случайных чисел, бл сравнения, регистр маски, регистр числа, запоминающее устройство (блок памятиJ и блок адреса (регистр адреса), разделенный на две части - старшую и младшую.

Устройство позволяет формировать последовательности случайных чисел с требуемыми законами распределения, а также марковские процесы. При этом реализуется метод обратных функций, основанный на сравнении равномерно распределенных случайных чисел со значениями воспроизводимой функции распределения F(x ) ,отыскании ин- , тервала, для которого F( x.)f F( Х| и выдаче соответствующего данному интервалу значения х.. Устройство позволяет также моделировать 2 различных законов распределения, где к - разрядность старшей части регистра гщреса. Выбор требумого закона осуществляется записью номера-требуемого закона в старшую часть регистра адреса. На каждом такте работы устройства формируются одновременно два разряда случайного числа С2 .

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

Цель изобретения - повышение быстродействия.

Поставленная цель достигается тем, что вероятностное устройство

для моделирования сложных стохастических систем, содержащее датчик равномерно распределенных случайных чисел, блок сравнения, первый вход которого соединен с выходом датчика равномерно распределенных случайных чисел, блок памяти, первый регистр числа, вход -которого соединен с выходом блока памяти, дополнительно содержит второй регистр числа, первый и второй блоки формирования адреса, коммутатор чис ла, коммутатор адреса, блок синхронизации, первый выход которого соединен с входом датчика равномерно распределенных спуч&йных чисел и первыми входами первого и второго блоков формирования адреса, второй выход соединен с управляющими входами первогого регистра числа, коммутатора с1.дреса и второго блока формирования адреса, а третий выход с управляющими Бxoдa и коммутатора числа, второго регистра числа и первого блока формирования адреса, второй вход блока сравнения соединен с выходом коммутатора числа, а выход - с втЪрыми входами первого и второго блоков формирования адреса, выходы которых соединены соответственно с первым и вторым вхдами коммьта;тора адреса, выкод коммутатора сздреса соединен с входом блока памяти, к выходу которого подключен вход второго регистра числа, выходы первого и второго регистров числа соединены соответственно с первым и вторым вxoдa И коммутатора числа.

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

На фиг, 1 приведена блок-схема 60 устройства} на фиг. 2 - функциональная схема блока формирования адреса/ на фиг. 3 - функциональная схема блоK:j синхронизации; на фиг. 4 - временные диаграг уи управляющих сигна65 OS. , Устройство (фиг. 1) содержит да чик 1 равномерно распределенных слу чайных чисел, блок 2 сравнения, ком мутатор 3 числа, первый 4 и второй 5 регистры числа, блок 6 памяти, ко мутатор 7 адреса, первый 8 и второй 9блоки формирования адреса и блок 10синхронизации. Каждый блок формирования алреса (фиг. 2) содержит первый-11 и второ 12 регистры, элемент 13 задержки и первый 14 и второй 15 элементы И. Каждый из регистров блока формирования адреса состоит из групп 16 триггеров. Блок синхронизации фиг. 3 содержит генератор 17 импульсов, триггер 18 и элемент 19 задержки. Выход датчика 1 равномерно распределенных случайных чисел соединен с первым входом блока 2 сравнения, второй вход которого соединен с выходом коммутатора 3 числ а выход - с вторыми входами первого 8 и второго 9 блоков формирования адреса. Первый выход блока 10 синхронизации соединен с входом датчика 1 равномерно распределенных случай ных чисел и первыми входами первого 8 и второго 9 блоков формирования адреса,: выходы которых соединеныответственно с первым и вторым вхо дами коммутатора 7 адреса. Выход коммутатора 7 адреса соединен с вхо дом бЛока б памяти, выход которого соединен с информационными входами первого 4 и второго 5 регистров числа. Выходы первого 4 и второго регистров числа соединены соответственно с первым и вторым входами коммутатора-3 числа. Второй выход блока 10 синхронизации соединен с управляющими входами первого регист ра 4 числа, коммутатора 7 адреса и второго блока 9 формирования адрес а третий выход - с управляющими вхо дами коммутатора 3 числа, второго регистра 5 числа и первого блока 8 формирования адреса. Вход элемента 13 задержки в блок формирования адреса соединен с первым входом первого регистра 11 и яв ляется первым входом первого регистра 11 и является первым входом блока, а выход - с первыми входами первого 14 и второго 15 элементов И Вторые входы первого 14 и второг 15 элементов И соединены соответственно с вторым и третьим входами первого регистра 11,- а выходы соответственно с первым и вторым входами второго-регистра 12, группа выходов которого является вы ходом блока. Групра входов первого .регистра 11 является вторым входом блока, а группа выходов соединена с группой входов второго регистра 12. Управляющие входы первого 11 и второго 12 регистров подключены к управляющему входу блока. Блок 10 синхронизации может быть выполнен из широкого набора известных одноименных блоков. Пример реализащш блока 10 синхронизации, удовлетворяющего требованиям.предлагаемого устройства,приведен на фиг.3, Устройство работает следую м образом. Датчик 1 равномерно распределен|ных случайных чисел формирует неза;висимые равномерно распределенное на интepBJaпe 0-1 случайные числа. В момент включения устройства на выходе датчика 1 вырабатывается первое случайное число. Дальнейшая синхронизация его работы выполняется импульсами С, поступающими с первого выхода блока 10 синхронизации. Очередное число вырабатывается датчиком 1 по окончании сигнала С. Коммутатор 3 числа подключает к входу блока 2 сравнения выход регистра 4 или выход регистра 5 коммутатор 7 адреса подключает к адресному входу блока б памяти выход блока 8 или блока 9 формив рования адреса. При поступлении f единичного сигнала на управляющий вход любого из коммутаторов на его выход подключается первый вход-коммутатора, при нулевом сигнале на управляющем входе на выход подключается второй вход коммутатора. Кодовые слова, настраиваюйще устройство на формирование случайных чисел с требуемой функцией распределения, записываются в блок б памяти. В одной ячейке записывается В 1 кодовых слов. Регистры 4 и 5 числа служат для хранения считываемых из блока б памяти кодовых слов. При разрешающем единичном сигнале на втором выходе блока 10 управления ) запись кодовых слов с выхода блока б памяти выполняется в регистр 4, при разрешающем единичном сигнале на третьем выходе блока 10 (.1 запись кодовых слов выполняется в регистр 5. Блок 2 сравнивает Е 2-1 знач;ений А, А,..., Ag с равномерно распределенным числом S , R результате сравнения на выходе блока 2 формируется т-разрядное слово q по гфавилу О, при О S : л. 1, при е -1, при А Ag, 2 , при А g 1 .

Блоки 8 и 9 формирования адреса служат для формирования случайного числа и поочередно являются адресными регистрами блока 6 памяти. На каждом такте работы устройства в одном из блоков формирования адреса формируется m разрядов случайного числа, другой является адресным регистром блока 6 памяти, что обеспечивается подключением выходов соответствующего блока адреса коммутатором 7 на вход блока б памяти. Регистры 11 и 12 блоков 8 и 9 выполнены на однотактных синхронизируемых 1) -триггерах группы 16 с синхронными установочными входами. Запись информации в триггер группы 16 может осуществляться как по установочным R - и 5 -входам, так и по и -входу по синхроимпульсу на С-входе при разрешающем сигнале на V -входе триггера.

Случайное п -разрядное число фор мируется за К шагов, п с m. Алгоритм формирования построен на объединении методов условных вероятностей и обратных функций. Моделирование m разрядов внутри шага осуществляется по методу обратных функций путем сравнения равномерно распределенного числа I со значениями условной функции распределения F(хгде 5 - случайное число, сформированное на предыдущих шагах. Вычисление условных функций распределения

р5(х|) осуществляется по методу условных вероятностей.

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

0 считывания кодов на блоке памяти,

It - число обращений к блоку памяти при формировании одного случайного числа, С2 - время сравнения кодов и формирования m разрядов случай5 ного числа, то, пренебрегая временем переключения коммутаторов, среднее время формирования числа в предлагаемом устройстве вычисляется по формуле

Т 4

1 7/г;2;

при

при t-;, С .

Среднее время формирования случайного числа в .устройстве без совмес щения Tg-k (.f ) следовательно, „„„„..„„„ щзоизводительности

дт

повышение

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

1. ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЛОЖНЫХ СТОХАСТИЧЕСКИХ СИСТЕМ, содержащее датчик равномерно распределенных случайных чисел, блок сравнения, первый вход которого соединен с выходом датчика равномерно распределенных случайных, чисел, блок памяти, первый регистр числа, вход которого соединен- с выходом блока памяти, отличающееся тем, что, с целью повыпдания быстродействия, оно дополни-. тельно содержит второй регистр числа, первый и второй блоки формирования адреса, коммутатор числа, коммутатор адреса, блок синхронизации, первый выход которого соединен с входом датчика равномерно распределенных случайных чисел и первыми входами первого и второго блоков формирования гщреса, второй выход соединен с управляющими-входами первого регистра числа, коммутатора адреса и второго блока формирования адреса, а третий выход - с управляющими входами коммутатора числа, второго регистра числа и первого блока формирования адреса, второй вход блока сравнения соединен с выходом коммутатора числа, а выход - с вторыми входами первого и второго блоков формирования адреса, выходы которых соединены соответственно с первым и вторым входами коммутатора адреса, выход коммутатора адреса соединен с входом блока памяти, к выходу которого подключен вход второго регистра числа, выходы первого и второго регистров: числа соединены соответственно с первым и вторым входами коммут атора числа. 2i Устройство по п. 1, отличающееся тем-, что, блок фор(Л мирования адреса содержит первый и второй регистры, первый и второй элементы И и элемент задержки, вход которого соединен с первым входом первого регистра и является первым входом блока, а выход соединен с первыми входами первого и второго элементов И, вторые входы первого и второго элементов И соединены соответСП ственно с вторым и третьим входами первого регистра, а выходы соединесо ел ны соответственно с первым и вторым входами второго регистра, группа выходов которого является выходом 00 блока, группа входов первого регистра является вторым входом блока, а группа выходов соединена с группой входов второго регистра, управляющие входы первого и второго регистров подключены к управляющему входу блока.

Риг. 2

«риъЗ

Фиъ 4