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

 

О П И С Л Н И Е Дззаа

ИЗОБРЕТЕНИЯ

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

Сотоз COLGTcKHx

Соцналнстнчес" .Hõ реслуслнк (61) огол пгсчьнос к -т ситд ьу (22) Заявлено 02.11.73 (21) 1968817/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 15,10.75. Бюллетень № 38

Дата опубликования описания 26.02.76 (51) М. Кл. G OGf 15, 20

G Обр 7/48

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

Совета Мнннстров СССР (53) УДК 681.3(088.8) ао делам нзобргтеннй и открытий (72) Автор изобретения

В. M. Захаров (71) Заявитель

Казанский ордена Трудового Красного Знамени государственный университет им. В. И. Ульянова-Ленина (54) УСТРОЙСТВО ДЛЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ

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

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

Недостатком известного устройства является сложность его схемного решения.

Целью изобретения является упрощение устройства.

Поставленная цель достигается тем, что устройство содержит регистр маски, первый вход которого соединен со вторым выходом блока сравнения, второй вход — с пятым выходом блока управления, третий вход в с выходом регистра числа, первый выход — с третьим входом блока сравнения, а второй выход — с третьим входом регистра адреса.

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

Уменьшение количества ячеек блока памяти уменьшает сложность электронного управления (запись-считывание) блока памяти (известно, что сложность электронного управле15 ния памяти с адресной выборкой информации определяется в основном количеством ячеек). Кроме того, цепь обратной связи дает возмо?кность получать кроме дискретных случайных величш; более слo?Kные процессы, Hапример цепи Маркова.

На чертеже изображена функциональная схема устройства, где обозначено:

1 — генератор равномерно распределенных случайных чисел: 2 — блок сравнения; 3— регистр маски; 4 — регистр числа; 5 — блок памяти; б — регистр адреса; 7 — блок управления.

Генератор 1 служит для получения исходного случайного числа. Вход его соединен с зо блоком управления 7, а выход в с блоком 2.

488212

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

1, 7 и регистром 3, выходы — с регистрами 3 и 6.

Регистр маски 3 служит для маскирования разрядов регистра 4.

Цель маскирования — в заданный такт работы устройства снимать информацию только с определенной части разрядов ячейки блока памяти, Выходами регистр маски соединен с блоком 2 и регистром 6, входами — с блоками 2 и 7. Регистр 4 соединен с выходом блока 5 и служит для приема содержимого ячеек блока памяти 5 и его хранения на время операции сравнения.

Блок 5 служит для хранения кода функции распределения и ее аргументов.

Регистр адреса 6 соединен с входом блока

5. Он разделен на две части — младшую и старшую. Младшая часть указывает место располо>кения отдельных ячеек блока памяти.

Старшая часть регистра указывает место расположения массива ячеек. Вход младшей части соединен с блоком 2, вход старшей части — с р ег истр о м 3.

Блок управления 7 служит для синхронизации всей работы устройства..

Принцип работы устройства состоит в следующем.

