Устройство для определения характеристик сетей

Устройство для определения характеристик сетей

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных устройств для моделирования сетевых задач операционного управления. Цель изобретения состоит в расширении функциональных возможностей за счет нахождения максимального пути между начальным и конечньм узлами сети, ранних сроков начала и окончания ветвей , ранних сроков свершения узлов и свободных резервов ветвей. Устройство содержит блок управления, блок моделирования топологии сети, блок расчета характеристик сети, генератор импульсов. Блок управления содержит узел памяти номеров свершившихся ветвей, регистр номера первой ветви, регистр номера обрабатываемой ветви. регистр номера анализируемой ветви, триггеры, коммутаторы, элементы И, элементы ИЛИ, элемент НЕ, элементы задержки. Блок моделирования топологии сети содержит узел памяти номеров начальных узлов ветвей сети, узел памяти номеров конечных узлов ветвей сети, узел номеров выходящих из узлов ветвей, узел памяти номеров, входящих в узлы ветвей, узел памяти номеров первьк выходящих из узлов ветвей , уз памяти номеров первых входящих в узлы ветвей, регистр номера выходящей ветви, регистр номера входящей ветви, регистр номера конечного узла ветви, регистр номера конечного узла сети, триггеры управления, триггеры управления коммутаторами, коммутаторы, дешифраторы, схему сравнения , элементы задержки, элементы ИЛИ, элементы И, элемент НЕ. Блок расчета характеристик сети содержит узел памяти меток свершения ветвей, узел памяти кодов длительностей вет- Beic, узел памяти характеристик узлов, регистр длительности ветви, регистры , сумматор, схему сравнения, коммутаторы , триггеры, элементы И, элементы ИЛИ, элементы задержки.Ма кси-- мальный путь между начальным и конечным узлами сети и другие ее характеристики определяются на основе поярусного моделирования сети. 3 ил. и сл го 4 t со 00

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

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

