Устройство для решения сетевых задач

 

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

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

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

РЕСПУБЛИК (gI)g С 06 F 15/20

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4471662/24-24 (22) 15,08.88 (46) 15.05.90. Бюл. № 18 (7I) Институт проблем регистрации информации АН УССР и Специальное конструкторско-технологическое бюро средств моделирования с опытным производством Института проблем моделирования в энергетике АН УССР (72) В.П.Приймачук и А.M.Ùeòèíèí (53) 681.33(088.8) (56) Авторское свидетельство СССР

¹ 930323, кл. G 06 1 7/122, 1980.

Авторское свидетельство СССР № 1161951, кл. G 06 F 15/20, !983. (54) УСТРОЙСТВО ДЗИ РЕШЕНИЯ СЕТЕВЫХ

ЗАДАЧ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в

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

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

На фиг.! представлена функциональная схема устройства; на Фиг.2 — то же, блока формирования топологии; на фиг.3 — то же, блока моделирования сети.

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

4 синхронизации

„„SU„„1564643 А 1

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

Блок 1 управления содержит уэеч .

5 памяти длительности ветвей, узел

6 памяти номеров моделируемых ветвей,, узел 7 измерения пути, узел 8 формирования адреса меток моделирования, регистр 9 номера отработавшей модели ветви, регистр 10 номера свободной модели ветви, триггер 11 прерывания, триггер 12 формирования меток моделирования, узел 13 сравнения номеров ветвей, узел !4 сравнения нсмерон уэлов, узлы 15 — 18 элементов 11, эле— менты И 19 — 22,узел 23 элемептс>в 11..1È, злементь: ИЛИ 24 — 28, элемент 1Н 29, лементы задержки 30 — 33.

1564643

Выход номера конечного узла ветви блока 2 формирования топологии соедиен через полюс 34 с входом узла 18 элементов И блока 1 управления. Вы5 ход номера подготавливаемой к моделированию ветви блока 2 формирования топологии соединен через полюс 35 с адресным входом узла 5 памяти и с входом схемы 13 сравнения блока 1 управ- !0 ления. Выход поиска свободной модели ветви блока 2 формирования топологии соединен через полюс 36 с входом считывания узла 5 памяти, с входом элементов И 21, 22 и.через элемент ИЛИ

27 с входом узла 16 элементов И блока 1 управления. Выход признака конечной ветви сети блока 2 формирования топологии соединен через полюс 37 с входом элемента И 22 блока 1 управ- 20 пения . Выход поиска прерывания блока

2 фор|:иров ания топологии со единен ч ерез полюс 38 с единичным входом триггера 11 прерывания блока 1 управления и с одноименным входом блока 3 моделей ветвей через полюс 39..Выход разрешения выдачи результата блока 2 формирования топологии соединен через полюс 40 с входом узла элементов блока 1 управления. Выход номера началь- 30 ного узла ветви блока 2 формирования топологии соединен через полюс 41 с входом схемы 14 сравнения блока 1 управления, oÀ разрешени агру ки послед- 35 ней ветви сети блока 3 моделей ветвей соединен через полюс 42 с входом элемента И 22 блока 1 управления. Выход метки моделирования узла блока 3 моделей ветвей соединен че- 40 реэ полюс 43 с входом элемента ИЛИ 28 и через элемент НЕ 29 с входом элемента И 21 блока 1 управления. Выход метки моделирования ветви соединен с входом элемента ИЛИ 25 через 45 полюс 44. Выход номера модели ветви блока 3 моделей ветвей соединен через полюс 45 с адресным входом узла

6 памяти и с информационным входом регистров 9 и 10 блока 1 управления.

Выход прерывания блока 3 моделей ветвей соединен через полюс 46 с входом считывания узла 6 памяти, с установочным входом регистра 9, с входом элемента 33 задержки и с нулевым входом 55 триггера 11 блока управлении.

Выход номера свершившейся ветви блока 2 подключен через полюс 47 к одноименному входу блока 1 выход начала анализа свершения ветви блока 2 подключен через полюс 48 к одноименному входу блока 1, выход кода дли- . тельности ветви блока 1 подключен через полюс 49 к одноименному входу блока 3, выход записи меток модели" рования узла блока 1 подключен через полюс 50 к одноименному входу блока

3„ выход считывания меток моделирования узла подключен через полюс 51 к одноименному входу блока 3, выход адреса меток моделирования узла подключен через полюс 52 к одноименному входу блока 3, тактовый выход блока

1 подключен через полюс 53 к одноименному входу блока 3., выход поиска свободной модели ветви блока 1 подключен через полюс 54 к одноименному входу блока 3, выход признака моделирования ветви блока 1 через полюс 55 подключен к одноименному входу блока 3, выход признака моделирования узла блока 1 подключен через полюс 56 к одноименному входу блока 3, вход опроса устройства подключен через полюс 57 к одноименному входу блока 1, первый выход блока 4 (вьфает серию импульсов ГИ1) через полюс

58 подключен к первому тактовому входу блока 2, второй выход блока 4 (выдает серию импульсов ГИ2) подключен через полюса 59 и .60 к второму тактовому входу блока 2 и к первому тактовому входу блока 1, третий выход блока 4 (выдает серию импульсов ГИЗ) подключен через полюс 61 к второму тактовому входу блока 1, вход пуска устройства подключен через полюс 62 к одноименному входу блока 2, вход кода номера ветви, исходящей из начального узла сети устройства; подключен через полюс 63 к одноименному входу блока 2, вход задания количества узлов сети устройства подключен через полюс 64 к одноименному входу блока 3, выход признака принадлежности ветви кратчайшему пути коммивояжера блока 1 подключен через полюс 65 к одноименному выходу устройства, выход признака принадлежности ветви множеству путей коммивояжера блока 1 подключен через полюс 66 к одноименному выходу устройства, выход веса пути блока 1 подключен через полюс 67 к одноименному выходу устройства.

Блок 2 формирования топологии содержит узел 68 памяти номеров начальных узлов ветвей сети, узел 69 памя1 з64 ти номеров конечных узлов ветвей сети, узел 70 памяти номеров выходящих ветвей узлов сети, узел 71 памяти номеров первой выходящей ветви узлов сети, регистр 72 выходящей ветви, регистр 73 начального узла подготавливаемой ветви, регистр 74 конечного узла подготавливаемой ветви, регистр 75 конечного узла анализируемой ветви, регистр 76 узла сети, триггер 77, дешифратор 78, узлы 79 и 80 сравнения кодов, элементы задержки 81 — 85, узлы 86-88 элементов HJ!H, элементы ИЛИ

89 — 91 элементы И 92 — 95, элемент

HF 96.

Блок 3 моделей ветвей (фиг.3) содержит К мо,делей ветвей (где К вЂ” количество путей, проходящих через все узлы сети) 97 и узел 98 поиска моде- 20 лей ветвей. Цифрами в скобках обозначены порядковые номера одинаковых по своему конструктивному исполнению и функциональному назначению блоков, узлов, элементов и полюсов. Каждая модель ветви 97 состоит из формирователя 99 временных интервалов, триггеров 100 и 101, э;.ементов И 102

108, узла 109 элементов И, элемента

ИЛИ 110, элементов задержки 111 и 112, 30 узла 113 памяти меток моделируемых ветвей, узла 114 памяти меток узлов, счетчика узлов 115 сети, формирователя 116 сброса модели ветви.

Узел 98 поиска моделей ветвей блока 3 моделей ветвей содержит шифра-—

35 тор 117 адреса, элементы ИЛИ 118 и

119 дешифратор 120 записи меток, дешифратор 121 считывания меток.

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

В узлы 68 — 71 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 72 — 75 предварительно обнуляются, а в регистр 76 узла сети заносится код номера любого узла сети, принятого за начальный узел моделирования сети. В узел 5 памяти длительностей ветвей блока 1 управления предварительно заносится информация о длительности ветвей сети, т.е. по адресу номера каждой ветви сети записывается код ее длительности.

Узел 6 памяти, узел 7 измерения пути, 55 узел 8 формирования меток моделирования, регистры 9 и 10 блока I управления, узлы памяти 113 (!), 113 (2),, .. °,113 (K) и 114 (1), 1!4 (2)...,, 643 6

114 (К), формиронлте,чи 9ч (!), 99(2)

