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

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

Цель изобротерия - повышение до- стоверности работы устройства за счет контроля наличия контуров на графе.

На фиг.1 изображена структурная устройства; на фиг, 2 - струк- турная схема блока формирования топологии; на фиг.З - структурная схема блока моделей ветвей.

Устройство содержит блок 1 управления, первый блок 2 формирования то пологий, второй блок 3 формирования топологии, блок 4 моделей ветвей, ге нератор 5 тактовых импульсов.

Блок 1 управления содержит с первого по четвертый узлы 6-9 памяти, первый и второй триггеры 10 и 11, с первого по седьмой элементы ИЛИ 12 - 18, с первого по третий элементы 19-21 задержки, с первого по шестой элементы И 22-27, элемент НЕ 28, узе 29 измерения длиннейшего пути, вход 30i меток контура графа устройства, вход 302 меток свершения ветвей графа устройства, выходы 31 и 32 номера подготавливаемой к моделированию ветви блоков 2 и 3, выходы 33 и ЗА поиска свободной ветви блоков 2 и 3, выходы 35 и 36 номера анализируемой ветви блоков 2 и 3, выходы 37 и 38 проверки свершения ветви блоков 2 и 3, выходы 39 и 40 поиска прерывания блоков 2 и 3,9ыходы 41 и 42 номера загружаемого узла графа блоков 2 и 3 информационные входы 43-48 блоков 2 и 3, выход 49 признака результата расчета длиннейшего пути блока 2, выход 50 номера модели блока 4, выход 51 отсутствия занятых моделей ветвей выход 52 прерывания блока 4, информационные входы 53-55 блока 4, первые и вторые тактовые входы 56 и 57 блока 2, первые и вторые тактовые входы 58 и 59 блока 3, информационный вход

60блока 4, первый и второй выходы

61и 62 генератора 5, управляющий вход 63 блока 1, вход 64 запуска блока 2, ход 65 номера начальной ветви графа устройства, вход 66 запуска блока 3, вход 67 кода номера конечной ветви графа устройства, вход 68 считывания номеров узлов контура

графа устройства, выход 69 метОк контура пути на графе устройства, вы

5

5

0 5

0

ход 70 признака нп.пичин пик.чл устройства, 71 :)начсни5т иаидлин- нейшего пути на графр.

Блоки 2 и 3 формирования топологии каждый содержит узел 72 памяти номеров начальных узлов ветвей сети, узел 73 памяти номеров конечных узлов ветвей сети, узел 74 памяти номеров выходящих ветвей узлов сети, узел 75 памяти номеров входящих ветвей узлов сети, узел 76 памяти номеров первой выходящей ветви узлов сети, узел 77 памяти номеров первой входящей ветви узлов сети, регистр

78номера выходящей ветви, регистр

79номера ветви, регистр 80 номера конечного узла ветви, регистр 81 конечного узла сети, триггеры 82 и 83, дешифраторы 84 и 85, дешифратор 86 сравнения кодов, линии 87 и 88 задержки, элементы ИЛИ 89-95, элементы И 96-101, элемент НЕ 102.

Узлы 72-77 памяти предназначены для хранения информации о топологии при моделировании сети в прямом направлении, узел 72 памяти - для хранения номера начального узла ветви по адресу номера этой ветви, узел

73памяти - для хранения номера конечного узла ветви по адресу номера данной ветви, узел 76 памяти - для хранения номера первой из списка ветвей, выходящих из данного узла, по адресу номера узла, узел 77 памяти - для хранения номера первой из списка ветвей, входящих в данный узел, по адресу номера узла, узел

74памяти - для хранения, в виде списков, номеров ветвей, выходящих из узлов сети, узел 75 памяти - для хранения, в виде списков, номеров ветвей,входящих в узлы сети.

Регистр 78 предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих из узла, регистр 79 - для промежуточного хранения номеров ветвей, входящих в узел, регистр 80 - для хранения номера анализируемого узла сети, регистр 81 - для постоянного хранения номера конечного узла сети.

Дешифраторы 84 и 85 состояния предназначены для сравнения поступающих на них кодов с кодовой комбинацией X, заданной постоянно в схеме, а дешифратор 86 сравнения кодов - для поразрядного сравнения кодов из ре- гистров 80 и 81.

3132230 4

Каждая модель 103 ветви содержит формирователь 104 временного интервала, триггеры 105 и 106, элементы И 107-112, элемент ИЛИ 113 и элементы 114 и 115 задержки.5

Схема 116 поиска моделей ветвей содержит шифратор 117 адреса и элементы ИЛИ 118-120.

Работу устройства рассматривают на примере контроля наличия контуров в 10 рассчитываемой сети и определения номеров узлов сети, которые принадлежат замкнутым путям.

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

В узлы 72-77 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 78-80 обнуляются, а в регистр 81 занос:ится код 20 номера конечного узла сети. Триггеры 82 и 83 блока 2 формирования топологии устанавливаются в нулевое состояние. В узлы 72-77 памяти блока 3 фордящей из начального узла сети, а на полюс 63 блока 3 формирования топологии - код номера ветви, входящей в коночный узел сети.

