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

 

Изобретение относится к области цифровой вычислительной техники, в (Частности к устройствам обработки информации специального назначения ,с точки зрения вычислительного устройства . Оно может быть использовано .при построении специализированных вычислительных устройств для моделирования сетевых задач оперативного управления. Изобретение позволяет сократить аппаратурные затраты при решении задачи поиска длиннейшего пути с помощью аппаратных средств. Это достигается введением блока управления , выполненного в виде шифратора , регистра состояния, генератора тактовых импульсов и триггера, арифметического блока и блока регист рации..Устройство реализует временное и пространственное моделирование исследуемого графа с пошаговым алго;ритмом поиска длиннейшего пути. 1 з. п. ф-лы, 5 ил. ю о Од | со

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

00QN

РЕСПУБЛИК (51) 4

РОСУДЯРСТВЕННЫЙ КОМИТЕТ COOP

fO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТКОЙ

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

Н АВТОБУСНОМУ СВИРВТВ\ЬСТВУ

«-= / (21) 36057 15/24-24 (22) 06.04.83 (46) 23.01.86. Бюп. У 3 (71) Институт проблем моделирования в энергетике АН УССР (72) С.П. ПЬлехов, А.Н. Ушаков и В.В. Федотов (53) 688.8(088.8) (56) Авторское свидетельство СССР ,Р 422002, кл. G 06 G 7/48, 1972.

Авторское свидетельство СССР

Ó 1024930, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

ПОИСКА ДЛИННЕЙШЕГО ПУТИ (57) Изобретение относится к области цифровой вычислительной техники, в . частности к устройствам обработки информации специального назначения..SU, 3206791,с точки зрения вычислительного устройства. Оно может быть использовано ,при построении специализированных вычислительных устройств для моделирования сетевых задач оперативного управления. Изобретение позволяет сократить аппаратурные затраты при решении задачи поиска длиннейшего пути с помощью аппаратных средств.

Это достигается введением блока управления, выполненного в виде шифратора, регистра состояния, генератора тактовых импульсов и триггера, арифметического блока и блока регистрации..Устройство реализует времено ное и пространственное моделирование ® исследуемого графа с пошаговым алгоритмом поиска длиннейшего пути. 1 s. п. ф-лы, 5 ил.

Выходы 26 - 28 образуют группу управляющих выходов топологических меток и берутся соответственно с еди. ничного выхода триггера 15 и последних разрядов буферных регистров 13 и 14.

Выход 29 узла 12 сравнения является выходом окончания временного моделирования.

Выход 30 является выходом регистра 11 текущего адреса, соответствую3 12067

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

Целью изобретения является упро- 1О щение функциональной схемы устройства.

На фиг. 1 изображена блок-схема устройства для решения задачи поиска длиннейшего пути, на фиг. 2 — ариф- 15 метический блок; на фиг. 3 — блок регистрации; на фиг. 4 — блок управления; на фиг. 5 — таблица соответствия входных комбинаций шифратора выходным. 20

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

Блок 1 моделирования топологии 25

1 сети содержит блок 5 памяти первой выходящей ветви, блок 6 памяти первой входящей ветви, блок 7 памяти выходящих ветвей, блок 8 памяти входящих ветвей, регистр 9 текущего узла, регистр 10 конечного узла, регистр 11 текущего адреса, узел 12 сравнения, буферные регистры 13 и 14, триггер

15, элементы ИЛИ 16 и 17 °

Вход 18 элемента ИЛИ 17 и вход

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

Входы 20 и 21 соответственно в ячейки памяти 5 и 6 являются управляю щими топологическими входами считыва- 4 нияа

Входы 22 и 23 являются входами обращения к буферным регистрам 13 и 14. Входы 24 и 25 предназначены для подачи управляющих сигналов записи соответственно в регистры 9 текущего узла и текущего адреса 11.

91 2 щие ему вход 3 1 — вход арифметического блока 3, и вход 32 — вход блока 4 регистрации.

Выход 33 является выходом считываемого адреса арифметического блока 3, соответствующие ему вход 34— вход блока 4 регистрации, и вход 35вход блока 1 формирования топологии.

Вьмоды 36 и 37 — управляющие топологические выходы считывания блока 2 управления.

Выходы 38 и 39 — выходы обращения к буферным регистрам 13 и 14 блока 2 управления.

Выходы,40 и 41 — управляющие топологические выходы записи блока 2 управления.

Входы 42 — 44 — группа управляющих входов топологических меток блока 2 управления.

Вход 45 — вход окончания временного моделирования блока управления

2. Выходы 46 — 56 — группа управляющих выходов блока 2 управления, соответствующая ей группа входов 57—

67 арифметического блока 3.

Выход 68 — счетный выход блока 2 управления, соответствующий ему вход

69 арифметического блока 3.

Выход 70 — информационный выход метки блока управления 2, соответствующий ему вход 71 арифметического блока 3.

Выход 72 — выход свершения узла ,арифметического блока 3, соответствующий ему входу 73 блока 2 управления.

Выходы 74-75 — управляющие выходы

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

76-77 блока 2 управления.

Выходы 78-79 — вьмоды свершения блока 4 регистрации, соответствующие им входы 80-81 блока 2 управления, выходной полюс 82 устройства.

Выходы 83 — 88 — группа управляющих выходов регистрации блока 2 управления, соответствующая ей группа входов 89 — 94 блока 4 регистрации, информационный вход 95 метки блока 4 регистрации.

В блоках памяти первой вьмодящей

5 и первой входящей 6 ветвей по адресу номера узла содержится информация о номере соответствующих ветвей. В последнем информационном разряде блоков памяти первой входящей ветви 6 содержится метка. Число бло1206791 I0!

55

3 ков 5 и 6 памяти равно числу узлов сети.

В блоках памяти выходящих 7 и входящих 8 ветвей информация о номере ветви содержится.по адресу номера предшествующей ветви. Таким образом содержится информация о соответствующем списке ветвей. По адресу номера последней ветви в списке находится информация . о номере узла и метка в последнем информационном разряде, Число блоков 7 и 8 памяти соответствует числу ветвей исследуемой сети.

На фиг. 2 приведена схема арифметического блока 3, который содержит блок 96 памяти длительности, блок.97 памяти длительности, блок 98 памяти ветвей, комбинационный сумматор 99, счетчик 100 длительности, регистр 101 относительной длительности, регистр

102 считываемой длительности, узел

103 сравнения, буферные регистры 104106, коммутаторы 107 и 108, элемент ИЛИ 109.

Блок 96 памяти длительности содержит по адресу номера ветви инфор-! мацию о ее длительности.

Блок 97 памяти длительности содержит пр адресу относительной длительности информацию о номере ветви.

Блок 98 памяти ветвей предназначен для хранения информации,о списке номеров ветвей, имеющих одинаковую относительную длительность, причем в таком списке по номеру первой из данных ветвей содержится информация о метке и в остальных по адресу номера ветвей содержится информация о номере предыдущей ветви в этом списке.

Узлы 12 и 103 сравнения представляют собой многоразрядную схему совпадения.

Регистры 9 — 11, 13, 14, 101, 102 . l04 " 106 представляют собой регист.ры с параллельным приемом информации.

На фиг. 3 приведена схема блока 4 регистрации, который содержит элемент ИЛИ 110, блок 111 памяти свершения ветвей, блок 112 памяти дерева длиннейших путей, блок 113 памяти ветвей длиннейшего пути, триггеры

114 и 115. Блок 11 памяти сверше.ния ветвей по адресу номера ветви содержит информацию о завершении процесса временного моделирования . ветви.

Блок 112 памяти дерева длиннейших путей по адресу номера ветви содержит информацию о ветвях, завершивших последними процесс временного моделирования для данного узла.

Блок 113 памяти ветвей длиннейшего пути по адресу номера ветви содержит информацию о принадлежности ветвей длиннейшего пути.

На фиг. 4 приведена схема блока 2 управления, который содержит триггер 116 прерывания, генератор 117 тактовых импульсов, регистр 118 состояния, шифратор 119.

Регистр 118 состояний представляет собой регистр с параллельным приемом информации, выполненный на двойных триггерах типа "ведущий— ведомый" так, что принимаемая в

20 регистр информация имеет место на его выходах лишь после снятия синхронизирующего сигнала управления от генератора импульсов.

Шифратор 119 преобразует комбина25. ции кодов на его входе в определенные комбинации кодов на выходе в зависимости от состояния регистра 118.

Шифратор выполнен на диодных сборках.

До момента решения задачи на устройстве оператор в блоки памяти первой выходящей ветви 5, первой входящей ветви 6, выходящих ветвей

7 и входящих ветвей 8 блока 1 формирования топологии заносит информацию о топологии сети, а в блоки памяти длительности 96 арифметического блока 3 — информацию о длинах ветвей.

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

Код конечного узла сети заносится в регистр 10 конечного узла, а код начального узла — через элемент

ИЛИ 17 по управляющему сигналу с входа 24 от блока 2 управления с выхода 40 — в регистр 9 текущего ysла. Все остальные регистры, счетчик, триггеры и остальные ячейки памяти устанавливаются в нулевое состояние.

Топологическое моделирование заключается в определении моментов

"свершения" узла и подготовке к временному моделированию ветвей, исходящих из свершившегося узла.

12067

Для установления факта "свершения" узла необходимо, чтобы закончились все входящие в узел ветви. Это определяется опросом всего списка входящ в узел BeTBeN 0 рос Качи- 5 кается с номера ветви, которая закончила процесс временного моделирования и, перебирая все элементы списка, проверяют свершения ветвей. По номеру последней в списке ветви счи- 10 тывают номер узла, в который входят данные ветви. По номеру узла переходят в начало списка и продолжают процедуру опроса до появления номера ветви, с которого 15 начался процесс. Если в результате обнаружится, что все входящие в узел: ветви закончили процесс временного .моделирования своих длительностей, то узел считается "свершенным" и пере- 20 ходит к формированию списка ветвей, выходящих из данного узла, и временному моделированию.

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

96 памяти и содержимого счетчика измерений суммированием определяют величину относительной длительности ,ветви. Максимально возможная длительи кость ветви в сети определяется 2

1, а полная емкость счетчика измен +3т\ рений равна 2 — 1, где m — число 35 ветвей в сети для случая, если сеть представляет собой последовательное соединение всех ветвей одна за другой в цепь. Далее, используя величину относительной длительности ветви 40 в качестве адреса, номер ветви записывается в блок 97 памяти длительности, а в и -й разряд информационного слова ставится метка, свидетельствующая о наличии в процессе вре- 45 менного моделирования ветви с данной относительной длительностью. В блоке . 98 памяти ветвей но адресу номера данной ветви заносится метка в н -м разряде. Данная метка предназначена 50 для определения последней из списка ветви с одинаковой относительной длительностью. Если список состоит. иэ одной ветви, то она будет, естест венно, первой и последней. Если же 55 на последующих этапах моделирования появляются ветви с такой же величиной относительной длительности, то, определив в процессе моделирования по метке наличие ветвей с данной относительной длительностью; выполняется запись новой ветви в ячейки памяти

Запись осуществляется следующим образом.

По адресу величины относительной длительности в блок 97 памятй длительности записывается номер новой ветви и метка в и -м разряде, а в блок 98 памяти ветвей по адресу номера новой ветви записывается номер ветви, которая до этого быпа в данном списке ранее, и метка в и -м .разряде не ставится. Таким образом, организуется связь между элементами с одинаковой относительной длительностью в процессе подготовки к временному моделированию.

Блок 2 управления организует функционирование устройства следующим образом. По адресу номера началь" ного узла и управляющему топологиЧескому сигналу считывания с входа

20 от блока 2 управления с выхода

36 иэ блока памяти первой выходящей ветви 5 поступает информация о номере ветви через элемент ИЛИ 16 и записывается по управляющему сигналу записи с входа 25 от блока 2 управле. ния с выхода 41 регистр 11 текущего адреса, с этого момента с выхода этого регистра на адресных шинах; блоков ? памяти выходящих ветвей находится информация о номере ветви, следовательно, в буферном регистре

13 находится номер следующей ветви в списке. С выхода 30 блока 1 формирования топологии через вход 3 1 арифметического блока 3 информация о номере ветви поступает на адресные шины блока 96 памяти длительности и через элемент ИЛИ 109 блока 98 памяти ветвей — на информационные шины блока 97 памяти длительности. По адресу номера ветви и управляющему сигналу считывания с входа 57 от блока 2 управления с выхода 46 информация о длительности ветви иэ блока 96 памяти длительности поступает на адресные шины блока 97 памяти длительности.

При этом прохождение информации о длительности ветви через буферный регистр 104, сумматор 99 (на второй вход которого в начальный момент поступает "0"), регистр 101 относи1206791

107

7 тельной длительнос ти, коммутатор обеспечивается управляющими сигналами соответственно с входов 65, 63, 66 арифметического блока 3 от блока ность. Далее считывается номер следующей ветви, имеющий такую же относительную длительность, и выполняется анализ "свершения" узла, в который

2 управления соответственно с выходов 54, 52 и 55.

По управляющему сигналу считывания с входа 59 арифметического блока 3 с выхода 48 блока 2 управления иэ блока 97 памяти длительности поступает информация в буферный регистр 105 (в данный момент времени нулевая-информация). Далее по управляющим сигналам записи с входов 58 и 60 арифметического блока 3, с выходов соответственно 47 и 49 блока 2. управления .заносится информация о номере ветви по адресу ее длины в блок 97 памяти длительности, и по адресу номера ветви в блок 98 памяти ветвей с входа 71 арифметического блока 3 из блока 2 управления с информационного выхода метки 70 в последние разряды заносится метка.

Вновь по управляющему сигналу записи с входа 25 в регистр 11 текущего адреса заносится информация иэ буферного регистра 13 о номере следующей ветви в списке. Повторяется вся последовательность сигналов аналогично изложенному.

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

2 управления не поступит сигнал метки с последнего разряда буферного регистра 13.

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

t5

45

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

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

Для этого блок 2 управления через счетный выход 68 в арифметический

1блок 3 на вход 69 подает импульс, который поступает на вход счетчика

100 и далее через коммутатор 107 — .

1 на адресные входы блока 97 памяти длительности. Прохождение информации обеспечивает управляющий сигнал с входа 63 арифметического блока 3 от блока управления соответственно с выхода 52.

Блоком 2 управления осуществляется считывание информации о номере ветви по адресу со счетчика 100 иэ блока 97 памяти длительности в буферный регистр 105 ° Процесс поступления счетных импульсов повторяется до тех пор, пока с выхода 74 последнего информационного разряда буферного регистра 105 арифметического блока 3 через вход 76 в блок 2 управления не поступит сигнал о метке, тем самымопределяется ветвь с минимальной относительной длительностью в данный момент времени.

Через коммутатор 108 по управляющему сигналу записи с входа 67 арифметического блока 3 с выхода 56 от блока 2 управления в регистр 102 считываемой длительности запоминается информация о номере ветви и устанавливается в единичное состояние триггер 116 прерывания в блоке 2 управления, Номер ветви из регистра 102 считываемой длительности находится через элемент ИЛИ 109 на адресных входах блока 98 памяти ветвей и с выхода 33 арифметического блока 3 че9, 12 рез вход 35 блока 1 формирования то пологии ч.ерез элемент ИЛИ 16 на входе регистра 11 текущего адреса, с входа 34 блока 4 регистрации через; элемент ИЛИ 110 на адресных шинах блока 111 памяти свершения ветвей.

Кроме того, эта информация находится на входе схемы 103 сравнения.

По управляющему сигналу записи с входа 25 блока 1 формирования топологии и с входа 89 блока 4 регистрации от блока 2 управления соответственно с выходов 41 и 83 записывает= ся номер ветви в регистр 1 1 текущего адреса и по адресу номера ветви с входа 95 заносится метка в блок 111 памяти свершении ветвей из регистра

102 считываемой длительности.

По адресу номера ветви из регист ра 11 текущего адреса с выхода 30 блока 1 формирования топологии на вход 32 блока 4 регистрации через элемент ИЛИ 110 при условии наличия метки по управляющему сигналу с входа 90 от блока 2 управления с вхо. да 84 устанавливается в,единичное состояние триггер 114.

В блоке формирования топологии по сигналу с входа 23 от блока 2 управ ления с выхода 39 по адресу из регистра 11 текущего адреса заносится ин1формация из блока 8 памяти входящих ветвей в буферный регистр 14 и далее

1 через элемент ИЛИ 16 — в регистр 11 текущего адреса. Таким образом, наличием сигнала с единичного выхода триггера 114 через выход 78 блока 4 регистрации на вход 80 блока 2 управления проверяются на "свершение" все последующие ветви из списка входящих в узел, начиная с ветви с минимальной относительной длитель-. ностью в данный момент.

Процесс повторяется до тех пор, пока с выхода последнего разряда 28 буферного регистра 14 блока 1 формирования топологии через вход 44 в блок 2 управления не поступит сигнал топологической метки, свидетельствую щей о том, что данная ветвь в анали зируемом списке последняя и в буферном регистре. 14 находится информация о номере узла, в котором она заканчивается.

Информация с выхода буферного регистра 14 через элемент ИЛИ 17 о номере узла запоминается в регистре 9 текущего узла,и подается далее на

Я}