99 (K) ape Mettttt tx интерв,<лов блока 3 >1(te лей ветвей tlpE UttitplfTcJlt> но обнуляются. Триггеры !! и 12 блока

1 управления, трпггер 7 блокя 2 формирования топологии, триггеры !00(1), !

0O(2),...,1OO(K) н !О!(1), 101(2), ...,l01(К) и формирователи 116(1), 116(2),..., 116(К) сброся модели ветви блока 3 моделей ветвей находятся первоначально в пулевом состоянии.

В счетчике узлов 115(1), 115(2), 115(К) сети блока 3 моделей ветвей предварительно заносится код, на единицу меньший количествя узлов сети.

После плчального устлновя ня полюс

63 блока 2 формнровлния топологии ttnдается код номера ветви, выходящей пз узла, принятого прн данном расчете зя начальный узел сети, т.е. номер которого записан в регистр 76 узла сети. Таким образом, начальный узел моделирования сети определяется tto адресу номера ветви в узле 68 памяти номеров начальных узлов блока 2 формирования топологии. г

В некоторый моме т времени сигнал "Пуск", поступающий ня полюс 62 блока 2 формирования топологии, проходит через элемент ИЛИ 91 и устанавливает триггер 77 в единичное состояние. Единичное состояние триггера 77 разрешает прохождение серии импульсов

ГИ1 (с первого выходя блокя 5) через г полюс 58 и ГИ2 (с второго выхода блока 4 через полюс 59) через элементы

И 93 и 94 соответственно. Кроме этого„ сигнал "Пуск" с входного полюса 62 поступает ня вход элемента задержки

81 и на вход считывания узла 68 памяти начальных узлов. Ilo этому сигналу в узле 68 памяти происходит считывание информации из ячейки памяти, адрес которой определяется номером ветви, поступающим с полюса 63. Так как ветвь выбрана, кяк выходящая из начального узла моделирования сети, то на выходе узла 68 памяти формируется код этого узла, который через узел

87 элементов ИЛИ поступает на адресный вход узла 71 памяти первой выходящей ветви 71 и на информлционный вход регистра плчяльвого узла 73 подготавливаемой ветви. Через время злдержки, достаточное для c÷èòûâàíèë информации из узла 68 плмятн, снгнял "I!yeti Itoявляется íil выхе;;е элементл злдержки

81 и поступяет; рез:элемент ffJflf H9

7 l 564643 8 на вход считывания узла 71 памяти и на управляющий вход регистра 73. Ilo этому сигналу из узла 71 памяти осуществляется считывание кода номера ветви, являющейся первой в списке ветвей, выходящих из начального узла моделирования сети. Код номера этой ветви с выхода узла 71 памяти через узел 86 элементов ИЛИ поступает на информационный вход регистра ?2 выходящей ветви и записывается в Hего по первому импульсу ГИ1, поступающему на управляющий вход регистра 72 с выхода элемента И 93, Кроме этого, по заданному сигналу "Пуск",, который поступил на управляющий вход регистра,73, в него записывается код номера начального узла ветви. С выхода регистра 73 код номера началь- 20 ного узла ветви поступает на выходной полюс 41.

Записанный код первой выходящей ветви с выхода регистра 72 поступает на адресный вход узла 70 памяти, а также через полюс 35 на адресный вход узла 5 памяти длительности ветвей.„ на информационный вход узла 6 памяти номеров моделируемых ветвей и на вход схемы сравнения 13 блока I управления.30

Затем импульс ГИ2, сдвинутый относительно импульса ГИ1, с выхода элемента И 94 поступает на вход считывания узла 70 памяти, а по адресу первой выходящей ветви считывается номер второй ветви, выходящей из рассматри1 ваемого узла, Кроме- того „импульс

ГИ2 с выхода элемента И 94 поступает на полюс 36 и на вход элемента задержки 85. С выхода элемента задержки 40

85 сигнал, задержанный на время, достаточное для считывания информации из узла 70 памяти, через элемент ИЛИ

90 поступает на вход считывания узла

69 памяти номеров конечных узлов вет- 45 вей сети. На адресный вход узла 69 памяти, с выхода узла 88 элементов

ИЛИ в это время поступает код номера ветви, считанный с узла 70 памяти. Из узла 69 памяти осуществляется считы- 50 вание кода номера конечного узла второй подготавливаемой ветви. Этот код с выхода узла 60 памяти поступает на информационный вход регистра 74 и записывается в него по приходу на управляющий вход следующего импульса

ГИ1 с выхода элемента И 93.

В блоке 1 управления сигнал поиска свободной модели ветви с полюса 36 поступает на вход считывания узла 5 памяти длительности ветвей, на вход элементов И 21 и 22 и через элемент

ИЛИ 27 на вход узла 16 элементов И.

На другой вход этого узла поступает код с выхода регистра 9 номера отработавшей модели ветви. Так как в рассматриваемый момент регистр 9 обнулен, то Hа выходе узла 16 элементов

И будет сформирован нулевой код, который через полюс 51 поступает на вход дешифратора 121 считывания меток блока 3 моделей ветвей. Так как на входе дешифратора 121 присутствует нулевой код, то ни на одном из выходов дешифратора сигнал считывания не сформируется и обращения к узлам

ll3(1), 113(2),...,113(Ê) памяти меток моделируемых ветвей иузлам 114(1), 114(2),...,114(К) памяти меток узлов не будет. Поэтому на выходах узлов

114(i)„. 114(2),...,114(К) памяти бубет присутствовать нулевой потенциал, что даст потенциал низкого уровня на полюсе 43. Этот потенциал через элемент НЕ 29 поступает на вход элемента И 21, на другой вход которого поступает сигнал поиска свободной модели ветви с полюса 36. На выходе элемента И 21 сформируется сигнал высокого уровня, который через элемент

ИЛИ 24 поступает на вход элемента задержки 30 и на полюс 54. Кроме того, по сигналу полюса 36, поступающему на вход считывания узла 5 памяти, осуществляется считывание длительности подготавливаемой ветви. Код длительности ветви с выхода узла 5 памяти через полюс 49 поступает в блок 3 моделей ветвей.

В блоке 3 моделей ветвей сигнал с полюса 54 поступает на входы элементов И 104(1) и 105(1) первой модели ветви 97(1). Так как в рассматриваемый момент все модели свободные, то триггер 100(I) первой модели ветви

97(l) будет находиться внулевом состоянии, и сигнал с выхода элемента

И 105(1) через элемент задержки 112(!) поступит на единичный вход триггера

100(1), устанавливая его в единичное состояние. Это означает занятость процессом моделирования длительности загружаемой ветви первой моделью ветви. Одновременно сигнал с выхода элемента И 105 (1) поступает на вход узла 109(1) элементов И, на другой вход полюса 49 поступает код длительнас1564643 ти подготавливаемой ветви. С выхода узла 109(1) элементов И код длитель"ности ветви поступает на информационный вход формирователя 99 (1) временного интервала и заносится в него в качестве исходной информации. Кроме этого, сигнал с выхода элемента

И 105(1)первой моделиветви через элемент ИЛИ 110(1) поступает на вход шиф10 ратора 117 адреса узла 98 поиска моделей ветвей. Шифратор 117 адреса сформирует код номера модели ветви (в данном случае первой), которая будет моделировать длительность первой выходя-,5 ! щей из узла ветви. С выхода дешифратора 117 код номера модели ветви через полюс 45 поступает в блок 1 управления.

В блоке 1 управления код номера модели ветви с полюса 45 поступает на информационный вход регистров 9 и 10 и на адресный вход узла памяти номеров моделируемых ветвей 6. На вход записи узла 6 памяти поступает сиг- 25 нал с выхода элемента ИЛИ 24, задержанный элементом 30 задержки на время поиска свободной модели ветви в блоке

3 моделей ветвей. По этому сигналу в узле 6 памяти производится запись ко- 30 да номера ветви, поступающего на информационный вход с полюса 35, по адресу номера модели ветви, в формирователь временного интервала которой уже внесена длительность ветви. Кроме этого, сигнал с выхода элемента за35 держки 30 поступает на установочный вход регистра 10 и записывает в него код номера модели ветви, а также на единичный вход триггера 12, устанавливая его в единичное состояние. Единичное состояние триггера 12 разрешает прохождение импульсов серии ГИЗ (с третьего выхода блока 4 через полюса 61) через элемент И 19 и элемент 45

ИЛИ 26 на счетный вход узла 8 формирования адреса меток моделируемых ветвей и на вход элемента задержки 31.

Первый импульс серии ГИЗ установит на выходе узла 8 код "1", который че- 50 рез узел элементов ИЛИ 23 и полюс 52 поступает на адресный вход узлов

113(1),113(2),...,113(К) памяти меток моделируемых ветвей и узлов 114(1), 114(2),...,114(K) памяти меток узлов всех моделей ветвей 97(1), 97(2), ..., 55

97(К) блока 3 моделей ветвей, Через время, достаточное для формирования кода на выходе узла 8 блока 1 управ- ления, на выходе элемента задержки

31 сформируется сигнал первого импульса серии ГИЗ, который через элемент ИЛИ 27 поступает на вход узла

16 элементов И, на другой вход которого поступает код с выхода регистра

97. Так как регистр 9 в настоящий момент находится в нулевом состоянии, то на выходе узла 16 элементов И сформируется нулевой код, который через полюс 51 поступает на вход дешифратора !21 считывания мегок блока 3 моделей ветвей. Так как на вход дешифратора !2! поступил нулевой код, то ни на одном из выходов дешифратора сигнал не сформируется. Выходы дешифратора 121 подключены к входам считывания узлов 113(1), 113(2),...,1!З(К) памяти меток моделируемых ветвей и узлов 114(1), 1?4(2),...,114(К) памяти меток узлов моделей ветвей 97(!)

97(21. ..,97(К), поэтому ни на одном из выходов указанных узлов памяти сигнал не сформируется. Потенциал низкого уровня метки моделирования узла с выходов узлов памяти 114(1), 114(2) ...,114(К) через полюс 43 поступает на вход элемента ИЛИ 28 блока 1 управления.

По истечении времени, достаточного для организации описанных процессов в блоке 3 моделей ветвей, на выходе элемента задержки 32 блока 1 управления сформируется сигнал задержанного импульса серии ГИЗ, который поступает на вход узла 15 элементов И.

На другой вход этого узла поступает код с выхода регистра 10, где записан номер найденной свободной модели ветви (в рассматриваемом случае первой).

С выхода узла 15 элементов И код HOмера модели ветви через полюс 50 поступает на вход дешифратора 120 записи меток блока 3 моделей ветвей. На первом выходе дешифратора, который соответствует номеру модели ветви, сформируется сигнал высокого уровня, поступающий на вход записи узлов

113(i) памяти меток моделируемьЖ ветвей и меток узлов 114(1), а также на вход элемента И 108(1) первой модели ветви 97(1), По этому сигналу в узел

113(l) памяти меток моделируемых ветвей записывается информация, поступающая с входного полюса 55> cl в узел

114(11 памяти меток узлов — информация с лолюса 56. Каж: ый импульс, сформированный нл выходе ллем лт; П l 08! 564643!

2 по сигналу с полюса 56, уменьшает .на

"1" код счетчика узлов 115(1).

В блоке 1 управления полюс 55 связан с выходом элемента ИЛИ 25. Первый вход элемента ИЛИ 25 связан с по5 пюсом 44 выхода метки моделирования ветви, и в рассматриваемый момент на нем присутствует потенциал низкого уровня,(в регистре 9 записан нулевой код). На второй вход элемента ИЛИ 25 поступает сигнал с выхода узла 13 сравнения номеров ветвей. Входы узла

13 сравнения связаны соответственно с ВЫХОДОМ узла 8 фОрмирОвания адреса меток моделирования и с полюсом 35.

Таким образом, на выходе узла 13 сравнения сформируется сигнал в том случае, когда адрес записи меток моделирования будет соответствовать номеру подготавливаемой ветви. В рассматриваемом случае на выходе узла 13 сравнения будет сформирован сигнал в том случае, если к моделированию подготавливается ветвь с номером "l". При 25 этом будет произведена запись единичной,метки в узел 113(1) памяти первой модели ветви 97(1) блока 3 моделей ветвей о первому адресу .

Полюс 56 связан с выходом элемен- Зп та ИЛИ 28 блока 1 управления. Первый вход элемента ИЛИ 28 связан с полюсом 43 выхода метки моделирования узла, где в рассматриваемый момент присутствует потенциал низкого уровня (в регистре 9 записан нулевой код, поэтому нет обращения ни к одной модели ветви). На второй вход элемента

ИЛИ 28 поступает сигнал с выхода схемы 14 сравнения номеров узлов. Входы 4О схемы 14 сравнения подключены соответственно к выходу узла 8 формирования адреса меток моделирования и к полюсу 41 номера начального узла подготавливаемой к моделированию ветви.

Таким образом, на выходе узла 14 сравнения сформируется сигнал при ус.повии, что здрес записи меток моделирования будет соответствовать номеру начального узла подготавливаемой к моделированию ветви". В рассматривае-мом моменте сигнал на выходе узла 15 сравнения будет сформирован в том случае, если к моделированию подготавливается ветвь, у которой номер начального узла равняется "1"; При этом единичная метка будет записана в узел 114(l) памяти первой модели ветви 97(1) блока 3 моделей ветвей по первому адресу, а код счетчика узлов сети 115(1) этой модели ветви уменьшится на "1".

Следующий импульс серии ГИЗ, который поступит с полюса 61 через элемент И 19 на счетный вход узла 8 формирования адреса меток моделируемых ветвей, установит на выходе узла код

"2". Этот код через узел 23 элементов

ИЛИ и полюс 52 поступает на адресный вход узлов 113(1), 113(2),. ° .,113(K) памяти меток моделируемых ветвеч и узлов 114(1), 114(2)...,,1!4(К)памяти меток узлов блока 3 моделей ветвей. Через время, достаточное для формирования кода на выходе узла 8 блока 1 управления, на выходе элемента задержки 31 сформируется сигнал второго импульса серии ГИЗ, который через элемент ИЛИ 27 поступает на вход узла 16 элементов И, на другой вход которого поступает код с выхода регистра 97. Так как регистр 9 в настоящий момент находится в нулевом состоянии, то на выходе узла 16 элементов И сформируется нулевой код, который через полюс 51 поступает на вход дешифратора 121 считывания меток блока 3 моделей ветвей. Так как на вход дешифратора 121 поступил нулевой код, то ни на одном из выходов дешифратора сигнал не сформируется, Выходы дешифратора 121 подключены к входам считывания узлов 113(1), 113(2) ...,113(K) памяти меток моделируемых ветвей и узлов 114(1), 114(2),..., 114(К) памяти меток узлов, поэтому потенциал низкого уровня метки моделирования узла с выхода узлов !14(1), 114(2),...,114(К) через полюс 43 поступает на вход элемента ИЛИ 28 блока

1 управления, а потенциал низкого уровня метки моделирования ветви с выхода узлов !13(1), 113(2),...,113(K) памяти блока моделей ветвей через полюс 44 поступает на вход элемента

ИЛИ 25.блока 1 управления.

По истечении времени, достаточного для органиэации описанных процессов в блоке 3 моделей ветвей, на выходе элемента задержки 32 блока 1 управления сформируется сигнал задержанного второго импульса серии ГИЗ, который поступает на вход узла 15 эле. МентоВ И. На другой вход этого узла поступает код с выхода регистра 10, где записан номер найденной свободной модели ветви. С выхода узла !5 эле1564643!

4 ментов И кад номера модели Ветви через полюс 50 поступает Hà Вход дешифратора 120 записи меток блока 3 моделей ветвей. Ila первом его выходе, который соответствует номеру свободной модели ветви, сформируется сигнал, поступающий на вход записи узла 113(l) памяти меток моделируемых ветвей и меток узлов 114(1) первой модели ветви 97(1). Ilo этому сигналу в узел

113(1) памяти меток моделируемых ветвей по второму адресу запишется единичная метка в случае, если к моделированию подготавливается ветвь с номерам 2, я в узел 114(1) памяти ме11 11

15 ток узлов IIo второму адресу заг гшется единичная метка в случае, если к моделированию подготавливается ветвь, у которой номер начального узла "2".

Следующий импульс серии ГИЗ увеличит на "1" код узла 8 формирования адреса меток моделируемых ветвей блока 1 управления и процесс записи метки моделирования ветвей и метки уз-25 лав повторяется для нового адреса, Так осуществляется запись единичной метки в узел 113(1) памяти меток моделируемых ветвей первой модели ветви

97(1) па адресу номера приготавливае- 0 мой к моделированию ветви и запись нулевой метки по всем остальным адресам, а также запись единичной метки в узел 114(1) памяти узлов первой модели ветви 97(1) по адресу номера начального узла подготавливаемой к мо35 делированию ветви,а запись нулевой метки — по всем остальным адресам.Описанный процесс поступления импульсов серии ГИЗ и запись меток моделирования ветвей и узлов будут продолжаться да теХ пар, пока на выходе . переполнения узла 8 формирования адресов моделированньгл ветвей блока 1 управления не сформируется сигнал 4 высокого уровня, что соответствует .перебору всех возможных номеров ветвей и узлов сети. Сигнал с выхода переполнения узла 8 поступает на нулевой вход триггера 12 и устанавливает 0

его в нулевое состояние. Нулевое состояние триггера 12 запрещает прохождение импульсов. серии ГИЗ через элемент И 19. Кроме этого, сигнал перепОлнения с ВыхОдя узля 8 пОступяет на вход сброса этого узла, устанавливая его в нулевое состояние.

Рассмотрим процесс подготовкИ K моделированию следующей ветви, Выходящей из нлчлльнага узла маделир11вяния ссти. Кяк отмечено, импульс серии ГИ2:с выхадл элемента И 94 блока 2 формирования топологии поступает нл вход считывлиия узла 17 памяти номеров Вьгходя1..их ветвей. Ня адресный

Вход узла 70 памяти в этот момент поступает код номера первой ветви, вьгхадящей из того же узла. Код номера этой ветви с выхода узла 70 памяти через узел 86 элементов HJIH поступает нл информационный вход регистра 72 вьгходящей ветви и. записывается в него па второму импульсу ГИ1, поступающему на управляющий вход регистра с выхода элемента И 93. С выхода регистра 72 код Второй выходящей Ветви через полис 35 поступает в блок 1 управления.

Кроме этого, кад второй ветви, выходящей из начлльнага узла моделирования, считанный из узла 70 памяти блока 2 формирования топологии через узлы 86 и 88 элементов И1М поступает на адресный вход узла 69 памяти номерОВ канечньгх узлов ветвей сети. На вход считывания узла 69 памяти через элемент ИЛИ 90 поступает сигнал первого импульса серии ГИ2 с выхода элеМента И 94, задержанный элементом задержки 85. Из узла 69 памяти считывается код номера конечного узла второй выходящей ветви. Этот код поступает на информационный вход регистра 74 и записывается в него по второму импульсу серии ГИ1, поступающему на установочный вход регистра с выхода элемента И 93. С выхода регистра 74 кад номера конечного узла второй ветви,выходящей из начального узла моделирования, через полюс 34 поcòóïàåò в блок 1 управления. Кроме этого, в блок 1 упрявлейия с выхода элемента

И 94 через полюс 36 поступает второй импульс серии ГИ2.

В блоке 1 управления сигнал поиска свободной модели ветьи с полюса

36 поступает на вход считывания узла

5 памяти длительности ветвей, на адресный Вход которого с полюсл 35 по-, ступает кад номера второй Выходящей ветви. Считанньпг код длительности. этой ветви через па нес 49 поступает в блок 3 моделей ветвей. Кроме этого, сигнал поиска свобадн и модели ветви с палюсл 36 через элемент И.1!И 27 поступает ня вход уэлл 16 элемен- . тов И, нл второй вход котораг 1 насту1564643

16

15 пает кад с выхода регистра 97. В рассматриваемый момент в регистре 9 хра— нится нулевой кад, поэтому, как атмвчалось, считывания информации из узлов памяти меток узла 114 блока моделей ветвей не производится, а на полюсе 43 присутствует нулевой потенциал. Этот потенциал через элемент НЕ 29 блока 1 управления поступает на вход элемента И 21, разрешая прохождение сигнала поиска свободной модели ветви с полюса 36 через элемент ИЛИ 24 на выходной полюс 54 и далее в блок 5 моделей ветвей. f5

В блоке 3 моделей ветвей сигнал пОиска свободной модели ветви с полюса 54 поступает на входы элементов И

104(1) и 105(1) первой модели ветви

97(1). Так как триггер 100(1) пер-. вой модели ветви находится в единичном состоянии, означающем занятость нЕрвой модели ветви, то сигнал с выхода элемента 104(1) поступает на полюс 54(2) второй модели ветви 97(2). 25

Триггер 100(2) .этой модели ветви нахадится в нулевом состоянии, поэтому на выходе элемента И 105(2) сформируется сигнал высокого уровня. Этот сигнал поступает на вход узла 109(2) 30 элементов И, и в формирователь 99(2) временных интервалов записывается код длительности второй ветви, выходящей из начального узла моделировачия,Кроме этого, сигнал с выхода элементов

105(1) через элемент зацержки 112(2) поступает на единичный вход триггера

100(2), устанавливая его в единичное состояние. По этому же сигналу шифратором 117 адреса узла 98 поиска 40 моделей ветвей формируется код номера второй модели ветви, который с выхода шифратора через полюс 45 поступает в блок l управления.

В блоке 1 управления код номера 45 модели ветви с .полюса 45 поступает на ацресный вход узла о памяти номеров моделируемых ветвей, на информационные входь! регистров 9 и 10 номеров отработавшей мацели ветви и номера свободной модели ветви. На вход записи узла б памяти и установочный вход регистра 10 поступает задержанный сигнал поиска свОбодной модели ветви с выхода элемента задержки ЗО.Про- 55 изводится запись кода номера второй исходящей ветви в узел б памяти по ацресу номера найденной свободной модели ветви и установка каца номера этой модели ветви в регистре 10. Кроме этого, сигнал с выхода элемента задержки 30 блока ) управления поступает на единичный вход триггера ! 2, устанавливая его в единичное состояние. Единичное сос таяние триггера 12 разрешает прохождение импульсов серии ГИЗ через элемент И 19 для формирования меток моделируемых ветвей и меток узлов. При этом каждый импульс ГИЗ увеличивает на "l код узла 8 формирования адреса меток моделирования. Кад с выхода узла 8 через узел элементов ИЛИ 23 и полюс 52 поступает на адресный вход узлов памяти 113(.1), 113(2),...,113(Ê) и

114(l), 114(2)„...,114(К) всер. моделей ветвей 97(1), 97(2),...,97(К) блока 3 моделей ветвей, Далее каждый импульс ГИЗ задержанный элементом задержки 31 блока 1 управления, через элемент ИЛИ 27 поступает на вход узла 16 элементов И, формируя на выходе узла нулевой кад, который через полюс 51 поступает на вход дешифратора 121 считывания меток блока 3 моделей ветвей. Н тевой код определяет отсутствие сигнала считывания на всех узлах 113(!), 113(2),...,113(К) памяти меток моделируемых ветвей и узлах 114(1), 114(2),...,114(К) памяти меток узлов. Отсутствие сигнала считывания определит нулевой потенциал на полюсах 43 и 44 блока 3 моделей ветвей. Кроме этого, каждый импульс ГИЗ, задержанный элементами задержки 31 и 32 блока 1 управления, поступает на вход узла 15 элементов И, формируя на выходе узла код номера той модели ветви, куда была записана длительность подготавливаемой к моделированию ветви (в рассматриваемом случае кад 2"). .Этот код через полюс 50 поступает на дешифратор 120 записи меток блока 3 моделей ветвей. На втором выходе дешифратора 120, который соответствует номеру модели ветви, сформируется сигнал, поступающий на входы записи узла 113(2) памяти меток моделируемых ветвей и узла 114 (2) памяти меток узлов, а также на вход элемента И 108 второй модели ветви. Происходит запись нулевой или единичной метки в узлы памяти 113(2) и 114(2) по адресу, который определяется кодом узла 8 формирования меток моделирования блока 1 управления. Единичная метка модели17

1564643 руемых ветвей в узел 113(2) памяти блока 3 моделей ветвей записывается в том случае, когда на выходе узла сравнения 13 блока 1 управления сформируется сигнал высокого уровня. Это произойдет в том случае, когда код узла 8 формирования адреса меток моделирования совпадает с кодом номера подготавливаемой ветви, т.е. в pacIp сматриваемом случае единичная метка записывается в узел 1)3(2) памяти второй модели ветви 97(2) блока 3 моделей ветвей по адресу номера данной ветви. Единичная метка узлов в узел )14(2) памяти блока 3 моделей ветвей записывается в том случае, когда на выходе узла сравнения 14 блока 1 управления сформируется сигнал высокого уровня. А это произойдет в том случае, когда код узла 8 формирования адреса моделирования совпадет с кодом номера начального узла подготавливаемой ветви, т.е. в рассматриваемом случае единичная мет- 25 ка записывается в узел ))4 (2 1 памяти второй модели ветви 97 12) блока 3 моделей ветвей по адресу номера начального узла второй ветви. Код счетчика узлов 115 (2) сети второй модели вет- 30 ви 97(2) уменьшается на "1".

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