В некоторый момент времени сигнал Пуск, поступающий на полюс 64 блока 2 формирования топологии , проходит через элемент ИЛИ 95 и устанавливает триггер 83 в единичное состояние, что разрешает прохождение серии импульсов ГШ (полюс 57) и ГИ2 (полюс 56) соответственно через элементы И 100 и 101. Кроме этого, сигнал Пуск поступает на вход элемента 87 задержки и на вход считывания узла 72 памяти начальных узлов. При поступлении сигнала считывания в узле 72 памяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 65. Так как ветвь выбрана как выходящая из начального узла моделируемой сети, на выходе узла 72 памяти появляется код начального узла, который поступает через

мирования топологии в виде списков элемент ИЛИ 90 на адресный вход узла

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

записывается номер ее конечного узла,30 ходе элемента 87 задержки и поступает

в узел 73 памяти по адресу каждой ветви - номер ее начального узла, в узел 74 памяти в виде списков - номера входящих ветвей, в узел 75 памяти в виде списков - номера выходящих ветвей, в узел 76 памяти по адресу каждого узла - номер первой входящей ветви, в узел 77 памяти по адресу номера каждого узла - номер первой выходящей ветви.

Регистры 78-81 обнуляются. Триггеры 82 и 83 устанавливаются в нулевое состояние. В узел 8 памяти блока 1 управления записывается информация о длительности каждой ветви моделируемой сети. Узел 7 памяти обнуляетс В узел 6 памяти записьшаются метки п тем адресам, номера узлов которых есть в моделируемой сети. Триггеры

Записанный код первой выходящей ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через выходной полюс 31 блока 2 формирования топологии и злемент ИЛИ 12 блока 1 управления - на адрес11 и 10 блока 1 управления устанавли-50 ный вход узла 9 памяти и информаци- ваются в нулевое состояние. Триггеры онный вход узла 8 памяти блока 1 уп105(1), 103(2),...,105(п) и 106(1), 106(2),..,,106(п) блока 4 моделей ветвей устанавливаются в нулевое состояние.

После начального установа на полюс 65 блока 2 формирования топологии подается код номера ветви, выхоравления.Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на вход считывания узла 74 памяти, 55 осуществляя выборку, по адресу первой выходящей из начального узла ветви, номера второй ветви, выходящей из того же узла. Одновременно по имдящей из начального узла сети, а на полюс 63 блока 3 формирования топологии - код номера ветви, входящей в коночный узел сети.

В некоторый момент времени сигнал Пуск, поступающий на полюс 64 блока 2 формирования топологии , проходит через элемент ИЛИ 95 и устанавливает триггер 83 в единичное состояние, что разрешает прохождение серии импульсов ГШ (полюс 57) и ГИ2 (полюс 56) соответственно через элементы И 100 и 101. Кроме этого, сигнал Пуск поступает на вход элемента 87 задержки и на вход считывания узла 72 памяти начальных узлов. При поступлении сигнала считывания в узле 72 памяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 65. Так как ветвь выбрана как выходящая из начального узла моделируемой сети, на выходе узла 72 памяти появляется код начального узла, который поступает через

76 памяти первой выходящей ветви.Через время задержки, достаточное для считывания информации из узла 72 памяти, сигнал Пуск появляется на вы

через элемент ИЛИ 89 на вход считывания узла 76 памяти. По этому сигналу происходит считывание из узла 76 памяти кода номера ветви,являющейся

первой в списке ветвей, выходящих из начального узла сети. Код первой выходящей ветви с выхода узла 76 памяти через злемент ИЛИ 91 поступает на информационный вход регистра 78

выходящей ветви и записывается в него по первому импульсу ГИ1, поступившему на управляющий вход регистра с выхода элемента И 100.

Записанный код первой выходящей ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через выходной полюс 31 блока 2 формирования топологии и злемент ИЛИ 12 блока 1 управления - на адресный вход узла 9 памяти и информаци- онный вход узла 8 памяти блока 1 управления.Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на вход считывания узла 74 памяти, осуществляя выборку, по адресу первой выходящей из начального узла ветви, номера второй ветви, выходящей из того же узла. Одновременно по им5132230/.

пульсу ГИ2 снгнл.ч пснп ка сноОодной модели через ныходной полюг 3 } блока 2 формирования топологии и элемент | ИЛИ 13 блока 1 управления поступает на вход считывания узла 9 памяти, на 5 вход элемента 20 задержки, на вход записи узла 6 памяти блока 1 управления и на входной полюс 60 поиска свободной модели блока 4 моделей ветвей. Одновременно код номера загружаемого О узла сети через выходной лолюс 61 блока 2 формирования топологии и элемент ИЛИ 16 блока 1 управления подается на адресный вход узла 6 памяти. Осуществляется считывание кода длительности загружаемой ветви сети с-узла 9 памяти. Этот код через выходной полюс 53 блока 1 управления поступает в блок 4 моделей ветвей.

Сигнал поиска свободной модели ветви с полюса 60 поступает на входы элементов И 109(1) и 110(1) первой модели 103(1) ветви блока 4 моделей ветвей. Так как все модели ветвей свободные, триггер 105(1) находится в нулевом состоянии и сигнал с выхода элемента 110(1) через элемент 115(1) задержки поступает на вход установки единичного состояния триггеА

