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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик

«i>881759 (61) Дополнительное к авт. свид-ву(22) Заявлено 1601,80 (21) 2869905/18-24 с присоединением заявки HP— (23) Приоритет

Опубликовано15,1181, Бюллетень М 42

Дата опубликования описания 1511,81 (5!)М, Кл.

С 06 F 15/20

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

СССР по делам изобретений и открытий (53) УДК 681. 325 (088.8) (72) Авторы изобретения

Б.С.Антипин, С.N.Ìàñëåíí (71) Заявитель (54 ) УСТРОЙСТВО ДЛЯ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

ВЕРОЯТНОСТНОГО ГРАФА

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

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

Такие модели графа позволяют определить характеристики связанности графа с вероятностными ребрами путем определения электрической проводимости между соответствующими вершинами по результатам розыгрыша состояния ребер (1J .

Наиболее близким к изобретению является устройство для моделирования вероятностного графа, содержащее блок кодирования и декодирования команд с 3ВМ, электронный коммутатор с m+3 выходными шинами, m триггеров памяти, m управляемых ключевых схем, . m вентилей, логическую схему и триггер результата. Функционирование уст- Зо ройства происходит по циклам. Каждый цикл содержит тактовые моменты Т,> сброс триггеров памяти и триггера результата В„..., С; ..., :щ — выдача импульсов на вейтили,Vù+i — испытание схемы, отображающей граф, на проводимостью„„+ -съем информации с триггера результата (2) .

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

Р(-е)=Е Р (1) p. (t), (ц вз. i где Р (t ) - вероятность безотказной работы системы к моменту времени Т

P (i) — вероятность выполнениязадачи системой в состоянии с i отказами.

Р; (t) . — вероятность состояния системы с 1 отказами к моменту времени с

m — количество звеньев, из которых состоит модель исследуемой системы.

Значение Р; (t), как правило, определяется расчетными методами, а значение Р«() при достаточно

881759 больших tII — методом статистических испытаний модели системы.

Очевидно, что оценить значение Р при отказах можно, определив число успешных реализацийП„,„,{наличие проводимости описывающего сйстему графа с 1 разомкнутыми ребрами) на общее число испытаний П;, в которых было 1 отказов (разомкнуто 1 ребер графа). Следовательно, задачей статических испытаний графа в этом случае будет получение оценок вероятностей (), \= 1 п т.е. определение зйачений Р „; и П; в процессе испытаний.

Известное устройство позволяет в каждом цикле испытания оценивать проводимость (связность) вероятностного графа и получать суммарную вероятность выполнения задачи Р однако при этом невозможно выделить значения P>>(I), используемые в со- 20 отношении P1) .

Цель изобретения — расширение функциональных возможностей известного устройства при исследовании вероятностных графов путем определения

Р Я, т.е. определения показателеЙ моделируемых графов.

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

И второй группы, вторые входы и выходы которых являются соответственно 45 группой входов и группой выходов устройства, выходом которого является второй выход коммутатора, введены вторая группа триггеров, третья группа элементов. И, первая и вторая груп. — ц пы счетчиков, счетчик, дешифратор, элемент ИЛИ, входы которого подключены соответственно к выходам элементов И первой группы, а выход элемента ИЛИ соединен со входом счетчика,, выходы которого соединены со входами дешифратора соответственно, управляющий вход которого подключен к третьему выходу коммутатора, первый выход которого соединен со входом "Сброс" счетчика и с нулевыми входами триггеров второй группы, единичные входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы соответственно, а выходы триггеров второй группы соединены со- 65 ответственно с первыми входами элементов И третьей группы, вторые входы которых объединены и являются входом устройства, а выходы элементов И третьей группы соединены со счетными входами счетчиков второй группы соответственно.

На чертеже приведена блок-схема устройства.

Устройство содержит генератор случайных чисел 1, тактовый выход которого соединен со входом коммутатора 2, а стохастический выход — с первыми входами элементов И 3, вторые входы которых соединены с выходами коммутатора 2, а выходы — c единичными входами триггеров 4,нулевые входы которых подключены к первому выходу коммутатора 2, а выходы к первым входам элементав И 5. Выходы элементов И 3 через элемент ИЛИ б, счетчик 7, дешифратор 8 подключены ко входам счетчиков 9 и к единичным входам триггеров 10, нулевые входы которых объединены со входом счетчика

7 и с выходом коммутатора 2, другой выход которого соединен со входом дешифратора 8. Выходы триггеров 10 через элементы И 11 соединены со входами счетчиков 12.

Устройство работает по циклам, каждый из которых содержит тактовые моменты Т<, Т,..., 7„..., 2

Т

В эти моменты в коммутаторе 2 формируются импульсы, которые выдаются на соответствующие выходные шины. Под действием импульса, поступающего по нулевой шине коммутатора 2, триггеры

4 устанавливаются в "0" и открывают элементы И 5. В "0" сбрасываются также счетчик 7 и триггеры 10. В тактовый момент Т элемент И 3 открыт и при наличии импульса на его другом входе (выходе 2 генератора 1) триггер 4 переходит в состояние "1", закрывая элемент И 5. Наличие или отсутствие импульса на выходе 2 генератора 1 определяет соответственно наличие или отсутствие ребра графа в розыгрыше, соответствующем состоянию . Аналогично происходит функционирование в моменты Ч.2..., ..., ° °

Импульсы с выходов элементов

И 34,..., И 3,...,и Зщ поступают также через элемент -ИЛИ 6 на счетный вход счетчика 7, представляющего собой двоичный счетчик импульсов. Следовательно, в счетчике формируется двоичное число К (К=1,...,i,...m), соответствующее количеству разомкнутых ребер графа в каждом цикле работы устройства. В моментТщ, на шину

m+) коммутатора 2 выдается импульс опроса дешифратора 8, при этом число

