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

Изобретение относится к вычислительной технике и может быть использовано при статическом моделировании сложных систем, представленных в вид вероятностного графа, с целью определения качественных характеристик, в частности показателей надежности систем. Известно устройство для моделирования вероятностного графа, содержащее блок кодирования и декодирования команд, поступающих от ЭВМ, электронный коммутатор с т+3 выходными шинами, тп триггеров памяти, п управляемых ключевых схем, m вентилей, логическ схему и триггер результата. Функцио нирование устройства происходит по циклам. Каждый цикл содержит тактовые моменты tu -сброс триггеров памя ти и триггера результата f ,; i .. . ,С -вьщача импульсов на вс Т -испытание схемы отображающей раф на проводимость, t съем информации с триггера результата . Недостатком данного устройства является необходимость использования ЭВМ. Наиболее близким к предлагаемому устройству является устройство для статистического моделирования вероятностного графа, содержащее генератор случайных чисел, тактовый и.стохасти ческий выходы которого соединены соответственно с входом коммутатора и с первыми входами элементов И первой группы, вторые входы которых под ключены соответственно к группе выходов коммутатора, первый выход которого соединен с нулевыми входами триггеров первой группы, единичные входы которых подключены соответственно к выходам элементов И первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы и выходы которых являются соответственно группой входов и группой выходов устройства, выходом которого является второй выход коммутатора, элемент ИЛИ, входы которого подключены к выходам элементов И первой группы, а выход соединен с входом с 1етчика, соединен ного выходом с входом дешифратора, управляющий вход которого подключен к третьему выходу дешифратора,первый выход которого соединен со входом Сброс счетчика и с нулевыми входам триггеров второй группы, единичные входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы, выходы триггеров второй группы соединены с первыми входами элементов И третьей группы, вторые входы которых объединены и являются входом устройства, а выходы соединены с входами счетчиков второй группы 2. Недостаток устройства заключается в большом количестве оборудования. Кроме того, наличие дешифратора затрудняет расширение устройства. Цель изобретения - сокращение аппаратурных затрат устройства. Поставленная цель достигается тем, что в устройство для моделирования вероятностного графа, содержащее генератор случайных чисел, коммутатор, первую, вторую и третью группу элементов И, первую и вторую группу счетчиков, первые входы и выходы элементов И первой группы являются соответственно группой информационных входов и группой информационных выходом устройства, выходы элементов И второй группы соединены с входами счетчиков первой группы, дополнительно введеным-разрядный регистр сдвига, (|п+1)-разрядный регистр сдвига, триггер, три элемента И, элемент задержки, элемент НЕ-, причем второй выход коммутатора соединен с единичными входами первых разрядов, нулевыми входами 2,3,...,w, разрядов т-разрядного регистра сдвига, 2,3,..., ..., (т+1) разрядов (т+1)-разрядного регистра сдвига и нулевым входом триггера, тактовый выход генератора случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (т+1)-разрядного регистра сдвига, выходы которого, кроме (т+1)-го, соединены с вторыми входами элементов И первой группы, (т+1)-и выход (т+1) разрядного регистра сдвига соединен через элемент задержки с вторым входом первого элемента И и входом элемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу Третьего элемента И, выходы которых соединены соответственно с сдвиговыми входами пт-разрядного и (гг+1) разрядного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходами т-разрядного регистра сдвига, а выходы - с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единич ный вход которого является управляющим входом устройства. На фиг.1 изображена структурная схема устройства; на фиг.2 - вариант набора схемы графа; на фиг.З - граф. Устройство содержит генератор 1 случайных чисел, элементы И 2 - 4, (т+1)-разрядный регистр 5 сдвига, первую группу элементов И 6,6 ,... ..,,6, элемент 7 задержки, элемент НЕ 8,m-разрядный регистр 9 сдвига, коммутатор 10, триггер 11, вторую группу элементов И 12 , 122,...,12, первую группу счетчиков 13,13 ,... ...,13, третью группу элементов И 14-,, ,..., 14, вторую группу . счетчиков 15 ,15 ,...,15fn, элемент И 16 (фиг.2.) . Устройство работает следующим образом. В исходном состоянии (т+1)-й разряд регистра 5 сдвига установлен в единичное состояние. В результате подготовлен к работе элемент И2.Импульс с тактового выхода генератора случайных чисел проходит через элемент И2 на вход коммутатора 10, и появляющийся на первом выходе коммутатора 10 импульс устанавливает в нулевое cocfояние триггер 11, устанавливает в единичное состояние первые разряды и сбрасывае г остальные разряды регистров 5 и 9 сдвига. На выходе (т+1)-го разряда регистра,3 сдвига появляется нулевой сигнал, который, пройдя через элемент 7 задержки, запрещает прохождение следую щих импульсов на вход коммутатора 10 и разрешает, пройдя через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И4. Следующий импуль с тактового выхода генератора проходит через элемент И4 на вход регистра 5 сдвига, сдвигая содержимое на один разряд и одновременно занося в первый разряд информацию о состоянии стохастич1еского выхода генератора 1 b то же время импульс с тактового выхода через элемент ИЗ попадает на вход сдвига регистра 9 сдвига только 1 3 тогда, когда на стохастическом выходе генератора присутствует единица. Каждый прошедший импульс сдвигает информацию (единицу в первом разряде) на один разряд и заносит в первый разряд регистра 9 нуль, так как информационный вход регистра 9 соединен с входом сигнала логического О. Последующие импульсы действуют аналогично . После прохождения тт импульсов на вход регистра 5 сдвига единица попадает в (т+1)-ый разряд и единичный сигнал, задержанный на элементе 7 задержки на время, достаточное для прохождения заднего фронта импульса, сдвинувшего единицу Вд(т+1)-ый разряд регистра 5, разрешает прохождение последующих импульсов на вход коммутатора 10 и запрещает, пройдя через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И4 на входы регистров 5 и 9 сдвига. Таким образом, в регистре 5 сдвига в первых m разрядах формируется информация о наличии или отсутствии ребер графа (1-е ребро присутствует, О ребро отсутствует), а в регистре 9 сдвига единица устанавливается только на выходе первого разряда, если в текущей реализации отсутствуют ребра графа (отказ m ребер графа) на выходе второго разряда, если в текущей реализации присутствует одно ребро (отказ т-1 ребер),..., на выходе m-го разряда, если в текущей реализации присутствует одно ребро (отказ т-1 ребер) ,..., на выходеm-го разряда, если присутствует m-l ребер (отказ одного ребра). Последующие импульсы с тактового выхода генератора 1 проходят через элемент И2 на вход коммутатора 10, в результате появляется импульс на втором выходе коммутатора 10, котррьй поступает на вход схемы, граф набранной из элементов И6. Если в данной реализации граф оказывается связанным, то импульс проходит на выход схемы граф, к которому подключен единичный вход триггера 11, устанавливая его в единицу. Если же граф оказывается несвязанным, то импульса на выходе схемы не будет,и триггер 11 останется в нулевом состоянии. Появляющийся затем на третьем выходе коммутатора 10 импульс опрашивает состояние разрядов регистра 9 сдвига, и в зависимости

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

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

подсчитьшаются реализации вьшавшие с 1п ,..., i , ..., 1 разомкнутыми ребрами м, а в счетчиках 15 ,..., 15,,.. ...,15 только те из них, при которых граф связан riycni Оценка вероятности получается из частного .

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

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

cpue.f