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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 801119023 гР 15/20 /Г ГОСУДАРСТВЕННЫЙ ПО ДЕЛАМ ИЗОБРЕ МИТЕТ ССС Й и ОткРыт ОПИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРСКОМУ СВИДЕТЕЛЬСТВ(72) Н.Ф. Морозов и В.Д. Трусов (71) Институт технической кибернетики АНБССР(56) 1. Авторское свидетельство СССР Р 222754, кл. С 06 Р 15/20, 1967.2. Авторское свидетельство СССР В 881759, кл, С 06 Г 15/20, 1980 (прототип)..(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕРОЯТНОСТНОГО ГРАФА, содержащее генератор случайных чисел, коммута-тор, первую, вторую и третью группы элементов И, первую и вторую группы счетчиков, первые входы и выходы элементов И первой группы являются соответственно группой информационных входов и группой информационных выходов устройства, первый выход коммутатора является управляющим выходом устройства, выходы элементов И второй группы соединены с входами счетчиков первой группы, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат; в устройство введены п 1-разрядный регистр сдвига ( в - максимальное число ребер моделируемых граф), (л+1)-разрядный регистр сдвига, триггер, три элемента И, элемент задержки и элемент НЕ, причем второй выход коммутатора соединен с единичными входами первых разрядов, нулевыми вхддами 2,3в разрядов в -разрядного регистра сдвига, 2,3, (в+1) разрядов (в+1) -разрядногорегистра сдвига и нулевым входомтриггера, тактовый выход генератора .случайных чисел соединен с первымивходами элементов И, стохастическийвыход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом(в+1)-разрядного регистра сдвига,выходы которого, кроме (в+1)-го, соединены с вторыми входами элементов Ипервой группы, (в+1)-й выход (в+1)- разрядного регистра сдвига соединен через элемент задержки с вторым входом первого элемента И и входомэлемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу третьего элемента И, выходы которых соединены соответ.ственно со сдвиговыми входами в-раз 1 рядного и (в+1)-разрядного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходами гп-разрядного регистра сдвига а выходы - с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единичный вход которого является управляющйм входом устройства.1 1119 ОИзобретение относится к вычислительной технике и может быть использовано при статическом моделированиисложных систем, представленных в видевероятностного графа, с целью опре 5деления качественных характеристик,в частности показателей надежностисистем,Известно устройство д:;я моделирования вероятностного графа, содержа.щее блок кодирования и декодированиякоманд, поступающих от ЭВМ, электронный коммутатор с в+3 выходными шинами, п триггеров памяти,в управляемыхключевых схем, п вентилей, логическую 15схему и триггер результата. функционирование устройства происходит поциклам. Каждый цикл содержит тактовые моменты Т -сброс триггеров памяти и триггера результата Т и-выдача импульсов на вентили,Т , -испытание схемы отображающейграф на проводимость, ,+2 - съем информации с триггера результата 1 1.Недостатком данного устройстваявляется необходимость использованияЗВМ,Наиболее близким к предлагаемомуустройству является устройство длястатистического моделирования вероят 30ностного графа, содержащее генераторслучайных чисел, тактовый и, стохастический выходы которого соединенысоответственно с входом коммутатораи с первыми входами элементов И пер"вой группы, вторые входы которых под-З 5ключены соответственно к группе выходов коммутатора, первый выход которого соединен с нулевыми входамитриггеров первой группы, единичныевходы которых подключены соответственно к выходам элементов И первойгруппы, а выходы триггеров первойгруппы подключены соответственно кпервым входам элементов И второйгруппы, вторые входы и выходы кото 45рых являются соответственно группойвходов и группой выходов устройства,выходом которого является второйвыход коммутатора, элемент ИЛИ, входы которого подключены к выходамэлементов И первой группы, а выходсоединен с входом советчика, соединен 1ного выходом с входом дешифратора,управляющий вход которого подключенк третьему выходу дешифр атор а, первыйвыход которого соединен со входом"Сброс" счетчика и с нулевыми входамитриггеров второй группы, единичные 23 2входы которых подключены к выходамдешифратора и к счетным входам счет.чиков первой группы, выходы триггеров второй группы соединены с первыми входами элементов И третьей группы, вторые входы которых объединеныи являются входом устройства, а выходы соединены с входами счетчиковвторой группы 2 3,Недостаток устройства заключаетсяв большом количестве оборудования.Кроме того, наличие дешифратора затрудняет расширение устройства.Цель изобретения - сокращениеаппаратурных затрат устройства.Поставленная цель достигается тем,что в устройство для моделированиявероятностного графа, содержащее генератор случайных чисел, коммутатор,первую, вторую и третью группу элементов И, первую и вторую группусчетчиков, первые входы и выходыэлементов И первой группы являютсясоответственно группой информационных входов и группой информационныхвыходом устройства, выходы элементовИ второй группы соединены с входамисчетчиков первой группы, дополнительно введены м-разрядный регистрсдвига, (в+1)-разрядный регистр сдвига, триггер, три элемента И, элементзадержки, элемент НЕ; причем второйвыход коммутатора соединен с единичными входами первых разрядов, нулевыми входами 2,3 э, разрядовв-разрядного регистра сдвига, 2,3, (а+1) разрядов (в+1)-разрядногорегистра сдвига и нулевым входомтриггера, тактовый выход генератораслучайных чисел соединен с первымивходами элементов И, стохастическийвыход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом(+1)-разрядного регистра сдвига,выходы которого, кроме Оп+1)-го,соединены с вторыми входами элементовИ первой группы, (в+1)-й выход (а+1)разрядного регистра сдвига соединенчерез элемент задержки с вторым входом первого элемента И и входом элемента НЕ, выход которого подключенк третьему входу второго элемента Ии второму входу третьего элемента И,выходы которых соединены соответственно с сдвиговыми входами щ-разрядного и (п 1+1) разрядного регистровсдвига, выход первого элемента Исоединен с входом коммутатора, третийз 11190 1выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходами ы-разрядного регистра сдвига, а выходы - с первыми входами элементов И третьей группы, выходы которых5 подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единичный.вход которого является управляю 1 О щим входом устройства.На фиг.1 изображена структурная схема устройства; на фиг.2 - вариант набора схемы графа; на фиг.З - граф.Устройство содержит генератор 115 случайных чисел, элементы И 2 - 4,(в+1)-разрядный регистр 5 сдвига,первую группу элементов И 6,6 ,6 щ, элемент 7 задержки, элемент НЕ 8 п -разрядный регистр 9 сдвигаЭ20 коммутатор 10, триггер 11, вторуюгруппу элементов И 12. 1212,13 П третью группу элементов И 1414 14 вторую группу счетчиков 15 ,15 15 элемент1И 16 (фиг.2).Устройство работает следующим образом.В исходном состоянии (в+1)-й разряд регистра 5 сдвига установлен вединичное состояние, В результате . подготовлен к работе элемент И 2.Импульс с тактового выхода генератора 1 случайных чисел проходит через элемент И 2 на вход коммутатора 10, и 35 появляющийся на первом выходе коммутатора 10 импульс устанавливает в нулевое состояние триггер 11, устанавливает в единичное состояние первые разряды и сбрасываеТ остальные разряды регистров 5 и 9 сдвига. На выходе (п+1)"го разряда регистра,5 сдвига появляется нулевой сигнал, который, пройдя через элемент 7 задержки, запрещает прохождение следующих импульсов на вход коммутатора 10 и разрешает, пройдя через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И 4. Следующий импульс с тактового выхода генератора про О ходит через элемент И 4 на вход регистра 5 сдвига, сдвигая содержимое на один разряд и одновременно занося в первый разрядинормацию осостоянии: стохастического выхода генератора 1. 55 Ы то же время импульс с тактового . выхода через элемент ИЗ попадает на вход сдвига регистра 9 сдвига только 23 4тогда, когда на стохастическом выходе генератора присутствует единица,Каждый прошедший импульс сдвигает информацию (единицу в первом разряде)на один разряд и заносит в первый разряд регистра 9 нуль, так как информационный вход регистра 9 соединен с входом сигнала логического "0".Последующие импульсы действуют. аналогично.После прохождения т импульсов на вход регистра 5 сдвига единица попадает в (1 ъ+1)-ый разряд И единичныйсигнал, задержанный на элементе 7 задержки на время, достаточное для прохождения заднего фронта импульса,сдвинувшего единицу в (в+1)-ый разряд регистра 5, разрешает прохождение последующих импульсов на вход коммутатора 10 и запрещает, пройдя через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И 4 навходы регистров 5 и 9 сдвига. Таким образом, в регистре 5 сдвига в первыхв разрядах формируется информация оналичии или отсутствии ребер графа (1-е ребро присутствует, 0 ребро отсутствует), а в регистре 9 сдвига единица устанавливается только на выходе первого разряда, если в текущей реализации отсутствуют ребра графа (отказ п ребер графа) на выходе второго разряда, если в текущей реализации присутствует одно ребро (отказв"1 ребер) на выходец-го разряда, если в текущей реализации присутствует одно ребро (отказ вребер) на выходе в-го разряда, если присутствует аребер (отказ одного ребра).Последующие импульсы с тактового выхода генератора 1 проходят через элемент И 2 на вход коммутатора 10, в результате появляется импульс на втором выходе коммутатора 10, который поступает на вход схемы, граф набранной из элементов И 6. Если в данной реализации граф оказывается связанным, то импульс проходит на выход схемы граф, к которому подклю". чен единичный вход триггера 11, устанавливая его в единицу. Если же граф оказывается несвязанным, то импульса на выходе схемы не будет,и триггер 11 останется в нулевом состоянии. Появляющийся затем на третьем выходе коммутатора 10 импульс опрашивает состояние разрядов регистра 9 сдвига, и в зависимостиот установленного в единицу разряда появляется импульс на выходе 1 -го элемента И второй группы элементов И 12, поступая на счетный вход К -го счетчика первой группы элементов И 14. Если триггер 11 установлен в единицу, то импульс поступает на счетный вход К -го счетчика второй группы счетчиков 15, Затем цикл работы устройства повторяется.Таким образом, по окончании процесса статистических испытаний ,в счетчиках 1313 13,подсчитываются реализации выпавшие с ,ф 1 уеу 1 разомкнутыми ребрами ь;, а в счетчиках 15,15 ,15, только те из них, при которых граф связан и ; . Оценка вероятности получается из частного и, ;/П;Устройство для статистического моделирования вероятностного графа легко расширяется при увеличении количества звеньев моделируемой системы путем добавления разрядов регистров сдвига, элементов И и счетчиков."Патент", г. Ужгород, ул. Проектная,иал Тираж 698 ИИПИ Государственного по делам изобретений 3035, Москва, Ж, Р Подписнооиитета СССРоткрытийуаская наб., д