По сигналу свершения узла осуществляется узлом 12 сравнения сравнение кодов номеров узлов в регистре 10 конечного узла и регистре 9 текущего узла, так как в последнем хранился номер анализируемого узла. В случае совпадения этих кодов с выхода 29 блока 1 формирования топологии на вход 45 блока 2 управления подается сигнал окончания временного моделирования.

После считывания информации из блока 96 памяти длительности на сумматоре 99 образуется и в регистр 101 относительной длительности заносится

06791 10 адресные входы блока памяти первой входящей ветви 6. Это обеспечивается подачей управляющих сигналов с входов 24 и 21 блока 1 формирования топологии от блока 2 управления соответственно с выходов 40 и 37.

Далее, как и для случая списка выходящих ветвей, блок 2 управления, используя информацию в блоке 6 памя-10 ти первой входящей ветви и в блоке 8 памяти входящих ветвей и регистр 11 текущего адреса, проверяет на свершение список входящих ветвей (для номера узла, находящегося в регистре текущего узла 9). При этом всякий раз аналогично осуществляется блоком 2 управления и блоком 4 регистрации проверка на "свершение" анализируемых ветвей. Кроме того, после

2О поступления через вход 44 в блок управления сигнала топологической метки информация о номере ветви в регистре 11 текущего адреса всякий раэ сравнивается через выход 30 блока 1

