Вероятностное устройство для анализа сетей

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советсник

Социалистическими

Республик и 1940175 (6l) Дополнительное к авт. свнд-ву (22) Заявлено 18.12.80 (21) 3222659/18-24 (51)М. Кл.

Q06F 15/36 с присоединением заявки № (Ьвудврвтвенвй квмвтвт

ССС0 ао делам нзвврвтенив в втврытвй (23) Приоритет (53) У@К 681..3(088. 8) Опубликовано 30.06.82. Бюллетень ¹ 24

Дата опубликования описания 30.06.82 (72) Авторы изобретения т

Б. И, Азаров, и B. М. Гришин .".; .

/ .

f и е

Московский ордена Ленина и ордена О И ибо кой Революции ееиенионный институт нм. Серго Орнжоиикноее --,. / (71) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО

ДЛЯ АНАЛИЗА СЕТЕЙ

Изобретение относится к вычислительной технике и предназначено для решения задач анализа сетей, представленных вероятностными графами, s ч астноoсcтTtиt, для определения надежности связи между входными и любыми из выходных элементов

5 рассматриваемой вероятностной сети.

Известны устройства для моделирования вероятностных графов, содержащие генератор тактовых импульсов, запомина-, ющие триггеры, схему сравнения гсел, запоминакецее устройство и другие уз-: лы С1), (2)

Наиболее близкой по технической сущности к предлагаемой является вероятностная машина, содержащая генератор тактовых импульсов, датчик случайных чисел, схему сравнения чисел, эапоминаквцее устройство, регистр сдвига, диодные вентили, потенциальные триггеры в 20 качестве промежуточной памяти, импульс= ные вентили, коммутационное поле, выходные счетчики и регулируемый счетчик циклов $3) .

Основным недостатком известного устройства является низкое быстродейс1 вне машины вследствие последовательного принципа работы. Это обстоятельство препятствует получению с помощью указанной машины достоверных статистичес» ких аналоговых искомых характеристик вероятностных графов и приемлемое машинное время, что обусловлено известной сходимостью метода Монте-Карло 1 WH

ГДЕ Й () - ЧИСЛО ЦИКЛОВ МОДЕЛИРОВаиияе

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

lleztb изобретения - повышение быс л. родействия.

Поставленная цель достигается тем, что вероятностное устройство для анализа сетей, содержащее генератор тактовых импульсов, блок выходных счетчиков, 3 9401 7 счетчик циклов, дополнительно содержич бпок наборного поля, блок И (1,2...) преобразователей код - вероятность по числу максимального количества вероят-, ностных элементов исследуемых сетей, формирователь двоичного кода, триггер, первый, второй, третий и четвертый формирователи импульсов, и элемент И, первый вход которого соединен с выходом генератора тактовых импульсов; второй вход — с единичным выходом триггера„ а выход - с входом третьего формирователя импульсов, счетным входом счетчика циклов и первым входом блока наборного попя ВыхОд третьего фОрмирователя импульсов соединен с группой сдвиговых входов блока преобразователей кодвероятность и входом четвертого формирователя импульсов, выход которого соединен с вторым входом блока наборного поля и блока выходных счетчиков, группа выходов блока наборного поля соединена с группой входов блока выходных счетчиков, нулевой и единичный входы формирователя двоичного кода являются нулевым и единичным входами устройства, а группа выходов .соединена с группой установочных входов счетчика циклов и 2 A. группами установочных входов блока преобразователей код — ве30 роятность, группа выходов которэго соединена с группой входов блока наборного поля, вход первого формирователя импульсов является входом запуска устройства, а выход соединен с входом сброса блока выходных счетчиков и с единичным входом триггера, нулевой вход которого соединен с выходом счетчика циклов, вход второго формирователя импульсов явпяеч ся входом записи числа циклов устройства, а выход соединен с управляющим ао входом счетчика числа циклов.

На чертеже представлена блок-схема предлагаемого устройства.

