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

Авторы патента:

G06F7/70 - с помощью стохастической последовательности импульсов, т.е. случайно возникающих импульсов, средняя частота повторения которых представляет числа

G06F15/173 - с использованием сети связи, например, соединение по схеме матрицы, смешанное соединение, соединение по схеме пирамиды, звезды, снежинки (схемы переключения интерфейсов G06F 13/40)

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

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

РЕСПУБЛИК

3Ю9 G 06 F 15/36

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3354202/18-24 (22) 09.11.81 (46.) 07.04.83. Бюл. Р 13 (72) Б.И.Азаров и В.N .Ãðèøèí (71) Московский ордена Ленина и ордена Октябрьской Революции авиационный институт им.Серго Орджоникидзе (53) 681.3 (088.8) (56) 1. Авторское свидетельство СССР

9 193158, кл. G 06 F 15/36, 1967.

2. Авторское свидетельство СССР по заявке Р 3222659/18-24, кл. С 06 F 15/36, 18.12.80. (54)(57) СТОХАСТИЧЕСКОЕ УСТРОЙСТВО

ДЛЯ ВЫЧИСЛЕНИЯ ХАРАКТЕРИСТИК ГРАФОВ, содержащее первый и второй формирователи импульсов, входы которых являются соответственно пусковым входом и входом записи числа циклов .устройства, первый триггер, единичный вход которого соединен с выходом первого формирователя импульсов, первый элемент И, первый вход которого соединен с единичным выходом первого триггера, генератор тактовых импульсов, выход которого соединен с. вторым входом первого элемента И, счетчик циклов, вход записи которого соединен с выходом второго формирователя импульсов, счетный вход подключен к выходу первого элемента И, а выход соединен с нулевым входом первого триггера, блок наборного поля, первый вход которого подключен к выходу первого элемента И,. блок преобразователей код-вероятность, группа выходов которого соединена с группой входов блока наборного поля, формирователь двоичного кода, нулевой и единичный вхо-. ды которого являются соответственно нулевым и единичным входами устройства, а группа выходов соединена с группами установочных входов счетчика циклов и блока преобразователей

„„SU„,1010628 А код-вероятность, третий формирователь импульсов, вход которого подключен к выходу первого элемента И, а выход соединен с группой сдвиговых входов блока преобразователей код-вероятность, четвертый формирователь импульсов, вход которого подключен к выходу третьего формирователя импульсов, блок выходных счетчиков, вход сброса которого подключен к выходу первого формирователя импульсов, а группа выходов является выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем реализации закона распределения случайного числа выходных С2 звеньев моделируемых сетей, оно дополнительно содержит регистр сдвига, дешифратор, первый и второй счет чики, генератор импульсов, пятый и шестой формирователи импульсов, второй триггер и второй элемент И,причем вход пятого формирователя и импуль сов,второй вход блока наборного поля и вход записи регистра сдвига подключены к выходу четвертого формирователя импульсов, выход пятого фор- . мирователя импульсов соединен с еди ничным входом второго триггера, вхо-. дом записи первого счетчика и входом сброса второго счетчика, счетный вход которого соединен с выходам регистра сдвига, а разрядные выходы соединены с группой входов дешифратора, единичный выход второго триггера соединен с первым входом второго элемента И, второй вход которого соединен с выходом генератора .импульсов, а 3ю выход соединен со счетным входом первого счетчика и тактовым входом регистра сдвига, выход первого счетчика соединен с нулевым входом второго триггера и входом шестого формирователя импульсов, выход которого соединен с управляющим входом дешифратора, выходы которого соединены с

1010628

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

Известно устройство, содержащее генератор тактовых импульсов, блок 10 выходных счетчиков, счетчик циклов и другие блоки f1 ). Это устройство позволяет последовательно разыгрывать случайные состояния элементов вероятностного графа., 15, Однако оно отличается ограниченными функциональными возможностями и низким быстродействием.