25 формирования топологии и вход 31 арифметического блока 3 узлом сравнения 103 с информацией; хранящейся; в регистре 102 считываемой длительности о номере ветви, с которой на3б чался анализ .

Сигнал совпадения кодов в узле

103 сравнения является сигналом свершения узла с выхода 72 арифметического блока 3 в блок 2 управления на вхоц 73. По этому сигналу и управляю. щему сигналу с выхода 85 блока 2 управления на вход 91 блока 4 регистрации заносится метка с входа 95 в ячейки памяти дерева длиннейших пу4О 1тей 112, так как именно данная ветвь окончила процесс моделирования последней среди всех ветвей, оканчивающихся в данном узле. .I

1206791

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

100. Число младших разрядов счетчика соответствует величине максимальной длины среди всех длин ветвей.

По адресу относительной длительности 4 из блока 97 памяти длительности с выхода последнего разряда буферного регистра 105 с выхода 74 арифметического блока 3 на вход 76 блока 2 управления считывается метг ка, в остальных разрядах будет ин--. ,формация о номере ветви, занесенной по этому адресу ранее при рассмотре. нии узла 1. Блок 2 управления сигна. лом с выхода 49 на вход 60 арифметического блока 3 по адресу номера ветви из регистра 11 текущего адреса записывает информацию о номере соответствующей ветви в блок 98,па, :мяти ветвей. Далее блоком 2 управления в блок 97 памяти длительности по адресу относительной длительности 4 заносится информация о номере следующей ветви.

