Устройство для вероятностного моделирования Советский патент 1975 года по МПК G06F17/18 G06F7/58 

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

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

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

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

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

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

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

Получение случайных чисел Xi(i, 2,..., п) с заданным законом распределения F(Хг) основано на сравнении равномерно распределенных случайных чисел | со значениями F(Xi), отыскивании интервала, где выполняется условие

F(Xi)(),(1)

И выдачи соответствующего данному интервалу значения Xi.

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

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

Реализация логарифмического перебора (например, по основанию логарифма, равном 4) может быть решена следующим образом.

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

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

илиилиили

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

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

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

F(X,)F(X,, F(X,,),:F(X,,) F(X,,).(X,,)

F(X,,)(X,,)

Пусть I попало в интервал F(X), F{Xie), тогда во 2-й такт проверяются условия

F(X,},:F(X,) F(X,),F(X,} F{X,),:F(X,,)

(.)(.в)

Пусть I попало в интервал F(Xi2), F(Xi, тогда в 3-й такт проверяются условия F(X,,)F(X,,}

f(.Y,3)(;,,)

F(X,,),:F(X,,-)

f(,s)f(:e)

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

F(X,,-), F(X,,), F(X,,), F(X,), F(X,), F(X,,),

F(X,,), F(X,,), F(X,,. Рассмотрим процесс образования адреса на этом примере. При сдвиговый регистр имеет 12 разрядов (по 3 разряда в группе). При реализации 1-го такта сравиепия групп значений F{Xi)-. F{Xie), ), F() выбираются из блока памяти по фиксированному адресу, например, по коду в сдвиговом регистре, имеющем вид 000000000000 После сравнения этой группы значений на сдвиговом регистре возможны четыре несовпадающие комбинации вида 001000000000 000 001 000 000 000 000 001000 000 000 000001 По этим адресам выбирается из блока памяти соответствующая группа значений F(Xi). «Единица сдвигается влево на один разряд и производится 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 000010 001 000 000 010 000 001 001000 010 000 000 001 010 000 000000 011 000 000 000 010 001 001000 000 010 000 001 000 010 000 000 001 010 000 000 000 011 По одному из этих адресов выбирается соответствующая группа значений F(Xi) для проведения 3-го такта сравнения. В итоге мы имеем 21 несовпадающую комбинацию. Из описания логарифмического перебора в заявке видно, что для хранения всех групп значений F{Xi) (при п 64) тоже необходима 21 ячейка. За три такта цикл сравнений заканчивается, т. е. отыскивается один из 64-х интервалов, в который попало случайное число |. Для реализации каждого из этих условий параллельным способом блок сравнения 2 должен содержать три схемы сравнения. В общем случае число значений F(Xi) в одной ячейке равно а-1, число значений Xi в одной ячейке равно а. Величина а выбирается из условия заданной длины ячейки и точности формирования закона распределения. После 3-го такта сравнения код из блока 2 поступает в сдвиговый регистр, сдвигается на один разряд и но этому адресу выбирается из блока памяти ячейка, содержащая группу чисел значении X, (в нащем примере в ячеике одновременно содержится четыре числа). Но так как каждому из 64 интервалов соответствует одно число, то из этих четырех чисел необходимо выбрать одио. Для этой цели служит регистр маски 3. Регистр маски может представлять собой регистр, состоящий из триггеров (или ряда вентилей), число которых равно числу разрядов в регистре числа 4, и разделенный на четыре части, каисчая часть соединена с одним 3 4-х выходов блока 2. В процессе цикла сравнений регистр маски открыт для информации, поступающей с регистра 4. После окончания сравнений те части регистра маски, куда по выходам из блока 2 поступили «нули, закрываются. Открытой остается только одна часть, куда поступила «1, и с разрядов регистра числа 4, которые соответствуют этой открытой части, снимается число л,-. При формировании марковских цепей информация с регистра 4 через эту открытую часть регистра маски поступает (по щине, соединяющей регистры 3 и 6) в старщую часть регистра 6. Эта информация определяет адрес, но которому пронс.ходит переход к следующей строке цепи. Вся информация в регистре 6 (в младщей и старшей частях) перед новым очередным циклом сравнения сбрасывается на «О. Функционирует устройство следующим образом. Блок управления 7 выдает команду, по которой генератор 1 вырабатывает и выдает в блок 2 случайное число с, одновременно из блока памяти через регистр 4 и регистр маски 3 в блок 2 поступает группа значений F{Xi), где она сравнивается с числом g. В результате операции сравнения блок 2 выдает код в младщую часть регистра 6. По этому коду из блока памяти выбирается ячейка, содержащая следующую очередную группу значений F{Xi). Этот цикл сравнений продолжается m тактов. Код, полученный на выходе блока 2 после окончания этого цпкла, поступает в младщую часть регистра 6, где он служит адресом ячейки, содержащей число Xj, и одновременно он поступает в регистр маски для маскирования остальных а-1 чисел А ,-, содержащихся в этой же ячейке. Считывание Х{-го значения производится с регистра 4 через регистр маски 3. При формировании цепей Маркова описанный выще алгоритм функционирования устройства служит для реализации одной строки стохастической матрицы. Переход от одной строки к другой производится за счет действия цени обратной связи, соединяющей регистр маски и старщую часть регистра 6. По этой связи текущее состояние цени (число Xj) поступает в старшую часть регистра 6, где оно служит а рТсом.асТивГ ячеек, соединяющих значения К) сте ю щей строки стохастической атрицы Текущее г..„,Г„„чс.г.ии ма1рицы. 1екущее „.,.1,,.. 1 -Il.JUJ,-состояние цепи снимается с регистра 4 через регистр маски. Формула изобретения Устройство для вероятностного моделирования, содержащее генератор равномерно распределенных случайных чисел, вход которого соединен с первым выходом блока управления, блок сравнешш, первый вход которого соединен е выходом генератора равномерно распределенных случайных чисел, второй вход - со вторым выходом блока унравления, а нервый выход - с нервым входом регистра адреса, второй вход которого соединен с третьим выходом блока управления, а выход - со входом блока памяти, выход которого подключен ко входу регистра числа.

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