Устройство для статистического моделирования вероятностного графа Советский патент 1981 года по МПК G06F15/173 G06G7/122 

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

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

Наиболее близким к изобретению является устройство для моделирования вероятностного графа, содержащее блок кодирования и декодирования команд с ЭВМ, электронный коммутатор с т+3 выходнЕлми шинами, m триггеров памяти,m управляемых ключевых схем, .т вентилей, логическую схему и триггер результата. Функционирование устройства происходит по циклам. Каждый цикл содержит тактовые моменты TQ сброс триггеров памяти и триггера результата г.. . ,г;... , Xff, - вьщача импульсов на вентили ,Тт - испытание схемы, отображающей граф, на проводимость Т f,, -съем информации с триггера результата 2 .

При статическом моделировании

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

то пользуются следующей зависимостью m

.p(-e)lP (i)p(t),(o

15

P(t) - вероятность безотказной

где работы системы к моменту времени Т ,

IJ (i) - вероятность выполнения 20задачи системой в состоянии с i отказами. Р; (t) - вероятность состояния системы с i отказами к моменту времени t ,

25 т - количество звеньев, из которых состоит модель исследуемой системы. Значение f (t), как правило, определяется расчетными методами, а

30 значение Р.4,( ПРИ достаточно больших m - методом статистически испытаний модели системы. Очевидно, что оценить значение при i отказах мЬжно, определив число успешных реализацийП(наличие пр водимости описывающего систему графа с i разомкнутыми ребрами) на общее число испытаний г , в которых ,было i отказов (разомкнуто i ребер графа. Следовательно, задачей статических испытаний графа в этом случае будет получение оценок вероятнос тей PJJ (i) , i 1 1 т.е. определение значений Pyj и П, в процессе испытаний. Известное устройство позволяет в каждом цикле испытания оценивать проводимость (связность) вероятностного графа и получать суммарную вероятность выполнения задачи однако при этом невозможно выделить значения Р,,) , используемые в соотношении . Цель изобретения - расширение функциональных возможностей известного устройства при исследовании вероятностных графов путем определения (i, т.е. определения показателей моделируемых графов. Для достижения поставленной цели в устройство для статистического моделирования вероятностного графа, со держащее генератор случайных чисел, тактовый и стохастический выходы которого соединены соответственно со входом коммутатора и с первыми входами элементов И первой группы, вторые входы которых подключены соответ ственно к группе выходов коммутатор первый выход которого соединен с ну- левыми входами триггеров первой груп пы, единичные входы которых подключе ны соответственно к выходам элементов и первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы и выходы которых являются соответственно группой входов и группой выходов уст ройства, выходом которого является второй выход коммутатора, введены вторая группа триггеров, третья груп па элементов. И, первая и вторая груп пы счетчиков, счетчик, дешифратор, элемент ИЛИ, входы которого подключены соответственно к выходам элеме тов И первой группы, а выход элемен та ИЛИ соединен со входом счетчика,, выходы которого соединены со входам дешифратора соответственно, управляю щий вход которого подключен к треть му выходу коммутатора, первый выход которого соединен со входом Сброс счетчика и с нулевыми входами триггеров второй группы, единичные входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы соответственно, а вых триггеров второй группы соединены с ответственно с первыми входами элементов И третьей группы, вторые вхоы которых объединены и являются входом устройства, а выходы элементов И третьей группы соединены со счетньами входами счетчиков второй группы соответственно. На чертеже приведена блок-схема устройства. Устройство содержит генератор случайных чисел 1, тактовый выход которого соединен со входом коммутатора 2, а стохастический выход - с первыми входами элементов И 3, вторые входы которых соединены с выходами коммутатора 2, а выходы - с единичными входами триггеров 4,нулевые входы которых подключены к первому выходу коммутатора 2, а выходы к первым входам элементов И 5. Выходы элементов И 3 через элемент ИЛИ б, счетчик 7, дешифратор 8 подключены ко входам счетчиков 9 и к единичным входам триггеров 10, нулевые входы которых объединены со входом счетчика 7 и с выходом коммутатора 2, другой выход которого соединен со входом дешифратора 8. Выходы триггеров 10 через элементы И 11 соединены со входами счетчиков 12. Устройство работает по циклам, каждый из которых содержит тактовые моменты TO , т , . . . , . . . ,Г ,Т, В эти моменты в коммутаторе 2 формируются импульсы, которые выдаются на соответствующие выходные шины. Под действием импульса, поступающего по нулевой шине коммутатора 2, триггеры 4 устанавливаются в О и открывают элементы И 5. В О сбрасываются также счетчик 7 и триггеры 10, В тактовый момент t-1 элемент И 3 открыт и при наличии импульса на его другом входе (выходе 2 генератора 1) триггер 4 переходит в состояние 1, закрывая элемент И 5. Наличие или отсутствие импульса на выходе 2 генератора 1 определяет соответственно наличие или отсутствие ребра графа в розыгрыше, соответствующем состоянию T/i . Аналогично происходит функционирование в моменты Tj.... ,Т;,.., tj . Импульсы с выходов элементов И 3/1,..., И 3i,..., поступают также через элемент -ИЛИ 6 на счетный вход счетчика 7, представляющего собой двоичный счетчик импульсов. Следоват-ельно, в счетчике формируется двоичное Число К (,...,i,...т), соответствующее количеству разомкнутых ребер графа в каждом цикле работы устройства. В моментТ на шину ( коммутатора 2 выдается импульс опроса дешифратора 8, при этом число К, записанное в счетчике 7, дешифрируется, и на К-ой выходной шине дешифратора 8 появляется импульс, который поступает на вход К-го счетчика состояний. Одновременно этот им пульс поступает на единичный вход триггера 10 , опрокидывает его и отпирает элемент И 11| по первому входу. В моментТг,. на шину m коммутатора 2 выдается испытующий импульс, который поступает на вход схемы, описываклдей граф и набранной из элементов И 5. Если в данном розыгрыше граф оказывается связанным, то этот импульс проходит на выход описывающей схемы, к которому подключены вторые входы элементов И 11 Поскольку открытым оказывается толь ко элемент И 11, испытующий импульс записывается в 12 счетчике успешных состояний. Если же граф оказывается несвязными то импульса на выходе описывающей его схемы не будет и в счетчик ничего не запишется. Затем цикл работы устройства пов торяется. Таким образом, по окончании процесса статистических испытаний в сч чиках 9-) , ,, ,,- 9|,, .,, 9г11 .будут подсчитаны выпавшие с l,.,,t,,,, m paзомкнутыми ребрами п , а в счетчика 12х,,,,,12 ,,,,,12гп только те из ни при которых граф был связан nycn.i.Оценка вероятности Р, (i) получаетс из частного riyj./п. Устройство может быть реализован на базе известных цифровых приборов например,, интегрешьных микросхем. Устройство позволяет расширить класс моделируемых сложных систем, описываемых вероятностным графом, при сравнительно небольшом объеме используемого оборудования, Формула изобретения Устройство для статического моде лирования вероятностного графа, сод жащее генератор случайных чисел, та товый и стохастический выходы которого соединены соответственно со вх дом коммутатора и с первыми входами элементов И первой группы, вторые входы которых подключены соответственно к группе выходов коммутатора, , первый выход которого соединен с нулевыми входами триггеров первой группы, единичные входы которых подключены соответственно к выходам элементов И первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы и выходы которых являются соответственно группой входов и группой выходов устройства, выходом которого является второй выход коммутатора, о тличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения показателей моделируемых графов оно содержит вторую группу rpHrrepoBj третью группу элементов И, первую и вторую группу счетчиков, счётчик дешифратор, элемент ИЛИ, входы которого подключены соответственно к выходам элементов И первой группы, а выход элемента ИЛИ соединен со входом счетчика, выходы которого соединены со входами деоыгфратора соответственно управляющий вход которого подключен к третьему выходу коммутатора, первый выход которого соединен со входом Сброс счетчика и с нулевыми входами триггеров второй группы единичные входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы соответственно, а выходы триггеров второй группы соединены соответственно с первыми входами элементов И третьей группы, вторые входы которых объединены и являются входом устройства, а- выходы элементов И третьей группы соединены со счетными входами счетчиков второй группы соответственно, Источники информации, принятые во внимание при экспертизе 1.Четвериков В.Н. , Баканович Э,А, Меньков А.В. Вычислительная техника для статистического моделирования, М,, Советское радио, 1978, 2.Авторское свидетельство СССР 222754, кл. G 06 F 15/20, 1967 (прототип),