ГИЗ на выходе переполнения узла 8 блока 1 .управления не сформируется сигнал высокого уровня. Указанный сигнал поступает на нулевой вход триггера 12, устанавливая его в нулевое со- 40 стояние. Этим запрещается прохождение импульсов ГИЗ через элемент И 19. Процесс.подготовки к моделированию второй ветви, выходящей из начального узла моделирования сети, на этом окан-4 чивается.

Так осуществляется подготовка ветвей, выходящих из начального узла моделирования сети, к процессу временного моделирования их длительности до тех пор, пока не будет . подготовлена последняя ветвь из списка выходящих ветвей. После. этого по адресу ее номера в узле 70 памяти номеров выходящих ветвей блока 2 формирования топологии будет считан код Х, который запишется в регистр 72. Выход регистра 72 подключен к дешифратору 78 состояния Х, где путем сравнения кодов выработается сигнал конца списка выходящих из узла ветвей. Этот сигнал с выхода дешифратора 78 поступает на нулевой вход триггера 7, устанавливая его в нулевое состояние. Нулевое состояние триггера запрещает прохождение импульсов I H) и ГИ2 через соответственно элементы И 93 и 94.

Кроме этого, сигнал с выхода дешифратора 78 поступает на полюс 38. С полюса 38 сигнал поиска прерывания поступает на единичный вход триггера

