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

 

УСТРОПСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕРОЯТНОСТНОГО ГРАФА, содержащее генератор случайных чисел, коммутатор , первую, вторую и третью группы элементов И, первую и вторую группы счетчиков, первые входы и выходы элементов И первой группы являются .соответственно группой информационных входов и группой информационных выходов устройства, первый выход коммутатора является управляющим выходом устройства, выходы элементов И .второй группы соединены с входами счетчиков первой группы о тличающееся тем, что, с целью сокращения аппаратурных затрат; в устройство введены m-разрядный регистр сдвига (т - максимальное число ребер моделируемых граф), (т+1)-разрядный регистр сдвига, триггер, три элемента И, элемент задержки и элемент НЕ, причем второй .выход коммутатора соединен с единичными входами первых разрядов, нулевыми вхбдами 2,3,... ,к разрядов п разрядного регистра сдвига, 2,3,..., ..., (т+1) разрядов () -разрядного регистра сдвига и нулевым входом триггера, тактовый выход генератора случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (т+1)-разрядного регистра сдвига, выходы которого, кроме (т+1)-го, соединены с вторыми входами элементов И первой группы, (т+1)-й выход (т+1)разрядного регистра сдвига соединен о ® через элемент задержки с вторым входом первого элемента И и входом л элемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу третьего элемента И, выходы которых соединены соответственно со сдвиговыми №-раз рядного и ()-разрядного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий со выход которого соединен с первыми о входами элементов И второй группы, Кд . вторые входы которых соединены с со выходами tn-разрядного регистра сдвига, а выходы - с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы а вторые входы объединены и соединены с выходом триггера, единичный вход которого является управляющим .входом устройства.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1119023 г

З 511 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3527988/18-24 (22) 23 ° 12.82 (46) 15.10.84. Бюл. Ф 38 (72) Н.Ф. Морозов и В.Д. Трусов (71) Институт технической кибернетики АН БССР (53) 681 ° 325 (088.8) (56) 1. Авторское свидетельство СССР .Р 222754, кл. G 06 F 15/20, 1967.

2. Авторское свидетельство СССР