Повторяется описанный анализ на

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

Так повторяется до тех пор, пока в блок 2 управления с полюса 77 не поступит сигнал. метки о том, что ветвь, по адресу которой в буферном регистре 106 проводилось считывание информации из блока 98 памяти ветвей, является последней в списке ветвей с равной относительной длительностью. В этом случае считанная в регистр 102 считываемой длительности информация является не номером очередной ветви, а лишь меткой, по которой и определяется конец спис ка блоком 2 управления. Затем триггер 116 прерывания ставится в нулевое состояние, а по адресу величины относительной длительности в счетчи.ке 100 в памяти длительности 97 обнуляется метка.

Число импульсов, накопленное к моменту окончания моделирования в счетчике 100, будет соответствовать величине длиннейшего пути в сети.

3S

40 входящей в данный узел и принадлежа-. щей дереву длиннейших путей.

Процесс определенияструктуры длин- нейшего пути продолжается до прихода в

4 начальный узелсети ипоявления навходе 42блока 2управления сединичного выхода 26трггера 15нулевого сигнала, так каклншь уэтого узлане имеетсясписка входящих в него ветвей.

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

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

10 IS

Для определения ветвей, принадлежащих длиннейшему пути, т.е. определения его структуры, по номеру конечного узла сети в регистре 9 текущего узла из блока 6 памяти первой входящей ветви и блока 8 памяти входящих ветвей аналогично вызывается список свершившихся ветвей и находится по сигналу с входа 92 блока 4 регистрации от блока 2 управления с выхода 86 ветвь, свершившаяся в данном узле последней (в данный момент — в конечном узле). Об этом будет служить сигнал с единичного выхода 79 триггера 115. блока 4 регистрации на вход 81 блока 2 управления, по сигналу с входа 93 блока 4 регистрации от блока 2 управления с выхода 87 заносится сигнал метки с полюса 95 в ячейки памяти ветвей длиннейшего пути 113.

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

