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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(61) Дополнительно (22) Заявлено 16.01,8 т. свид-ву(21) 2869905/18-2 1)М, К . С 06 Г 15/20 исо ниемза ударствеииый комитет. СССР о делам изобретений и открытий(53 681.325 (088.8) Дата опубликования описания 1511(72) Авторы изобретени в типин, С.М.Масле 1) Заявите 54) УСТРОЙСТВО ДЛЯ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАН ВЕРОЯТНОСТНОГО ГРАФА,кт опа Зн редел значеИзобретение относится к вычислительной технике и может быть использовано при статическом моделировании сложных систем, представленных в виде вероятностного графа, с целью определения качественных характеристик, в частности показателей надежности этих систем.Известны модели графа, содержащие запоминающие триггеры, управляемые кЛючевые схемы, которые входами управления подсоединены к выходам запоминающих триггеров и соединены между собой в схему, отображающую граф. Такие модели графа позволяют определить характеристики связанности графа с вероятностными ребрами путем определения электрической проводимости между соответствующими вершинами по результатам розыгрыша состояния ребер (11 .Наиболее близким к изобретению является устройство для моделирования вероятностного графа, содержащее блок кодирования и декодирования команд с ЭВМ, электронный коммутатор с и+3 выходными шинами, п 1 триггеров памяти,т управляемых ключевых схем, и вентилей, логическую схему и триггер результата. Функционирование уст- Зо ройства происходит по циклам. Каждыйцикл содержит тактовые моменты Тосброс триггеров памяти и триггера результатаВ, С; , ч;,1 - выдачаимпульсов на вейтили,Г,1,+ - испытание схемы, отображающей граф, на проводимость+ -съем информации стриггера результата 2).При статическом моделированиирафов, описывающих большой класс сложх систем, с целью определения поазателей надежности этих систем, часо пользуются следующей зависимостьюи.Р=1 РР, юв,з, 1где Р(с) - вероятность безотказнойработы системы к моменту времени ТРВ(1) - вероятность выполнения .задачи системой в состоянии сотказами,Р; (с) - вероятность состояниясистемы сотказамик моменту времени си - количество звеньев, изкоторых состоит модельисследуемой системыачение Р, (е), как правило,яется расчетными методами,ние Р 4(1 при достаточнобольших т - методом статистических испытаний модели системы.Очевидно, что оценить значение Р приотказах можно, определив число успешных реализацийп(наличие проводимости описывающего сйстему графа с 1 разомкнутыми ребрами) на общее число испытаний П;, в которых ,былоотказов (разомкнуто 1 ребер графа). Следовательно, задачей статических испытаний графа в этом случае будет получение оценок вероятностей(1), - 1 " щ т.е. определение зйачений Р ; и П; в процессе испытаний.Известное устройство позволяет в каждом цикле испытания оценивать проводимость (связность) вероятностного графа и получать суммарную вероятность выполнения задачи Р однако при этом невозможно выделить значения Р, используемые в со отношении1 .Цель изобретения - расширение функциональных возможностей известного устройства при исследовании вероятностных графов путем определения 5 РЯ, т.е, определения показателей моделируемых графов.Для достижения поставленной цели в устройство для статистического моделирования вероятностного графа, со-держащее генератор случайных чисел, тактовый и стохастический выходы которого соединены соответственно со входом коммутатора и с первыми входами элементов И первой группы, вторые входы которых подключены соответственно к группе выходов коммутатора первый выход которого соединен с нулевыми входами триггеров первой группы, единичные входы которых подключены соответственно к выходам элемен тов и первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы и выходы которых являются соответственно 4группой входов и группой выходов устройства, выходом которого являетсявторой выход коммутатора, введенывторая группа триггеров, третья группа элементов. И, первая и вторая груп. - цпы счетчиков, счетчик, дешифратор,элемент ИЛИ, входы которого подключены соответственно к выходам элементов И первой группы, а выход элемента ИЛИ соединен со входом счетчикавыходы которого соединены со входамидешифратора соответственно, управляющий вход которого подключен к третьему выходу коммутатора, первый выходкоторого соединен со входом "Сброс"счетчика и с нулевыми входами триггеров второй группы, единичные входыкоторых подключены к выходам дешифратора и к счетным входам счетчиковпервой группы соответственно, а выходытриггеров второй группы соединены со ответственно с первыми входами элементов И третьей группы, вторые входы которых объединены и являютсявходом устройства, а выходы элементов И третьей группы соединены сосчетными входами счетчиков второйгруппы соответственно.На чертеже приведена блок-схемаустройства.Устройство содержит генераторслучайных чисел 1, тактовый выходкоторого соединен со входом коммутатора 2, а стохастический выход - спервыми входами элементов И 3, вторые входы которых соединены с выходами коммутатора 2, а выходы - сединичными входами триггеров 4,нулевые входы которых подключены к первому выходу коммутатора 2, а выходык первым входам элементав И 5, Выходыэлементов И 3 через элемент ИЛИ б,счетчик 7, дешифратор 8 подключены ковходам счетчиков 9 и к единичным входам триггеров 10, нулевые входы которых объединены со входом счетчика7 и с выходом коммутатора 2, другойвыход которого соединен со входомдешифратора 8. Выходы триггеров 10через элементы И 11 соединены со входами счетчиков 12,Устройство работает по циклам,каждый из которых содержит тактовыемоменты оГщя+гВ эти моменты в коммутаторе 2 формируются импульсы, которые выдаютсяна соответствующие выходные шины. Поддействием импульса, поступающего понулевой шине коммутатора 2, триггеры4 устанавливаются в "0" и открываютэлементы И 5. В "0" сбрасываютсятакже счетчик 7 и триггеры 10. В тактовый момент Т элемент И З открыт и при наличии импульса на егодругом входе (выходе 2 генератора 1)триггер 4 переходит в состояние "1",закрывая элемент И 5. Наличие илиотсутствие импульса на выходе 2 генератора 1 определяет соответственно наличие или отсутствие ребра графа в розыгрыше, соответствующем состоянию Т 1 . Аналогично происходитфункционирование в моменты Ч.2., ,Импульсы с выходов элементовИ 34, И ЗИЗЕЙ поступаюттакже через элемент .ИЛИ б на счетныйвход счетчика 7, представляющего собой двоичный счетчик импульсов. Следовательно, в счетчике формируетсядвоичное число К (К=1, ,в),соответствующее количеству разомкнутых ребер графа в каждом цикле работы устройства. В моментТщ, на шинут+ коммутатора 2 выдается импульсопроса дешифратора 8, при этом числоК, записанное в счетчике 7, дешифрируется, и на К-ой выходной шине дешифратора 8 появляется импульс, который поступает на вход К-го счетчика состояний. Одновременно этот им пульс поступает на единичный вход триггера 10 , опрокидывает его и отпирает элемент И 11 по первому входу. В моментТ + на шину т 2 коммутатора 2 выдается испытующий 5 импульс, который поступает на вход схемы, описывающей граф и набранной из элементов И 5. Если в данном розыгрыше граф оказывается связанным, то этот импульс проходит на выход описывающей схемы, к которому подключены вторые входы элементов И 11. Поскольку открытым оказывается только элемент И 13 испытующий импульс записывается в 12счетчике успешных состояний. Если же граф оказывается несвязныьы то импульса на выходе описывающей его схемы не будет и в счетчик 12 ничего не запишется.Затем цикл работы устройства пов торяется.Таким образом, по окончании процесса статистических испытаний в счетчиках 91,,. 91 9 щ будут подсчитаны выпавшие с 1, , п ра зомкнутыми ребрамИ и;, а в счетчиках 1212112 п,только те из них, при которых граф был связан и д.Оценка вероятности Рполучается из частного и,; ) и 30Устройство может быть реализовано на базе известных цифровых приборов, например,. интегральных микросхем.Устройство позволяет расширить 35класс моделируемых сложных систем,описываемых вероятностным графом,при сравнительно небольшом объемеиспользуемого оборудования.40Формула изобретенияУстройство для статического моделирования вероятностного графа, содержащее генератор случайных чисел, так товый и стохастический выходы которого соединены соответственно со входом коммутатора и с первыми входами элементов И первой группы, вторые входы которых подключены соответственно к группе выходов коммутатора,первый выход которого соединен с нулевыми входами триггеров первой группы, единичные входы которых подключены соответственно к выходам элементов И первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы ивыходы которых являются соответственно группой входов и группой выходов устройства, выходом которого является второй выход коммутатора, о т-,л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения показателей моделируемых графовоно содержит вторую группу триггеров,третью группу элементов И, первуюи вторую группу счетчиков, счетчикдешифратор, элемент ИЛИ, входы которого подключены соответственно к выходам элементов И первой группы, авыход элемента ИЛИ соединен со входом счетчика, выходы которого соединены со входами дешифратора соответственно управляющий вход которогоподключен к третьему выходу коммутатора, первый выход которого соединенсо входом "Сброс" счетчика и с нулевыми входами триггеров второй группыединичные входы которых подключенык выходам дешифратора и к счетнымвходам счетчиков первой группы соответственно, а выходы триггеров второй группы соединены соответственнос первыми входами элементов И третьей группы, вторые входы которыхобъединены и являются входом устройства, а выходы элементов И третьейгруппы соединены со счетными входамисчетчиков второй группы соответственно.Источники информации,принятые во внимание при экспертизе1. Четвериков В.Н., Баканович Э.А,Меньков А.В. Вычислительная техникадля статистического моделирования.М., "Советское радио", 1978.2. Авторское свидетельство СССРУ 222754, кл. С 06 Г 15/20, 1967.Ромжа одпис ак илйал ППП "Патент", г.ужгород, ул,Проектная,4 5/74 Тираж 748ВНИИПИ Государственного копо делам изобретений и о113035, Москва, Ж, Рауш тета СССРрытийая наб., д.4/