11 блока l управления, устанавливая его в единичное состояние, а также через полюс 39 на вход элемента ИЛИ

118 узла 98 поиска моделей ветвей блока 3 моделей ветвей, а также на вход формирователей сброса 116(1), 116(2), ...,116(К) всех моделей ветвей. С выхода элемента ИЛИ )18 сигнал поиска прерывания поступает на входы элементов И 102(1) и 103(1) первой модели ветви 97(1) . Так как в рассматриваемый момент подготовлены к моделированию ветви, выходящие из начального узла моделирования сети, и моделей. ветвей, закончивших процесс моделирования,нет, то триггер прерывания 101(1) первой модели ветви 97(1) будет находитьсяв нулевом состоянии,.

Разрешающий потенциал с нулевого выхода триггера 101(1) поступает на вход элемента И 102(1), и на выходе элемента сформируется сигнал поиска прерывания, который через полюс (2,); поступает на входы элементов И 102(2, и )03(2) второй модели ветви 97(2).

Так как триггер прерывания 101(1) второй модели ветви 97(2) также находится в нулевом состоянии, то сигнал поиска прерывания, сформированный на выходе элемента 102(2), через полюс (3,1) поступит на входы элементов

И 102(3) и 103(3) третьей модели ветви 97(3) и т.д . до К. Так как в рассматриваемый момент нет триггеров прерывания 101(1), 101(2),...,101(К), находящихся в единичном состоянии, то на выходе ни одного из элементов

103(l), 103(2)....,103(К) сигнал прерывания не сформируется. Поэтому на выходе элемента ИЛИ 119 узла 98 поиска моделей ветвей, входы которого соединены с выходами элементов И

103(1), 103(2),..., 103(К),будет присутствовать потенциал низкого уровня.

