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

1509925 Составитель В. ЧерньпповБланар Техред Л,Олийнык Корректор Т, Палий Редакто каз 5815/48 ираж б 68 Подписн Производственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 1 ВНИИПИ Государственного комитета по изобретениям и от 113035, Москва, Ж, Раушская наб.,тиям при ГКНТ СС4/5/ Блок 3 моделей ветвей (фиг. 3) со-, держит М моделей ветвей 68. (где М " количество ветвей в максимальном се,чении сети) и узел 69 поиска моделей ветвей, Цифрами в скобках обозначены порядковые номера совершенно одинаковых по своему конструктивному исполнению и функциональному назначению блоков, узлов, элементов и полюсов. Каждая модель ветви 68 (Фиг. 3) состоит из формирователя 70 временных интервалов, триггеров 71 и 72, элементов И 3"78, элемента .ИЛИ 79, элементов 80 и 81 задержки. 3 50992ка моделей ветвей, входы 31 и 32 блока формирования топологии, вход 33блока управления.Входными полюсами устройства яв 5ляются вход 34 начального пуска ивход 35 номера ветви. Выходным полюсом является выход 36 величины длиннейшего пути,Блок 1 управления (фиг. 1) предназначен для организации взаимодействия между блоком 2 Формирования топологии и блоком 3 моделей ветвей впроцессе моделирования с целью определения величины длиннейшего пути исследуемой сети, а также для контроляправильности функционирования каждоймодели ветви.Блок 2 формирования топологии предназначен для определения номеров ветвей, входящих в исследуемый узел сети, и номеров ветвей, выходящих из исследуемого узла сети, а также для определения момента окончания процессавычислений. Блок 3 моделей ветвей 25предназначен для организации процессавременного моделирования длительностей ветвей сети, генератор 4 импульсов - для формирования серий импульсов ГИ 1 и ГИ 2, сдвинутых один относительно другого.В блоке 1 управления (фиг. 1)узел 5 памяти длительностей ветвейпредназначен для хранения информациио величинах длительностей ветвей сети, а именно для хранения по адресуномера ветви кода длительности даннойветви. Узел 6 памяти номеров моделируемых ветвей предназначен для хранения инФормации о соответствии номера 40модели ветви из блока 3 моделей.ветвей номеру ветви сети, моделируемойв текущий момент времени данной моделью ветви. Узел 7 памяти метоксвершения ветвей предназначен для хра 45нения информации о завершении процесса временного моделирования длитель"настей ветвей сети.Блок 2 Формирования топологии(Фиг. 2) содержит узел 37 памяти но-меров начальных узлов ветвей сети,узел 38 памяти номеров конечных узловветвей сети, узел 39 памяти номероввыходящих ветвей узлов сети, узел 40памяти номеров входящих ветвей узловсети, узел 41 памяти номеров первойвыходящей ветви узлов сети, узел 42памяти номеров первой входящей ветвиузлов сети, регистр 43 номера выходя-т щей ветви, регистр 44 номера входящей ветви, регистр 45 номера конечного узла ветви, регистр 46 номера конечного узла сети, триггеры 47 и 48, дешифраторы 49 и 50, дешифратор 51 сравнения кодов, элементы 52 и 53 задержки, элементы ИЛИ 54-60, элементы И 61-66, элемент НЕ 67,Узлы 37-42 памяти предназначены для хранения информации о топологии моделируемой сети (узел 37 памяти - для хранения номера началЬного узла ветви по адресу номера данной ветви, узел 38 памяти - для хранения номера конечного узла ветви по адресу номера данной ветви, узел 39 памяти - для хранения в виде списков номеров ветвей, выходящих из узлов сети, узел 40 памяти - для хранения в виде списков номеров ветвей, входящих в узлы сети, узел 41 памяти для хранения по адресу номера узла номера ветви, первой из списка ветвей, выходящих из данного узла, а узел 42 памяти - для хранения по адресу номера узла номера ветви, первой из списка ветвей, входящих в данный узел).Регистр 43 предназначен для промежуточного хранения номера ветви при определении ветвей, выходящих из узла, а регистр 44 - для промежуточного хранения номера ветвеи, входящих в узел. Регистры 45 и 46 предназначены для хранения номера конечного узла ветви и для постоянногб хранения номера конечного узла сети, соответственно.Дешифратор 51 сравнениякодов предназначен для поразрядного сравнения кодов из регистров 45 и 46.Дешифраторы 49 и 50 состояния предназначены для сравнения поступающих на них кодов с кодовой комбинацией состояния Х,заданного постоянно в схеме,5 5099Схема узла 69 поиска моделей ветвей (фиг. 3) содержит шифратор 82 ад"реса и элементы ИЛИ 83 и 84.Входы 29(1), 29(2)29(М) кодадлительности ветви соединены с входами элементов И 77(1), 77(2)77(М).Входы 30(1), 30(2)30(М) измерительной серии импульсов соединены свходами элементов И 78(1), 78(2)78(М) узла моделей ветвей 68, Вход18(1) поиска свободной модели ветвисоединен с входами элементов И 75(1)и 76(1) первой модели ветви 68(.1). ВыВыход элемента И 75(1) первой модели 5ветви 68(1) соединен с входом 18(2)поиска свободной модели ветви второймодели ветви 68(2), выход элементаИ 75(2) второй модели ветви 68(2) соединен с входом 8(3) свободной модели ветви третьей модели ветви 68(3)и так далее до М. Вход 22 поиска прерывания.соединен с;ходом элементаИЛИ 83 узла 69 поиска моделей ветвейблока 3 моделей ветвей. Выход элемента ИЛИ 83 узла поиска моделей ветвейсоединен с входом (1,1) поиска прерывания первой модели ветви 68(1), Первая цифра в скобках обозначает болеевысокой в иерархии порядковый номер(в данном случае номер модели ветви),а вторая более низкий в иерархии номер (в данном случае порядковый номервхода или выхода этой модели),Входы (1,1), (2,1)(М,1) поиска прерывания моделей, ветвей 68(1),3568(2)68(М) соединены с входамиэлементов И 3(1),73(2), .,73(М) и.4(1),74(2)74(М). Выход элемента И 73(1) первой модели ветви 68( 1) 40соединен с входом (2,) поиска прерывания второй модели ветви 68(2), выход элемента И 73(2) второй моделиветви 68(2) соединен с входом (3,1).поиска прерывания третьей модели ветви 68(З) и т.д. до М-й модели ветви.Вьходы (1,2),(2,2)(М,2) переполнения формирователей временных интервалов 70(М) моделей ветвей 68(1),68(2)68(М) соединены с входамиэлемента ИЛИ 83 узла поиска моделейветвей 69. Выходы (1,4),(2,4)(М,4)сигналов прерывания с выходов элементов И 74(1), 74(2) 74(М) моделейветвей 68(1), 68(2)68(М) соединены с входами элемента ИЛИ 84. Выходы (1;3),(2,3) .(М,З) кода моделей ветвей с выходов элементов ИЛИ 79(1),79(2),79(М моделей ветвей 68,25 668(2)68(М) соединены с входами шифратора 82 адреса узла 69 поискамоделей ветвей. Выход 25 прерыванияблока 3 моделей ветвей соединен с выходом элемента РЛИ 84 узла 69 поиска моделей ветвей. Выход 24 номера модели ветви соединен с выходом шифратора 82 адреса узла 69 поиска моделей ветвей.Формирователи временного интервала 70(1), 70(2)70(М) моделейветвей 68(1), 68(2) . 68(М) предназначены для временного моделирования длительностей ветвей сети. Шифратор 82 адреса узла 69 поиска моделей ветвей предназначен для формирования адреса каждой модели ветви.В блок 1 управления (фиг. 1) дополнительно введены узел 85 памяти времени начала моделирования ветвей, узел 86 определения разности двух кодов, блок 87 сравнения, третий элемент И 88, второй и третий элементы ИЛИ 89-90, четвертый элемент 91 задержки, выходные полюса 92 и 93 сигналов неверной обработки длительности ветви и неверно обработанной ветви соответственно.Устройство работает следующим образом.В узлы 37-42 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети, а в узел 5 памяти длительности ветвей записываются длительности ветвей. Регистры 43-45 предварительно обнуляются, а в регистр 46 конечного узла сети заносится код номера конечного узла сети. Триггеры 9, 47 э 48 71(1)э 71(2)эфэ 1(М) 72(1) 72(2) .72(М) находятся первоначально в нулевом состоянии, узел 7 памяти меток свершения, узел 6 памяти номеров моделируемых ветвей и узел 8 памяти времени начала моделирования ветви блока 1 управления обнуляются.После начального установа на полюс 35 блока 2 формирования топологии подается код номера ветви, выходящей из узла, принятого при данном решении за начальный. Начальный узел, таким образом, определяется по адресу номера ветви в узле 37 памяти блока 2 корми" рования .топологии.В некоторый момент времени сигнал "Пуск", поступающий на полюс 34, проходит через элемент ИЛИ 60 и устанав-ливает триггер 48 в единичное состоя509925ние. Единичное состояние триггера 48 разрешает прохождение серии импульсов ГИ 1 (полюс 31) и ГИ 2 (полюс 32) соответственно через элементы И 65 и 66, Кроме этого, сигнал "Пуск" поступает на вход элемента 52 задержки и на вход считывания узла 37 памяти начальных узлов. При поступлении сигнала разрешения выборки в узле 37 па мяти происходит считывание ячейки памяти по адресу номера ветви, поступающего с полюса 35. Так как ветвь выбрана, как выходящая из начального узла сети, то на выходе узла 37 памяти.по является код начального узла сети, ко" торый через элемент ИЛИ 55 поступает на адресный вход узла 41 памяти первой выходящей ветви. Через время задержки, достаточное для считывания 20 информации из узла 37 памяти, сигнал "Пуск" появляется на выходе элемента 52 задержки и поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти. Сигнал выборки по адре су начального узла позволяет сосчитать из узла 41 памяти код номера ветви, являющейся первой в списке ветвей, выходящих из начального узла сети, Код первой выходящей ветви с выхода 30 узла 41 памяти поступает через элемент ИЛИ 56 на информационный вход регистра 43 номера выходящей ветви и записывается в него. по первому импульсу ГИ 1, поступившему на управляющий вход регистра с выхода элемента И 65Записанный код первой выходящей ветви с выхода регистра 43 поступает на адресный вход узла 39 памяти, че рез выходной полюс 16 блока 2 формирования топологии - на вход элемента ИЛИ 89, а также на информационный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, С вы хода элемента ИЛИ 89 код первой выходящей ветви поступает на адресный вход узла 5 памяти длительностей ветви, а также на адресный вход узла 85, памяти времени начала моделирования ветвей блока 1 управления.Затем импульс ГИ 2, сдвинутый отно" сительно импульса ГИ 1, поступает на вход считывания узла 39 памяти номеров входящих ветвей узлов сети блока 2 формирования топологии и по. адресу первой выходящей из начального узла ветви осуществляет выборку второго номера ветви, выходящей .из того же узла, Одновременно импульс ГИ 2 через элемент ИЛИ 40 поступает на вход считывания узла 5 памяти длительностей ветвей, на вход записи узла 85 памяти времени начала моделирования ветвей, на вход элемента 13 задержки блока 1 управления и вход 18 поиска свободной модели ветви блока 3 моделей ветвей. По этому сигналу ГИ 2 и адресу номера первой выходящей из узла ветви осуществляется считывание кода длительности этой ветви из узла 5 памяти длительностей ветвей, а также запись в узел 85 памяти времени начала моделирования ветвей кода, хранящегося в узле 8 измерения длиннейшего пути.Одновременно сигнал поиска свободной модели ветви с полюса 18 поступает на входы элементов И 75(1) и 76(1) первой модели ветви 68(1) и блока 3 моделей ветвей. Так как все модели ветвей свободны, то триггер 72(1) находится в нулевом состоянии и сигнал с выхода элемента И 76(1) через элемент 81(1) задержки, поступает на вход установки единичного состояния триггера 72(1),который через время задержки, достаточное для срабатывания всех элементов, устанавливает его в единичное состояние, что означает занятость процессом моделирования длительности некоторой ветви первой моделью ветви. Одновременно сигнал с выхода элемента И 76(1) поступает на первый вход элемента И 77(1) и через элемент ИЛИ 74(1) на вход дешифратора 82 адреса, На второй вход элемента И 77(1) через полюс 29 поступает код длительности ветви, который через элемент И 77(1) заносится в качестве исходной информации в формирователь 70(1) временного интервала,С выхода шифратора 82 адреса полученный по сигналу с полюса (1,3) код адреса модели ветви через полюс 24 поступает на адресный вход узла 6 памяти .номеров моделируемых ветвей блока 1 управления, Через время, достаточное для организации описанных процессов в блоке 3 моделей ветвей, на выходе элемента 13 задержки блока 1 управления появляется сигнал, поступающий на вход записи узла 6 памяти номеров моделируемых ветвей. Сигнал записи позволяет записать по адресу номера выбранной модели ветви (в данном случае первой) номер ветви, дли 15099 тельность которой внесена уже в формирователь 70 временного интервала данной модели ветви. На этом заканчивается подготовка первой выходящей из5 узла ветви к процессу временного моделирования длительности.Таким образом, подготовка одной ветви к временному моделированию включает считывание из блока 2 формирова- О ния топологии номера ветви, затем считывание ее длительности, поиск свободной от вычислений модели ветви, ввод в ее формирователь временного интервала кода длительности ветви, запись в узел номеров моделируемых ветвей по адресу номера выбранной модели ветви номера первой ветви, а также запоминание времени начала моделирования ветви, т.е, раннего начала ветви. 20Далее считанный по ацресу номера первой выходящей ветви из узла 39 памяти выходящих ветвей блока 2 формирования топологии номер следующей ветви в списке выходящих из узла ветвей по ступает на информационный .вход регистра 4 и с приходом второго импульса ГИ 1 записывается в указанный регистр. Записанный в регистр 43 код поступаетавновь на адресный вход узла 39 памяти, 30 а также через полюс 6 и элемент ИЛИ 89 блока 1 управления на адресный вход узла 5 памяти длительностей ветвей и информационный вход узла 6 памяти номеров моделируемых ветвей, С35 приходом второго импульса ГИ 2 из узла 5 памяти длительностей ветвей считывается длительность второй исходящей из узла ветви и для нее в узел 85 памяти времени начала моделирования ветвей записывается содержимое узла 8 измерения длиннейшего пути.Далее считанный код длительности второй исходящей ветви поступает через полюс 29 на входы элементов И 77(1), 77(2). 77(И) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 18(1) на входы элементов 75(1) и 76(1) первой модели ветви 68 поступает сигнал поиска свободной модели ветви. Так как триггер 72(1) первой модели ветви находится в единичном состоянии, означаю щим ее занятость, то сигнал с выхода элемента 75(1) поступает на вход 18(2) второй модели ветви, триггер 72(2)55 которой находится в нулевом состоянии. Тогда сигнал с выхода элемента И 76(2) второй модели ветви 68(2) 251 Опоступает на вход элемента И 77(2) и в формирователь временных интервалов 70(2) вводится исходная информация о коде длительности ветви, Одновремен-, но сигнал с выхода элемента И 76(2) через элемент 81(2) задержки устанавливает триггер 72(2) в единичное состояние, по этому же сигналу на выходе шифратора 82 адреса формируется номер второй модели ветви, который через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления, и при появлении через некоторое время сигнала на выходе элемента 13 задержки в узел 6 памяти по адресу номера модели ветви записывается номер ветви, код длительности которой введен в формирователь 70 временного интервала данной модели ветви.Так осуществляется подготовка ветвей, выходящих из начального узла, к процессу временного моделирования их длительностей до тех пор, пока не считана последняя ветвь из списка. По адресу ее номера в узле 39 памяти блока 2 формирования топологии считывается код Х, который записывается в регистр 43, Так как выход регистра 43 подключен к дешифратору 49 состояния Х, в комбинационной схеме путем сравНения кодов определяется информация о конце списка. Дешифратор 49 вырабатывает на выходе сигнал, который поступает на нулевой вход триггера 48, сбрасывая его в нулевое состояние. Кроме этого, сигнал с выхода дешифратора поступает на полюс 21. С последнего сигнал (поиска прерывания) поступает на единичный вход триггера прерывания 9 и устанавливает его в единичное состояние. Одновременно сигнал поиска прерывания поступает в блок моделей ветвей. Так как выполняется моделирование длительностей ветвей, выходящих из начального узла сети, и моделей ветвей, закончивших процесс моделирования, не имеется, то триггер прерывания 9 остается в единичном состоянии. На счетный вход узла 8 измерения длиннейшего пути и через полюс 30 во все формирователи 70 временного интервала моделей ветвей, триггеры 72 которых находятся в единичном состоянииначинают поступать импульсы серии ГИ 1. Так продолжается до тех пор, пока хотя бы один из формирователей 70 временного150992 интервала не вьщает сигнал об окончании процесса временного моделирования длительности ветви.Сигналы с выхода формирователей 70(1), 70(2)70(М) временного интервала поступают на единичные входы триггеров 71(1), 71(2)71(М) и устанавливают триггеры в единичное состояние. Одновременно сигнал с выхода 1 О формирователей 70 поступает через элемент ИЛИ 83 на вход поиска преры-. вания (1,1) первой модели ветви и в случае, если триггер 71(1) находится в единичном состоянии, сигнал прерывания с выхода элемента 74(1) поступает через элемент ИЛИ 84 и полюс 25 в блок 1 управления, устанавливает триггер 72(1) в нулевое состояние, что означает освобождение модели ветви для 20 последующих вычислений, Одновременно этот сигнал черезэлемент 80 задержки сбрасывает триггер 1(1) в нулевое состояние и вьщает с полюса (1,3) сигнал на вход шифратора 82 адреса, по кото рому формируется номер данной модели ветви, Номер модели ветви с выхода шифратора 82 адреса через полюс 24 поступает на адресный вход узла 6 памяти номеров моделируемых ветвей блока 1 управления.При получении с полюса 25 сигнала прерывания, который поступает на вход считывания узла 6 памяти номеров моделируемых ветвей, считывается по адресу номера модели ветви номер ветви35 сети, Этот номер поступает через элемент ИЛИ 12 на адресный вход узлапамяти меток свершения ветвей, а также через элемент ИЛИ 89 на адресный вход узла 5 памяти длительностей ветвей. Через время, достаточное для считывания номера ветви, на вход записи узла 7 памяти меток свершения ветвей через элемент 14 задержки поступает сигнал прерывания, и по адресу номера ветви в узел 7 памяти меток свершения ветвей записывается метка1 , характеризующая . свершение процесс а моделирования длительности дан- - 50 ной ветви . Одновременно сигнал прерыв ан ия с выхода элемента 1 4 задержки поступает на вход считывания узла 8 5 памяти времени начала моделирования ветви . Считываемая из узла 8 5 памяти по адресу кода ветви информация о начале моделирования ветви поступает на . первый вход узла 86 определения раз " но сти двух кодов(схема вычитания) ,512на второй вход которого подается код(конца моделирования ветви) текущеговремени моделирования сети с выходаузла 8 измерения длиннейшего пути.Через время, достаточное для записи метки в узел 7 памяти меток свершения ветвей, с выхода элемента 15 задержки сигнал прерывания поступает наразрешающий вход узла 86 определенияразности двух кодов, через полюс 28в блок 2 формирования топологии, через элемент ИЛИ 90 на вход считыванияузла 5 памяти длительности ветвей, атакже через элемент 9 задержки, наразрешающий вход блока 87 сравнения.Из узла 5 памяти длительностей ветвей считывается код длительности обрабатываемой ветви, а на выходе узла 86 определения разности двух кодовпоявляется разность времен начала иконца моделирования рассматриваемойветви. На информационные входы блока 87 сравнения поступают коды с выхода узла 86 определения разностидвух кодов и узла 5 памяти длительностей ветвей.Таким образом, на выходе узла 86определения разности двух кодов появляется код разности между кодами,определяющими время начала и времяконца моделирования ветви, равныйдлительности ветви при правильноммоделировании длительности. При различии кодов (неправильное моделирование ветви), поступающих на блок 87сравнения, на его выходе появляется сигнал сбоя, поступающий на выходной полюс 92 неверной отработкидлительности ветви и на вход элемен"та И 88. На второй вход элемента И 88поступает адрес кода ветви. Выход элемента И 88 соединен с выходным полю -сом 93 номера неверно отработаннойветви,Далее в работе устройства код номера ветви, считанной ранее с выхода узла 6 памяти номера моделируемойветви, через полюс 26 поступает наадресный вход узла 38 памяти конечно"го узла блока 2 формирования топологии, а сигнал начала анализа ветви сполюса 28 поступает на вход тригге"ра 47 и устанавливает его в единичноесостояние. Единичное состояние триггера 47 разрешает прохождение импуль"сов ГИ 1 (полюс 31) и ГИ 2.(полюс 32)через элементы И 63 и 64. Кроме того,сигнал начала анализа ветви поступаетиска прерывания. Наличие нулевого сигнала метки Свершения ветви означает,что хотя бы в одной из ветвей списка,входящих в узел, не завершился процесс временного моделирования своей5длительности и, следовательно, в дан"ном узле йе сформирована функция Пдля всех входящих в него ветвей. Тог-.да сигнал поиска прерывания с полю-.са 21 поступает на единичный входтриггера прерывания 9 и одновременночерез полюс 22 на вход элемента ИЛИ 83узла поиска моделей ветвей 59 блока 3моделей ветвей, С выхода элементаИЛИ 83 сигнал поступает на входы элементов И 73(1) и 74(1) первой моделиветви.Если модель ветви закончила про цесс моделирования длительности ветви ,которая еще не анализировалась,то триггер 71 находится в единичномсостоянии. Тогда сигнал с выхода элемента 74 такой модели ветви вновь по ступает на вход шифратора 82 адресадля формирования номера данной модели ветви, сбрасывает в нулевое состояние триггеры 71 и 72, а также черезэлемент ИЛИ 83 выдает сигнал прерывания, Блок 1 управления, получив номер модели ветви и сигнал прерывания,повторяет все описанные операции,связанные с анализом свершения ветви. Если в блоке 3 моделей ветвей неимеется моделей, имеющих триггеры 71в единичном состоянии, то процесс анализа прерывания не проводится и импульсы серии ГИ через элемент И 1 Облока 1 управления продолжают посту пать в узел 8 определения длиннейшего пути и в блок 3 моделей ветвей.Если сигнал метки свершения ветви с полюса 27 имеет единичное значение, т.е. процесс формирования длительности для ветви закончился, то онвыдает разрешение на прохождение импульса ГИ 2 через элемент И 61 блока 2 формирования топологии на входсчитывания узла 40 памяти входящейветви. На адресные входы узла 40 памяти в это время поступает код номера первой входящей ветви в списке свыхода регистра 44,По адресупервой вхо. дящей ветви из узла 40 памяти считывает-ся код номера второй ветви в списке,ко торый поступает через элемент ИЛИ 58 55на информационные входы регистра .44и записывается в него с приходомвторого .импульса ГИ 1 с выхода эле 13150 на вход элемента 53 задержки и на вход считывания узла 38 памяти. С при ходом сигнала считывания в узле 38 памяти конечного узла по адресу номера ветви, вызвавшей прерывание, проис ходит считывание ячейки памяти, в которой записан номер конечного узла: рассматриваемой ветви, Код считанного номера узла с выхода узла 38 памяти поступает на адресные входы узла памяти первой выходящей ветви и на информационныевходы регистра 45 конечного узлаЧерез время задержки, достаточное для считывания информации из узла 38 памяти, сигнал начала анализа ветви поступает на управляющий вход регистра 45 конечного узла и на вход считывания узла 42 памяти. По задержанному сигналу начала анализа ветви в регистре 45 происходит запись номера конечного узла ветви, а в узле 42 памяти по адресу номера конечного узла происходит считывание номера ветви, первой в списке входящих в рассмаФ- риваемый узел ветвей. Код номера первой входящей ветви с выхода узла 42 памяти поступает через элемент ИЛИ 58 на информационный вход регистра 44 входящей ветви и записывается в него по первому импульсу ГИ 1, поступающему на управляющий вход регистра с выхода элемента И 63. С выхода регистра 44 код номера первой входящей ветви поступает через полюс 19 и элемент ИЛИ 12 на адресный вход узла 7 памяти меток свершения ветвей блока 1 управления и на адресный вход узла 40 памяти номеров входящих ветвей блока 2 формирования топологии. Первый импульс ГИ 2 поступает с выхода элемента И 64 на вход элемента И 61 блока 2 формирования топологии и через полюс 20 на вход считывания узла 7 памяти меток свершения блока 1 управления.Метка свершения, считанная по адресу первой ветви с выхода узла 7 .памяти меток свершения ветвей, поступает через полюс 27 в блок 2 формирования топологии. Если метка отсутствует, что означает несвершение процесса моделирования длительности ветви с данным номероМ, то нулевой сигнал мет ки с полюса 27 через элемент НЕ 67 и элемент ИЛИ 59 сбрасывает триггер 4 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 67 поступает через элемент ИЛИ 57 на полюс 21 по 9925 1415 150992 мента И 63. Далее через полюс 19 осуществляется опрос метки свершения данной ветви, входящей в рассматри" ваемый узел, и переход к следующей ветви из списка входящих в него ветвей.Описанный процесс анализа входящих ветвей продолжается до тех пор, пока не опрошены все ветви, входящие 10 в рассматриваемый узел, что соответствует выполнению функции конъюнкции относительно входных ветвей для рассматриваемого узла, В этом случае по адресу последнего номера ветви в списке из узла 40 памяти считывается ин-формация Х определяющая конец списка. Код Х записывается в регистр входящей ветви 44 и далее поступает на вход дешифратора 50 состояния, ко торый путем сравнения кодов вырабатывает сигнал конца списка. Полученный сигнал проходит через элементы ИЛИ 59 и 60 и устанавливает триггеры 47 и 48 соответственно в нулевое и единич ное состояния, Сигнал с выхода дешифратора 50 поступает также на вход элемента И 62, второй вход которого связан с выходом дешифратора 51 сравнения кодов, Последний сравнивает ко ды, хранящиеся в регистре конечного узла сети 46 и регистре 45 конечного узла.Регистр 46 хранит код конечного узла сети, а регистр 45 - код рассматриваемого узла сети, сформировавшего функцию конъюнкции в данный момент времени. Если значения этих кодов совпадают (сформирована логическая функция конъюнкции для конечного узла 40 сети), то дешифратор 51 сравнения кодов выдает разрешение на прохождениесигнала конца списка с выхода дешифратора состояния 50 через элемент И 62на выходной полюс 23 блока 2 формиро вания топологии, что соответствует концу моделирования заданной сети, Данный сигнал с полюса 23 поступает на вход элемента И 11 блока 1 управ" ления и разрешает выдачу во внешние устройства величины длиннейшего пути сети, накопленной к данному моменту в узле 8 измерения, длиннейшего пути. Если не сформирован конечный узел сети, то сигнал с выхода дешифратора 50 поступает через элемент ИЛИ 54 на вход считывания узла 41 памяти первойвыходящей ветви, на адресный вход которого в этот момент времени поступа 516ет код номера сформированного узла сети. Вновь начинается описанный процесс подготовки к временному моделированию длительностей тех ветвей, которые выходят из данного сформированного узла,Описанные процессы подготовкиветвей к временному моделированию.длительностей с запоминанием кодоввремени начала моделирования и анализа ветви, закончивших процесс временного моделирования, с контролемправильности моделирования каждой ветвичередуются в указанном порядке иповторяются до тех пор, пока не сформирован заданный конечный узел ". сетис выдачей сформированной в узле 8 измерения длиннейшего пути блока 1 управления величины длиннейшего пути всети. В процессе всего временного моделирования сети при неправильной работе устройства на выходных полюсах 92и 93 фиксируются все сбойные ситуации, связанные с неправильным формированием длительностей ветвей сети,Формула изобретенияУстройство для моделирования задач о длиннейшем пути в сетях по авт.св.11- 1161951, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет введения контроля правильности временного моделирования сети, в блок управления устройства дополнительно введены узел памяти времени начала моделирования ветвей, узел определения разности двух кодов, блок сравнения, третий элемент И, второй и третий элементы ИЛИ, четвертый элемент задержки, вход которого соединен с выходом третьего элемента задержки, управляющим входом узла определения разности двух кодов и первым входом третьего элемента ИЛИ, выход которого соединен с управляющим входом узла памяти длительности ветвей, адресный вход которого соединен с адресным входом узла памяти времени начала моделирования ветвей, выходом второго элемента ИЛИ и первым входом третьего элемента И, второй вход которого соединен с выходом блока сравнения и является выходом сигнала неверной обработки длительности ветви блока управления и устройства в це" лом, выход третьего элемента И является выходом сигнала неверно отработан 17 1509925 18ной ветви блока управления и устрой- соединен с вторым информационным вхоства в целом, выход узла измерения дом узла определения разности двух длиннейшего пути соединен с первым ин- кодов, выход которого соединен с перформационным входом узла определения вым информационным входом блока срав 5разности двух кодов и информационным нения, второй информационный вход ковходом узла памяти времени начала мо- торого соединен с выходом уэла памяти делирования ветвей, вход записи кото- длительности ветвей, управляющий вход рого соединен с входом первого эле-. блока сравнения соединен с выходом мента задержки и вторым входом тре О четвертого элемента задержки, первый тьего элемента ИЛИ, выход второго эле- и второй входы третьего элемента ИЛИ мента задержки соединен с входом счи- соединены соответственно с входами нотывания узла памяти времени начала мера подготавливаемой ветви и поиска моделирования ветвей, выход которого свободной модели ветви.