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

СОЮЗ СОВЕТСКИСОЦИАЛИСТИЧЕСН РЕСПУБЛИК Г 15/3 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(71) Московский ордена Ленина и ордена Октябрьской Революции авиационный институт им.Серго Орджоникидзе(56) 1. Авторское свидетельство СССРМ 193158, кл. 6 06 Г 15/36, 1967.2. Авторское свидетельство СССРпо заявке Р 3222659/18-24,кл. С 06 Е 15/36, 18,12.80,(54)(57) СТОХАСТИЧЕСКОЕ УСТРОЙСТВОДЛЯ ВЫЧИСЛЕНИЯ ХАРАКТЕРИСТИК ГРАФОВ,содержащее первый и второй формирователи импульсов, входы которых являются соответственно пусковым входом и входом записи числа циклов .устройства, первый триггер, единичныйвход которого соединен с выходомпервого формирователя импульсов, первый элемент И, первый вход которого соединен с единичным выходом первого триггера, генератор тактовыхимпульсов, выход которого соединен свторым входом первого элемента И,счетчик циклов, вход записи которого соединен с выходом второго формирователя импульсов, счетный входподключенк выходу первого элемента И, а выход соединен с нулевым входом первого триггера, блок наборного поля, первый вход которого подключен к выходу первого элемента И,.блок преобразователей код-вероятность, группа выходов которого соединена с группой входов блока наборного поля, формирователь двоичного кода, нулевой и единичный вхо-.ды которого являются соответственнонулевым и единичным входами устройства, а группа выходов соединена сгруппами установочных входов счетчика циклов и блока преобразователей,8010106 код-вероятность, третий формирователь импульсов, вход которого подключен к выходу первого элемента И, а выход соединен с группой сдвиговых входов блока преобразователей код-вероятность, четвертый формирователь импульсов, вход которого подключен к выходу третьего формирователя импульсов, блок выходных счетчиков, вход сброса которого подключен к выходу первого формирователя импульсов, а группа выходов является выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем реализации закона распределения случайного числа выходных С 2 звеньев моделируемых сетей, оно дополнительно содержит регистр сдвига, дешифратор, первый и второй счет чики, генератор импульсов, пятый и шестой формирователи импульсов, вто" рой триггер и второй элемент И,причем вход пятого Формирователя и импуль сов,второй вход блока наборногополя и вход записи регистра сдвига подключены к выходу четвертого Формирователя импульсов, выход пятого фор- . мирователя импульсов соединен с еди- ничным входом второго триггера, входом записи первого счетчика и входом сброса второго счетчика, счетный вход которого соединен с выходам регистра сдвига, а разрядные выходы соединены с группой входов дешифратора, единичный выход второго триггера соединен с первым входом второго элемента И, второй вход которого соединен с выходом генератора импульсов, а ВЬ выход соединен со счетным входом первого счетчика и тактовым входом регистра сдвига, выход первого счетчика соединен с нулевым входом второго триггера и входом шестого Формирователя импульсов, выход которого соединен с управляющим входом дешифратора, выходы которого соединены с1010628 Изобретение относится к вычислительной технике, а более конкретно к специализированным вычислительным устройствам, предназначенным для получения оценок качества функциони- ,5 рования систем управления, представляемых сложными вероятностными графами.Известно устройство, содержащее генератор тактовых импульсов, блок 10 выходных счетчиков, счетчик циклов и другие блоки Г 1 . Это устройство позволяет последовательно разыгрывать случайные состояния элементов вероятностного графа. , 15,Однако оно отличается ограниченными функциональными возможностями и низким быстродействием.Наиболее близким к предлагаемому является вероятностное устройство анализа сетей, представляе 20 мых вероятностными графами, которое содержит генератор тактовых импульсов, триггер формирователи импульсов, элемент И, счетчик циклов, блок наборного поля, блок п 1,2,)25 преобразователей код-вероятность по числу максимального количества вероятностных элементов исследуемых сетей, формирователь двоичного кода и блок выходных счетчиков 123.30Основным недостатком этого устройства является отсутствие воэможности вычисления законов распределения случайного числа неизолированныхуправляемых ) выходных звень ев вычисляемых графов вероятностной сети. Закон распределения является наиболее полной характеристикой любой случайной величины. Зная его, можно вычислить и любые другие чис ловые характеристики случайной величины, например дисперсию и математическое ожидание.Цель изобретения " расширение функциональных возможностей путем оп ределения законов распределения случайного числа выходных звеньев вычисляемых графов.Поставленная цель достигается тем, что стохастическое устройство, содержащее первый и второй формирователи импульсов, входы которых являются соответственно пусковым входом и входом записи числа циклов устройства, первый триггер, единичный вход которого соединен с выходом первого 55 формирователя импульсов, первый элемент И, первый вход которого соединен с единичным выходом первого триггера, Генератор тактовых импульсов,выход которого соединен с вторым входом первого элемента И, счетчик циклов, вход эаписи которого соединен свыходом второго формирователя импульсов, счетный вход подключен к выходупервого элемента И, а выход соединен с нулевым входом первого триггера, блок наборного поля, первый входкоторого подключен к выходу первогоэлемента И, блок преобразователейкод-вероятность, группа выходов которого соединена с группой входов блока наборного поля, формирователь двоичного кода, нулевой и единичный входы которого являются соответственнонулЕвым и единичным входами устройства, а группа выходов соединена с группами установочных входов счетчикациклов и блока преобразователей кодвероятность, третий формировательимпульсов, вход которого подключен к выходу первого элемента И, авыход соединен с группой сдвиговыхвходов блока преобразователей кодвероятность, четвертый формировательимпульсОв, вход которого подключен квыходу третьего формирователя импульсов, блок выходных счетчиков,вход сброса которого подключен к выходу первого формирователя импульсов, а группа выходов является выходами устройства, дополнительно содержит регистр сдвига, дешифратор, первый и второй счетчики, генератор импульсов, пятый и шестой формирователи импульсов, второй триггер и второй элемент И, причем вход пятогоформирователя импульсов, второй входблока наборного поля и вход эаписирегистра сдвига подключены к выходучетвертого формирователя импульсов,выход пятого формирователя импульсовсоединен с единичным входом второготриггера, входом записи первого счетчика и входом сброса второго счетчика, счетный вход которого соединен свыходом регистра сдвига, а разрядныевыходы соединены с группой входов дешифратора, единичный выход второготриггера соединен с первым входомвторого элемента И, второй вход которого соединен с выходом генератораимпульсов, а выход соединен со счетгруппой входов блока выходных счетчиков, группа выходов блока наборного поля соединена с группой входов регистра сдвига.ным входом первого счетчика и тактовым входом регистра сдвига, выходпервого счетчика соединен с нулевымвходом второго триггера и входомшестого формирователя импульсов,выход которого соединен с управляющим входом дешифратора, выходы дешифратора соединены с группой входов блока выходных счетчиков, группавыходов блока наборного поля соединена с группой входов регистра 1 Осдвига.На чертеже изображена блок-схема устройства,Устройство содержит первый 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 тактовых импуль Осов, а первый вход - с единичным выходом первого триггера 3, Выход элемента 5 И соединен с входом третьего формирователя 7 импульсов, счетным входом счетчика 6 циклов и первым входом блока 15 наборного поля.Вход четвертого формирователя 8 импульсов подключен к выходу третьегоформирователя 7 импульсов и соеди. нен с группой сдвиговых входов блока21 преобразователей код-вероятность,а выход соединен с вторым входом блока 15 наборного поля, входом записирегистра 17 сдвига и входом пятогоформирователя 9 импульсов, выходкоторого соединен с единичным входом 55второго триггера 10, входом сбросавторого счетчика 18 и входом записипервого счетчика 12. Нулевой входвторого триггера .10 соединен с входом шестогоформирователя 14 импульсов и выходом первого счетчика 12, аединичный выход подключен к первомувходу второго элемента 13 И, второйвход которого связан с выходом генератора 11 импульсов. Выход второго элемента 13 И соединен со счетнымвходом первого счетчика 12 и тактовым входом регистра 17 сдвига. Выходшестого формирователя 14 импульсовподключен к управляющему входу дешифратора 19Группа выходов формирователя 16 двоичного. кода связана с груп-.пами входов блока 21 преобразователейкод-вероятность счетчика б циклов,Группа входов блока 15 наборного полясоединена с группой выходов блока 21преобразователей код-вероятность, агруппа выходов - с группой входов регистра 17 сдвига, выход которого подключен к счетному входу второго счетчика 18Группа входов дешифратора 19соединена с разрядными выходами второго счетчика 18, а группа выходовсоединена с группой входов блока 20выходных счетчиков,Блок 15 наборного поля идентиченаналогичному блоку прототипа и состоит изп(1,2) импульсных вентилейпо числу максимального количествавероятностных элементов исследуемыхсетей ) и шнурового коммутатора, спомощью которого из импульсных вен-тилей реализуется физическая модельграфа исследуемой вероятностной сети.Модель реализуется как с помощьюсоответствующих соединений между задействованными на данное испытаниеимпульсными вентилями ( элементамисети), так и коммутацией входов ивыходов этих вентилей на соответствующие выходы и входы блока.Блок.21 преобразователей код-вероятность также идентичен аналогичному блоку прототипа и состоит изв(21- 21 щ) одиночных преобразователей, каждый из которых в своюочередь, состоит из датчика псевдослучайных чисел ДПСЧ), регистрачисла и цифрового компаратора. Каждый задействованный на конкретноеиспытание преобразователь предназначен для "разыгрывания" случайногосостояния соответствующего элемента исследуемой вероятностной сети,для чего выход цифрового компаратора этого преобразователя соединяют с соответствующим входом указанного элемента импульсного вентиля в блоке 15 наборного поля ).Формирователь 16 двоичного кодатакже идентичен аналогичному блокупрототипа и представляет собой группу переключателей, коммутирующихсигналы уровней "0" и ф 1" в соответствии с установленным адресоми заданным кодом на разрядные входылибо счетчика б циклов либо соответствующего ДПСЧ или соответствующего регистра числа в соответствующем преобразователекод-вероятностьблока .":.1.лУстройство работает следующимобразом.На блоке 15 наборного поля посрел:твом шнуровой коммутации реализуэтся граф анализируемой или опорный структурный граф синтезируемой вероятностной сети, причем выходные зненья сети подключаются к информа ционным входам регистра 17 сдвига, а входные звенья соединяются с выходом первого элемента 5 И. Импульсы, поступающие с этого выхода, используются н качестве сигнала "прозвон ки" сети, Затем с помощью формирователя 16 двоичного кода по соответствующим адресам в блок 21 преобразователей код-вероятность заносятся начальные случайные комби нации дноичных чисел для ДПСЧ, а также двоичные коды вероятностей состояния элементов сети для регистров числа, Далее посредством формирователя 16 двоичного кода и второго формирователя 2 импульсов в счетчик б циклов заносится необходимое число циклов моделирования, по команде "Пуск" сбрасываются выходные счетчики блока 20 и первый триггер 3, а затем происходит моделирование сети методом Монте-Карло.Каждый элементарный цикл моделирования проходит следующим образом.По переднему фронту каждого импульса генератора 4 тактовых импульсов, прошедшего на выход первого элемента 5 И и далее в счетчик б циклов и блок 15 наборного поля, посредством формирователя 7 импульсов сначала формируется короткий им пульс для одновременного обновления содержимого всех ДПСЧ блока 15 преобразователей код-вероятность, которое с помощью цифровых компараторов сравнивается с содержимым ре гистров числа, и далее на выходах компараторов появляются сигналы, разрешаюц 1 ие или не разрешающие прохождение импульса через соответствующий импульсный вентиль, причем сигналы на выходах компараторов сохраняются н течение всего элементарного цикла моделирования, Затем с помощью Формирователя 8 импульсов Формируется стробирующий импульс, отпирающий одновременно все импульсные вентили блока 15 наборного поля и обеспечивающий прохождение импульса "прозвонки" только в период действия стробирующего импульса. В противном случае в структурах, содержащих обратные связи, возникают участки сети, которые остаются в устойчином состоянии и препятствуют нормальному прохождению импульса "прозвонки" по этим участкам во вто ром, третьем и других последующих тактах. Задний фронт стробирующего импульса используют для записи логических состояний ныходных звеньев сети в регистр 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/ 4 . Подпис Тираж илиал ППП фПате пульсов генератора 4 тактовых импульсов на выход элемента 5 И до момента подачи очередного сигнала фПуск" на вход формирователя 1 импульсов.После окончания работы устройства в блоке 20 выходных счетчиков содержится полная информация об искомом законе распределения, которая далее может использоваться для вычисления различных статистических числовых характеристик,Предлагаемое устройство выгодно отличается от прототипа расширенными функциональными возможностями, что позволяет эффективно решать задачи анализа и синтеза сложных технических систем, представленных ввиде вероятностного графа. Положительный эффект изобретения помимовысокого быстродействия, состоит втом, что оно позволяет вычислять распределения случайного числа неиэолированных звеньев. Такие характеристики особенно важны при оценкеэффективности различных вариантов 10 структур систем управления различной Физической природы. Предлагаемое устройство позволяет также оперативно оценивать надежность разнообразных технических систем, форма лизованных в виде вероятностногографа. г. Ужгород, ул .Проектная,