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

 

Изобретение относится к области вьиислительной техники и может быть использовано для определения вероятности связи между двумя элементами вероятностного графа. Цель изобретения состоит в повьшении точности. Устройство содержит сдвигающий регистр 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. Повышение точности определеi (Л 4: 4 Од 00

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1

ÄÄSUÄÄ 1244673 ц114 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

13, ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3758390/24-24 (22) 24.04.84 (46) 15.07.86. Бюл. Р 26 (72) В.М.Полищук, В. В. Соколов и Н.И.Крылов (53) 681.333(088.8) (56) Авторское свидетельство СССР

N - 940175, кл. G 06 F 15/36, 1980.

Авторское свидетельство СССР

Ф 1010628, кл. С 06 F 15/36, 1981. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ХАРАК.

ТЕРИСТИК ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано для определения вероятности связи между двумя элементами .вероятностного графа. Цель изобретения состоит в повьппении точности.

Устройство содержит сдвигающий регистр 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„, К x;e(P 0Р ) + (- 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 устройства.

Вероятность существования связи между входным и выходным элементами рассматриваемой вероятностной сети вычисляется по формуле

Pj,1 -й путь, представленный набором элементов х; сети, составляющих данный путь, = 1,Е, общее количество элементов рассматривае мой сети, (C И, Р, - Р (х„м11 — вероятность существования 1-го элемента сети; — максимальное количество путей и их элементов соответственно.

15 В исходном состоянии каждый 2 -й регистр 4 задания -го пути (< f 1,2,..., м j ) устанавливается так, что существование -ro элемен.та (1 = (1,2,...,н 1 сети н данном

20 пути соответствует установке в единичное состояние 1 --го разряда регистра. В каждый 1-й регистр 9 записы.вается значение вероятности существования 1 -го элемента сети. Переклю25 чатель 31 устанавливается в положение, соответствующее числу К путей рассматриваемой сети.

Работа устройства начинается подачей сигнала на вход 32. Этот сиг30 нал устанавливает в исходное (нулевое) состояние регистр 1, блок 7, сумматор t3 и триггер 16. Этот же сигнал поступает через элемент ИЛИ 25 на входы элементов И 17 и 18. ЭлеЗ5 мент И 18 в данный момент закрыт запрещающим потенциалом, поступающим с выхода К-го разряда регистра 1 через первую секцию переключателя 31, а элемент И 17 открыт потенциалом с

40 выхода элемента НЕ 22, Сигнал с выхода. элемента И 17 устанавливает триггер 14 в нулевое состояние, поступает на тактовый вход регистра 1, а через элемент 27 — на вход элемен45 та ИЛИ 24 и первый вход блока 2 элементов И. Первый сигнал, поступивший на тактовый вход регистра 1, записы-, 1244

5 вает " 1" в первый разряд регистра, а каждый последующий записывает " 1" в очередной разряд, сохраняя "1" в предыдущих младших разрядах регистра.

Код, записанный в регистр 1, через

5 блок 2 поступает в блок 3, каждый раз данный код представляет собой пер вое сочетание из К по 1 . Все осталь— ные сочетания формируются последовательно с поступлением импульсов на пусковой вход блока 3. Каждое сочетание представляется на выходе блока 3 соответствующей комбинацией единичных сигналов, которые. подаются на входы соответствующих элементов И 5 и при совпадении их с единичными сигналами на выходах регистров 4 появляются на выходах элементов И 5 и входах элементов ИЛИ 6. Этим осуществляешься . согласно формуле (1) объединение эле— ментов x„ путей сети, входящих в данное сочетание.

Согласно формуле (1) вычисляются произведения значений К„. вероятностей существования элементов сети получен25 ного объединения. Двоичный код с выходов элементов ИЛИ 6 поступает на информационные входы блока 7. В это время сигнал через элемент ИЛИ 24 и

I элемент задержки 28 поступает на входы элементов И 19 и 20. До определен30 ного момента, пока не будут сформированы в блоке 3 все сочетания из К по элемент И 19 закрыт, а элемент

И 20 открыт потенциалом, поступившим через вторую секцию переключателя 31 с (К + 1) — го выхода блока 3 (или выхода триггера 14, если K =.ги). Следовательно, сигнал проходит через эле- . мент И 20 на вход установки прямого кода блока 7, нулевой вход триггера 15, установочный вход регистра 12, записывая в нем число, равное значению вероятности P = 1,00...0, через элемент задержки 29 и элемент ИЛИ 26 на вход синхронизации блока 7, а через элемент 30 на вход элемента И 21.

На одном из информационных выходов блока 7, соответствующем первому из единичных сигналов поданного на его информационные входы кода, появляет- 5ц ся разрешающий потенциал, кдторый открывает соответствующий блок эле3 ментов И 8, чем обеспечивается выдача числа из соответствующего регистра 9 через элемент ИЛИ 10 на первый информационный вход блока 11. На второй информационный вход блока 11 поступает число, записанное ранее в ре673 4 гистре 12. После этого появляется сигнал на выходе элемента И 21, открытого потенциалом с нулевого выхода триггера 15, и поступает на вход синхронизации блока 11; результат умножения записывается .в регистр 12, а с выхода блока 11 сигнал окончания умножения поступает на вход элемента ИЛИ

26. Цикл выделения очередной единицы и последующей операции умножения повторяется. После выделения всех единиц обеспечивается перемножение всех значений вероятностей существования элементов сети, входящих в данное объединение. С приходом очередного сигнала на вход синхронизации блока 7 на его выходе окончания выделения единиц появляе;ся сигнал, который поступает, во-первых, на вход синхрониза— ци сумматора 13, обеспечивая тем самым сложение числа, находящегося в сумматоре.13, с числом, находящимся в регистре 12; результат сложения чисел og.тается в сумматоре 13. Вовторых, сигнал поступает на пусковой вход блока 3, обеспечивая формирование очередного сочетания на установ— ку триггера 15 в единичное состояние, чем предотвращается подача сигнала на вход синхронизации блока 11. С этого момента работа устройства по вычислению произведения вероятностей существования элементов сети и суммированию этих произведений повторяется, но для очередного объединения элементов, заданного очередным состоянием.

После формирования последнего соI четания из К по (для данного фиксированного значения j ) выполняются все операции для данного сочетания, очередной сигнал, поступивший на пусковой вход блока 3, обеспечивает появление на (k +1) — м выходе блока 3 или его выходе окончания перебора сочетаний (при g-= -m) единичного сигнала, который устанавливает триггер 14 в единичное состояние, обеспечивая тем самым закрытие элемента И 20 и открытие элемента И 19. Тогда сигнал с выхода окончания выделения единиц блока 7 через элемент ИЛИ

24, элемент задержки 28 и элемент И

19 поступает на счетный вход триггера 16, изменение состояния которого обусловливает изменение знака слагаемых в сумматоре 13, и на вход элемента ИЛИ 25. Далее работа устройства

1244673 повторяется, но при этом обеспечивается реализация очередного слагаемого правой части формулы (1). После вычисления последнего члена формулы (1) на единичном выходе К -го разряда регистра 1 имеется положительный потенциал, который через первую секцию пер еключателя 31 открывает элемент И 18 и через элемент НЕ 22 закрывает элемент И 17. Это обеспечивает прекращение работы устройства и вьдачу сигнала через элемент, HJJH 25 и элемент И 18 на выход 33 окончания работы устройства.

Формула изобретения

Устройство для вычисления характеристик графов, содержащее сдвигающий регистр, два триггера и два элемента И, причем выход первого триггера соединен с первым входом первого элемента И, а выход второго элеменI та И подключен к тактовому входу

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

ИЛИ объединен с установочными входами сдвигающего регистра, триггера 4О знака, сумматора, блока выделения единиц и является информационным входом устройства, выход первого элемента ИЛИ соединен с первыми входами второго и третьего элементов И, вы- 45 ход второго элемента И подключен к нулевому входу второго триггера и через первый элемент задержки к входу блока элементов И и первому входу второго элемента ИЛИ, выход которого 50 через второй элемент задержки соеди-, нен с первыми входами четвертого и пятого элементов И, первая и вторая группы разрядных выходов сдвигающего регистра подключены к соответствую- 55 щим входам группы блока элементов И, входы которого соединены с соответствующими входами записи исходного сочетания блока перебора. сочетаний, выходы выдачи сочетаний которого подключены к первым входам элементов

И группы, вторые входы которых сое— динены с соответствующими разрядными выходами регистров первой группы, выходы элементов И группы подключены к входам соответствующих элементов

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

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

1244673 8 сочетаний блока перебора сочетаний подключены к соответствующим неподвижным контактам второй группы переключателя, последний неподвижный кон такт второй группы которого соединен с выходом второго триггера, второй . замыкающий контакт переключателя подключен к входу второго, элемента НЕ и второму входу пятого элемен10 та. И.