Устройство для моделирования вероятностного графа

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕРОЯТНОСТНОГО ГРАФА, содержащее первый генератор елучайных сигналов , первый выход которого соединен с (. входом блока индикации, a второй с информационным входом ключа, управляющий вход которого подключен к единичнсэму выходу первого триггера, выход ключа соединен с входе счетчика, выход которого соединён с входом первого элемента ИЛИ и нулевым входом первого три ггера, единичный вход которого является входом устройства, генератор импульсов, выход которого подключен к первому входу первого элементе И и через элемент НЕ к nepBOf входу второго элемента И, выходы первого и второго эяёментов М соединены ссютветственно с вторым и третьим входами блока индикации и образуют выходы устройства , второй и третий генераторы случайных сигналов, выходы которых тюдключенЫ соответственно к нулево ,му и единичному входам второго триггера, единичный выход которого соединен с запрещающим входом элемента запрета, a нулевой выход - с четвёртым входом блока индикации, ин рмационный вход элемента запрета соединен с выходом первого элемента ИЛИ, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет моделирования поведения сложной системы путем учета вероятности появления ошибок 1 и Н рода при определении факта окончания процесса выполнения случайного объема работ, в него введены второй элемент НЕ, четвертый и пятый генераторы случайных сигналов третий и четвертый триггеры, третий и четвертый элементы И и второй элемент ИЛИ, вход второго элемента НЕ соединен с выходом элемента запрета, пятым входом блока индикации и вторым входом третьего элемента И, выход четвертого гене{ атора случайных i сигналов соединен с нулевым входом i третьего триггера и вюстым входом бло to ка индикации, выход пятого гене ратора случайных сигналов соеди sj нен с нулевым входом четвертого | триггера, третьим входом четвертого элемента И и седьмым входом блока индикации, единичные выходы третьего и четвертого триггеров по лючены соответственно к первым входам третьего и четвертого элементов И и третьему входу третьего элемента И, второй вход четвертого элемента И соединен с выходом второго элемента НЕ, выходы третьего и четвёртого элементов И соединены с входами второго элемента ИЛИ, выход которого подключен к

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

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

РЕСЙУЬЛИН ее ао уд): G 06 G 7/52

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

4.(21) 3365896/18-24 (22) 17. 12, 81. (46) 07.07.83.. Бюл. 1 25 (53) 681.325. 5 (088.8) ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

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

К АВТОРСКОМЪ СВИДЕТЕЛЬСТВУ (72) В.П.Бугров, Л.S.Беляев !0.И.Гла голев, И.Н.Долганюк, .Е.-ЯЯарповск 1й, Н.ЛЯоробейников, Л.Д.Радовскнй,, В.И.Родионов, И.Ф.Свиридов и R.Н.Толмачев (56) 1..Авторское свидетельство СССР и 8073!!1, кл. G. 06 F 7/52,. 1978 (прототип). (5!!)(57) УСТРОЙСТВО ДЛЯ ИОЛЕЛИРОВАНИЯ ВЕРОфТТИОСТНОГО: ГРАФА, содержащее первый генератор случайных сиг: налов, первый выход которого соединен.с, первым входом блока индикации, .а второй - с инФормационным входом ключа,.управляющий вход которого подключен к единичному выходу перво" .ro триггера, выход ключа соединен с, входом счетчика, выход которого соединен.с входом первого элемента ИЛИ и нулевым входом первого триггера, единичный вход. которого является входом устройстве, генератор импульсов, выход которого подключен к первому входу первого элемента И и через . элемент НЕ к первому входу второго элемента И, выходы первого и второго элементов И соединены соответственно с вторым и третьим. входами блока индикации и образуют выходы устройства, второй и третий генераторы случайных сигналов, выходы которых подключень! соответственно к нулевому и единичному входам второго триггера, единичный выход которого соединен с.запрещающим входом элемен.та запрета, а нулевой выход - с четвертым входом блока индикации, инфор" мационный вход элемента запрета еое-. динен с выходом первого элементе ИЛИ, отличающееся тем, что, с целью расайрения функциональных возможностей устройства за счет моделирования поведения сложной системы путем учета вероятности появления оаибок 1 и !! рода при определении

Факта окончания процесса выполнения случайного объема работ, в него введены второй элемент НЕ, четвертый и пятый генераторы случайных сигналов третий и четвертый триггеры. третий и четвертый элементы И и второй weмент ИЛИ, вход второго элемента НЕ соединен с выходом элемента запрета, С пятым входом блока индикации и вторым входом третьего элемента И, выЙ ход четвертого генератора случайных сигналов соединен с мулевым входом третьего триггера и шестым входом бло © ка индикации, выход пятого гене- ратора случайных сигналов соеди- ® 4 нен с нулевым входом четвертого триггера, третьим входом четверто- 4 го элемента И и седьмым входом блока индикации, единичные выходы третьего и четвертого триггеров подключены соответственно к первым входам третьего и четвертого элементов И и третьему входу .третьего элемента И, второй вход четвертого элемента И соединен с выходом второго элемента НЕ,- выходы третье"

ro и четвертого элементов И соеди" невы с входами второго элемента

ИЛИ, выход которого подключен к

1027741 вторым входам первого и второго эле" ro и четвертого триггеров соедийены ментов И, а единичные входы третье- с шиной установки.

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

Существует класс сложных систем, моделируемых с помощью вероятностных графов, вершины которых отображают работоспособное состояние или состояние отказа элементов системы, 10 а длины дуг "соответствуют случайным объемам работ, причем при определении факта окончания процесса выполнения случайного объема работы возмож" но появления ошибок 1 и И рода. Ошиб-15 ка 1 рода означает, что работа фактически выполнена, но не произошла фиксация факта окончания процесса выполнения данной работы, а ошибка

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

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

Однако устройство не позволяет исследовать поведение сложной системы . учетом процессов отказов и восста2 новлений при выполнении случайных . объемов работ.

Наиболее близким техническим ре" шением к предлагаемому является устройство, содержащее первый генератор случайных сигналов, первый выход которого соединен с первым входом блока индикации, а второй - с информационным входом ключа, управляющий вход которого подключен к выходу первого триггера, выход ключа соединен с входом счетчика, выход которого соединен с входом элемента ИЛИ и одним из входов первого триггера, второй вход которого является входом устройства, генератор импульсое, выход которого подключен к первому входу первого элемента И и через элемент HE - к первому входу второго элемента И, выходы элементов И соединены соответственно с вторым и третьим входами блока индикации, а также элемент запрета, второй триггер, второй и третий генераторы случайных сигналов, выходы которых подключены соответственно к первому и второму входам второго триггера, первый и второй выходы которого соединены соответственно с четвертым входом блока индикации и первым входом элемента; запрета, второй вход кото1 ,рого подключен к выходу элемента ИЛИ, а выход соединен с вторыми входами элементов И, Это устройство позволяет моделировать поведение сложной системы с учетом процессов отказов и восстановлений при.выполнении случайных объемов работ, ассоциируемых с вершинами графа (2 ).

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

fl рода.

10277 4

3

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

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

1 4 третьего элемента И, второй вход чет. вертого элемента И соединен с выходом второго элемента НЕ, выходы-тре" тьего и четвертого элементов И соединены с входами второго элемента

ИЛИ, выход которого подключен к вторым входам первого и второго элементов И, а единичные входы третьего и четвертого триггеров соединены с шиной установки.

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

Устройство содержит генератор 1 случайных сигналов, ключ 2, счетчик

3, первый триггер 4, первый элемент ИЛИ 5, элемент 6 запрета, второй триггер 7, второй, третий и четвертый генераторы 8-10 случайных сигналов, элемент НЕ 11, первый и второй элементы И 12 и 13, блок 14 индикации, четвертый генератор 1 » случайных сигналов, третий триггер

16, элемент НЕ 17, третий и четвертый элементы И 18 и 19, четвертый триггер 20, пятый генератор 21, случайных сигналов, элемент ИЛИ 22.

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

В момент подачи на вход устройст" ва сигнала запуска триггеры 4, 16 и 20 устанавливаются в единичное состояние, что приводит в состояние готовности элементы И 18 и 12, элемент 6 запрета и ключ 2. Импульсы от генератора 1 начинают поступать через ключ 2 на вход счетчика 3.

Через случайное время после отсчета числа импульсов, соответствующего длине дуги взвешенного графа, счетчик 3 переполняется и выдает импульс, который перебрасывает триггер 4 в нулевое состояние, закрывая ключ 2, и одновременно через элемент ИЛИ 5 поступает на вход элемента 6 запре" та. При единичном состоянии триггеров

7, 16 и 20 импульс с выхода элемента 6 поступает через элемент И 18 и элемент ИЛИ 22 на первые входы элементов И 12 и 13. На второй вход элемента И 12 поступают импульсы с гене" ратора 10 непосредственно, а на второй вход элемента И 13 - через элемент НЕ 1 1. Изменение частоты и скваж" ности импульсов генератора. 10 устанавлив ается вероятност ь Р, соответствующая выходу А. При. моделировании в случае единичного состояния триггеров 7, 16 и 20 сигнал, соответству.5 10 ющий, факту завершения процесса.выпол. нения случайного объема работы, с вероятностью P проходит на выход k, а с вероятностью а=1-р - на выход 8.

Процесс отказов и восстановлений при выполнении случайного объема работы моделируется сменой состояний триггера 7, который в момент запуска устройства устанавливается в единичное состояние. При поступлении на нулевой вход. триггера 7 сигнала от генератора 8, моделирующего отказы в процессе выполнения случайного объема рабат, ассоциируемых с данной вершиной графа, триггер 7 переходит в нулевое состояние, которое сохраняется до тех пор пока на единичный вход триггера не поступит сигнал от генератора 9, моделирующего процесс восстановления.

Отсутствие сигнала на.выходе. элемента 6 запрета означает, что либо не произошло переполнение счетчика 3, либо триггер 7 установился в нулевое состояние. Оба эти события показыва" ют, что процесс выполнения случайного объема работ, ассоциируемого с данной вершиной графа, фактически нв окончен. При этом на первом входе элемента И 19 имеется разрешающий сигнал ат триггера 16, установленного в единичное состояние при запуске устройства, а на в" ором входе элемента

И 19 присутствует разрешающий сигнал с выхода элемента НЕ 17, вход которого соединен с выходом элемента

6 запрета. Указанное сочетание разрешающих сигналов на первом и втором входах элемента И 19 приводит к тому, чта при поступлении на третий вход импульса от генератора 21 случайных сигналов, имитирующих появление ошибок П рода, этот импульс через элемент ИЛИ 22 поступает на первые входы элементов И 12 и 13. На второй вход элемента И 12 поступают импульсы с генератора 10 непосредственно, а на второй вход элемента И 13 - через элемент НЕ 11.

Поэтому сигнал, соответствующий ошибке П рода с вероятностью Р, проходит на выход А, а с вероятностью q=l-p - на выход В. Импульс от генератора 21 случайных сигналов одновременно с поступлением на третий вход элемента И 19 подается на вход триггера 20, перебрасывая1 этот триггер в нулевое состояние. При этом на третьем входе элемента И 18

27.741 6 появляется запрещающий сигнал с выхода триггера 20 и сигнал с выхода эле" мента 6 запрета, соответствующий фактическому выполнению случайного объема работ, ассоциируемого с данной вершиной графа, с учетом процессов отказов и восстановлений в процессе выполнения этого объема работ, не поступает через элемент И 18

10 на один из входов элемента ИЛИ 22.

Поэтому на выходах А и В не фиксируется факт окончания процесса выполнения случайного объема работ, ассоциируемых с данной вершиной граба, а регистрируется с вероятностью р H q=l"р соответственно появление ошибки П рода.

Процесс Формирования ошибки 1 рода моделируется с помощью генера20 тора 15 случайных сигналов и триггера 16, Эта часть схемы работает следующим образом. Импульс от генератора 15 случайных сигналов, имитирующих появление ошибок 1 рода, поступает на вход триггера 16 и перебрасывает его в нулевое состояние. Нулевое состояние триггера 16 приводит к тому, что на первые входы элементов И 18 и 19 подается запрещающий сигнал. При этом элемент И 18

З0 не пропускает на вход элемента

ИЛИ 22 сигнал с выхода элемента 6 запрета о фактическом окончании процесса выполнения случайного объема работ, ассоциируемого с данной верЗ5 виной графа, а элемент И 19 не пропускает сигнал ошибки П рода. Таким образом, на первых входах элементов

И 12 и 13 при нулевом состоянии триггера 16 имеются запрещающие сиг4о налы, что приводит к невозможности регистрации на выходах А и В устройства факта окончания процесса выполнения данной работы.При этомблок 14 индикации, предназначенный для накоп45 ления статическихданных обисследуемом графе, фиксирует ошибку 1 рода.

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

50 для исследования надежности комплексов алгоритмов и программ.

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

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

1027741

Р

Составитель С.Назаров

Редактор H.Ãðèøàíîâà Техред С.Иигунова . Корректор О.Тигор

Заказ 4742/54 Тираж 706 . Подписное

ВНИИПИ Государственного комитета СССР по.делам изобретений. и открытий

f13035, Москва, _#_-35, Рауаская наб., д. 4/5

»евое юею авююю юе филиал ППП "Патент", r. Ужгород, ул. Проектная, 4