Получение случайных чисел X„(i =1, 2, ..., n) с заданным законом распределения F (X;) основано на сравнении равномерно распределенных случайных чисел (со значениями

F(X;), отыскивании интервала, где выполняется условие г (х,) а - (F (õ;+,), и выдачи соответствующего данному интервалу значения Х,.

Для реализации соотношения (1) все значения F (X;) разбиты на группы. Группы выбираются из блока памяти логарифмическим перебором и каждая группа сравнивается с числом E параллельно.

Логарифмический перебор осуществляется упорядоченным расположением значений

F (Х,) и Х, по группам.

Реализация логарифмического перебора (например, по основанию логарифма, равном

4) может быть решена следующим образом.

Блок 2 содержит три цифровые схемы сравнения, одни входы которых подключены к блоку 1 (генератору случайных равномерно распределенных чисел), а другие — к блоку 3 (регистру маски) и два двухвходовых вентиля.

Каждая схема сравнения имеет два выхода для фиксирования результатов сравнения

«больше» и «меньше» и «равно». Эти выходы соединены с входами вентилей по принципу дифференциального анализатора. В итоге блок 2 имеет 4 выхода. Такое соединение выходов схем сравнения необходимо, чтобы при сравнении группы значений F(X,) (эти значения берутся в порядке монотонного возрастания) на одном из 4-х выходов блока 2 и только на одном появлялся сигнал «1», т. е. в результате операции сравнения на выходах блока 2 появляется код, имеющий вид:

1 0 0 0

0 1 0 0

1О или или или

0 0 1 0

0 0 0 1

По этому коду (по сигналу «1») фиксируется один из 4-х одновременно сравниваемых

15 интервалов.

Указанный код поступает в младшую часть регистра 6. Эта часть регистра представляет собой сдвиговый регистр, разделенный на

4 группы разрядов. Каждая из этих групп

20 соединена с одним из выходов блока 2. Таким образом, сигнал «1» с выхода блока 2 может поступить в одну, и только одну, из 4-х групп сдвигового регистра 6. Сигнал «1» поступает в первый разряд. Перед проведением очеред25 ного такта сравнения «1» сдвигается в соседний разряд. Сдвиг производится по сигналу, поступающему из блока управления 7. По полученному таким образом в сдвиговом регистре коду, как по адресу, производится вы30 борка информации из блока памяти.

Например, пусть n=64(i=1,64) и пусть основание логарифма равно 4, тогда для реализации соотношения (1) необходимо три такта. В первый такт проверяются условия

F(X,) (! (F(A„)

F(x„) (;(г(х„)

F (A „) ((F (X„)

F (х„) («(F(xÄ)

Пусть попало в интервал (F(X,),Е(Х 6) j, тогда во 2-й такт проверяются условия

F(x,) (! (F(x4)

F(х,) «(F (x,)

Р (х,) (-; (Р (Х„) (х„) :(F(x,.)

50 Пусть g попало в интервал (F(Х ), F(Х 6), тогда в 3-й такт проверяются условия г(х„) «(F(x„)

F (х ) (c (F (X„) (X„) а ":(F (X„) (х,4) а ((х„)

В эти три такта из блока памяти выбраны б0 три ячейки, в которых содержатся такие группы значений г(х„), F(x„), (х,,), (х,), г(х,), г(х„), б5 F (Х! 3) F (Х14)) F (Х15)

488212

Рассмотрим процесс образования адреса на этом примере.

При п=б4 сдвиговый регистр имеет 12 разрядов (по 3 разряда в группе).

При реализации 1-го такта сравнения групп значений Г(Х;): F(X„), F(X ), F(X„) выбираются из блока памяти по фиксированному адресу, например, по коду в сдвиговом регистре, имеющем вид

000 000 000 000

После сравнения этой группы значений на сдвиговом регистре возможны четыре несовпадающие комбинации вида

001 000 000 000

000 001 000 000

000 000 001 000

000 000 000 001

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

F (X,). «Единица» сдвигается влево на один разряд и производится 2-й такт сравнения.

После этого такта сравнения на сдвиговом регистре возможны 16 несовпадающих комбинаций вида

011 000 000 000 010 001 000 000

010 000 001 000 010 000 000 001

001 010 000 000 000 011 000 000

000 010 001 000 000 010 000 001

001 000 010 000 000 001 010 000

000 000 011 000 000 000 010 001

001 000 000 010 000 001 000 010

000 000 001 010 000 000 000 Oll

По одному из этих адресов выбирается соответствующая группа значений F(X;) для проведения 3-ro такта сравнения.

В итоге мы имеем 21 несовпадающую комбинацию. Из описания логарифмического перебора в заявке видно, что для хранения всех групп значений F(X,) (при n=64) тоже необходима 21 ячейка.

3а три такта цикл сравнений заканчивается, т. е. отыскивается один из 64-х интервалов, в который попало случайное число .

Для реализации каждого из этих условий параллельным способом блок сравнения 2 должен содержать три схемы сравнения.

В общем случае число значений F (X;) в одной ячейке равно а — 1, число значений Х; в одной ячейке равно а.

Величина а выбирается из условия заданной длины ячейки и точности формирования закона распределения.

После 3-го такта сравнения код нз блока 2 поступает в сдвиговый регистр, сдвигается на один разряд и по этому адресу выбирается из блока памяти ячейка, содержащая группу. чисел значений Х; (в нашем примере в ячейке одновременно содержится четыре числа).

Но так как каждому из 64 интервалов соответствует одно число, то из этих четырех чисел необходимо выбрать одно. Для этой цели сл уж ит р ег истр м а с к и 3.

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

В процессе цикла сравнений регистр маски открыт для информации, поступающей с регистра 4. После окончания цикла сравнений те части регистра маски, куда по выходам нз блока 2 поступили «нулн», закрываются. Открытои Остается только Одна часть, куда поступила «1». и с разрядов регистра числа 4

10 которые соответствуют этой открытой части, сшгмается число Х;.

Прн формировании марковских цепей информация с регистра 4 через эту открытую часть регистра маски поступает (по шине, соединяющей регистры 3 и 6) в старшую часть реги=тра б. Эта информация определяет ад15 рес, по которому происходит переход к следу он(ей строке цепи.

Вся информация в регистре 6 (в младшей и старшей частях) перед новым очередным циклом сравнения сбрасывается на «О».

50 регистра 6, где оно служит aipeсoм массива ячеек, соединяющих значения F (X;) следующей строки стохастнческой матрицы. Текущее состояние цепи снимается с регистра 4 через регистр маски.

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

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

Блок управления 7 выдает команду, по которой генератор 1 вырабатывает и выдает

B блок 2 случайное число, одновременно нз блока памяти через регистр 4 и регистр маски 3 в блок 2 поступает группа значений

Г(Х;), где она сравнивается с числом .

В результате операции сравнения блок 2 выдает код в мла,1шую часть регистра 6. По этому коду из блока памяти выбирается ячейка, содержащая следующую очередную группу значений Г.(Х,;). Этот цикл сравнений продолжается т=log„n тактов.

Код, полученный на выходе блока 2 после окончания этого цикла, поступает в младшую часть регистра 6, где он служит адресом ячейки, содержащей число Х;, н одновременно он поступает в регистр маски для маскирования остальных а — 1 чисел Х;, содержащихся в этой же ячейке.

Считывание Х;-ro значения производится с регистра 4 через регистр маски 3.

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

Переход от одной строки к другой производится за счет действия цепи обратной связи, соединяющей регистр маски и старшую часть регистра 6. По этой связи текущее состояние цепи (число Х;) поступает в старшую часть

488212

Составитель Э. Сечихина

Техред Т. Курилко

Корректор А. Дзесова

Редактор Ь. Капкина

Заказ 141/6 Изд. № 1881 Тираж 679 Подписное

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

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

Типография, пр. Сапунова, 2 рог0 СОединен с первым вых0.10м блока управления, блок сравнения, первый вх0,1 ".îторого соединен с выходом генератора равномерно распределенных слу айных чисел, второй вход — со вторым выходом блока управления, а первый выход — с первым вхо", ом регистра адреса, второй вход которого соединен с третьим выходом блока управления, а выход — со входом блока памяти, выход которого подключен ко входу регистра числа, вход которого подключен к четвертому выходу блока управления, отли ающееся тем, что, с целгио упрощения устройства, оно содержит регистр маски, первый вход которого соединен со вторым выходом блока сравнения, второй вход — с пятым выходом блока управления, третий вход — с выходом регистра числа, первый выход — с третьим входом блока сравнения, а второй выход — с третьим входом регистра адреса.