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

,8012446 4 С 06 Р 15/2 ОСУДАРСТВЕНКЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ АНИЕ ИЗОБРЕТЕНИЯ 13, 13НОМУ СВИДЕТЕЛЬСТВУ . ък ы.,:,.- 2 Бюл. У 26к, В.В.Сокол свидетельство СССР 06 Р 15/36, 1980. идетельство СССР С 06 Р 15/36, 1981(54) УСТРОЙСТВ ТЕРИСТИК ГРАФО (57) Изобретен вычислительной использовано д ности связи ме вероятностного ния состоит в ЛЯ ВЫЧИСЛЕНИЯ ХАРАК е относится к облас техники и может быть я определения вероя ду двумя элементами графа, Цель изобрет овьппении точности. е-. ер(21) 3758390/2(56) АвторскоеУ 940175, кл. САвторское свВ 1010628, кл. Устройство содержит сдвигающий регистр 1, блок 2 элементов И, блок 3перебора сочетаний, первую группурегистров 4, группу элементов И 5,группу элементов ИЛИ 6, блок 7 выделения единиц, группу блоков элементов И 8, вторую группу регистров 9,третий элемент ИЛИ 10, блок 11 умножения, буферный регистр 12, сумматор 13, второй триггер 14, первыйтриггер 15, триггер 16 знака, второй 17, третий 18, пятый 19, четвертый 20 и первый 21 элементы И, первый 22 и второй 23 элементы НЕ, вто"рой 24, первый 25 и четвертый 26 элементы ИЛИ, первый 27, второй 28, тртий 29 и четвертый 30 элементы заджки, переключатель 31, вход 32 и выход 33, Повьппение точности определе1244673ния характеристик графов обеспечива- выходным элементами вероятностного.ется за счет вычисления вероятности графа согласно аналитической формусуществования связи между входным и ле. 1 ил,гдеПр. к;Е(р,О р,И.ОР)- количество путей между входным и выходным элементами рассматриваемой сети, К Й ю; Изобретение относится к вычислительной технике и предназначено длявычисления характеристик сетей, представленных вероятностными графами,в частности, для определения вероятности существования связи между любымвходным и любым из выходных элементоврассматриваемой вероятностной сети.Цель изобретения состоит в повышении точности,На чертеже представлена функциональная схема устройства.Устройство содержит сдвигающийрегистр 1, блок 2 элементов И,блок 3перебора сочетаний, первую группурегистров 4, группу элементов И 5,группу элементов ИЛИ 6, блок 7 выделения единиц, группу блоков элементов И 8, вторую группу регистров 9,третий элемент ИЛИ 10, блок 11 умножения, буферный регистр 12, сумматор 13, второй триггер 14, первыйтриггер 15, триггер 16 знака, второй17, третий 18, пятый 19, четвертый20 и первый 21 элементы И, первый 22и второй 23 элементы НЕ, второй 24,первый 25 и четвертый 26 элементы ИЛИ,первый 27, второй 28, третий 29 ичетвертый 30 элементы задержки, переключатель 31, вход 32 и выход 33 устройства.Вероятность существования связимежду входным и выходным элементамирассматриваемой вероятностной сети вычисляется по формуле н 1-й путь, представ-ленный набором элемен.тов к; сети, составляющих данный путь, 1-1 Еобщее количество элементов рассматриваемой сети, 1 ( И , Р, - . Р (хм 11 - вероятность существования 1-го элементасети;- максимальное количество путей и их элементов соответственно.15 В исходном состоянии каждый 2 -йрегистр 4 задания-го пути(1,2м) устанавливаетсятак, что существование-го элемен.та ( 1 = 11,2н ) сети н данном 20 пути соответствует установке в единичное состояние 1 -го разряда регистра. В каждый 1-й регистр 9 записы.вается значение вероятности существования 1 -го элемента сети. Переклю 25 чатель 31 устанавливается в положение, соответствующее числу К путейрассматриваемой сети. Работа устройства начинается подачей сигнала на вход 32. Этот сигнал устанавливает в исходное (нулевое) состояние регистр 1, блок 7,сумматор 13 и триггер 16. Этот жесигнал поступает через элемент ИЛИ 25на входы элементов И 17 и 18. ЭлеЗ 5 мент И 18 в данный момент закрыт запрещающим потенциалом, поступающимс выхода К-го разряда регистра 1через первую секцию переключателя 31,а элемент И 17 открыт потенциалом с 40выхода. элемента НЕ 22, Сигнал с выхода. элемента И 17 устанавливаеттриггер 14 в нулевое состояние, поступает на. тактовый вход регистра 1,а через элемент 27 - на вход элемента ИЛИ 24 и первый вход блока 2 элементов И. Первый сигнал, поступившийна тактовый вход регистра 1, записы-, 12441вает "1" в первый разряд регистра, а каждый последующий записывает " 1" в очередной разряд, сохраняя "1" в предыдущих младших разрядах регистра, Код, записанный в регистр 1, через5 блок 2 поступает в блок 3, каждый раз данный код представляет собой первое сочетание из К по 1 . Все осталь - ные сочетания формируются последовательно с поступлением импульсов на пусковой вход блока 3. Каждое сочетание представляется на выходе блока 3 соответствующей комбинацией единичных сигналов, которые. подаются на входы соответствующих элементов И 5 и при совпадении их с единичными сигналами на выходах регистров 4 появляются на выходах элементов И 5 и входах элементов ИЛИ 6. Этим осуществляется . согласно формуле (1) объединение эле - ментов М путей сети, входящих в данное сочетание.Согласно формуле (1) вычисляются произведения значений К вероятностей существования элементов сети получен 25 ного объединения. Двоичный код с выходов элементов ИЛИ 6 поступает на информационные входы блока 7, В это время сигнал через элемент ИЛИ 24 иэлемент задержки 28 поступает на входы элементов И 19 и 20. До определен 30 ного момента, пока не будут сформированы в блоке 3 все сочетания из К поэлемент И 19 закрыт, а элемент И 20 открыт потенциалом, поступившим через вторую секцию переключателя 31 З 5 с (К + 1) - го выхода блока 3 (или выхода триггера 14, если К =. и). Следовательно, сигнал проходит через элемент И 20 на вход установки прямого кода блока 7, нулевой вход триггера 15, установочный вход регистра 12, записывая в нем число, равное значению вероятности Р = 1,00;О, через элемент задержки 29 и элемент ИЛИ 26 на вход синхронизации блока 7, а через элемент 30 на вход элемента И 21. На одном из информационных выходов блока 7, соответствующем первому из единичных сигналов поданного на его информационные входы кода, появляет ц ся разрешающий потенциал, кдторый открывает соответствующий блок элементов .И 8, чем обеспечивается выдача числа из соответствующего регистра 9 через элемент ИЛИ 10 на первый 55 информационный вход блока 11. На второй информационный вход блока 11 поступает число, записанное ранее в ре 673 4 гистре 12. После этого появлЯется сигнал на выходе элемента И 21, откры.того потенциалом с нулевого выхода триггера 15, и поступает на вход синхронизации блока 11; результат умножения записывается в регистр 12, а с выхода блока 11 сигнал окончания умножения поступает на вход элемента ИЛИ 26. Цикл выделения очередной единицы и последующей операции умножения повторяется. После выделения всех единиц обеспечивается перемножение всех зна.чений вероятностей существования элементов сети, входящих в данное объединение. С приходом очередного сигнала на вход синхронизации блока 7 на его выходе окончания выделения единиц появляе; ся сигнал, который поступает, во-первых, на вход синхронизади сумматора 13, обеспечивая тем самым сложение числа, находящегося в сумматоре 13, с числом, находящимся в регистре 12; результат сложения чисел остается в сумматоре 13. Вовторых, сигнал поступает на пусковой вход блока 3, обеспечивая формирование очередного сочетания на установку триггера 15 в единичное состояние, чем предотвращается подача сигнала на вход синхронизации блока 11. С этого момента работа устройства по вычислению произведения вероятностей существования элементов сети и суммированию этих произведений повторяется, но для очередного объединения элементов, заданного очередным состоянием. После формирования последнего сочетания из К по(для данного фиксированного значения) выполняются все операции для данного сочетания, очередной сигнал, поступивший на пусковой вход блока 3, обеспечивает появление на (К+1) - м выходе блока 3 или его выходе окончания перебора сочетаний (при 1(= в ) единичного сигнала, который устанавливает триггер 14 в единичное состояние , обеспечивая тем самым закрытие элемента И 20 и открытие элемента И 19. Тогда сигнал свыхода окончания выделения единиц блока 7 через элемент ИЛИ 24, элемент задержки 28 и элемент И 19 поступает на счетный вход триггера 16, изменение состояния которого обусловливает изменение знака слагаемых в сумматоре 13, и на вход элемента ИЛИ 25. Далее работа устройстваповторяется, но при этом обеспечивается реализация очередного слагаемого правой части формулы (1). После вычисления последнего члена формулы (1) на единичном выходе К -го разряда регистра 1 имеется положительный потенциал, который через первую секцию переключателя 31 открывает элемент И 18 и через элемент НЕ 22 закрывает элемент И 17, Это обеспечивает прекращение работы устройства и вьдачу сигнала через элемент, ИЛИ 25 и элемент И 18 на выход 33 окончания работы устройства.15Формула изобретения Устройство для вычисления характе. ристик графов, содержащее сдвигающий регистр, два триггера и два элемента И, причем выход первого триггера соединен с первым входомпервого элемента И, а выход второго элеменФа И подключен к тактовому входу25 сдвигающего регистра, о т л и ч а ющ е е с я тем, что, с целью повышеНия точности, в устройство дополнительно введены триггер знака, четыре элемента ИЛИ, третий, четвертый и пятый элементы И, четыре элемента задержки, два .элемента НЕ, переключатель, блок умножения, буферный регистр,. сумматор, блок перебора сочетаний, две группы регистров, блок вьделения единиц, группа элементов И, 35. группа блоков элементов И, группа элементов ИЛИ и блок элементов И, причем первый вход первого элемента ИЛИ объединен с установочными входами сдвигающего регистра, триггера 40 знака, сумматора, блока выделения единиц и является информационным входом устройства, выход первого элемента ИЛИ соединен с первыми входами второго и третьего элементов И, вы ход второго элемента И подключен к нулевому входу второго триггера и через первый элемент задержки к входу блока элементов И и первому входу второго элемента ИЛИ, выход которого 50 через второй элемент задержки соеди-, нен с первыми входами четвертого и пятого элементов И, первая и вторая группы разрядных выходов сдвигающего регистра подключены к соответствую щим входам группы блока элементов И, входы которого соединены с соответствующими входами записи исходного сочетания блока перебора. сочетаний,выходы выдачи сочетаний которогоподключены к первым входам элементов И группы, вторые входы которых сое - динены с соответствующими разрядными выходами регистров первой группы, вы. ходы элементов И группы подключены к входам соответствующих элементов ИЛИ группы, входы которых соединены с соответствующими информационными входами блока выделения единиц, информационные выходы которого подключены к первым входам соответствующих блоков элементов И группы, вторые входы которых соединены с выходами соответствующих регистров второй группы, выходы блоков элементов И группы подключены к входам третьего элемента ИЛИ, выход которого соединен с первым. информационным входом блока умножения, информационный выход которого подключен к информационному входу буферного регистра, выход которого соединен с вторым информационным входом блока умножения и информационным входом сумматора, вход управления режимом которого подключен к выходу триггера. знака, выход окончания пере" бора сочетаний блока перебора сочетаний соединен с единичным входом второго триггера, выход окончания выделения единиц блока вьделения единиц подключен к входу синхронизации сумматора, пусковому входу блока перебора сочетаний, единичному входу первого триггера и второму входу второго элемента ИЛИ, выход пятого элемента И соединен со счетным входом триггера знака и вторым входом первого элемента ИЛИ, выход первого элемента НЕ подключен к второму входу второгоэлемента И, выход второго элемента НЕ соединен с вторым входом четвертого элемента И, выход которого подключен к входу установки прямого кода блока выделения единиц, установочному входу буферного регистра, нулевому входу первого триггера и через третий элемент задержки к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом окончания умножения блока умножения, выход . четвертого элемента ИЛИ подключен к входу синхронизации блока выделения ециниц и через четвертый элемент задержки к второму входу первого элемента И, выход которого соединен с входом синхронизации блока умножения,разрядные выходы первой группы сдвигающего регистра подключены к соответствующим неподвижным контактампервой группы переключателя, первыйподвижный контакт которого соединенс входом первого элемента НЕ и вторым входом третьего элемента И, выход которого является выходом окончания работы устройства, разрядныевыходы, начиная со второго, выдачи 12446738сочетаний блока перебора сочетаний подключены к соответствующим неподвижным контактам второй группы переключателя, последний неподвижный кон такт второй группы которого соединен с выходом второго триггера, второй замыкающий контакт переключателя подключен к входу второго, элемента НЕ и второму входу пятого элемен 1 О та. И.