При г1ОД1 О1оик( Bt THH к поде л- нию выполняется считывание ее номера из блока 2 моделирования топологии, считывание ее длительности из ЗУ длительности блока 1 управления, поиск свободной от вычислений модели ветви блока 4 мсшелей ветвей, запись в формирователь временного интервала свободной модели кода длительности ветвей, запись номера ветви сети по

15

адресу модели ветви в узле 8. Кроме того, производится запись О в узел 6 памяти по адресу начального узла загружаемой ветви.

Далее считанный из узла 72 памяти выходящих ветвей блока 2 формирования топологии по адресу номера первой выходящей из узла ветви код номера следующей ветви поступает через 20 элемент ИЛИ 91 на информационный

вход регистра 78 и с приходом второго импульса ГИ1 записывается в указанный регистр. Записанный в регистр 78 код снова поступает на адресный вход узла 74 памяти, а также через полюс 31 и элемент ИЛИ 12 - на адресный вход узла 9 памяти и информационный вход узла 8 памяти блока 1 управления. С приходом второго им25

ра 105(1). Триггер через время задерж- пульса ГИ 2 из узла 9 памяти длитель- ки, достаточное для срабатывания всех ностей считывается длительность вто- элементов, устанавливается в единичное состояние, что означает занятость данной модели процессом моделирования. Одновременно сигнал с выхода эле-35 мента И 110 поступает на первый вход элемента И-111. и через элемент ИЛИ 113 на вход шифратора адреса. На второй вход элемента И 111 череэ входной полюс 53 поступает код длительности вет 40 модели ветви находится в единичном ви. Этот код записывается в качестве состоянии, сигнал поиска свободной исходной информации в формирователь модели с выхода элемента И 109(1) 104(1) временного интервала. С выхода шифратора 117 адреса код номера модели ветви через полюс 50 поступает на адресный вход узла 9 памяти блока 1

рой исходящей из узла ветви и поступает через полюс 53 на входы элементов И 111(1), 111(2),...,111(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 60(1) на входы элементов И 109 и 110 поступает сигнал поиска свободной модели ветви. Так как триггер 105(1) первой

через полюс 60(2) поступает на входы элементов И 109(2) и 110(2) вто- 5 рой модели ветви. Так как триггер 105(2) этой модели ветви находится в нулевом состоянии, сигнал с выхода элемента И 110 поступает на вход элемента И 111. На второй вход элеуправления. Через время, достаточное для организации опцсанных процессов, в блоке 4 моделей ветви на выходе

элемента 20 задержки блока 1 управле-50 мента И 111 поступает код длительнония появляется сигнал, поступающий на вход записи узла 9 памяти номеров моделируемых ветвей. Происходит запись номера загружаемой ветви сети по адресу выбранной модели ветви. На этом заканчивается подготовка первой ветви, выходящей из начального узла сети, к процессу моделирования.

А

При г1ОД1 О1оик( Bt THH к поде л- нию выполняется считывание ее номера из блока 2 моделирования топологии, считывание ее длительности из ЗУ длительности блока 1 управления, поиск свободной от вычислений модели ветви блока 4 мсшелей ветвей, запись в формирователь временного интервала свободной модели кода длительности ветвей, запись номера ветви сети по

адресу модели ветви в узле 8. Кроме того, производится запись О в узел 6 памяти по адресу начального узла загружаемой ветви.

Далее считанный из узла 72 памяти выходящих ветвей блока 2 формирования топологии по адресу номера первой выходящей из узла ветви код номера следующей ветви поступает через элемент ИЛИ 91 на информационный

вход регистра 78 и с приходом второго импульса ГИ1 записывается в указанный регистр. Записанный в регистр 78 код снова поступает на адресный вход узла 74 памяти, а также через полюс 31 и элемент ИЛИ 12 - на адресный вход узла 9 памяти и информационный вход узла 8 памяти блока 1 управления. С приходом второго им

пульса ГИ 2 из узла 9 памяти длитель- ностей считывается длительность вто- модели ветви находится в единичном состоянии, сигнал поиска свободной модели с выхода элемента И 109(1)

рой исходящей из узла ветви и поступает через полюс 53 на входы элементов И 111(1), 111(2),...,111(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 60(1) на входы элементов И 109 и 110 поступает сигнал поиска свободной модели ветви. Так как триггер 105(1) первой

- пульса ГИ 2 из узла 9 памяти длитель ностей считывается длительность вто- -35 40 модели ветви находится в единичном состоянии, сигнал поиска свободной модели с выхода элемента И 109(1)

через полюс 60(2) поступает на входы элементов И 109(2) и 110(2) вто- 5 рой модели ветви. Так как триггер 105(2) этой модели ветви находится в нулевом состоянии, сигнал с выхода элемента И 110 поступает на вход элемента И 111. На второй вход эле

сти ветви, который и записывается в формирователь 104(2) временного интервала. Одновременно сигнал с выхода элемента И 110 через элемент 115(2) задержки устанавливает триггер 105(2) в единичное состояние.Кроме того, сигнал с выхода элемента И 110 через элемент ИЛИ 113 поступаот мл Illll(}lp,rr( p I 17 ,1Л1КЧ Л, Г Де фп)мируотся код и(1М( |).ч данной модели нетпи. )Т()Г кол чергч полюг SO пает нл ядреснын пхол узла 8 памяти иомерон моделируемых ветвей блока 1 управления. По приходу сигнала чапи- ги с элемента 20 задержки происходит чапись номера ветви сети по адресу номера модели ветви.

Описанный процесс подготовки ветвей сети к моделированию продолжается до тех пор, пока не подготовлена последняя ветвь, выходящая из давно го узла. В этом случае по адресу ее номера из узла 74 памяти считывается код X, KoTopbrfi записывается в регистр 78. Выход регистра 78 подключен к дешифратору 84 состояния, поэтому на выходе последнего появляется сигнал. Этот сигнал поступает нулевое состояние. Одновременно сиг

вход триггера 83, сбрасывая его в нулевое состояние. Кроме того,сигнал с выхода дешифратора через элемент ШШ 92 поступает на полюс 39, с которого сигнал поиска прерывания через элемент ИЛИ 17 поступает на вход триггера 11 блока 1 управления, устанавливая его в единичное состояние. Одновременно сигнал поиска прерывания поступает на полюс 55 блока моделей ветвей. Так как в описываемый момент (подготовлены все ветви, исходящие из начального узла сети) нет моделей ветвей, которые закончили моделирование, сигнала прерывания из блока моделей ветвей на полюсе 52 не будет,и триггер 11 блока 1 управления остается в единичном состоянии.

Единичное состояние триггера прерывания 11 разрешает прохождение импульсов серии ГИ2 через элемент И 22 на счетный вход узла 29 измерения длиннейшего пути блока 1 управления и через полюс 54 на элементы И 1 12( 1), 112(2),...,112(п) всех моделей ветвей блока 4 моделей ветвей. У тех моделей ветвей, у которых триггер 105 находится в единичном состоянии, импульсы серии ГИ2 поступают на вход формирователей 104 временного интервалу. Так продолжается до тех пор, пока хотя бы один из/формирователей 104 временного интервала не выдает сигнал об окончании процесса временного моделирования длительности ветви.

В ПЧ1М глч лао гит нллы г ныхода форм1трпвателрй 104(1), 104(2),..., 104fn) ppeMOHHoin интервлла погтупа- на единичные пходы триггеров

106(1), 106(2) 106(п), устанавливая их в елиничноо состояние. Одновременно сигнал с выходов формирователей 104(1), 104(2),..., 104(п) поступают череч члемент НИИ 118 на

вход поиска прерывания (1,1) первой М()дели ветви. В случае, если три1-гер 106(1) первой модели ветви находится в единичном состоянии, сигнал прерывания с в з1Хода элемента И 108(1) поступает через элемент ИЛ11 119 и полюс 52 в блок 1 управ.ления. Кроме того, сигнал прерывания с выхода элемента И 108(1) поступает на вход триггера 105(1), устанавливая его в

5

5

0

5

0

5

нал прерывания с выхода элемента И 108(1) через элемент ШШ 113(1) поступает на вход шифратора 117, а через элемент 114(1) задержки устанавливает триггер 106(1) в нулевое состояние. С шифратора 117 код номера модели ветви, окончившей моделирование, через полюс 50 поступает на адресный вход узла 8 памяти номеров моделируемых ветвей блока 1 управления. На вход считывания указанного узла памяти с полюса 52 поступает сигнал прерывания. Происходит считывание, по номеру модели ветви, номера ветви сети. Этот код поступает на полюса 43 и 44, а через элемент ИЛИ 18 - на адресный вход узла 7 памяти. Через время, достаточное для считывания номера ветви, на вход записи узла 7 памяти через элемент 19 задержки поступает сигнал, и по адресу номера ветви в узел 7 памяти записывается 1, характеризующая завершение процесса моделирования данной ветви. Через время, достаточное для записи метки свершения, сигнал с выхода элемента 21 задержки поступает на первые входы элементов И 26 и 27. Так как триггер 24 обратного хода в данный момент находится в нулевом состоянии, на втором входе элемента И 26 присутствует разрешающий потенциал, и сигнал начала анализа свершения ветви поступает с его выхода на полюс 47 и далее в блок 2 формирования топологии. На втором входе элемента И 27 присутствует запрещающий потенциал с единичного выхода

триггера 10, поэтому сигнал начала анализа ветви в блок 3 формирования топологии не поступает. Это исключа-, ет включение блока 3 формирования топологии на этапе моделирования сети в прямом направлении.

В блоке 2 формирования топологии код номера ветви с полюса 43 поступает на адресный вход узла 73 памяти конечного узла, а сигнал начала анализа ветви с полюса 47 поступает на вход триггера 82 и устанавливает его в единичное состояние. Единичное состояние триггера 82 разрешает прохожI, следовательно, в данном узле не

дение импульсов ГИ1 через элемент 5 в данный узел ветвей не свершилась И 98, а импульсов ГИ2 - через элемент И 99. Кроме того, сигнал начала анализа поступает на вход элемента 88 задержки и на вход считывания узла 73 памяти. Происходит считывание ячейки памяти по адресу номера свершившейся ветви, т.е. считывание номера конечного узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистра 80 конечного узла. Через время задержки, достаточное для считывания инсформирована функция И для всех входящих в него ветвей.

В этом случае сигнал поиска преры- 20 вания с полюса 39 через элемент ИЛИ 17 поступает на единичный вход триггера 11 и одновременно через полюс 55 на вход элемента ИЛИ 118 узла 116 поиска моделей ветвей блока 4 моде- 25 лей ветвей. С выхода элемента ИЛИ 118 сигнал поступает на входы элементов И 107(1) и 108(1) первой модели ветви. Если модель ветви закончила процесс моделирования ветви, которая еще

формации из узла 73 памяти, сигнал на- е анализировалась, триггер 106 начала анализа ветви поступает на уп- ходится в единичном состоянии, и тог- равляющий вход регистра 80 конечного узла и на вход считывания узла 77 памяти. По этому сигналу происходит запись номера конечного узла ветви в регистр 80 и считывание номера первой, входящей-в этот узел, ветви с узла 77 памяти. Код номера первой входящей ветви с выхода узла 77 памяти поступает через элемент ИЛИ 93 на информационный вход регистра 79 входящей ветви и записывается в него по первому импульсу ГИ1, поступающему на управляющий вход регистра с выхода элемента И 98. С выхода регистра 79 код номера первой входящей ветви поступает через полюс 35 и элементы ИЛИ 14 и 18 на адресньм вход узла 7 памяти блока 1 управления, на адресный вход узла 75 памяти входящих ветвей и на дешифратор 85. По первому импульсу ГИ2 сигнал проверки свершения ветви с выхода элемента И 99 поступает через элемент ИЛИ 96 на

вход считывания узла 75 памяти, а че- рез элемент И 96 на вход считьгаания рез полюс 37 и элемент ИЛИ 15 - на узла 75 памяти входящих ветвей. На вход считьшания узла 7 памяти блока 1 управления. Метка свершения, счида сигнал с выхода элемента И 108 снова поступает на вход шифратора адреса 117, а также через элемент

35 ИЛИ 120 выдает сигнал прерывания. Блок 1 управления, получив номер модели ветви и сигнал прерывания, по- вторяет все описанные операции, связанные с анализом свершения ветви.

Если же в блоке 4 моделей ветвей не имеется моделей, у которых триггер 106 находится в единичном состоянии, процесс анализа не проводится и импульсы серии ГИ1 продолжают поступать

5 через элемент И 22 в узел 29 определения длиннейшего пути блока 1 управления и в формирователи временного интервала моделей ветвей блока 4 моделей ветвей.

Если сигнал метки свершения ветви с полюса 45 имеет единичное значение, т.е. моделирование данной ветви закончилось, этот сигнал выдает разрешение на прохождение импульса ГИ2 чеадресные входы последнего в это время поступает код номера первой входящей

50

танная по адресу первой ветви, с выхода узла 7 памяти поступает через полюс 45 в блок 2 формирования топологии, а через полюс 46 - в блок 3 формирования топологии. Если метка отсутствует, нулевой сигнал метки с полюса 45 через элемент НЕ 102 и элемент ИЛИ 94 сбрасывает триггер 94 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 102 поступает через элемент ИЛИ 92 на полюс 39 поиска прерывания. Наличие нулевого сигнала метки свершения ветви означает, что хотя бы одна из входящих

I, следовательно, в данном узле не

данный узел ветвей не свершилась

е анализировалась, триггер 106 находится в единичном состоянии, и тог-

да сигнал с выхода элемента И 108 снова поступает на вход шифратора адреса 117, а также через элемент

ИЛИ 120 выдает сигнал прерывания. Блок 1 управления, получив номер модели ветви и сигнал прерывания, по- вторяет все описанные операции, связанные с анализом свершения ветви.

Если же в блоке 4 моделей ветвей не имеется моделей, у которых триггер 106 находится в единичном состоянии, процесс анализа не проводится и импульсы серии ГИ1 продолжают поступать

через элемент И 22 в узел 29 определения длиннейшего пути блока 1 управления и в формирователи временного интервала моделей ветвей блока 4 моделей ветвей.

Если сигнал метки свершения ветви с полюса 45 имеет единичное значение, т.е. моделирование данной ветви закончилось, этот сигнал выдает разрешение на прохождение импульса ГИ2 че

рез элемент И 96 на вход считьгаания узла 75 памяти входящих ветвей. На

адресные входы последнего в это время поступает код номера первой входящей

ветпи с выхода регистра 79. По адресу первом «ходящей ветви из узла 75 памяти считывается код номера второй входящей в данный узел ветви. Этот код поступает через элемент ИЛИ 93 на информационные входы регистра 79 и записывается в него с приходом второго импульса ГИ1. Далее осуществляется опрос метки свершения данной ветви. Р сдн ветвь свершилась, осуществляется переход к опросу свершения следующей ветви, входящей в рассматриваемый узел, и т.д.

Описанный процесс анализа свершения ветвей продолжается до тех пор, пока не опрошены все ветви, входящие в рассматриваемый узел. В этом случае по адресу последнего номера ветви из узла 75 памяти считывается код

X, определяющий конец списка входящих20 окончено. Отличительной чертой ука- в данный узел ветвей. Код X записывается в регистр 79 входящей ветви и далее поступает на вход дешифратора 85 состояния, вырабатывая сигнал конца списка, который проходит через 25 элементы ИЛИ 94 и 95 и устанавливает триггеры 82 и 83 соответственно в нулевое и единичное состояние. Сигнал с выхода дешифратора 85 поступает такзанного момента является отсутствие моделей ветвей занятых процессом моделирования, при наличии несвершенных узлов сети. При этом при проверке свершения узла, во время обработки прерывания от последней модели ветви, которая занята процессом моделирования, сигнал проверки свершения ветви с полюса 37 поступает на

же на первый вход элемента И 86,вто- 30 первый вход элемента И 23 блока 1

рой вход которого связан с выходом дешифратора 86 сравнения кодов, который сравнивает коды, хранящиеся в регистре 81 конечного узла сети и в

регистре 80 конечного узла ветви. Ре-35 об отсутствии занятый моделей вет

гистр 81 хранит код конечного узла сети, а регистр 80 - код рассматриваемого узла сети, сформировавшего функцию коньюнкции Б данный момент времени. Если значение этих кодов не совпадает, сигнал с выхода дешифратора 85 поступает через элемент ИЛИ 89 на вход считывания узла 76 памяти первой выходящей ветви, на адресный вход которого в этот момент времени поступает код номера сформированного узла сети. Начинается процесс подготовки к моделированию тех ветвей, которые выходят из данного сформированного узла.

Если в сети отсутствуют циклы (контуры), описанный процесс подготовки ветвей к моделированию, временное моделирование и анализ ветвей, моделирование которых закончено, че- редуются в указанном порядке и повторяются до тех пор, пока не сформируется конечный узел сети. В этом случае дешифратор сраннетшя кодов блока 2 формирования топологии выдает разрешение на прохождение сигнала с выхода дешифратора 85 через элемент

И 97 на выходной полюс 49, что соответствует концу моделирования заданной сети. Сигнал с полюса 49 поступает на вход элемента И 12 блока 1 управления и разрешает выдачу на

внешнее устройство величины длиннейшего пути сети с узла 7, сигнал наличия циклов с выхода элемента И 24 отсутствует. Все ячейки узла 6 памяти обнулены.

Если в топологии сети есть контур, описанный процесс моделирования сети в прямом направлении остановится в момент отработки прерывания от последней ветви, моделирование которой

окончено. Отличительной чертой ука-

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

управления. На второй вход этого элемента поступает разрешающий потенциал с выхода элемента ИЛИ 120 блока 4 моделей ветвей, что сигнализирует

вей. Так как в рассматриваемый узел входят ветви, моделирование которых еще не происходило, наступает момент, когда нулевой сигнал метки свершения ветви с узла 7 памяти блока 1 управления через элемент НЕ 28 поступает на третий вход элемента И 23. На выходе последнего появляется сигнал, KOTopbtfi поступает на вход триггера 10, устанавливая его в единичное состояние. Кроме того, сигнал с выхода элемента И 23 поступает в блок 3 формирования топологии. Начинается процесс моделирования сети в обратном направлении. При этом в узле 6 памяти останутся метки по тем адресам, которые соответствуют номерам узлов, принадлежащих контуру сети, и по тем адресам, которые соответствуют номерам узлов, связанных с узлами контура цепочкой входящих ветвей.

Сигнал с полюса 64 проходит через элемент ИЛИ 95 и устанавливает триг131322304

rep 83 блока 3 формирования топологии в единичное состояние. Единичное состояние триггера 83 разрешает прохождение серии импульсов ГИ1 через элемент И 100, а серии импульсов ГИ2 - 5 через элемент И 101. Кроме того, сигнал с полюса 64 поступает на вход эле- элемента 87 задержки и на вход считывания узла 72 памяти.На адресные входы последнего поступает код номера 0 ветви, входящей в конечный узел сети. Так как в узле 72 памяти по адресу ветвей моделируемой сети записаны их конечные узлы, по приходу сигнала

14

ресу номера первой входящей в кинс ч- ный узел ветви осуществляется считывание кода длительности этой ветви из узла 5. По этому же сигналу происходит запись метки О в узел 6 памяти по адресу номера загружаемого узла, поступаемого с выхода элемента ИЛИ 21 блока 3 формирования топологии через полюс 42. Одновременно сигнал поиска свободной модели с полюса 60 поступает на входы элементов И 109(1) и 109(2) блока 4 моделей ветвей. Так как все модели ветвей свободные, триггер 105(1) перечитывания из узла 72 памяти считыва- 5 вой модели находится в нулевом состоется код конечного узла сети. -Этот янии и сигнал с выхода элемента

код поступает через элемент ИЛИ 90 110(1) через элемент 115 задержки пона адресный вход узла 76 памяти первой входящей ветви. Через время, достаточное для считывания информации из узла 72 памяти, сигнал с полюса 64 появляется на выходе элемента 87 задержки и поступает через элемент ИЛИ 89 на вход считьшания узла 76 памяти.По этому сигналу происходит считьгаание кода номера первой ветви, входящей в конечный узел сети. Код номера первой входящей ветви с выхода узла 76 памяти поступает через элемент ИЛИ 91 на информационный вход регистра 78 и записывается в него по первому импульсу ГИ1, поступающего на управляющий вход регистра с выхода элемента И 100.

Записанный код первой входящей в конечный узел ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через полюс 31 и элемент ИЛИ 12 - на адресный вход узла 9 памяти и информационный вход узла 8 памяти номеров моделируемых ветвей блока 1 управления.

Импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на

ступает на вход триггера 105(1) и ус танавливает его в единичное состоя20

ние, что означает занятость процессом моделирования первой модели ветви. Одновременно сигнал с выхода эле мента И 110(1) поступает на первый вход элемента И 110(1) и через эле мент ИЛИ 113(1) на вход шифратора ад реса 117. На второй вход элемента И 111(1) через полюс 53 поступает код длительности ветви, который и за писывается в формирователь 104(1)

30 временного интервала. С выхода шифратора 117 адреса код адреса модели ветви поступает на адресный вход узла 7 памяти номеров моделируемых ветвей блока 1 управления. По поступ

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

40

вход считьгеания узла 74 памяти бло- 5 узла 74 памяти блока 3 формирования

ка 3 формирования топологии, и по адресу первой входящей в конечный узел ветви считывается в код номера второй ветви,входящей в тот же узел. Одновременно по импульсу ГИ2 сигнал поиска свободной модели с выхода элемента И 101 через полюс 33 и элемент ИЛИ 13 поступает на вход считывания узла 9 памяти,на вход записи узла

топологии код номера второй, входящей в конечный узел, ветви поступает на информационный вход регистра 43 и с приходом второго импульса ГИ1 50 записывается в него. После этого опять происходит поиск свободной от вычислений модели ветви, запись кода длительности в ее формирователь временного интервала, запись номе6 памяти,на элемент 20 задержки бло- ра моделируемой ветви по ад- ка управления, на полюс 60 поиска ресу номера выбранной модели свободной модели блока 4 моделей в узел 8 памяти блока 1 уп- ветвей. По сигналу считывания и ад- равлеиия.

14

ресу номера первой входящей в кинс ч- ный узел ветви осуществляется считывание кода длительности этой ветви из узла 5. По этому же сигналу происходит запись метки О в узел 6 памяти по адресу номера загружаемого узла, поступаемого с выхода элемента ИЛИ 21 блока 3 формирования топологии через полюс 42. Одновременно сигнал поиска свободной модели с полюса 60 поступает на входы элементов И 109(1) и 109(2) блока 4 моделей ветвей. Так как все модели ветвей свободные, триггер 105(1) перступает на вход триггера 105(1) и устанавливает его в единичное состоя

ние, что означает занятость процессом моделирования первой модели ветви. Одновременно сигнал с выхода элемента И 110(1) поступает на первый вход элемента И 110(1) и через элемент ИЛИ 113(1) на вход шифратора адреса 117. На второй вход элемента И 111(1) через полюс 53 поступает код длительности ветви, который и записывается в формирователь 104(1)

временного интервала. С выхода шифратора 117 адреса код адреса модели ветви поступает на адресный вход узла 7 памяти номеров моделируемых ветвей блока 1 управления. По поступлению сигнала с выхода элемента 20 задержки происходит запись номера ветви (в данном случае первой ветви, входящей в конечный узел сети) по адресу выбранной модели ветви. На этом заканчивается подготовка первой, входящей в конечный узел сети, ветви к процессу моделирования. Далее считанный по адресу номера первой, входящей в конечный узел, ветви из

топологии код номера второй, входящей в конечный узел, ветви поступает на информационный вход регистра 43 и с приходом второго импульса ГИ1 50 записывается в него. После этого опять происходит поиск свободной от вычислений модели ветви, запись кода длительности в ее формирователь временного интервала, запись номеПроцесс подготовки петпей, входящих в конечный узел сети, к процессу моделирования осуществляется до тех пор, пока не считывается последняя ветвь из списка входящих ветвей. По адресу ее номера в узле 74 памяти считывается код X, который записывается в регистр 78 блока 3 формирования топологии.

Сигнал поиска прерывания с полюсом 40 поиступает на вход триггера 11 блока 1 управления и устанавливает его в единичное состояние. Так как в

0 ратном направлении. На втором входе элемента И 27 присутствует раз- решающий потенциал с единичного выхода триггера 10. Поэтому сигнал начала анализа свершения ветви свыхорассматриваемый момент нет моделей

ветвей, окончанщих моделирование,сиг- да элемента И 27 поступает на полюс нал прерывания отсутствует и триггер 48 и дальше на блок 3 формирования 11 остается в единичном состоянии. топологии.

В блоке 3 формирования топологии код номера сверщивщейся ветви с полю- 20

25

Единичное состояние тирггера 11 раз- рещает прохождение импульсов серии ГИ1 на счетный вход узла 29 измерения длиннейшего пути и через полюс 54 на все формирователи 104 в ременного интервала, триггера 105 которых находятся в единичном состоянии. Так продолжается до тех пор, пока хотя бы один из формирователей 104 временного интервала не выдает сигнал об окончании процесса временного моделирования.

Сигналы с выхода формирователей 104(1), 104(2),..., 104(п) временного интервала поступают на единичные входы триггеров 106(1), 106(2),...,106(п)

са 43 поступает на адресный вход узла 73 памяти, а сигнал начала анализа свершения ветви с полюса 47 поступает на вх од триггера 82 и устанавливает его в единичное состояние. Кроме того, сигнал с полюса 43 поступает на вход элемента 88 задержки и на вход считывания узла 73 памяти, где происходит считьгоание (по адресу номера свершившейся ветви) номера начального узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистса 43 поступает на адресный вход уз ла 73 памяти, а сигнал начала анали за свершения ветви с полюса 47 пост пает на вх од триггера 82 и устанавливает его в единичное состояние. Кроме того, сигнал с полюса 43 посту пает на вход элемента 88 задержки и на вход считывания узла 73 памяти, где происходит считьгоание (по адресу номера свершившейся ветви) номера начального узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регисти устанавливают их в единичное состояние. Одновременно сигналы с выходов 35 ра 80 начального узла. Через время формирователей 106(1), 106(2),..., задержки, достаточное для считыва- 106(п) поступают через элемент ИЛИ 118 ния информации из узла 73 памяти, на вход поиска прерываний (1,1) первой модели ветви. Начинается этап обработки прерывания, аналогично гистра 80 начального узла и на вход пу обработки прерывания при моделиро- считьгоания узла 77 памяти. По этому вании сети в прямом направлении. Опсигнал начала анализа свершения ветви поступает на управляющий вход ресигналу происходит запись номера начального узла ветви в регистр 80 и считывание из узла 77 памяти (по 45 адресу номера начального узла ветви) кода номера первой выходящей из этого узла ветви. Далее этот код поступает в блок 1 управления, где проверяется свершение считанной ветви.

ределяется номер модели ветви, окончившей моделирование. По этому номеру определяется код номера свершившейся ветви, записывается метка 1 в узел памяти свершения по адресу номера ветви. Код номера свершившейся ветви поступает на полюса 43 и 44

сигналу происходит запись номера начального узла ветви в регистр 80 и считывание из узла 77 памяти (по 45 адресу номера начального узла ветви) кода номера первой выходящей из этого узла ветви. Далее этот код поступает в блок 1 управления, где проверяется свершение считанной ветви.

и далее в блоки формирования тополо- 50Если ветвь не свершилась, процесс гии. Сигнал прерывания с полюса 52временного моделирования продолжает- поступает на вход элемента 19 задерж-ся дальше. Если же первая ветвь,иски, и после времени задержки на эле-ходящая из рассматриваемого узла, ментах 19 и 21 появляется на выходе имеет единичную метку свершения, из элемента 21 задержки блока 1 управ- 55узла 75 памяти считывается код сле- ления. Этот сигнал поступает на первые входы элементов И 26 и 27. Так . как триггер 10 находится в единичном

дующей ветви и производится проверка ее свершения. Процесс проверки свершения ветвей, исходящих из рассостоянии, на втором входе элемента И 26 присутствует запрещающий потенциал с нулевого выхода триггера 10. Поэтому сигнал с выхода элемента 21

задержки через элемент И 26 не проходит и на полюсе 47 присутствует запрещающий потенциал. Этим исключается запуск блока 2 формирования топологии при моделировании сети в обратном направлении. На втором входе элемента И 27 присутствует раз- решающий потенциал с единичного выхода триггера 10. Поэтому сигнал начала анализа свершения ветви свыхоВ блоке 3 формирования топологии код номера сверщивщейся ветви с полю-

са 43 поступает на адресный вход узла 73 памяти, а сигнал начала анализа свершения ветви с полюса 47 поступает на вх од триггера 82 и устанавливает его в единичное состояние. Кроме того, сигнал с полюса 43 поступает на вход элемента 88 задержки и на вход считывания узла 73 памяти, где происходит считьгоание (по адресу номера свершившейся ветви) номера начального узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистра 80 начального узла. Через время задержки, достаточное для считыва- ния информации из узла 73 памяти, гистра 80 начального узла и на вход считьгоания узла 77 памяти. По этому

ра 80 начального узла. Через время задержки, достаточное для считыва- ния информации из узла 73 памяти, гистра 80 начального узла и на вход считьгоания узла 77 памяти. По этому

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

сигналу происходит запись номера начального узла ветви в регистр 80 и считывание из узла 77 памяти (по адресу номера начального узла ветви) кода номера первой выходящей из этого узла ветви. Далее этот код поступает в блок 1 управления, где проверяется свершение считанной ветви.

Если ветвь не свершилась, процесс временного моделирования продолжает- ся дальше. Если же первая ветвь,исходящая из рассматриваемого узла, имеет единичную метку свершения, из узла 75 памяти считывается код сле-

дующей ветви и производится проверка ее свершения. Процесс проверки свершения ветвей, исходящих из рас

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

Описанные процессы подготовки ветвей к моделированию, временное моделирование и анализ ветвей, моделирование которых окончено (при моделировании сети в обратном направлении), продолжается до тех пор, пока не окончится моделирование всех ветвей, входящих в свершившиеся узлы. В этом случае при обработке прерывания от модели- ветви, которая последней окончила процесс моделирования, сигнал проверки свершения ветви с полюса 37 поступает на первый вход Элемента И 2А, на второй вход указанного элемента - сигнал отсутствия за нятых моделей ветвей с полюса 51, а на третий вход через элемент НЕ 28 - нулевая метка свершения из узла 7 памяти. С выхода элемента И 24 сиг

нал наличия цикла поступает на выход-35 мой блока управления подключены соот- ной полюс 70. При этом в узле 6 памяти останутся метки по тем адресам, которые соответствуют номерам узлов, принадлежащих контуру сети.

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

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

Устройство для моделирования направленных графов, содержащее блок управления, первый блок формирования топологии, блок моделирования ветвей, генератор тактовьгх импульсов, вход

50

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

O

5

0

0

5

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

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

1413

пр,)в Т(, пыкод ficMcpa чагружаемог учла 1 раф;) первого блока формирования Tonojioi-ии подключен к чет1,|рнад- цят(му вх(1ду блока управления, восьмой, девятый и десятый выходы блока управления подключены соответственно к второму, третьему и четвертому информационным входам первого блока формирования топологии, при этом бло управления содержит четыре узла па- мяти, пять элементов И, два триггера элемент НЕ, три элемента задержки и узел измерения длиннейшего пути,причем в блоке управления входы с перво

го по пятьй блока управления подклю- f5 го элемента И подключен к счетному

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

вертый выход блока управления подклю-40 ветви второго блока формирования точен к выходу четвертого узла памяти, выход первого элемента И подключен к входу узла измерения длиннейшего пути и пятому выходу блока управления.

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

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

55

А

триггера

го

ПОДКЧИ К И к П Ч ПОМУ ПХОДу

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

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

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

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

входы блока управления подключены со- О узла памяти, выходы элементов ИЛИ

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

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

5

0

5

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

()) w/J

10)

wИЗ

(2.П 060.

вО(1.

«W/

№() -X

кпгу;

шг)

а/п

5ЧИ

01

го//г;

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