Процесс будет продолжаться до появления сигнала метки с выхода 27 блока 1 формирования топологии на вход 43 блока 2 управления о том, что данная ветвь из списка выходящих из анализируемого узла последняя, следовательно, в регистре 11 текущего адреса — информация о .номе- . ре ее начального узла.

Полученный номер начального узла ветви заносится в регистр 9 текущего узла, и организуется поиск ветви, 13 12 того регистров, блоков памяти, триггера элементов ИЛИ, о т л и ч а ю— щ е е с я тем, что, с целью упрощения функциональной схемы устройства, в него введены арифметический блок, блок, регистрации и блок управления, содержащий триггер, выход которого соединен с первым входом шифратора, первый и второй выходы которого подключены к соответствующим входам триггера, генератор тактовых импульсов, первый и второй выходы которого подключены к входам синхронизации шифратора и регистра, информационный вход которого соединен с третьим выходом шифратора, а в блоке моделиро1

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

5

55 метического блока, информационный вход которого подключен к десятому выходу шифратора блока управления, одиннадцатый выход которого подключен к входу управления записью арифметического блока и входу управления за;писью блока регистрации, информационная группа входов шифратора блока управления соединена с группой выхо1 дов арифметического блока, второй информационный вход которого объединен с первым информационным входом блока регистрации и подключен .к выходу третьего регистра блока модели.рования топологии сети, выход арифметического блока подключен к второму информационному входу блока регистрации и к входам третьей группы второго элемента ИЛИ блока моделирования топологии сети, группа управляющих входов блока регистрации соединена с второй, группой выходов шифратора блока управления, седьмой и восьмой входы которого подключены к выходам блока регистрации, причем арифметический блок выполнен в виде первого и второго коммутаторов, узла сравнения, первого, второго, третъего, четвертого и пятого регистров, счетчика, сумматора, первого, второго и третьего блоков памяти элементов ИЛИ, выход которого подключен к первому входу первого блока памяти, управляющий вход записи которого соединен с управляющими входами. записи второго и третьего блоков памяти и подключен к входу управления записью арифметического блока, выход первого блока памяти подключен к входу первого регистра, выходы всех разрядов которого, кроме последнего, соединены с первым информационным входом первого коммутатора, второй информационный вход которого подключен ко всем разрядам, кроме последнего, второго регистра, вход которого соединен с выходом второго блока памяти, выход первого коммутатора соединен с информационным входом третьего регистра, выход которого соединен с первыми входами узла сравнения и элемента ИЛИ, второй вход узла сравнения соединен с вторым входом элемента ИЛИ, с первыми входами второго и третьего блоков памяти и подключен к второму информационному входу арифметического блока, выход третье15 12 ro блока памяти соединен с информа- . ционным входом четвертого регистра, выход которого соединен с первым входом сумматора, второй вход которого соединен с первым информационным входом второго коммутатора и подключен к выходу счетчика, счетный вход которого соединен с первым информационным входом арифметического блока, выход сумматора подключен к информационному входу пятого регистра, выход которого соединен с вторым информационным входом второго коммутатора, выход которого соединен с вторым входом второго блока памяти, . выходы всех разрядов, кроме послед. его, второго регистра соединены с

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

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

