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

1244673

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

i

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

Цель изобретения состоит в повышении точности.

На чертеже представлена функцио- нальйая схема устройства.

Устройство содержит сдвигающий регистр 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 устройства.

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

p-pfp 1/PU... uPj 2: Пр,- ( JM . П р,, (,-e(.j)

, Пр. , «i-eCP uRjU uP)

- количество путей между входным и выходным элементами рассматриваемой сети, k 4 ш ;

Pj - J-и путь, представ- ленный набором элементов (, сети, состав- ляющих данньй путь,

51 1, е ;.

с - общее количество элементов рассматривае- мой сети, И i

Rj - P(x.) - вероятность существо- 10вания 1-го элемента

сети;

К1, п - максимальное количество путей и и« элементов соответственно.

15 В исходном состоянии каждьгй -и регистр 4 задания j-го пути О lj2,..,,w) устанавливается так, что существование -го элемен- . та ( i 11,2,...,м ) сети в данном 20 пути соответствует установке в единичное состояние V-го разряда регистра. В казкдый i-й регистр 9 записы .ваетс.я значение вероятности существования 1 -го элемента сети. Переклю- 2S чатель 31 устанавливается в положение, соответствующее числу К путей рассматрива.емой сети.

Работа устройства начинается подачей сигнала на вход 32. Этот сигнал устанавливает в исходное (нулевое) состояние регистр 1, блок 7, сумматор 13 и триггер 16. Этот же сигнал поступает через элемент ИЛИ 25 на входы элементов И 17 и 18. Элемент И 18 в данньй момент закрыт запрещающим потенциалом, поступающим с выхода К.-ГО разряда регистра 1 через первую секхдаю переключателя 31, а элемент И 17 открыт потенциалом с выхода элемента НЕ 22. Сигнал с выхода элемента И 17 устанавливает триггер 14 в нулевое состояние, поступает на тактовый вход регистра Т, а через элемент 27 - на вход элемента ИЛИ 24 и первьй вход блока 2 элементов И. Первый сигнал, поступивщий на тактовьй вход регистра 1, записы- ,

взет

в первьп разряд регистра.

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

Согласно формуле (1) вычисляются произведения значений К вероятностей существования элементов сети получен- ного объединения. Двоичный код с выходов элементов ИЛИ 6 поступает на информационные входы блока 7. В это время сигнал через элемент ИЛИ 24 и элемент задержки 28 поступает на входы элементов И 19 и 20. До определенного момента, пока не будут сформированы в блоке 3 все сочетания из К по i , элемент И 19 закрыт, а элемент И 20 открыт потенциалом, поступившим через вторую секцию переключателя 31 с (К + 1)-го выхода блока 3 (или вы- хода триггера 14, если ). Следовательно, сигнал проходит через эле- мент И 20 на вход установки прямого кода блока 7, нулевой вход тригге- ра 15, установочный вход регистра 12, записывая в нем число, равное значению вероятности Р 1,00. ..О, через задержки 29 и элемент ИЛИ 26 на вход синхронизации блока 7, а че- рез элемент 30 на вход элемента И 21. На одном из информационных выходов блока 7, соответствующем первому из единичных сигналов поданного на его информационные входы кода, появляет- ся разрешающий потенциал, открывает соответствующий блок эле- ме нтов И 8, чем обеспечивается выдача числа из соответствующего регистра 9 через элемент ИЛИ 10 на.первый информационный вход блока 11. На второй информационный вход блока 11 поступает число, записанное ранее в ре

5

р- до,г . й- 35. , 5 50 55 2446734

гистре 12. После этого появляется

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

После формирования последнего сочетания из К по J (для данного фиксированного значения j ) выполняются все операции для данного сочетания, очередной сигнал, поступивший на пусковой вход блока 3, обеспечивает появление на (К + О-м выходе блока 3 или его выходе окончания перебора сочетаний (при ) единичного сигнала, который устанавливает триггер 14 в единичное состояние , обеспечивая тем самым закрытие элемента И 20 и открытие элемента И 19. Тогда сигнал с выхода окончания выделения единиц блока 7 через элемент ИЛИ 24, элемент задержки 28 и элемент И 19 поступает на счетный вход триггера 16, изменение состояния которого обусловливает изменени е знака слагаемых в сумматоре 13, и на вход элемента ИЛИ 25. Далее работа устройства

30

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

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

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

И

40

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

55

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

5

12446736

сочетания блока перебора.сочетаний.

0

5

0

5

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

ра сочетаний, единичному входу перво-

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

71

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

2446738 .

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

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