Устройство содержит генератор 1 таю товых импульсов (ГТИ), первый формирователь 2 импульсов, триггер 3, элемент И 4, третий формирователь 5 импульсов, четвертый формирователь 6 импулы=ов, второй формирователь 7 импульсов, счетчик 8 циклов, блок 9 наборного поля, формирователь 10 двоичного кода, блок 11 выходных счетчиков, блок преобразователей 12 код - вероятность.

Выход первого форм(ирователя 2 имПульсов соединен с входом сброса блока 55 выходных счетчиков 11 и единичным входом триггере 3, единичный выход ко торого соединен с первым входом эле5 4. мента И 4. Второй вход элемента И 4 соединен с выходом ГТИ 1, а выход соединен с первым входом блока 9 наборного поля, счетным входом счетчика 8 циклов и входом третьего форммирователя

5 импульсов, выход которого соединен с

Группой сдвиговых входов блока преобразователей 12 код-вероятность и входом четвертого формирователя 6 импульсов. Выход четвертого формирователя 6 импульсов соединен с управляксцим входом блока

11 выходных счетчиков и вторым входом блока 9 наборного поля, группа выходов которого соединена с группой входов блока 11 выходных счетчиков. Выход втор— го формирователя 7 импульсов соединен с управляющим входом счетчика 8 циклов, Bblxoll KOTopot.o coeAHHeH с нулевым вхо дом триггера 3. Группа выходов формирователя 10 двоичного кода соединена .с группой установочных входов счетчика 8 циклов и с группами установочных входов блока преобразователей 12 код — вероятность, группа выходов которого соединена с группой входов блока 9 наборного поля. Блок 9 наборного поля состоит из д (1,2...) импульсных вентилей по числу максимып»ного количества вероятностных элементов исследуемых сетей и шнурового коммутатора, с помощью которого из импульсных вентилей реализуется физическая модель графа исследуемой вероятностной сети, Модель реализуется как соответствующими соединениями между задействованными на данное испытание импульсными вентилями (эпементами сети), так и коммутацией входов и выходов этих вентилей на соответствующие выходы и входы блока 9 наборного поля, Блок 12 преобразователей код - вероятность состоит из VI одиночных преобразователей, каждый из которых в свою очередь состоит из датчика псевдослучайных чисел (ДПСЧ), регистра числа и цифрового KoMBBpsTopB. Каждый задействоваиный нв конкретное испытание пре- . образователь предназначен для "разыгрывания" случайного состояния соответствующего элемента исследуемой вероятностной сети, для чего вйход цифрового компаратора этого преобразователя соединяется с соответствукзцим входом указанного элемента (импульсного вентиля в блоке 9 наборного поля).

Формирователь 10 двоичного кода представляет собой группу переключателей, коммутирующих сигналы уровней

940175 6 турах, содержащих обратные связи, возникают участки сети, которые остакл ся в устойчивом состоянии (триггерный эффект) и препятствуют нормальному прохождению импульса прозвонки по этим участкам во втором, третьем и других последующих тактах. С формированием каждаго импульса ГТИ одновременно происходит вычитание содержимого счетчика 8 циклов. Затем описанный процесс повторяется..

Число элементарных циклов,. описанных выше, занесено в счетчик 8 циклов, и в момент, когда содержимое этого счетчика становится равным нулю, происходит переключение триггера 3, который формирует сигнал, запрещакщий прохождение импульсов ГТИ на выход элемента И 4 до момента подачи очередного сигнала Запуск" на вход формирователя 2 импульсов.

Предлагаемое устройство позволяет довести скорость моделирования верояч» постных графов до десяти миллионов элементарных циклов моделирования в секунду.

Предлагаемая блок-схема выгодно от личает предлагаемое устройство от прототипа значительно более высоким бысч родействием и расширенными возможностями по типам исследуемых структур вероятностных сетей, a также возможность исследования произвольных структур без каких-либо ограничений.

"0" и "1" в соответствии с установленным адресом и заданным кодом на разрядные входы либо счетчика 8 циклов, либо соответствующего ДПСЧ или соответствующего регистра числа в соответствующем преобразователе 12 код — вероятность.

Устройство работает следу куцим образом, 1

На блоке 9 наборного поля посредс вом шнуровой коммутации реализуется граф исследуемой вероятностнойсети, причем выходные звенья сети подключаются к выходным счетчикам блока 11, а . входные звенья сое диняются с выходом элемента И 4. Импульсы, поступающие с этого выхода, используются в качестве сигнала "прозвонки" сети. Затем с помощью формирователя 10 двоичного кода по соответствующим адресам в блок преобразователей 12 код - вероятность заносятся начальные случайные комбинации двоичных чисел для ДПСЧ, а также двоичные коды вероятностей состояния элементов сети для регистров числа. gaлее посредством формирователя 10 двоичного кода и формирователя 7 импульсов в счетчик 8 циклов заносится необходимое число циклов моделирования, по ко- 30 манде Запуск сбрасываются выходные счетчики блока 11 и триггер Э, затем происходит моделирование исследуемой сети методом Монте-Карло. Каждый элементарный цикл моделирования проходит следующим образом. По переднему фронту каждого импульса ГТИ 1, прошедшего на выход элемента И 4 и далее в счетчик 8 циклов и блок 9 наборного поля, посредством формирователя 6 импульсов сначала формируется короткий импульс. для одновременного обновления содержимого всех ДПСЧ блока преобразователей

12 код - вероятность, которое с помощью цифровых компараторов сравнивается с 45 содержимым регистров числа и далее на выходах компараторов появляются сигналы, разрешающие или не разрешающие прохождение импульса через соответствующий импульсный вентиль, причем сигнал сохраняется в течение всего элементарного цикла моделирования. Затем с помощью формирователя 6 импульсов формируется стробирукший импульс, отпирающий одновременно все импульсные венти55 ли блока 9 наборного поля и обеспечивакхдий прохождение импульса прожонки только в период действия стробируюшего импульса. В противном случае в струкВысокое быстродействие за счет . параллельного принципа работы, универсальность функциональных блоков, байтовая органиэация стохастической машины и и рограммо-схемная совместимость ее с 3BN делают Описанное устройство. молным инструментом, предназначенным для моделирования сложных технических систем, представленных вероятностными графами.

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

Вероятностное устройство дпя анализа сетей, содержашее генератор тактовых импульсов, блок выходных счетчиков, счетчик циклов, о т л и ч а ю ш е е с я

".ем что, с целью повышения бы тродей1 ствия, онс содержит блок наборного поля, блок и (1, 2...) преобразователей кодвероятность по числу максимального количества вероятностных элементов исследуемых сетей, формирователь двоичBHHHHH Заказ 4669/71 Тираж 731 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

7 9401 ного кода, триггер, первый, второй, тре- тий и четвертый формирователи импульсов и элемент И, первый вход которого соединен с выходом генератора тактовых импульсов, второй вход - с единичным выходом триггера, а выход - с входом третьего формирователя импульсов> счетным входом счетчика циклов и первым входом блока наборного поля, выход третьего формирователя импульсов соеди- о нен с группой сдвиговых входов блока преобразователей код - вероятность и входом четвертого формирователя импульсов, выход которого соединен с вто рым входом блока наборного поля и блоком выходных счетчиков, группа выходов блока наборного поля соединена с группой входов блока выходных счетчиков, нулевой и единичный входы формирователя двоичного кода являются ну- 2о левым и единичным входами устройства, а группа выходов соединена с группой . установочных входов счетчика циклов и с

75 . 8

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

Источники информации, принятые во внимание при экспертиза

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

% 191908, кл. 506 G 7/48, 1965.

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

No 222754, кл. 606 8 7/48, 1967.

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

l4 193158, кл. G06 6 7/15, 1966 (прототип) .