Этот потенциал через полюс 4Ь поступает на нулевой вход триггера )1 бло19 156464 ка 1 управления, подтверждая его единичное состояние. Единичное состояние триггера 11 разрешает прохождение импульсов серии ГИ1 через элемент

И 20 на счетный вход узла 7 измерения пути и на полюс 53. С полюса 53 импульсы измерительной серии поступают на вход элементов И 106(1), 106(2), ...,106(K) всех моделей ветвей 97(1), 97(2),...,97(К) блока 3 моделей ветввй, и проходят на входы формирователей 99 временных интервалов тех моделей ветвей 97, у которых триггер

100 занятости находится в единичном

15 состоянии. С приходом каждого импульса измерительной серии коц формирователей временных интервалов уменьшается на "l", а узел измерения пути суммирует временное моделирование. С 20 приходом количества импульсов измеритЕльной серии, равного минимальному кОду, записанному в какой-либо формнрователь, последний обчуляется и выдает сигнал об окончании процесса 25 временного моделирования длительности ветви.

Сигналы с выходов формирователей временных интервалов 99(1), 99(2),..., 99(К) поступают на единичные входы «О триггеров 101(1), 101(2)...,,10)(K) устанавливая их в единичное состояние, а также на входы элемента ИЛИ

118 узла 98 поиска моделей ветвей.

С выхода элемента ИЛИ 118 сигнал поиска прерывания через полюс (1,1) поступает на входы элементов И 102(1) и 103(1) первой модели ветви 97 (1).

Если триггер прерывания 101(1) первой модели ветви 97(1) установлен в еди- 40 ннчное состояние, на выходе элемента

103(- 1) сформируется сигнал прерывания, который через полюс (1,2) поступает на вход элемента ИЛИ 119 узла 98 поиска моделей ветвей. В противном слу- 45 чае сигнал поиска прерывания сформируется на выходе элемента И 102(l) первой модели ветви 97(1). Этот сигнал через полюс (2,1),поступает на входы элементов И 102(2) и 103(2) вто- 0 рой модели ветви 97(2). Если триггер

101(2) второй модели ветви 97(2) также находится в нулевом состоянии, сигнал поиска прерывания, сформированный на выходе элемента 102(2), через полюс (3,1) поступает на входы элементов И 102(3) и 103(3) третьей мо-, дели ветви 97(3) и т.д., пока не обнаружится модель ветви, в которой

3 20 триггер прерывания 101 установлен в единичное состояние. Сигнал прерывания, сформированный на выходе элемента И 103 этой модели ветви, поступает на вход элемента ИЛИ 119 узла 98 поиска моделей ветвей. С выхода элемента ИЛИ 119 сигнал прерывания через полюс 46 поступает в блок 1 управления. Кроме этого, сигнал прерывания, сформированный на выходе элемента И 103 блока 3 моделей ветвей, через элемент ИЛИ 110 поступает на вход шифратора адреса 117 узла 98 поиска моделей ветвей. С выхода шифратора 117 код номера модели ветви, выставившей прерывание, через полюс

45 поступает в блок 1 управления. Кроме этого, сигнал, сформированный на выходе элемента И 103 блока 3 моделей ветвей. поступает на вход формирователя 116 сброса модели ветви, устанавливая его триггер в единичное состояние, а также через элемент задержки Ill поступает на нулевой вход триггера прерывания 101, устанавливая его в нулевое состояние.

В блоке 1 управления сигнал прерывания с входного полюса 46 поступает на вход считывания узла б памяти номеров моделируемых ветвей и на установочный вход регистра 9 номера отработавшей модели ветьи. На адресный вход узла 6 памяти и на информационный вход регистра 9 с полюса 45 поступает код номера модели ветви, выставившей прерывание. Осуществляет. ся запись кода номера отработавшей модели ветви в регистр 9 и считывание информации из ячейки памяти узла б памяти по адресу номера модели ветви, т.е. считывание кода номера ветви, моделирование длительности которой закончено. Код. номера ветви с выхода узла 6 памяти поступает на полюс 47. Кроме этого, сигнал прерывания с полюса 46 поступает на нулевой вход триггера 11, устанавливая его в нулевое состояние, а так- же на вход элемента задержки 33. Через время, достаточное для считываь ния кода номера ветви из узла 6 памяти, на выходе элемента задержки 33 сформируется сигнал начала анализа свершения ветви, который через полюс 48 поступает в блок 2 формирования топологии.

B блоке 2 формирования топологии сигнал начала анализа свершения ветви

1564643 с полюса 48 поступает на вход элемента задержки 83 и через элемент ИЛИ 90 на вход считывания узла 69 памяти номеров конечных узлов ветвей сети, нл адресный вход которого с полюса 47 через элемент ИЛИ 88 поступает код номера ветви, моделирование длительности которой окончено. Происходит считывание информации из ячейки узла

69 памяти, где записан номер конеч10 ного узла рассматриваемой ветви. С выхода узла 69 памяти код номера конечного узла ветви поступает на информационные входы регистра 74 канечl5 ного .узла подготавливаемой ветви и регистра 75 анализируемой ветви. Через время, достаточное для считывания информации из узла 69 памяти, на выходе элемента задержки 83 сформиZO руется сигнал высокого уровня, который поступает на вход элемента задержки 84 и на установочный вход регистра 75. Происходит запись кода номера конечного узла обрабатываемой ветви в регистр 75. С выхода регистра

75 код номера конечного узла ветви через узел 87 элементов. ИЛИ по тугает на адресный вход узла 71 памяти номеров первой выходящей ветви, Через вре-, мя, достаточное для записи номера конечного узла ветви в регистр 75, на выходе элемента задержки 84 сформируется сигнал высокого уровня, который поступает на вход элемента И 92. На

35 другой вход этого элемента в случае, если-код конечного узла обрабатываемой ветви не равняется коду номера узла сети, принятого за начальный узел моделирования сети (процесс моделиро- 40 ванин находится не в конечной точке и на выходе узла 80 сравнения кодов присутствует нулевой потенциал), поступает разрешающий потенциал с выхода элемента HE 96.

На выходе элемента И 92 сформиру.ется сигнал, который через элемент

ИЛИ 89 поступает нл вход считьпзания узла 71памяти и установочный вход регистра 73, а через элемент ИЛИ 91

50 на единичный вход триггера 77. Триггер 77 устанавливается в единичное состояние, разрешая прохождение импульсов ГИ1 и ГИ2 соответственно через элементы И 93 и 94. На этом заканчивается этап обработки прерывания от

55 модели ветви, которая закончила процесс моделирования длительности ветви, и начинается я этап подготовки к моделиравлнию ветвей, выходящих нз конечного уэлл обрлблтывлемай ветви, Сигнал, который поступает нл вход считывания узла 71 памяти, осуществляет считывание ячейки памяти по адресу, который поступает нл адресный вход с выхода регистра 75 конечного узла анализируемой ветви через элемент ИЛИ 87, т.е. считывается первая в списке ветвь, выходящая из калечного узла ветви, моделирование длительности которой окончено. Кад номера считанной ветви с выхода узла 7! памяти через узел 86 элементов ИЛИ поступает на информационный вход регистра 72 выходящей ветви и записывается в него па первому импульсу

ГИ1, поступлющему нл управляющий вход регистра с выходя элемента И 93. Кроме этага,код номера IIE!pooII выходящей ветви с выхода узла 71 памяти блока

2 формирования топологии через узлы

S6 и 88 элементаг> ИЛИ поступает нл адресный вход узла 69 памяти номеров конечных узлов ветвей сети. На вход считывания указанного узла через элемент ИЛИ 90 поступает сигнал с элемента задержки 82, задержанный нл время, достаточное для считывания информации из узла 7! памяти. Па этому сигналу из узла 69 памяти осуществляется считывание кода номера конечного узла первой выходящей ветви. Этот

1 кад с выхода узла 71 памяти поступает на информлцианньп вход регистра 74 и записывается в нега по первому импульсу ГИ1, паступаюц)ему на установочный вход регистра с выходя элемента

И 93. С выходя регистра 74 кад номера канечн.!го узла первой выходящей ветви через полюс 34 поступает в блок

1 управления. Кроме этого, па сигналу, который поступил нл устанавачпый вход регистра 73, в него злписываеT ся кад начального узла -ервой выходящей ветви из регистра 75. С выхода ðåгистра 73 кад номера нлчлльпага узла ветви поступает нл выходной полюс 41.

Записанный код первой выходящей ветви с выхода регистра 7? поступает на лдресньп вхад узла 70 памяти, л также через выходной полюс 35 блока формирования топологии 2 — нл лдресV

HbIH вход узла 5 памяти длительности . ветвей, пл информационный вх jI уэлл

6 памяти номеров моделируемых ) «твей и нл вход узла сравнения I I бл)кл I уирлвл..ния . 4 I

23 памяти 114 через полюс 43 и элемент

НЕ 29 блока 1 управления поступает на вход элемента И 21, запрещая прохождение сигнала поиска свободной модели ветви с полюса 36 через этот элемент.

В рассматриваемом случае (при единичной метке узла) сигнал поиска сва= бадной моде/и ветви может быть сформирован на выходе элемента И 22. Эта произойдет при наличии разрешающих сигналов на входах элемента И 22, связанных с полюсом 37 и с полюсом

