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

формируется сигнал, по которому триг- 30 разом, те разряды счетчика, на кото

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

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

Блоки 7 памяти ПТН отличаются организацией записи. Когда на второй вход блока 7 памяти ПТН (фиг. 3) поступает адресный код, по соответствующему адресу производится выборка информации, которая с задержкой на время выборки формируется на его первых выходах и подается на блок 8 определения минимума, где сравнивается с текущим значением содержимого блока 11 подсчета количества разорванных дуг. После задержки на время сравнения на выходе соответствующего блока 8 определения минимума может сформироваться сигнал разрешения записи (в зависимости от результата сравнения). Таким образом, сигнал разрешения записи на четвертом входе блока 7 памяти ПТН формируется с некоторой суммарной задержкой по отношению к сигналу адресного кода на первом входе этого же блока. Сигнал разрешения записи на входе блока .6 памяти параметров достижимости форрые от наборного поля 9 поступают О, оказываются блокированными и в работе счетчика не участвуют. Эти же нулевые блокирующие сигналы, поступающие от наборного поля 9, подаются на разрешающие входы элементов И, которые включены после прямых и инверсных выходов триггеров. Эти элементы И оказываются закрытыми, и на входы

элементов И 4 и входы блока 11 подаются нулевые сигналы. Это означает, что соответствующие элементы И 4 и входы блока 11 в работе устройства не участвуют, поскольку они соответствуют незадействованным в топологии графа дугам, а перебор дуг при моде,- лировании их разрыва соответствует тем| логическим элементам 4, на пер- вые входы которых с наборного поля 9

поступают 1.

Блок 11 подсчета количества разорванных дуг (фиг. 5) состоит из формирователя 11.1, представляющего собой одновибратор, счетчиков 11.2

и 11.3, генератора 11.4 и мультиплексора 11.5. На первую группу входов блока 11 подсчета количества разорванных дуг подается код перебора подмножеств от блока 10 перебора подмно

жеств. По сигналу с выхода блока 1 управления на второй вход блока 11 подсчета количества разорванных дуг поступает запускающий сигнал. Накаждом подготовительном цикле этот сигнал нулевой, а на каждом рабочем цикле - единичный. При окончании каждого подготовительного цикла с помощью формирователя 11.1 счетчики 11.2 и 11.3 сбрасываются и на генератор 11.4 с выхода переполнения счетчика 11.2 поступает разрешающий сигнал. Генератор 11.4 работает до заполнения счетчика 11.2. С помощью мульти- плексора 11.5 на его входе формируются импульсы, количество которых соответствует количеству единиц в коде, поступающем от блока 10 перебора подмножеств. Эти импульсы под- считываются счетчиком 11.3, и на его выходе формируется двоичный код, соответствующий количеству единиц в коде, поступающем от блока 10 перебора подмножеств, которое соответствует количеству разорванных дуг.

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

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

0

0 5 0 5 0

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

C(n+i)BwO 9л faока. з, конец цикла.

Фиг. 2

Установка 8 исюдное состояние

Г выхода и/юна 8j - {разрешение janucu)

Cfux.J йдока Ctux.Qj f/нжаб (запись)

С Вых. ffloKa I 1

(адрес, ини N дершин, от которой on редел ftn- tli йостижиность)

С Выи fauna 11 2 (количество разорванных дуе)

Счет

1 Купону 2

Cfpoc

Вторым Входам

fflQKod 10 и. 11 (счет подмножеств и запуск при подсчете количества разорванных дуг)

/Г третьим бходам блоков 7 и 10 (установка б исходное состояние

.

-«г1|

3

вх Г

От

Hubfa- ногс поля 9

C&tfrtt

6af l (счет),

ГЛяЗ

Фиг. 5

Составитель 0.Гречухина

Редактор И.Рыбченко Техред . М.Дидык

Заказ 1712/48Тираж 667Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб„, д. 4/5

быхоЗ

К бкЗбл. 4ij

К Л 25д 11

дыход (хвкоди zSa.i)

Корректор Л.Пилипенко