РЕСПУБЛИН (50 4 G 06 F 15/20

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

Н A ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

13

ВИЙДЮ о" ;.„" q

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3793098/24-24 (22) 22.09.84 (46) 07.07.86. Бюл. № 25 (71) Институт проблем моделирования в энергетике AH УССР (72) А.Г.Додонов, Л.И.Минченко, С.П.Пелехов и Н.N.Ñàñþê (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 305484, кл. G 06 G 7/34, 1969.

Авторское свидетельство СССР № 1024930, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СЕТЕЙ (57) Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных устройств для моделирования сетевых задач операционного управления. Цель изобретения состоит в расширении функциональных возможностей за счет нахождения максимального пути между начальным и конечным узлами сети, ранних сроков начала и окончания ветвей, ранних сроков свершения узлов и свободных резервов ветвей. Устройство содержит блок управления, блок моделирования топологии сети, блок расчета характеристик сети, генератор импульсов. Блок управления содержит узел памяти номеров свершившихся ветвей, регистр номера первой ветви, регистр номера обрабатываемой ветви, „„SU„„1242980 А I регистр номера анализируемой ветви, .триггеры, коммутаторы, элементы И, элементы ИЛИ, элемент НЕ, элементы задержки. Блок моделирования топологии сети содержит узел памяти номеров начальных узлов ветвей сети, узел памяти номеров конечных узлов ветвей сети, узел номеров выходящих из узлов ветвей, узел памяти номеров, входящих в узлы ветвей, узел памяти номеров первых выходящих из узлов ветвей, узел памяти номеров первых входящих в узлы ветвей, регистр номера выходящей ветви, регистр номера входящей ветви, регистр номера конечного узла ветви, регистр номера конечного узла сети, триггеры управления, .триггеры управления коммутаторами, коммутаторы, дешифраторы, схему сравнения, элементы задержки, элементы ИЛИ, элементы И, элемент НЕ. Блок расчета характеристик сети содерямт узел памяти меток свершения ветвей, узел памяти кодов длительностей ветвек, узел памяти характеристик узлов, регистр длительности ветви, регистры, сумматор, схему сравнения, коммутаторы, триггеры, элементы И, элементы ИЛИ, элементы задержки. Макси-мальный путь между начальным и конечным узлами сети и другие ее характеристики определяются на основе поярусного моделирования сети. 3 ил.

1 12

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

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

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

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

Блок 1 содержит узел 34 памяти номеров свершившихся ветвей, регистр

35 номера первой ветви, регистр 36 номера обрабатываемой ветви, регистр

37 номера анализируемой ветви, три тригrера 38 — 40, три коммутатора 4 1—

43, семь элементов И 44-50 три элемента ИЛИ 51-53, элемент НЕ 54, четыре элемента 55-58 задержки.

Блок 2 содержит узел 59 памяти номеров начальных узлов ветвей сети, узел 60 памяти номеров конечных узлов ветвей сети, узел 61 памяти номеров выходящих из узлов ветвей, узел 62 памяти номеров входящих в узлы ветвей, узел 63 памяти номеров первых выходящих из узлов ветвей, узел 64 памяти номеров первых входящих в узлы ветвей, регистр 65 номера выходящей ветви, регистр 66 номера входя— щей ветви, регистр 67 номера конечного узла ветви, регистр 68 номера конечного узла сети, первый 69 и второй 70 триггеры управления, первый 71, второй 72 и третий 73 триггеры управления коммутаторами, четыре коммутатора 74-7?, первый 78 и второй 79 дешифраторы, схему 80 сравнения, первый 81 и второй 82 элементы задержки, элемент ИЛИ 83, элемент И 84, элементы ИЛИ 85-89, элементы И 90-94, элемент НЕ 95.

Блок 3 содержит узел 96 памяти меток свершенияветвей,узел 97 памяти кодов длительностей ветвей, узел 98

42980 2 памяти характеристик узлов, регистр

99 длительности ветви, регистр 100 вспомогательный, регистр 101 характеристики узла, сумматор 102, регистр 103 суммы, схему 104 сравнения, 5 три коммутатора 105-107, два триггера 108 и 109, шесть элементов И 110115, два элемента ИЛИ 116 и 117, седьмой элемент И 118, три элемента

1О 119 121 задержки

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

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

На входной полюс 5 подается код номера ветви, выходящей из начально— го узла. По сигналу "Пуск", поступающему через входной полюс 6, начинает работу блок 2, который последовательно определяет номера ветвей, выходящих из начального узла сети. Генератор 4 стробирует работу всех блоков устройства набором тактовых им35 пульсов ГИ 1 — ГИ 5, сдвинутых относительно друг друга. Работа блока 2 осуществляется по импульсам ГИ 1 и

ГИ 2. По импульсу ГИ 1 блок 2 определяет номер ветви, выходящей из на40 чального узла, и подает код этого но— мера через полюс 9 в блок 1. Через полюс 7 в блок l поступает сигнал, разрешающий работу блока по записи номеров ветвей, начальные узлы кото4$ рых свершились. Ветви необходимо записать в виде последовательности их номеров в узел 34 памяти с тем, чтобы в последующем можно было провести анализ свершения их конечных узлов.

5О Код номера ветви через полюс 9 поступает на инфомационный вход регистра 35 и через коммутатор 41 (так как на.управляющий вход этого коммутатора пода. ется с полюса 7 единичный сигнал) на адресный вход узла 34 памяти. Регистр 35 исходно был обнулен. также как и триггер 38. С выхода регистра 35 информация поступает на

2980 4 такта в узле 34 памят о адресу второй ветви, выходящей из начального узла, будет записан код первой ветви, по адресу которой на нервом такте был записан нулевой код и метка в ви5 де единицы в дополнительном п+1 разряде.

В регистре 35 будет записан код номера второй ветви, а триггер 38 останется в единичном состоянии, так

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

15 узле 34 памяти по адресу кода третьей ветви будет записан код второй ветви, по адресу кода второй ветви будет храниться код первой, а по адресу кода первой — метка в дополнительном

20 и+1 разряде слова. В регистре 35 будет записан код третьей ветви. Аналогичным образом запись в узел 34 памяти будет осуществляться и в пос25 ледующих тактах, т.е. в узле 34 памяти по адресу кода последующей ветви будет храниться код предыдущей, по адресу первой — метка, а в регистре 35 — код последней ветви.

3 124 информационный вход узла 34 памяти.

Дополнительный n+1-й разряд информационного входа узла 34 памяти соединен с инверсным выходом триггера 38.

При записи номера первой ветви, выходящей из начального узла сети, на п+1-й разряд поступает единица, так как триггер 38 находится в нулевом состоянии. По тактовому импульсу ГИ 2 в блоке 2 выполняется определение номера следующей ветви, выходящей из начального узла, но с выхода блока на полюс 9 по-прежнему поступает код номера первой ветви. По следующему сигналу ГИ 3 выполняется запись содержимого регистра 35 и сигнала с инверсного выхода триггера 38 в узел 34 памяти по адресу первой ветви. Сигнал записи формируется на выходе элемента И 44, на входы которого подается постоянный сигнал разрешения с полюса 7 и тактовый сигнал

ГИ 3, и он поступает на вход разрешения записи узла 34 памяти ° Затем по сигналу, сформированному на выходе элемента И 45 и поступающему на вход разрешения записи регистра 35 и единичный вход триггера 38, в ре— гистр 35 записывается номер первой ветви, и триггер 38 устанавливается в единичное состояние. На входы элемента И 45 подается сигнал разрешения с полюса 7 и тактовый сигнал

ГИ 4. По тактовому импульсу ГИ 5 на данном этапе вычислений никаких действий не выполняется. На следующем 35 такте по импульсу ГИ 1 блок 2 выдает код номера следующей ветви, выходящей из начального узла сети, который через полюс 9 поступает в блок 1. По импульсу ГИ 3 на выходе элемента И 44 формируется сигнал, который разрешает запись в узел 34 памяти содержимого регистра 35 и значения сигнала с инверсного выхода триггера 38 по адресу кода номера но †4 вой ветви, выходящей из начального узла сети. В регистре 35 в данный момент времени содержится код номера первой ветви, выходящей из начального узла, а с инверсного выхода триггера 38 будет поступать нулевой сигнал, так как триггер 38 находится уже в нулевом состоянии. По сигналу

ГИ 4 с генератора 4 на выходе элемента 45 формируется сигнал, по кото-55 рому в регистр 35 будет занесен код номера второй ветви, выходящей из начального узла. В результате второго

Когда все ветви, выходящие из начального узла сети, будт записаны в узле 34 памяти блока 1, и блок 2 оп-, ределит, что список ветвей, выходящих из начального узла, закончен, то по очередному импульсу ГИ 1 блок 2 снимет постоянный сигнал разрешения на полюсе 7 и сформирует импульсный сигнал окончания списка выходящих из рассматриваемого узла ветвей, который через полюс 8 поступит в блок 1. Этим сигналом заканчивается первый этап работы устройства, призванный обеспечить загрузку кодов номеров выходящих из начального узла сети ветвей в виде некоторой последовательности в узел 34 памяти блока I. Этот этап загрузки узла" будет неоднократно повторяться при последукнцем функционировании.

Следукпций этап заключается в анализе ветвей, номера которых записаны в виде последовательности в узле 34 памяти блока 1. Суть анализа состоит в оценке свершения конечных узлов данных ветвей. Узел считается свершившимся только в том случае, когда проанализированы все ветви, входящие в него. На этапе анализа ветви форми1242980 руется величина ее раннего окончания, !аксимальная из этих характеристик для ветвей с одинаковым конечным узлом записывается в узел 98 памяти

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

При этом номера ветвей, выходящие

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

20 как н исследуемой сети нет ветвей с одинакоными номерами. Выполнив загрузку свершившегося узла., устройство возвращается к прерванному этапу анализа последовательности ветвей.

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

ЗО анализ е ветвей пр едьдущей последователт ности. Этот процесс буцет продол— жаться до тех пор, пока все узлы сети не будут сформированы, признаком чего служит отсутствие очередной пос— ледонательности ветвей, подготовлен— ной c анализу, либо свершение конечного узла сети, так как в отличие от всех остальньгх узлов только этот узел íе имеет выходящих ветвей и мо Щ жет свершиться лишь после обязательного свершения всех остальных узлов.

Этап анализа ветвей начинается по сиг;=.àëó блока 2, который поступает в блок 1 через полюс 8 и означает окончание этапа загрузки узла. Сигнал с полюса 8 устанавливает в единичное состоянгЫ триггер 39 блока 1, который исходно находился в нулевом состоянии. В исходном нулевом состоянии находится и триггер 40. Сигналы с единичного выхода триггера 39 и с нулевого выхода триггера 40 разрешают по импульсу ГИ 2 формирование на выходе эпемента И 49 сигнала, поступающего через элементы ИЛИ 51 и 52 на входы разрешения записи регистров 36 и 37.

На информационные входы этих регистров через коммутаторы 2 и 43 в соответстнии с нулевым сигналом на их управляющих входах (который поступает от единичного выхода триггера 40, находящегося в нулевом состоянии) поступает код "номера ветви, записан— ный в регистре 35 и являющийся, в соотве.тствии с предьдущим описанием этапа загрузки узлов, последним н последовательности ветвей, анализ которой необходимо выполнить. В результате код номера ветви по ГИ 2 заносится в регистры 36 и 37. В регистре 36 код номера ветви предназначен для прохождения процесса анализа данной последовательности ветвей н следующих тактах. Из регистра 37 код номера ветви поступает через полюс 15 в блок 2 и через .по— люс 16 в блок 3. По тактовому импульсу ГИ 3 на выходе элемента И 50 формируется сигнал, который устанавливает в нулевое состояние триггер 38, через элемент 58 задержки устанавливает н единичное состояние триггер 40 и поступает на вход элемента ИЛИ 53.

Тогда на выходе элемента ИЛИ 53 формируется сигнал, который через элемент 57 задержки сбрасывает триггер

39, прекращая его работу на этапе анализа, и через полюс 17 разрешает работу блока 3 и через него блока 2 по определению величины раннего окончания данной ветви и проверки свершения ее конечного узла. В блоке 1 к моменту тгрекращения его работы триг— геры 38 и 39 установились в нулевые состояния, триггер 40 — н единичное, а н регистре 35 находится код номера ветви анализируемой последовательности. На выходах блока 1 сформирован код номера ветви анализируемой последовательности, который через полюсы 15 и 16 поступает соответственно в блоки 2 и 3, управляющий же сигнал по тактовому импульсу ГИ 3 через полюс 17 поступает в блок 3, который меткой отмечает свершение данной ветви н соответствующем узле памяти, формирует постоянный управляющий сигнал коммутатором через полюс 19 и сигнал считывания кода начального узла данной ветви через полюс 20 в блоке 2. Полученный номер узла поступает из блока 2 через полюс 12 в блок 3, где и фиксируется в соответствующем регистре. Одновременно н блоке 3 по номеру анализируемой ветви, поступающему с полюса 16, считы1242980 вается код длительности этой ветви.

Все описанные операции выполняются по тактовому импульсу ГИ 4. Затем в блоке 3 определяется и фиксируется. величина раннего окончания данной ветви по тактовому импульсу ГИ 5. В блоке 2 по сигналу от. блока 3, сформированному по ГИ 1 и поступающему через полюс 21, начинает анализ свер10 шения конечного узла данной ветви.Он заключается в определении кода номера конечного узла и всего множества номеров ветвей, входящих в данный узел. Код номера конечного узла ана15 лизируемой ветви по тактовому импульсу ГИ 1 через полюс 13 поступает в блок 3, где фиксируется в соответствующем регистре. Одновременно через полюс 10 в блок 3 поступает код номе20 ра первой ветви, входящей в данный узел. Синхронно тактовому импульсу

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

30 подается сигнал через полюс 11, по которому к блоке 3 определяется на— личие метки свершения первой ветви, входящей в данный узел. Сигнал о наличии такой метки через полюс 18 поступает в блок 2. Считанная величина раннего окончания конечного узла ветви сравнивается в блоке 3 со сформированной ранее величиной раннего окончания ветви, тоже входящей в данный узел, записанной в блоке 1 и анализ которой выполняется. В случае, если величина раннего окончания анализируемой ветви окажется больше величины раннего окончания ее конечного узла, имеющейся в блоке З,то синх- ронно тактовому импульсу ГИ 3 по номеру данного узла запишется новая величина, соответствующая раннему окончанию анализируемой ветви. На этом блок 3 заканчивает работу по определению характеристики данного узла. Продолжается лишь анализ его свершения. Блок 2, синхронно импульсу ГИ 1, подает через полюс 10 номер очередной ветви из списка, входящих 55 в данный узле, и по тактовому импульсу ГИ 2 сигналом через полюс 11 считывает из блока 3 значение метки свершения этой ветви. Единичное значение метки свидетельствует о том, что анализ такой ветви уже проводился ранее, нулевое значение метки свидетельствует об обратном. Естественно, что первое же считанное нулевое значение метки одной из входящих в узел ветвей является признаком несвершения данного узла и служит сигналом к прекрашению дальнейшего анализа свершения узла. Если же все ветви, входящие в узел, имеют метки свершения, то это есть признак свершения данного узла, и тогда блок 2 самостоятельно переходит к описанному выше этапу загрузки этого узла, т.е. записи номеров множества исходящих из него ветвей в узел 34 памяти блока 1.

Различие с описанным выше заключается в том, что сигналом к началу запуска узла служит не сигнал Пуск с полю— са 6, а сигнал, формируемый в блоке 2. Это различие будет рассмотрено ниже при описании работы блоков устройства.

Работа блока 2 по анализу сверше— ния рассматриваемого узла оканчива— ется либо в результате обнаружения несвершившейся ветви, входящей в данный узел, о чем свидетельствует нулевой сигнал с полюса 18, либо в результате окончапия этапа загрузки свершившегося узла. В любом случае признаком завершения работы служит сигнал, синхронизированный по ГИ 1 и поступающий через полюс 8 ь блок I.

По этому сигналу триггер 39 вновь устанавливается в единичное состояние.

В момент прерывания работы блока 1 по анализу последовательности ветвей триггер 40 находился в ециничномсостоянии, и поэтому по тактовому сигналу ГИ 2 на выходе элемента И 48 будет сформирован управляюций сигнал, который поступает на вход считывания узла 34 памяти и на вход элемента 55 задержки. На адресный вход узла 34 памяти подается код, записанный в регистре 36, через коммутатор 41, так как на управляющем входе этого коммутатора будет присутствовать нулевой сигнал с полюса 7. Единичный сигнал от блока 2 через этот полюс снима.ется при появлении сигнала на полюсе 8.

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

1242980

i0 коц номера следующей, в анализируемой последовательности, ветвей, имеюший нулевое значение дополнительногo (и+1)-го разряда, либо кодовьпл набор с единицей в дополнительном разряде.

В зависимости от значения дополнительного (n+1)-го разряда будет сформирован сигнал на выходе элементов

И 46 и 47, Если в дополнительном (и+1)-м разряде считян нуль, то это означает, что остальные разряды со— держат код номера следующей ветви, которую необхоДимо анализировать, и он поступает через коммутатор 43, на управляющем входе к оторого присутствует единичный сигнал с единичного выхода триггера 40, на информационный вход регистра 37 и записывается в негo по сигналу с выхода элемента 55 заДBPKKN, Нулевой сигнал с (п+1)-ro разряда выхода узла 34 памяти через инвертор 54 поступает на вход элемента

И 46 и разрешает, синхронно тактовому импульсу ГИ 3, формирование на его выходе управляющего сигнала, который поступает через элемент ИПИ.51 на вход разрешения записи регистра 36, осуществляет перепись содержимого регистра 37 в регистр 36 через комму,татор 42 благодаря тому, что на управляющем входе коммутатора 42 присутст1зует единичный сигнал с единичного выхода -.ðèãã.åðà .40.

Одновременно сигнал, сформирован35 ный на выходе элемента И 46, поступает на вход элемента ИЛИ 53, на выходе которого появляется управляющий сигнал, который через элемент 57 зацержки сбрасывает триггер 39 в нуле- 40 вое состояние, прекращая тем самым работу блока 1, и поступает также через полюс 17 в блок 3, разрешая работу блоков 3 и 2 по последующему анализу новой ветви в соответствии с описанным вьппе.

Описанная последовательность работы блоков устройства по анализу множества кодов номеров ветвей, выходящих из свершившихся узлов, будет про50 должаться до тех пор, пока данное множество не закончится. Признаком конца множества анализируемых ветвей, записанного в виде поспедовательности кодов их номеров в узле 34 памяти блока 1, будет единичное значение (0+1) гО разряда кода считанного из узла 34 памяти по сигналу, сформированному па выходе элемента И 48. Тогда единичный сигнал с {и+1)-го разря— да выхода узла 34 памяти поступит на вход элемента И 47 и разрешит синх— ронно тактовому импульсу ГИ 3 формирование на выходе элемента И 47 управляющего сигнала, который через элемент 56 задержки сбросит в нуль триггер 40, В результате триггер 39 останется в единичном состоянии, а триггер 38 — в единичном, если при анализе предыдущей последовательности ветвей свершились узлы, имеющие выходящие из них ветви, и в следующем такте синхронно импульсу ГИ 2 генератора 4 на вьг оде элемента И 49 будет сформирован управляющий сигнал, по которому начнется анализ нового множества;ветвей., выходящих из узлов, свершившихся при анализе предыдущего мкожест за.

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

При сформировании конечного узла ня соответствующем выходе блока 2 появится сигнал, который через полюс 14 поступит в блок 3 и разрешит выдачу через полюс 23 расчетной величины длиннейшего пути между начальным и конечным узлами исследуемой сети. Одновременно через полюс 8 в блок 1 поступит очередной сигнал о свершении узла, который установит триггер 39 в единичное состояние, В результате на выходе элемента И 48 появится сигнал, который считывает из узла 34 памяти код, который будет иметь единицу в (и+1)-м разряде, так как предыдущая ветвь будет последней в анализируемой последовательности.

Ведь для свершения конечного узла сети необходимо свершение всех вет— вей сети и, следовательно, первый триггер 38 также будет в нулевом состояпии в связи с тем, что новая последовательность выходящих ветвей не могла быть сформирована. Сигнал с (n+i)-го разряда выхода узла 34 памяти разрешит появление на выходе элемента И 47 управляющего сигнала, который через элемент 56 задержки сбросит в нуль триггер 40 (триггер 39 по-прежнему будет находиться в единичном состоянии). На следующем такте по импульсам на:выходе элементов И 49 и 50 не буцут сформированы сигналы, 1242980

12 так как нуль на единичном выходе триггера 38 запретит это. На этом закончится работа устройства. В блоке 3 будут храниться требуемые характеристики узлов сети, составляющие совместно с величинами .длительностей ветвей функционально полный набор исходных данных, необходимых для получения характеритсик ветвей.

Теперь рассмотрим отдельно работу блоков 2 и 3.

Блок 2 предназначен для определе-. ния кодов номеров ветвей, выходящих из свершившегося узла, определения кодов номеров ветвей, входящих в узел, и оценки его свершения, а также для формирования сигнала о свершении конечного узла сети. Множества входящих (как и выходящих) в узел ветвей записываются в виде последовательности, которая заключается в том, что по номеру предыдущей ветви последовательчости записан номер последующей, а по номерам последних ветвей — код X. Таким образом, в узлах

59-64 памяти хранится полная информация о топологии исследуемой сети.

Регистры 65-67 предварительно обнуляются, а в регистр 68 заносится код номера конечного узла сети. Триггеры 69 и 70 находятся первоначально в нулевом состоянии. После начально— го установа на полюс 5 блока 2 подается код номера ветви, выходящей из начального узла. В некоторый момент времени сигнал "Пуск", поступающий через полюс 6, проходит через элемент ИЛИ 89 и устанавливает в единичное состояние триггер 70. Единичное состояние триггера 70 разрешает прохождение импульсов ГИ 1 (полюс 24) и ГИ 2 (полюс 27) через элементы

И .93 и 94. Кроме того, сигнал "Пуск" поступает на единичный вход триггера 71, на вход элемента 81 задержки, а также через элемент ИЛИ 85 иа вход считывания узла 59 памяти. На адресный вход данного узла памяти через коммутатор 74 поступит с полюса 5 код номера ветви, выходящей из начального узла. Это будет возможно,так как в исходном состоянии с полюса 19 на управляющий вход коммутатора 74 поступает нулевой сигнал. По адресу номера ветви из узла 59 памяти считы-55 вается код номаф начального узла сети, который поступает на вход коммутатора 75. Так как триггер 71, управляющий коммутатором 75, установлен пусковым сигналом в единичное состояние, то код номера начального узла поступит на адресный вход узла 63 памяти. На вход считывания узла 63 памяти с выхода элемента 81 задержки через элемент ИЛИ 83 поступит задержанный на время срабатывания узла 59 сигнал пуска, который выполнит считывание кода номера первой ветви, выходящей из начального узла сети. Этот же сигнал установит в единичное состояние триггер 72, управляющий коммутатором 76, на вход которого поступит считанная из узла 63 памяти информация. Единичное состояние триггера 72 разрешит поступление кода номера первой выходящей из начального узла сети ветви на информационный вход регистра 65, куда и запишется по импульсу ГИ 1, поступившему с выхода элемента И 93 на управляющий вход регистра 65. С выхода регистра 65 через полюс 9 полученный код номера первой выходящей из начального узла ветви поступит в блок 1 для последую ющей обработки. Туда же с единичного выхода триггера 70 через полюс 7 поступает управляющий сигнал. Одновременно код номера ветви с выхода регистра 65 поступает на адресный вход узла 61 памяти. По тактовому импуль— су ГИ 2 на выходе элемента И 94 будет сформирован управляющий сигнал, который сбросит в нуль триггер 72 и выполнит считывание из узла 61 памяти кода номера следующей из множества выходящих из начального узла ветви. Так как триггер 72 находится теперь в нулевом состоянии, то код номера следующей ветви через коммутатор 76 поступит на информационный вход регистра 65, но запишется туда только по импульсу ГИ 1, приходящему с выхода элемента И 93. Таким образом, в течение всего такта на выходе регистра 65 код номера выходящей ветви изменяться не будет, так как изменение производится по тактовому импульсу ГИ 1. Одновременно содержимое регистра 65 ноступает на вход дешифратора 78, где сравнивается с кодом состояния Х. По адресу номера последней ветви, выходящей из начального узла, будет считая и записан в регистр 65 код Х. Тогда на выходе дешифратора 78 будет сформирован сигнал, который поступит на нулевой

1242980

14 вход триггера 70, сбросит er o в нуль, и тем самым прекратит поступление через полюс 7 управляющего сигнала в блок 1. Одновременно сигнал с дешифратора 78 через элемент ИЛИ 87 и полюс S поступит в блок 1, что будет свидетельствовать об окончании этапа запуска узла. На этапе анализа ветвей блок 2 выполняет операцию анализа свершения конечного узла ветви, Через полюс 15 с блока 1 поступает код номера анализируемой ветви. Через . коммутатор 74, на управляющем входе которого присутствует с полюса 19 единичный сигнал, код поступает на адресный вход узла 59 памяти, из соответствующей ячейки которого по сигналу блока 3 через полюс 20 считывается код номера конечного узла данной ветви, который поступает через полюс 12 в блок 3. Одновременно код номера ветви поступает на адресный вход узла 60 памяти, из соответствующей .ячейки которого по сигналу с полюса 21 блока 3 считывается код номера конечного узла дачной ветви,который через полюс 13 поступает обратно в блок 3. Эти данные необходимы для работы блока 3. Анализ свершения

30 конечного узла данной ветви начинается по сигналу блока 3 через полюс 22, которыи, синхронно импульсу ГИ танавливает в единичные состояния триггеры 69 и 73. Единичное состояние триггера 69 разрешает формирование

35 управляющих сигналов на выходе элементов И 91 и 92. Одновременно сигнал с полюса. 22 поступает на вход элемента 82 задержки и на вход считьтвания узла 60 памяти (через элемент ИЛИ 86). На выходе узла 60 памяти появляется считанный код номера конечного узла данной ветви., который поступает на информационные входы

4 регистра 67 и узла 64 памяти. Сигнал с выхода элемента 82 зацержки поступает на управляющие входы решистра 67 и узла 64 памяти. В регистр 67 записывается код номера конечного узла анализируемой ветви, а из узла 64 памяти по коду номера узла считывается код номера первой из множества входящих в данный узел ветвей. С выхода узла 64 памяти код номера первой входящей в узел ветви через коммутатор 77 (так как триггер 73, управляющий коммутатором 77, находится в единичном состоянии) поступает на информационный вход регистра 66. Далее по сигналу ГИ 1 с выхода элемента И 91 этот код записывается н регистр 66 и ноступает через полюс 10 в блок 3 для считывания метки свершения ветви. Одновременно код ветви с выхода регистра 66 поступает на информационный вход узла 62 и на вход дешифратора 79. По тактовому импульсу ГИ 2 на выходе элемента И 92 формируется сигнал„ который поступает через полюс 11 в блок 3, где считывается значение метки свершения ветви, код которой находится в регистре 66.

Если считанное значение метки равно единице, то единичный сигнал с полюса 18 поступает на вход элемен— га И 84 и разрешает прохождение через него управляющего сигнала с элеменга И 92. Сигнал с выхода элемента

И 84 сбрасывает в нуль триггер 73 и считывает код номера следующей входящей в узел ветви из узла 62 па— мяти. Считанная информация через коммутатор 77 (так как управляюддй им триггер 73 находится в нулевом состоянии), поступает на информационный вход регистра 66, куда и записывается в следуюшем такте по импульсу ГИ 1 с элемента И 91. Если же считанное значение метки свершения равно нулю, то нулевой сигнал с полюса 18 через элемент НЕ 95 и элемент ИЛИ 88 сбрасывает триггер 69 и поступает на вхоц элемента ИЛИ 87, на выкоде которого формируется управляющий сигнал, который через полюс 8 поступает в блок 1.

Если при анализе свершения ветвей, в одяш ъх в узелр нулевого сигнала о значении мегки свершения не приходит, то по адресу последней считывается из узла 62 памяти код состояния Х в. регистр 66. По этому коду дешифратор 79 вырабатывает сигнал, который сбрасывает в нуль триггер 69, устанавливает в единицу триггер 70 и поступает на первый вход элемента И 90, на второй вход которого поступает сигнал с. блока 80, который вырабатывает сигнал в случае совпадения кода свершенного узла, записанного в регистре 67, и кода конечного узла сети, записанного в регистре 68.

С выхода элемента И 90 сигнал о свершении конечного узла сети поступает в блок 3., и устройство прекращает работу, как описывалось выше. Если

124?980 !

15 же свершился не конечный узел, то сигнал с выхода дешифратора 79 сбрасывает в нуль триггер 71, который разрешает поступление через коммутатор 75 кода свершившегося узла, записанного в регистре 67, на адресный вход узла 63 памяти. Сигнал с выхода, дешифратора 79 через элемент ИЛИ 83 поступает на вход считывания, узла 63

10 памяти. Далее вновь выполняется. этап запуска узла.

Блок 3 в процессе функционирования устройства определяет величину раннего окончания анализируемой ветви, 15 сравнивает ее с имеющейся величиной раннего окончания конечного узла этой ветви, полученной в результате предыдущих анализов входящих в этот узел ветвей, и если полученная харак- 2

20 теристика ветви больше имеющейся характеристики ее конечного узла, то присваивает данному узлу величину полученной характеритиски. В результате в момент свершения данного узла в блоке 3 по номеру узла будет записана величина раннего окончания входящей в него ветви, имеющей наиболь— шее значение, т.е. величина раннего свершения узла. Блок 3 работает сле—

30 дующим образом. Предварительно узел 96 памяти меток свершения и узел 98 ранних окончаний узлов очищаются от всякой информации. Триггеры 108 и 109 находятся в нулевом состоянии.

В процессе анализа ветви блок 1 подает через полюс 16 и блок 3. код номера анализируемой ветви. Работа блока 3 начинается с момента получения от блока 1 сигнала запуска, синх— ронизированного по тактовому импуль40 су ГИ 3, через полюс 17. Сигнал с полюса 17 поступает на единичные входы первого и второго триггеров 108 и 109 и устанавливает их в единичные состояния. Единичный сигнал с выхода триггера 109 разрешает формирование на выходах элементов И 110-114 управляющих сигналов по соответствующим тактовым импульсам ГИ 4, ГИ 5, ГИ 1, ГИ 2 и ГИ 3. Одновременно еди ничный сигнал с выхода триггера 109 через полюс 19 поступает в блок 2 и на управляющий вход коммутатора 105, разрешая прохождение через него кода номера анализируемой ветви с полюса

16 ° Этот код с выхода коммутатора 105 поступает на адресный вход узла 96 памяти, IIa информационном входе которого постоянно присутствует единич,ный сигнал. По следующему тактовому импульсу ГИ 4 сигнал с выхода элемента И 110 поступает Ia вход записи узла 96 памяти и записывает по номеру анализируемой ветви единичное значение метки свершения . Этим же сигналом из узла 97 памяти кодов длительностей ветвей по адресу номера анализируемой ветви считывается код ее длительности, который поступает на информационный вход регистра 99. Одновременно сигнал с элемента И 110 через полюс 20 поступает в блок 2, где считывается код номера начальнога узла анализируемой ветви. Считан ный код узла через полюс 12 поступает через коммутатор 106 (так как на его управляющем входе присутствует единичный сигнал с выхода триггера

108) на информационный вход регистра 100. Одновременно сигнал с элемента И 110 через элемент ИЛИ 117 и элемент 120 задержки поступает на вход разрешения записи регистра 100, куда заносится код номера начального узла анализируемой ветви. По тактовому импульсу ГИ 5 сигнал с выхода элемента И 111 поступает на