42. Разренающий сигнал с полюса 3/, который связан с выходом узла 79 сравнения кодов блока. 2 формирования топологии, сформируется при совпадении кодов, записанных s регистрах 74 и 76, т.е. когда конечный узег подготавливаемой ветви равняется начат ьному узлу моделирования сети (путь замыкается в исходной точке). Разрешающий сигнал на полюсе 42,который связан с объединенным выходом элементов И 107 (1), 107(2),...,107(К) блока 3 моделей ветвей, будет сформирован в там случае, если счетчик 115 узлов сети модели ветви, откуда считывается метка узлов, будет абнулен, и на его выходе переполнения.„ связанном с входом элемента l !7,, буд= : сформирован сигнал высокого урания (моделируемый путь прошел через все узлы и подготавливаемая ветвь замыкает его в начальном узле моделирования сети).

В рассмотренном примере сигнал поиска свободной модели ветви с выхода элемента И 22, а при считывании нулевой метки узла с выхода элемента

И 21 через элемент ИЛИ 24 поступает на вход элемента задержки 30, а также на выходной полюс 54.

Если хотя бы на одном из полюсов

37 или 42 отсутствует разрешающий сигнал, а из узла 114 riамяти меток узлов блока 3 моделей ветвей считана единичная метка, сигнал поиска свободной модели ветви не вырабатьгвается, длительность ветви в формирователь временного интервала модели ветви не заносится и подготовка ветви к моделированию на этом заканчива-ется.

Если же сигнал поиска свободной модели ветви выработался с полюса 54, ан поступает на вход элементов И

104(1) и 105 (l) первой модели вет1564643

Затем импульс ГИ2, сдвинутый относительна импульса ГИ1, с выхода элемента И 94 блока 2 формирования топологии поступает на вход считывания узла 70 памяти, и по адресу первой выходящей ветви осуществляется считывание номера второй ветви, выходящей из рассматриваемого узла.Кроме этага, сигнал ГИ2 с выхода элеменl0 та И 94 через полюс 36 поступает в блок 1 управления. В блоке 1 управлеНия сигнал поиска свободной модели с ветви с полюса 36 поступает на вход считывания узла 5 памяти длительности ветвей, на вход элементов И 21 и

22 и через элемент ИЛИ 27 на вход узла 16 элементов И. На другой вход указанного узла элементов И с регистра 9 поступает код номера модели

Ветви, прерывание от которой обрабатывалось последним. На выходе узла

16 элементов И сформируется код указанной модели ветви, который через полюс 51 поступает на вход дешифрато- 25 ра 121 считывания меток блока 3 моделей ветвей. На том выходе дешифратора, который соответствует номеру модели ветви, сформируется сигнал, поступающий на вход считывания узлов

113 и 114 памяти указанной модели ветви, а также на вход элемента И 107.

На адресный вход узлов 113 и 114 через полюс 52 с узла 23 элементов ИЛИ блока I управления поступает код, сформированный на выходе. узла 18 эле35 ментов И. Первый вход узла 18 элементов И подключен к полюсу 34 и на него из блока 2 формирования тополоI гии поступает ° код кОКОчнОГО узла под 40 готавливаемой к моделированию ветви, на другой вход узла 18 элементов И поступает разрешающий потенциал с нулевого выхода триггера 12. Таким образом, на выходе узла 18 элементов И.> 45 а значит, и на адресном входе узлов памяти 113 и 114 блока 3 моделей ветвей будет сформирован код конечного узла подготавливаемой х моделированию ветви. Осуществляется считывание информации из узла 114 памяти меток узлов тай модели ветви, которая окончила моделирование длительности ветви па адресу номера канечнога узла подготавливаемой к моделированию ветви. И если считана единичная метка, которая означает, что данная ветвь входит в уже пройденный узел сети, сигнал высокого уровня с выхода узла

26

1564643

25 ви 97(1) блока 3 моделей ветвей. Если триггер 100(1) первой модели ветви 97(l) находится в единичном состоянии (модель занята), сигнал с выхода

5 элемента И 104(1) через чолюс 54(2) поступает на вход элементов И 104(2) и 105(2) второй модели ветви 97(2).

Если триггер 100(2) второй модели ветви 97(2) также находится в единичном состоянии, сигнал с выхода эле. мента И !04(2) через полюс 54(3) поступает на вход элементов И 104(3) и

105(3) третьей модели ветви 97(3) и т.д. до первой свободной модели ветви, у которой триггер 100 находится в нулевом состоянии. У этой модели ветви сигнал высокого уровня с выхода элемента И 105 поступает на вход элемента И 109 и в формирователь 99 временных интервалов данной модели ветви заносится код длительности подготавливаемой ветви, который поступает на другой вход эЛемента И 109 с полюса 49. Кроме этого, сигнал с выхо- 25 да элемента И 105 через элемент задержки 112 поступает на вход -..Риггера 100, устанавливая его в единичное состояние. Далее сигнал с выхода элемента И 105 через элемент ИЛИ 110 30 поступает на вход шифратора 117 адреса узла 98 поиска моделей ветвей.

На выходе шифратора адреса сформируется код номера данной свободной модели ветви, который через полюс 45 поступает в блок 1 управления.

В блоке 1 управления код номера модели ветви с полюса 45 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей, на информа- 4р ционный вход регистров 10 и 9 номера свободной модели ветви и регистра номера, отработавшей модели ветви. На информационный вход узла 6 памяти в /

Рассматриваемый момент поступает код 45 номера подготавливаемой ветви с полю. са 35, а на вход записи — задержанный сигнал поиска свободной модели ветви с выхода элемента задержки 30.

Происходит запись номера подготавлиI ваемой ветви в узле 6 памяти по адресу номера модели ветви, которая будет моделировать ее длительность. Кроме этого,, задержанный сигнал поиска свободной модели ветви с выхода элемента задержки 30 поступает на установочный вход регистра 10, куда записывается номер модели ветви. Кроме этого задержанный сигнал поиска свободной модели ветви с выхода элемента задержки 30 поступает на вход триггера 12 формирования меток моделирования. Начинается процесс записи меток моделируемых ветвей в узел 1!3 памяти и меток узлов в узел 114 памяти блока 3 моделей ветвей.

Потенциал высокого уровня с единичного выхода триггера 12 блока 1 управления поступает на вход элемента И 19 и разрешает прохождение импульсов ускоренной серии ГИЗ с полюса 61 через элемент И 19 и элемент ИЛИ 26 на счетный вход узла 8 формирования меток моделирования. Первый импульс серии ГИЗ установит на выходе узла 8 код "l", который поступает на вход схем 13 сравнения номеров ветвей и номеров узлов 14, а также через узел

23 элементов ИЛИ и полюс 52 на адресные входы узлов памяти 113 и 114 всех моделей ветвей 97 блока 3 моделей ветвей. Кроме этого, сигнал серии

ГИЗ, задержаний элементом задержки

31 на время, достаточное для срабатывания узла 8, проходит через элемент

ИЛИ 27 и поступает на вход узла 16 элементов И. На другой вход указанного узла с выхода регистра 9 поступает код модели ветви, которая окончила моделирование длительности ветви. Указанный код с выхода узла 1.6 элементов

И через полюс 51 поступает на дешифратор 121 считывания меток узла 98 поиска моделей ветвей блока 3 моделей ветвей. На выходе дешифратора

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

114 указанной модели. ветви 97. Происходит считывание метки моделируемой ветви из узла памяти 113 и метки узла из узла памяти 114 по первому адресу.

Сигнал считанной метки моделируемой ветви с выхода узла памяти 113 через полюс 44 поступает на вход элемента ИЛИ 25 блока 1 управления. Если была считана единичная метка, на выходе элемента ИЛИ 25 сформируется сигнал высокого уровня, который через полюс 55 поступает на информационный вход узлов памяти 113 всех моделей ветвей 97 блока 3 моделей ветвей. В рассматриваемый момент на выходе элемента задержки 32 блока 1 управления сформируется сигнал высо ) 7

156464 кого уровня первого импульса ускоренной серии ГИЗ, который поступил на вход элемента задержки 32 с выхода элемента задержки Çl. Задержанный сигнал поступает на вход узла 15 элементов И, на другой вход которого поступает код найденной свободной модели ветви с выхода регистра 10. Сформированный на выходе узла 15 элементов И код свободной модели ветви через полюс 50 поступает на вход дешифратора 120 записи узла 98 поиска моделей ветвей блока 3 моделей ветвей.

На выходе дешифратора, который соответствует номеру свобоцной модели ветви, сформируется сигнал высокого уровня, поступающий на вход записи узлов памяти 113 и 114 указанной модели ветви. Происходит запись единичной метки 20 в узел 113 памяти меток моделируемых ветвей. Если же из узла 113 памяти отработавшей модели ветви будет считана нулевая метка, на первом входе элемента ИЛИ 26 блока 1 управления 25 будет присутствовать потенциал низкого уровня, а сигнал на выходе элемента будет определяться наличием сигнала на втором входе, который связан с выходом узла сравнения 13. Сигнал высокого уровня на выходе схемы сравнения 13 сформируется в том случае, кorда код узла 9 формирования адреса меток моделирования будет равен коду номера подготавливаемой к моделирова35 нию ветви, поступающему с полюса 35, т.е. когда к моделированию подготавливается ветвь с номером l". В этом случае сигнал высокого уровня с выхоца элемента ИЛИ 25 через полюс 55 поступает на информационный вход узлов памяти 113 всех моделей ветвей