Ф 881759, кл. G 06 F 15/20, 1980 (прототип). .(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕРОЯТНОСТНОГО ГРАФА, содержащее генератор случайных чисел, коммута- тор, первую, вторую и третью группы элементов И, первую и вторую группы счетчиков, первые входы и выходы элементов И первой группы являются соответственно группой информационных входов и группой информационных выходов устройства, первый выход коммутатора является управляющим выходом устройства, выходы элементов И второй группы соединены с входами счетчиков первой группы, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат; в устройство введены rn-разрядный регистр сдвига (rn — максимальное число ребер моделируемых граф), (m+1)-разрядный регистр сдвига, триггер, три элемента И, элемент задержки и элемент НЕ, причем второй выход коммутатора соединен с единичными входами первых разрядов, нулевыми вхддами 2,3,...,m разрядов m —разрядного регистра сдвига, 2,3,..., ..., (m+1) разрядов (в+1) -разрядного регистра сдвига и нулевым входом триггера, тактовый выход генератора .случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (m+1)-разрядного регистра сдвига, выходы которого, кроме (в+1)-го, соединены с вторыми входами элементов И первой группы, (м+1)-й выход (m+1)разрядного регистра сдвига соединен через элемент задержки с вторым е входом первого элемента И и входом элемента НЕ, выход которого подключен к третьему входу второго элемента

И и второму входу третьего элемента

И, выходы которых соединены соответ- Я .ственно со сдвиговыми вхоДами в-раз рядного и (m+1)-разрядного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с Ю выходами m-разрядного регистра сдвига, а выходы — с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единичный вход которого является управляющИм входом устройства.

1 11190

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

Известно устройство д-.я моделирования вероятностного графа, содержа.щее блок кодирования и декодирования команд, поступающих от 3ВМ. электронный коммутатор с m+3 выходными шинами, m триггеров памяти, m управляемых ключевых схем, п вентилей, логическую 5 схему и триггер результата. Функционирование устройства происходит по циклам. Каждый цикл содержит тактовые моменты -сброс триггеров памяти и триггера результата Т „ ...,,и,, °

-выдача импульсов на вентили,,„ -испытание схемы отображающей граф на проводимость, „„ — съем информации с триггера результата (1 ).

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

ЗВИ.

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

"Сброс" счетчика и с нулевыми входами триггеров второй группы, единичные

23 2 входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы, выходы триггеров второй группы соединены с первыми входами элементов И третьей группы, вторые входы которых объединены и являются входом устройства, а выходы соединены с входами счетчиков второй группы (2 j.

Недостаток устройства заключается в большом количестве оборудования.

Кроме того, наличие дешифратора затрудняет расширение устройства.

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

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

И второй группы соединены с входами счетчиков первой группы, дополнительно введены м-разрядный регистр сдвига, (m+1)-разрядный регистр сдвига, триггер, три элемента И, элемент задержки, элемент НЕ; причем второй выход коммутатора соединен с единичными входами первых разрядов, нулевыми входами 2,3,...,э, разрядов в-разрядного регистра сдвига, 2,3,..., ..., (а+1) разрядов (я+1) -разрядного регистра сдвига и нулевым входом триггера, тактовый выход генератора случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (m+1)-разрядного регистра сдвига, выходы которого, кроме (m+1)-го, соединены с вторыми входами элементов

И первой группы, (в+1)-й выход (m+1) разрядного регистра сдвига соединен через элемент задержки с вторым входом первого элемента И и входом элемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу третьего элемента И, выходы которых соединены соответственно с сдвиговыми входами m-разрядного и (ra+1) разрядного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий з 11190

1 выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходами ы-разрядного регистра сдвига, а выходы — с первыми входами элементов И третьей группы, выходы которых

5 подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единичный вход которого является управляю10 щим входом устройства.

На фиг.1 изображена структурная схема устройства; на фиг.2 — вариант набора схемы графа; на фиг.3 — граф.

Устройство содержит генератор 1

15 случайных чисел, элементы И 2 — 4, (m+1)-разрядный регистр 5 сдвига, первую группу элементов И 6„,6 ...,6, элемент 7 задержки, элемент

НЕ 8 m -ðàçðÿäíûé регистр 9 сдвига

Э

20 коммутатор 10, триггер 11, вторую группу элементов И 12 „,12,....,12

° ° ° » ...,13П„ третью группу элементов

И 14„,142,...,14„„ âòîðóþ группу счетчиков 15,15,..., 15„„ элемент

И 16 (фиг.2) °

Устройство работает следующим образом.

В исходном состоянии (m+1)-й разряд регистра 5 сдвига установлен в единичное состояние. В результате . подготовлен к работе элемент И2.Импульс с тактового выхода генератора 1 случайных чисел проходит через элемент И2 на вход коммутатора 10, и 35 появляющийся на первом выходе коммутатора 10 импульс устанавливает в нулевое состояние триггер 11, устанавливает в единичное состояние первые разряды и сбрасываеТ остальные разряды регистров 5 и 9 сдвига. На выходе (п +1)-го разряда регистра,5 сдвига появляется нулевой сигнал, который, пройдя через элемент 7 задержки, запрещает прохождение следую-45 щих импульсов на вход коммутатора

10 и разрешает, пройдя через элемент

НЕ 8, прохождение импульсов через элементы ИЗ и И4. Следующий импульс с тактового выхода генератора про- 50 ходит через элемент И4 на вход регистра 5 сдвига, сдвигая содержимое на один разряд и одновременно занося в первый разрядин ормацию осостоянии . стохастического выхода генератора 1. 55

Ы то же время импульс с тактового . выхода через элемент ИЗ попадает на вход сдвига регистра 9 сдвига только

23 4 тогда, когда на стохастическом выходе генератора присутствует единица.

Каждый прошедший импульс сдвигает информацию (единицу в первом разряде) на один разряд и заносит в первый разряд регистра 9 нуль, так как информационный вход регистра 9 соединен с входом сигнала логического "0". Последующие импульсы действуют. аналогично.

После прохождения m импульсов на вход регистра 5 сдвига единица попадает в (ra+1)-ый разряд и единичный. сигнал, задержанный на элементе 7 задержки на время, достаточное для прохождения заднего фронта импульса, сдвинувшего единицу в (m+1)-ый разряд регистра 5, разрешает прохождение последующих импульсов на вход коммутатора 10 и запрещает, пройдя через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И4 на входы регистров 5 и 9 сдвига. Таким образом, в регистре 5 сдвига в первых ю разрядах формируется информация о наличии или отсутствии ребер графа (1-е ребро присутствует, 0 ребро отсутствует), а в регистре 9 сдвига единица устанавливается только на выходе первого разряда, если в текущей реализации отсутствуют ребра графа (отказ rn ребер графа) на выходе второго разряда, если в текущей реализации присутствует одно ребро (отказ в-1 ребер),..., на выходе m-го разряда, если в текущей реализации присутствует одно ребро (отказ rn-1 ребер),..., на выходе m-го разряда, если присутствует m-1 ребер (отказ одного ребра).

Последующие импульсы с тактового выхода генератора I проходят через элемент И2 на вход коммутатора 10, в результате появляется импульс на втором выходе коммутатора 10, который поступает на вход схемы, граф набранной из элементов И6. Если в данной реализации граф оказывается связанным, то импульс проходит на выход схемы граф, к которому подклю-. чен единичный вход триггера 11, устанавливая его в единицу. Если же граф оказывается несвязанным, то импульса на выходе схемы не будет,и триггер 11 останется в нулевом состоянии. Появляющийся затем на третьем выходе коммутатора tO импульс опрашивает состояние разрядов регистра 9 сдвига, и в зависимости

1119023 от установленного в единицу разряда появляется импульс на выходе k -го элемента И второй группы элементов

И12, поступая на счетный вход K -го счетчика первой группы элементов И14.

Если триггер 11 установлен в единицу, то импульс поступает на счетный вход k --ro счетчика второй группы счетчиков 15. Затеи цикл работы устройства повторяется.

Таким образом, по окончании процесса статистических испытаний ,в счетчиках 13„,...,13,...,13

1 подсчитываются реализации выпавшие с ь „,..., 1,...,1 разомкнутыми ребрами h; à в счетчиках 15„ ° ... 15> ...,15„, только те из них, при которых граф связан n „; . Оценка вероятности получается из частного n> Ä;/q, Устройство для статистического моделирования вероятностного графа легко расширяется при увеличении количества звеньев моделируемой системы путем добавления разрядов регистров сдвига, элементов И и счетчиков.

11 19023

Г 3

l

6 О Й к О

Составитель С. Назаров

Редактор Н. Воловик -Техред .С.Мигунова Корректор 0. Луговая

Заказ 7455/37

Тираж 698 Подписное

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

113035, Москва, Ж-35, Рауаская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4