Наиболее близким к предлагаемому является вероятностное устройство анализа сетей, представляе20 мых вероятностными графами, которое содержит генератор тактовых импульсов, триггер формирователи импуль( сов, элемент И, счетчик циклов, блок наборного поля, блок m (1, 2,...)

25 преобразователей код-вероятность по числу максимального количества вероятностных элементов исследуемых сетей, формирователь двоичного кода и блок выходных счетчиков 123.

Основным недостатком этого устройства является отсутствие воэможности вычисления законов распределения случайного числа неизолированных (управляемых ) выходных звень- 35 ев вычисляемых графов вероятностной сети. Закон распределения является наиболее полной характеристикой любой случайной величины. Зная его, можно вычислить и любые другие чис- 40 ловые характеристики случайной величины, например дисперсию и математическое ожидание.

Цель изобретения вЂ” расширение функциональных возможностей путем оп- 45 ределения законов распределения случайного числа выходных звеньев вычисляемых графов.

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

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

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

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

12, второй элемент 13 И, шестой формирователь 14 импульсов, блок 15 наборного поля, формирователь 16 двоичного кода, регистр 17 сдвига, второй счетчик 18, дешифратор 19, блок:

20 выходных счетчиков и блок 21 преобразователей код-вероятность.

Выход первого формирователя 1 им- . пульсов соединен с единичным входом первого триггера 3 и входом сброса блока 20 выходных счетчиков, а вход является пусковым входом устройства.

Вход второго формирователя 2 импульсов является входом записи числа циклов устройства, а выход подключен 35 к входу записи счетчика б циклов, выход которого соединен с нулевым входом первого триггера 3. Второй вход элемента 5 И соединен с выходом генератора 4 тактовых импуль- 40 сов, а первый вход вЂ” с единичным выходом первого триггера 3. Выход элемента 5 И соединен с входом третьего формирователя 7 импульсов, счетным входом счетчика 6 циклов и пер- 45 вым входом блока 15 наборного поля.

Вход четвертого формирователя 8 импульсов подключен к выходу третьего формирователя 7 импульсов и соеди. нен с группой сдвиговых входов блока

21 преобразователей код-вероятность, а выход соединен с вторым входом блока 15 наборного поля, входом записи регистра 17 сдвига и входом пятого формирователя 9 импульсов, выход которого соединен с единичным входом 55 второго триггера 10, входом сброса второго счетчика 18 и входом записи первого счетчика 12. Нулевой вход второго триггера -10 соединен с входом шестого формирователя 14 импуль- 60 сов и выходом первого счетчика 12, а единичный выход подключен к первому входу второго элемента 13 И, второй вход которого связан с выходом генератора 11 импульсов. Выход второго элемента 13 И соединен со счетным входом первого счетчика 12 и тактовым входом регистра 17 сдвига. Выход шестого формирователя 14 импульсов подключен к управляющему входу дешифратора 19 ° Группа выходов формирователя 16 двоичного. кода связана с груп-. пами входов блока 21 преобразователей код-вероятность счетчика б циклов.

Группа входов блока 15 наборного поля соединена с группой выходов блока 21 преобразователей код-вероятность, а группа выходов - с группой входов регистра 17 сдвига, выход которого подключен к счетному входу второго счетчика 18 ° Группа входов дешифратора 19 соединена с разрядными выходами второго счетчика 18, а группа выходов соединена с группой входов блока 20 выходных счетчиков.

Блок 15 наборного поля идентичен аналогичному блоку прототипа и состоит изп (1,2...) импульсных вентилей (по числу максимального количества вероятностных элементов исследуемых сетей ) и шнурового коммутатора, с помощью которого из импульсных вен- тилей реализуется физическая модель графа исследуемой вероятностной сети.

Модель реализуется как с помощью соответствующих соединений между задействованными на данное испытание импульсными вентилями (элементами

-сети ), так и коммутацией входов и выходов этих вентилей на соответствующие выходы и входы блока.

Блок 21 преобразователей код-вероятность также идентичен аналогичному блоку прототипа и состоит из

m(21 . вЂ” 21щ} одиночных преобразователей, каждый из которых в свою очередь, состоит из датчика псевдослучайных чисел (ДПСЧ), регистра числа и цифрового компаратора. Каждый задействованный на конкретное испытание преобразователь предназначен для "разыгрывания" случайного состояния соответствующего элемента исследуемой вероятностной сети, для чего выход цифрового компаратора этого преобразователя соединяют с соответствующим входом указанного элемента (импульсного вентиля в блоке 15- наборного поля ).

Формирователь 16 двоичного кода также идентичен аналогичному блоку прототипа и представляет собой группу переключателей, коммутирующих сигналы уровней "0" и "1" в соответствии с установленным адресом и заданным кодом на разрядные входы либо счетчика б циклов„ либо соответствующего ДПСЧ или соответствующего регистра числа в соответствую-щем преобразователе код-вероятность блока ."=.1.

Устройство работает следующим образом.

1010628

На блоке 15 наборного поля посрел:твом шнуровой коммутации реализуэтся граф анализируемой или опорный структурный граф синтезируемой вероятностной сети, причем выходные зненья сети подключаются к информа- 5 ционным входам регистра 17 сдвига, а входные звенья соединяются с выходом первого элемента 5 И. Импульсы, поступающие с этого выхода, используются н качестве сигнала "прозвон- 1Д ки" сети. Затем с помощью формирователя 16 двоичного кода по соответствующим адресам в блок 21 преобразователей код-вероятность заносятся начальные случайные комби- 15 нации дноичных чисел для ДПСЧ, а также двоичные коды вероятностей состояния элементов сети для регистров числа. Далее посредством формирователя 16 двоичного кода и второго формирователя 2 импульсов в счетчик б циклов заносится необходимое число циклов моделирования, по команде "Пуск" сбрасываются выходные счетчики блока 20 и первый триггер 3, а затем происходит моделирование сети методом Монте-Карло.

Каждый элементарный цикл моделирования проходит следующим образом.

По переднему фронту каждого импульса генератора 4 тактовых импульсов, прошедшего на выход первого элемента 5 И и далее в счетчик б циклов и блок 15 наборного поля, посредством формирователя 7 импульсов сначала формируется короткий им- 35 пульс для одновременного обновления содержимого всех ДПСЧ блока

15 преобразователей код-вероятность, которое с помощью цифровых компараторов сравнивается с содержимым ре- 40 гистров числа, и далее на выходах компараторов появляются сигналы, разрешающие или не разрешающие прохождение импульса через соответствующий импульсный вентиль, причем сигналы на выходах компараторов сохраняются н течение всего элементарного цикла моделирования, Затем с помощью формирователя 8 импульсов формируется стробирующий импульс, отпирающий одновременно все импульсные вентили блока 15 наборного поля и обеспечивающий прохождение импульса "прозвонки" только в период действия стробирующего импульса. В противном случае в структурах, содержащих обратные связи, возникают участки сети, которые остаются в устойчином состоянии и препятствуют нормальному прохождению импульса

"прозвонки" по этим участкам во вто- 60 ром, третьем и других последующих тактах. Задний фронт стробирующего импульса используют для записи логических состояний ныходных звеньев сети в регистр 17 сдвига. 65

Далее вступает в работу часть схемы управления, состоящая из формирователя 9 импульсов, второго триггера 10, первого счетчика 12, генератора 11 импульсов, второго элемента 13 И и формирователя 14 импульсов. Задний фронт стробирующего импульса поступает на формирователь 9 импульсов, который формирует короткий импульс, устанавливаюций второй триггер 10 в единичное состояние, сбрасывающий второй счетчик 18 и одновременно записывающий в первый счетчик 12 фиксированное двоичное число, соответствующее числу разрядов регистра 17 сдвига. Появившаяся гогическая "1" на выходе второго триггера 10 дает возможность прохождению импульсов генератора 11 импульсов на счетный вход первого счетчика 12 и тактовый вход регистра 17 сдвига, который после прохождения стробирующего импульса с выхода формирователя 8 импульсов переходит в режим сдвига записанной в нем информации. Для того, чтобы не снижать быстродействия всего устройства, генератор 11 импульсов работает на повышенной по сравнению с генератором 4 тактовых импульсов частоте. По мере сдвига унитарного двоичного кода, записанного в регистр 17 сдвига, и заполнения второго счетчика 18 происходит вычитание содержимого первого счетчика 12,и н момент, когда содержимое этого счетчика обратится в ноль, на его выходе появляется импульс. переноса, который сбрасывает второй триггер 10, запрещая тем самым прохождение импульсон с выхода генератора 11 импульсов на тактовый вход регистра 17 сдвига, одновременно запуская формирователь 14 импульсов.

В этот момент на входах дешифратора

19 сформировано двоичное число, соответствующее числу неизолиронанных выходных звеньев вероятностной сети, полученное н данной реализации, Далее с выхода формирователя

14 импульсов поступает короткий импульс, разрешающий работу дешифратора 19, в результате чего меняется содержимое одного из счетчиков .блока 20.

С формированием каждого импульса генератора 4 тактовых импульсов одновременно происходит нычитание содержимого счетчика 6 циклов .

Затем описанный процесс пов :-.оряется.

Число описанных элеме-. тарных циклов занесено в счетчик 6 циклон, и в момент, когда содержимо этого счетчика становится равным нул:о, происходит переключение первого триггера 3, который формирует сигнал, запрещающий прохождение им1010628

ВНИИПИ Заказ 2490/38 Тираж 704 . Подписное

Филиал ППП "Патент", г. Ужгород, ул .Проектная,4 пульсов генератора 4 тактовых импульсов на выход элемента 5 И до момента подачи очередного сигнала

"Пуск" на вход формирователя 1 импульсов.

После окончания работы устройства в блоке 20 выходных счетчиков содержится полная информация об искомом законе распределения, которая

Ф далее может использоваться для вычисления различных статистических числовых характеристик.

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

TGM что оно позволяет вычислять распределения случайного числа неиэолированных звеньев. Такие характеристики особенно важны при оценке эффективности различных вариантов

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