Устройство для вероятностного моделирования

т 1 ц 488212 Сояз Сосетских Социалистических реслубликГосударственный комитет Сооета Миннстрое СССР(53) УДК 681.3(088.8) ло делам изобретений и открытий(72) Автор изобретения В. М. Захаров Казанский ордена Трудового Красного Знамени государственный университет им. В. И. Ульянова-Ленина(54) УСТРОЙСТВО ДЛЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ Изобретение относится к области вычислительной техники и предназначено для моделирования случайных процессов, Оно может быть применено как самостоятельное устройство, так и совместно с ЭВМ.Известно устройство для вероятностного моделирования, содержащее генератор равномерно распределенных случайных чисел, блок сравнения, блок управления, регистр адреса, регистр числа, блок памяти, блок логарифмического перебора,Функционирование устройства основано на логарифмическом способе выборки информации из блока памяти, что и определило достоинства устройства; относительно высокое быстродействие и возможность применить наиболее простой тип памяти - память с адресной выборкой информации.Недостатком известного устройства является сложность его схемного решения.Целью изобретения является упрощение устройства.Поставленная цель достигается тем, что устройство содержит регистр маски, первый вход которого соединен со вторым выходом блока сравнения, второй вход - с пятым выходом блока управления, третий вход в с выходом регистра числа, первый выход - с третьим входом блока сравнения, а второй выход в с третьим входом регистра адреса. Эти отличия позволяют, во-первых, реализовать логарифмический перебор без специального узла - блока логарифмического перебора и, во-вторых, применить логарифмический перебор по основаншо логарифма, большему 2-х, что увеличивает быстродействие и уменьшает количество ячеек блока памяти (например, прп основании логарифма, равном 4, быстродействие увеличивается в 2 ра за, количество ячеек уменьшается в 4 раза).Уменьшение количества ячеек блока памяти уменьшает сложность электронного управления (запись-считывание) блока памяти (известно, что сложность электронного управле ния памяти с адресной выборкой информации определяется в основном количеством ячеек). Кроме того, цепь обратной связи дает возможность получать кроме дискретных случайных величш более сложные процессы, например цепи Маркова.На чертеже изображена функциональнаясхема устройства, где обозначено:1 - генератор равномерно распределенныхслучайных чисел; 2 - блок сравнения; 3 - регистр маски; 4 - регистр числа; 5 - блок памяти; б - регистр адреса; 7 - блок управления,Генератор 1 служит для получения исходного случайного числа, Вход его соединен с 30 блоком управления 7, а выход - с блоком 2.Блок 2 служит для параллельного сравнениягруппы граничных значений интервалов разбиения области определения формируемойслучайной функции с исходным случайнымчислом. Входы блока 2 соединены с блоками1, 7 и регистром 3, выходы - с регистрами 3и 6.Регистр маски 3 служит для маскированияразрядов регистра 4.Цель маскирования - в заданный такт работы устройства снимать информацию толькос определенной части разрядов ячейки блокапамяти, Выходами регистр маски соединен сблоком 2 и регистром 6, входами - с блоками 2 и 7. Регистр 4 соединен с выходом блока 5 и служит для приема содержимого ячеекблока памяти 5 и его хранения на время операции сравнения.Блок 5 служит для хранения кода функциираспределения и ее аргументов.Регистр адреса 6 соединен с входом блока5. Он разделен на две части - младшую истаршую, Младшая часть указывает месторасполокения отдельных ячеек блока памяти.Старшая часть регистра указывает место расположения массива ячеек. Вход младшей части соединен с блоком 2, вход старшей части - с регистром 3.Блок управления 7 служит для синхронизации всей работы устройства;Принцип работы устройства состоит в следующем,Получение случайных чисел Х,(з=1, 2и) с заданным законом распределения Р(Х;)основано на сравнении равномерно распределенных случайных чиселсо значениямиР(Х;), отыскивании интервала, где выполняется условиеР(Х,) (,(Р(х;,),и выдачи соответствующего данному интервалу значения ХДля реализации соотношения (1) все значения Р(Х;) разбиты на группы. Группы выбираются из блока памяти логарифмическимперебором и каждая группа сравнивается счисломпараллельно,Логарифмический перебор осуществляетсяупорядоченным расположением значенийР (Х,) и Х, по группам.Реализация логарифмического перебора(например, по основанию логарифма, равном4) может быть решена следующим образом.Блок 2 содержит три цифровые схемысравнения, одни входы которых подключенык блоку 1 (генератору случайных равномернораспределенных чисел), а другие - к блоку 3(регистру маски) и два двухвходовых вентиля,Каждая схема сравнения имеет два выходадля фиксирования результатов сравнениябольше и меньше и равно. Эти выходысоединены с входами вентилей по принципудифференциального анализатора. В итогеблок 2 имеет 4 выхода. Такое соединение выходов схем сравнения необходимо, чтобы при сравнении группы значений Р(Х,) (эти значения берутся в порядке монотонного возрастания) на одном из 4-х выходов блока 2 и только на одном появлялся сигнал 1, т, е.в результате операции сравнения на выходах блока 2 появляется код, имеющий вид;1 О О О О 1 О О 1 О или илиилиО О 1 О О О О 1По этомч коду (по сигналу 1) фиксируется один из 4-х одновременно сравниваемых 15 интервалов.Указанный код поступает в младшую частьрегистра 6. Эта часть регистра представляет собой сдвиговый регистр, разделенный на 4 группы разрядов. Каждая из этих групп 20 соединена с одним из выходов блока 2. Такимобразом, сигнал 1 с выхода блока 2 может поступить в одну, и только одну, из 4-х групп сдвигового регистра 6. Сигнал 1 поступает в первый разряд. Перед проведением очеред ного такта сравнения 1 сдвигается в соседний разряд. Сдвиг производится по сигналу, поступающему из блока управления 7, По полученному таким образом в сдвиговом регистре коду, как по адресу, производится вы борка информации из блока памяти,Например, пусть а=64(з=1,64) и пусть основание логарифма равно 4, тогда для реализации соотношения (1) необходимо три такта. В первый такт проверяются условияР(Х 1)(Р(хзв)1 (Х 1 в) 4( Р (Хз з)Р(Х) (в(Р(ХЯз)40 Р (Хяз). ( Р (Хв 4)Пусть Ц попало в интервал Р(Х 1),Р(Х,тогда во 2-й такт проверяются условияР(Х,) (,(Р(Х,)Р(Х,) (;(Р(Х 1 з)(Х 12) щ в ( (Х 1 в)50 Пустьпопало в интервал Р(Х), Р(Х,Д,тогда в 3-й такт проверяются условияР(хзз) ( (Р(хзз)Р(Х) ;(Р(Х)Р(Х) (";(Р(х )Р(Х,) (,(Р(Х, )В эти три такта из блока памяти выбраныб 0три ячейки, в которых содержатся такие группы значенийР (Х 1 в)э Р (Хзз)1 Р (Х 4 з)1Р(х,), Р(х,), Р(х),б 5 Р(Х), Р(Х), Р(Х).10 15 20 25 30 35 40 45 50 Рассмотрим процесс образования адреса на этом примере.При гг=б 4 сдвиговый регистр имеет 12 разрядов (по 3 разряда в группе).При реализации 1-го такта сравнения групп значений Г(Х;): Р(Х), Р(ХЫ), Р(Х.8) выбираются из блока памяти по фиксированному адресу, например, по коду в сдвиговом регистре, имеющем вид000 000 000 000После сравнения этой группы значений на сдвиговом регистре возможны четыре несовпадающие комбинации вида001 000 000 000 000 001 000 000 000 000 001 000 000 000 000 001По этим адресам выбирается из блока памяти соответствующая группа значений Р(Х,). Единица сдвигается влево на один разряд и производится 2-й такт сравнения.После этого такта сравнения на сдвиговом регистре возможны 16 несовпадающих комбинаций вида011 000 000 000 010 001 000 000010 000 001 000 010 000 000 001001 010 000 000 000 011 000 000000 010 001 000 000 010 000 001001 000 010 000 000 001 010 000000 000 011 000 000 000 010 001001 000 000 010 000 001 000 010000 000 001 010 000 000 000 011По одному из этих адресов выбирается соответствующая группа значений Р(Х;) для проведения 3-го такта сравнения,В итоге мы имеем 21 несовпадающую комбинацию. Из описания логарифмического перебора в заявке видно, что для хранения всех групп значений Р(Х,) (при гг=б 4) тоже необходима 21 ячейка.За три такта цикл сравнений заканчивается, т. е. отыскивается один из 64-х интервалов, в который попало случайное число .Для реализации каждого из этих условий параллельным способом блок сравнения 2 должен содержать три схемы сравнения.В общем случае число значений Г(Х;) в одной ячейке равно а - 1, число значений Х; в одной ячейке равно а.Величина а выбирается из условия заданной длины ячейки и точности формирования закона распределения.После 3-го такта сравнения код цз блока 2 поступает в сдвиговый регистр, сдвигается на один разряд и по этому адресу выбирается из блока памяти ячейка, содержащая группу чисел значений Х; (в нашем примере в ячейке одновременно содержится четыре числа). Но так как каждому из 64 интервалов соответствует одно число, то из этих четырех чисел необходимо выбрать одно. Для этой цели служит регистр маски 3.Регистр маски может представлять собой регистр, состоящий из триггеров (или ряда вентилей), число которых равно числу разрядов в регистре числа 4, и разделенный на четыре части, каждая часть соединена с одним цз 4-х выходов блока 2.В процессе цикла сравнений регистр маски открыт для информации, поступающей с регцстра 4. После окончания цикла сравнений те части регистра маски, куда по выходам цз блока 2 поступили нули, закрываются. Открытой оаеся только одна асть, куда поступила 1, и с разрядов регистра числа 4 которые соответствуют этой открытой части,сшгмается число Х;. Прц формировании марковских цепей информация с регистра 4 через эту открытую часть регистра маски поступает (по шине, соедццяющей регистры 3 ц 6) в старшую часть реги:тра б. Эта информация определяет адрес, по которому происходит переход к следующей строке цепи.Вся информация в регистре 6 (в младшей ц старшей частях) перед новым очередным циклом сравнения сбрасывается на 0. Функционирует устройство следующим образом.Блок управления 7 выдает команду, покоторой генератор 1 вырабатывает ц выдаетв блок 2 случайное число ";, одновременно цзблока памяти через регистр 4 ц регистр маски 3 в блок 2 поступает группа значенийГ(Х,), где она сравнивается с числом ,В результате операции сравнения блок 2выдает код в младшую часть регистра 6. Поэтому коду из блока памяти выбирается ячейка, содержащая следующую очередную группу значений Г(Х,;). Этот цикл сравнений продолжается т =ой,гг тактов.Код, полученный на выходе блока 2 послеокончания этого цикла, поступает в младшуючасть регистра 6, где он служит адресомячейки, содержащей число Х;, ц одновременно он поступает в регистр маски для маскирования остальных а - 1 чисел Х;, содержащихся в этой же ячейке,Считывание Х;-го значения производится срегистра 4 через регистр маски 3.При формировании цепей Маркова описанный выше алгоритм функционирования устройства служит для реализации одной строкистохастической матрицы,Переход от одной строки к другой производится за счет действия цепи обратной связи,соединяющей регистр маски ц старшую частьрегистра 6. По этой связи текущее состояниецепи (число Х,) поступает в старшую часть регистра 6, где оно служит адресом массива ячеек, соединяющих значения Г(Х;) следующей строки стохастцческой матрицы. Текущее состояние цепи снимается с регистра 4 через регистр маски. Формула изобретения Устройство для вероятностного моделирования, содержащее генератор равномерно распределенных случайных чисел, вход кото488212 Составитель Э. СТехред Т, Курил Корректор А. Дзесов едактор Ь. Ианаказ 141/6ЦНИИ Тираж 679 комитета Совета Мпнистро ретений и открытий Раушская наб., д. 4/5ПодписноеСР Изд.1881сударственногопо делам изоМосква, Я(.35,ипография, пр. Сапунова, 2 рого соединен с первым выходом блока управления, блок сравнения, первый вход ко. торого соединен с выходом генератора равномерно распределенных случайных чисел, второй вход - со вторым выходом блока управления, а первый выход - с первым входом регистра адреса, второй вход которого соединен с третьим выходом блока управления, а выход - со входом блока памяти, выход которого подключен ко входу регистра числа,вход которого подключен к четвертому выходу блока управления, о тл и и а и щеес я тем, что, с целгио упрощения устройства, оно содержит регистр маски, первый вход которого соединен со вторым выходом блока сравнения, второй вход - с пятым выходом блока управления, третий вход - с выходом регистра числа, первый выход - с третьим входом блока сравнения, а второй выход - с 1 О третьим входом регистра адреса.