К, записанное в счетчике 7, дешифрируется, и на К-ой выходной шине дешифратора 8 появляется импульс, который поступает на вход К-ro счетчи881759. ка состояний. Одновременно этот им пульс поступает на единичный вход триггера 10„, опрокидывает его и отпирает элемент И 11 по первому входу. В момент f +> на шину rn 2 коммутатора 2 выдается испытующий 5 импульс, который поступает на вход схемы, описывающей граф и набранной из элементов И 5. Если в данном розыгрыше граф оказывается связанным, то этот импульс проходит на выход описывающей схемы, к которому подключены вторые входы элементов И 11.

Поскольку открытым оказывается только элемент И 11 испытующий импульс записывается в 12 к счетчике успешных состояний. Если же граф оказывается несвязныьы . то импульса на выходе описывающей его схемы не будет и в счетчик 12„ ничего не запишется.

Затем цикл работы устройства повторяется.

Таким образом, по окончании процесса статистических испытаний в счетчиках 91,...,. 9j, 9m будут подсчитаны выпавшие с 1,... (,... п ра- 25 зомкнутыми ребрами n а в счетчиках

12,..., 121,...,12® только те из них, при которых граф был связан и„ д .

Оценка вероятности Р (i) получается из частного п„ ;! п 30

Устройство может быть реализовано на базе известных цифровых приборов, например,. интегральных микросхем. устройство позволяет расшиРить 35 класс моделируемых сложных систем, описываемых вероятностным графом, при сравнительно небольшом объеме используемого оборудования.

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Четвериков В.Н., Баканович Э.А, Меньков А.В. Вычислительная техника для статистического моделирования.

М., "Советское радио", 1978.

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

9 222754, кл. G 06 F 15/20, 1967 (прототип).

881759

Составитель A.Êàðàñoâ.

Техред М.Рейвес Корректор М.Шароши

Редактор Н.Ромжа

Заказ 9975/74 Тираж 748 Подписное

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

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

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