97 блока 3 моделей ветвей, а в узел памяти 113 найденной свободной модели ветви записывается единичная мет- 45 ка. В противном случае в узел памяти

113 найденной свободной модели ветви записывается нулевая метка, Так осуществляется формирование и запись в узел памяти 113 свободной модели ветви метки моделируемых ветвей по первому адресу.

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

28 поступает на вход элемента ИЛИ 28 блока 1 управления. Если была считана единичная метка, на выходe элемента

ИЛИ 28 сформируется сигнал высокого уровня. В противном случае сигнал на выходе элемента ИЛИ 28 будет определяться вторым входом элемента, связанным с выходом схемы сравнения 14.

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

1 подготавливается ветвь с номером начального узла, равным "1". Таким образом, сигнал единичной метки узла на выходе элемента ИЛИ 28 сформируется в том случае, если из узла 114 памяти меток узлов отработавшей модели ветви блока 3 моделей ветвей будет считана единичная метка или если к моделированию подготавливается ветвь у которой начальный узел равняется

"1". С выхода элемента ИЛИ 28 сигнал единичной или нулевой метки через . полюс 56 поступает на информационный вход узлов памяти 114 всех моделей ветвей 97 блока моцелей ветвей.

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

Следующий сигнал серии ГИЗ, поступающий на счетный вход -узла 8 формирования адреса меток моделирования блока 1 управления с выхода элемента ИЛИ 26, установит на выходе узла код "2". Этот код через элемент

ИЛИ 23 и полюс 52 поступает на адресный вход узла 113 памяти меток моделируемых ветвей и узла 114 памяти меток узлов всех моделей ветвей

97 блока 3 моделей ветвей. Кроме этого, сигнал серии ГИЗ с выхода элемента ИЛИ 26 блока 1 управления через элемент задержки 31 и элемент ИЛИ 27 поступает на вход узла 16 элементов

И, на другой вход которого поступает код отработавшей модели ветви с выхода регистра 9. С выхода узла,lб элементов И код отработавшей модели ветви через полюс 51 поступает на

30

1564643

10 вход дешифратора !21 считывания меток узла 98 поиска моделей ветвей блока 3 моделей ветвей. На Выходе дешифратора, который соответствует номеру отработавшей модели ветви, сформируется сигнал, который поступает на вход считывания узла 113 памяти меток моделируемых ветвей и узла 114 памяти меток узлов указанной

1 модели ветви 97. Считанная метка моделируемой ветви с выхода узла памяти !!3 через полюс 44 поступает на вход элемента ИЛИ 25 блока 1 управления, а метка узла с выхода узла па- 15 мяти 114 блока 3 моделей ветвей через полюс 43 поступает на вхоц элемента

ИЛИ 28 блока 1 управления. Если из узла памяти 113 отработавшей модели ветви блока 3 моделей ветвей считана единичная метка или подготавливается к моделированию ветвь с номером

"2", на выходе элемента ИЛИ 25 блока

1 управления сформируется сигнал высокого уровня, который через полюс 25

55 пос.тупает на информационный вход

1 узлов памяти 113 всех моделей ветвей 97 блока 3 моделей ветвей. Если из узла памяти !14 отработавшей модели ветви блока 3 моделей ветвей счи-30 тана единичная метка или к моделированию подготавливается ветвь, у которой начальный узел равняется "2", на выходе элемента ИЛИ 28 блока 1 управления сформируется сигнал высокого уровня, который через полюс 56 поступает-на информационный вход узлов памяти 114 всех моделей ветвей 97 блока

3 моделей ветвей.

В рассматриваемый момент в блоке 4п

1 управления сформируется задержанный элементами задержки 31 и 32 сигнал второго импульса серии ГИЗ. Этот сигнал поступает на вход узла 15 элементоВ И на ДругОй ВХОД KQTQpoI О 45 с выхода регистра 10 поступает код . свободной модели ветви. С выхода узла

15 элементов И код свободной модели ветви через полюс 50 поступает на вход дешифратора 120 записи меток узла 98 поиска моделей ветвей блока 3 моделей ветвей ° На выходе дешифратора, который соответствует номеру свободной модели ветви, сформируется сигнал, который поступает на вход запи55 си узлов памяти 113 и 114 указанной модели ветви. Происходит запись метки моделируемых Ветвей с полюса 55 в узел памяти 113 и метки узлов В узел памяти 114 с полюса 56 по второму адресу.

Следующий импульс серии ГИЗ, поступивший на счетный вход узла 8 формирования адреса меток моделирования блока 1 управления, установит на выходе узла код "3 . Повторяется описанный процесс формирования метки моделируемых ветвей и запись ее в узел памяти 113 сьободной модели ветви 97 блока 3 моделей ветвей, формирование метки узлов и запись ее в узел памяти !14 свободной модели ветви по третьему адресу и т.д.

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

Сигнал переполнения поступает на нулевой вход триггера 12, устанавливая его в нулевое состояние. Нулевое состояние триггера 12 запрещает прохождение сигналов серии ГИЗ через элемент И 19 на счетный вход узла 8.

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

Начинается процесс подготовки к моделированию второй по списку ветви, \ выхоцящей из свершившегося узла. Как отмечалось вышее, код номера первой выходящей ветви с выхода регистра 72 блока 2 формирования топологии поступает н адресный вход узла 70 памяти номеров выходяших ветвей. На вход считывания указанного узла поступает сигнал ГИ2 с выхода элемента И 94.

Происходит считывание из узла 70 памяти ячейки памяти по адресу номера первой выходящей ветви, т.е, считывается номер второй ветви, выходящей из свершившегося узла. Код номера считанной ветви с выхода узла 70 памяти через узел 86 элементов ИЛИ поступает на информационный вход регистра 72 и записывается в него по импульсу серии ГИ1, поступ-ющему на установочный зход регистра с выхода элемента V. 93. С выхода регистра 72 код номера FTupoIE выходящей ветви

1564643

32 вновь поступает F.,à адресный вход узла 70 памяти, а также через выходной полюс 35 в блок 1 управления.

Кроме этого, в блоке 2 формирова-ния топологии код номера второй выходящей ветьн с выхода узла 70 памяти через узлы 86 и 88 элементов

ИЛИ поступает на адресный вход узла

69 памяти номеров конечных. узлов ветвей сети. На вход считывания указан10 ного узла через элемент ИЛИ 90 поступает задержанный сигнал импульса

ГИ2 с выхода элемента задержки 85. По этому сигналу из узла 69 памяти производится считывание кода номера конечного узла второй выходящей ветви.

Считанный коц с выхода узла 69 памяти поступает на информационный вход регистра 74 и записывается в него по

20 второму импульсу ГИ1, поступающему на установочный вход регистра с выхода элемента И 93. С выхода регистра 74 код номера конечного узла второй выходящей ветви через полюс 25

34 поступает в блок 1 управления.

Таким образом, при подготовке к моделированию второй выходящей ветви в блок 1 управления с. блока 2 формиро-вания топологии через полюс 35 поступает код номера подготавливаемой ветви, через полюс 34 — код номера конечного узла подготавливаемой ветви и через полюс 41 — код номера начального узла подготавливаемой ветви.

Кроме этого,в блок 1 управления через

35 а полюс Зб с блока формирования топологии поступает сигнал второго импульса ГИ2 поиска свободной модели ветви.

B блоке 1 управления сигнал поиска

40 свободной модели ветви с полюса Зб через элемент ИЛИ 27 поступает на вход узла 16 элементов И, на другой вход которого поступает код отработавшей модели ветви с выхода регистра 9.

Сформировавшийся на выходе узла 16 элементов И код отработавшей модели ветви через полюс 51 поступает на вход дешифратора II21 считывания меток узла 98 поиска моделей ветвей

50 блока 3 моделей ветвей. На выходе дешифратора, который соответствует номеру отработавшей модели ветви, сформируется сигнал, поступающий на вход считывания узлов памяти 113 и 114 указанной модели ветви. Происходит

55 считывание метки узлов из узла памяти 114 по адресу номера конечного узла подготавливаемой к моделированию ветви, поступающего с полюса 34 блока 1 управления через элементы И

18 и ИЛИ 23 и полюс 52 на адресный вход узлов памяти 113 и 114 всех моделей ветвей 97 блока 3 моделей ветвей. Если из узла памяти 114 считана единичная метка, обозначающая, что данная ветвь образует частный контур сети, сйгнал единичной метки с выхода узла памяти 114 через полюс

43 и элемент НЕ 29 блока 1 управления поступает на вход элемента И 21, запрещая прохождение сигнала поиска свободной модели ветви через этот элемент. В этом случае, если на входных полюсах 37 и 42 (как рассматривалось выше) присутствуют разрешающие сигналы, сигнал поиска свободной модели ветви сформируется на выходе элемента И 22. С выхода элемента И 22, а в случае считывания нулевой метки узла — с выхода элемента И 21, сигнал поиска свободной модели через элемент ИЛИ 24 и полюс 54 поступает блок 3 моделей ветвей. В последнем по этому сигналу ищется свободная модель ветви, в формирователь 99 временных интервалов которой заносится код длительности подготавливаемой к моделированию ветви. Далее производится формирование меток моделируемых ветвей и запись их в узел памяти 113 свободной модели ветви, а также формирование меток узлов и запись их в узел памяти 114 указанной модели ветви. В результате в узле памяти 113 сформируются единичные метки по тем адресам, по которым были считаны единичные метки с узла памяти 113 отработавшей модели ветви, а также по адресу номера подготавливаемой к моделированию ветви.

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