06791 16 третьего регистра подключен к инфор- мационному выходу арифметического блока.

2. Устройство по п. 1,. о т л и— ч а ю щ е е с я тем, что блок регистрации выполнен в виде первого и второго триггеров, первого, второго и третье.

ro блоков памяти н элемента ИЛИ,причем выход элемента ИЛИ подключен к первому входу первого блока памяти, выход кото:рого соединен с входом первого триггера, входы управления записью всех блоков памяти объединены и подключены к входу управления записью блока регистрации, 15 первый вход. элемента ИЛИ соединен с адресными входами второго и третьего блоков памяти и подключен к первому информационному входу блока регистрации, второй вход элемента ИЛИ подклю20 чен к второму информационному входу блока регистрации, выход второго блока памяти соединен с входом второго триггера, второй вход первого блока памяти, первый и второй входы второ25 го и третьего блоков памяти подключены к группе входов блока регистрации, выходы первого и второго триггеров соединены с первым и вторым выходами блока регистрации.

1206791

68

7$ N89 67 фиг. Z

1206791

1206791

l /ме

omaeee хеолме ломеа

Вцядте юмвт

ООООО1 ааааа о

0ООО1О

000001 ооа 011

OOOOlO

OOOlOO

ooool1

000100

N01tu

000701

000710

001ао l

000111

001000

001001 ео1о10

001077

OOrol0

001100

0Ol0n

OOl Ol

001700 ая101

001107 юа/ l f

00100

ЯЕ1ОО

01аоо

001777

1 7

Ю и юап

010000

oiow

010001

OlOOlO опоя

001077

010011

010101

0lo 100

ОО1ООО ооооо1

010101

010110

010117 оп за

n uo

011000

411010

01700

011010 тити

0110I1

only

01 0111

077101 отто

0770о0

077770

Фие. Х

Заказ 8714/50 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 г

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель А. Колчин

Редактор П. Коссей Техред З.Палий Корректор Л. Патай