Описанный процесс подготовки к моделированию ветвей, выходящих из свершившегося узла, будет продолжаться до тех пор, пока не будет подготовлена последняя ветвь из списка выходящих ветвей, После этого по адресу ее номера в узле 70 памяти номе33 15646 ров выходящих ветвей блока 2 формирования топологии будет считан код

Х, означающий конец списка выходящих ветвей, Этот код записывается в регистр 72, выход которого подключен 5 к дешифратору 78 состояния Х. В дешифраторе путем сравнения кодов вырабатывается сигнал конца списка выходящих из узла ветвей. Этот сигнал с выхода дешифратора 78 поступает на нулевой вход триггера 77, устанавливая его в нулевое состояние. Нулевое состояние триггера запрещает прохождение импульсов ГИI и ГИ2 через эле15 менты И 93 и 94 соответственно. Кроме этого, сигнал поиска прерывания с выхода дешифратора 78 через полюс

38 поступает в блок 1 управления.

В блоке 1 управления сигнал поиска прерывания с полюса 38 поступает на единичный вход триггера 11, устанавливая его в единичное состояние, а также через полюс 39 — в блок 3 моделей ветвей. С полюса 39 сигнал поиска прерывания поступает на вход стробирования формирователей )16 сброса всех моделей ветвей 97, а также на вход элемента ИЛИ 118 узла 98 поиска моделей ветвей. На выходе формирователя 116 сброса той модели ветви, на установочный вход формирователя сброса которой поступил сигнал с выхода элемента И 103, т.е. отработавшей модели ветви, прерывание от которой обрабатывалось последним, сформируется сигнал, поступающий на нулевой вход этого же формирователя, на нулевой вход триггера 100 занятости и на установочный вход счетчика 115 узлов. 40

Триггер 100 занятости устанавливается в нулевое состояние, что означает освобождение данной модели для дальнейших вычислений, а в счетчик 115 узлов записывается код, постоянно за- 45 дайный на полюса 64 и который на еди.ницу меньший количества узлов сети.

Сигнал поиска прерывания, KQTopbiH поступил на вход элемента ИЛИ l)8 узла

98 поиска моделей ветвей, .сформирует на выходе сигнал высокого уровня.

Этот сигнал через полюс (1,1),поступает на входы элементов И 102 (1) и

103 (1) первой модели ветви 97. Так как тРиггеР 101 прерывания пеРвой мо- 55 дели ветви находится в нулевом состоянии (если даже модель ветви и отработала временной интервал, то прерывание от нее уже отработано), на вы43 34 ходе элемента И ) О? сформируется сигнал высокого уровня, который через полюс (2,1) поступает на входы элементов И 102 (2) и 103(2) второй модели ветви 97(2). Если триггер IO) 2 прерывания второй модели ветви 97(2 ) находится в нулевом состоянии, сигнал с выхода элемента И 102(2 ) второй модели ветви 97(2 ) через полос (3.) j поступает на входы элементов И l02(3 ) и )03(3) третьей моделиветви 97(3),и т.д.Если в рассматриваемый моментв блоке 3 моделей ветвей имеются еще модели, которые окончили моделирование длительностей ветвей и триггер прерывания которых находится в единичном состоянии, сигнал прерывания с выхода элемента И 103 первой такой модели через элемент ИЛИ 119 и полюс 46 поступает в блок 1 управления, где сбрасывается в нулевое состояние триггер 11 и начинается процесс обработки прерывания от очередной модели ветви. Если же в рассматриваемый момент времени в блоке 3 моделей ветвей не имеется моделей, которые окончили моделирование, сигнал прерывания в блоке не вырабатывается и на выходном полюсе 46 будет присутствовать потенциал низкого уровня, Потенциал низкого уровня с полюса 46 подтверждает единичное состояние триггера II 6JIoK2 1 управления и импульсы измерительной серии начнут поступать через элемент И 20 на вход узла 7 измерения пути и через полюс 53 в блок 3 моделей ветвей.

В блоке 3 моделей ветвей импульсы измерительной серии с полюса 53 поступают на вход элементов И 106 всех моделей ветвей 97. У тех моделей ветвей, у котор:х триггер 100 находится в единичном состоянии (модель занята моделированием длительности ветви), на второй вход элемента И 106 поступает разрешающий потенциал с выхода триггера, и импульсы измерительной серии с выхода элемента И 106 поступают на счетный вход формирователя 99 временных интервалов, формирователи работают на вычитание, и с приходом количества импульсов. равного коду, записанному в счетчик формирователя, последний обнуляется, вырабатывая на выходе сигнал переполнения. Сигналы с выходов формирователей 99 временных интервалов моделей ветвей 97 поступают на вход элемента ИЛИ 118 узла

98 поиска моделей ветвей. Начинает3

1564643 ся описанный процесс поиска и обработки прерывания от моделей, которые окончили моделирование длительностей ветвей сети, 5

Описанные процессы подготовки исходящих ветвей к моделированию с проверкой метки узла и формированием массива меток моделируемых ветвей и меток узлов (построением маршрута по- lo следуемого контура пути ), временного моделирования длительностей загруженных ветвей с формированнем суммарной величины пути и обработки прерывания после окончания моделирования длительности каждой ветви сети будут выполняться в указанной последовательности. Продолжаться эти процессы будут до тех пор, пока при обработке очередного прерывания не окажется, 2л„ что конечный узел свершившейся ветви не будет равным начальному узлу моделирования сети (найден искомый контур пути). При этом в регис.тре 75 конечного узла анализируемой ветви бло- 25 ка 2 формирования топологии и в регистре 76 узла сети будут одинаковые коцы, а на выходе узла 8 сравнения кодов сформируется сигнал высокого уровня. С выхода узла 80 сигнал поступает на вход элемента И 95, на другой вход которого поступает задержанный элементами задержки 83 и 84 с полюса 48 сигнал начала анализа свершения ветви. На выходе элемента

И 95 сформируется сигнал разрешения выдачи результата, который через полюс 40 поступает на вход узла 17 элементов И блока 1 управления. На другой вход узла 17 элементов И поступа- 4Q ет код величины пути с выхода узла 7 измерения пути. С выхода. узла 17 элементов И код величины кратчайшего пути поступает на выходной полюс 67.

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

57, пройдя через элемент ИЛИ 26, установит код узла 8 равным "1". Этот код через узел 23 элементов ИЛИ и полюс 52 поступает на адресный вход узла 113 памяти меток моделируемых эет55 вей всех моделей ветвей 97 блока 3 моделей ветвей. Кроме этого, сигнал с полиса 57 через элемент ИЛИ 26, элемент задержки 31 и элемент ИЛИ 27 поступает на вход узла 1б элементов

И. На другой вход указанного узла с выхода регистра 9 поступает код отработавшей модели ветви, т.е. той модели ветви, прерывание от которой отрабатывалось последним. С выхода узла 16 элементов И код отработавшей модели ветв через полюс 51 поступает на вход дешифратора 121 считываниs меток узла 98 поиска моделей ветвей блока 3 моделей ветвей. На выходе дешифратора, который соответствует номеру отработавшей модели ветви, сформируется сигнал, который поступает на вход считывания узла 113 памяти меток моделируемых ветвей ука:. занной модели ветви 97. Происходит считывание метки из узла памяти 113 по первому адресу. Если из узла памяти 113 считана единичная метка, означающая, что ветвь с номером "1" входит в контур кратчайшего пути, сигнал высокого уровня с выхода узла памяти 113 через полюс 44 поступает на выходной полюс 65 меток: ветвей пути устройства. На выходной полюс бб номеров ветвей пути устройства поступает код "1" с выхода узла 9 блока

l управления. Если же из узла памяти

113 блока 3 моделей ветвей будет считана нулевая метка, на выходном полисе 65 устройства будет присутствовать потенциал низкого уровня. Это означает, что ветвь с номером 1 не входит в контур кратчайшего пути.

Следующий импульс с входного полюса 57 устройства установит на входе узла 8 блока 1 управления код "2", и процесс считывания метки моделируемых ветвей повторяется для второго адреса. Единичные метки по всем воз9 можным адре с ам ном еро в в ет в ей с е ти укажут полный контур кратчайшего пути, проходящего через все узлы сети.

В предложенном устройстве обеспечивается поступление необходимых сиг=налов предварительно-î .установа (на фиг.l, 2 и 3, не показаны).

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

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

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

I,-г,з

1564643

156464 З

Составитель А.Мишин

Редактор М,Келемеш Техред 11.Ходаннч Корректор С.Шекмар

Заказ 1161

Тираж 564

Подписное

ВН1И!1И Госуларственн г ., <омите га по изобретениям и oòêðûòèÿì при ГКНТ CCC.::

11303 >, Москва Ж )5 Ра)шская наб., д. /5

11оонзв<,н-твенно — s здатеньс к .ré ";; бн.гат 11атент, г, Ужгород„у.!. Гагарина, 1 )1