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

.80, 1206791 1)4 МИТЕТ СОСНИЯ И ОТНРЬГМ ТВЕННЫЯ ИЗОБРЕТЕ Е ОБРЕТВЧРВТВЪСТВУ(71) Институт проблем моделированияв энергетике АН УССР(56) Авторское свидетельство СССР(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИПОИСКА ДЛИННЕЙШЕГО ПУТИ(57) Изобретение относится к областицифровой вычислительной техники, вчастности к устройствам обработкиинформации специального назначения,с точки зрения вычислитройства. Оно может быт,при построении специали вычислительных устройстрования сетевых задач оуправления. Изобретениесократить аппаратурные решении задачи поискапути с помощью аппаратнЭто достигается введениравления, выполненного тора, регистра состояра тактовых импульсов иарифметического блока ирацииУстройство реалиное и пространственноеисследуемого графа с поритмом поиска длиннейшеп. ф-лы, 5 ил. Ушаков К АВТОРСКОМУ ельного усть использованзированных в для модели перативногопозволяет затраты при длиннейшегоых средств.ем блока упв виде шифра ния, генератотриггера, блока регисзует времен" моделировани шаговым алго го пути. 1 з,цахес ачба Виолете Юлю ООООО 7 ааааа о ООООта оооо ат ОООО 77 оаоото аоотао оооотт ооотоо йюююо оао тот оаатто еооото ооюоо 7 ооаттт оотою оотаат юююююото аототт аат ото ооттоо оаюатт оою от аоютоа алтот оаттот юю ют аотоо юююооооюооо аотттт 7 7 йуЮ Оюааоа аюию отааа 7 отоото оюоюют оотатт ото отт ототот ототоо оатооо ототот ооооат Оюатта ото ттт еюююо юю ио оттооо итата оттоо Фюдюю аттото оют ото оттают оттттто ототтт отттот оттюто оттооо отттто Заказ 8714/50Тираж 673 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5 г35 Вьпсоды 26 - 28 образуют группу управляющих выходов топологических меток и берутся соответственно с еди ничного выхода триггера 15 и последних разрядов буферных регистров 13 и 14,Выход 29 узла 12 сравнения является выходом окончания временного моделирования.Выход 30 является выходом регистра 11 текущего адреса, соответствую 12067Изобретение относится к цифровой вычислительной технике, в частности к устройствам обработки информации специального назначения с точки зре" ния вычислительного устройства, и может быть использовано при построе" нии специализированных вычислительных устройств для моделирования сете. вых задач оперативного управления.Целью изобретения является упро О щение функциональной схемы устройства.На фиг. 1 изображена блок-схема устройства для решения задачи поиска длиннейшего пути; на фиг. 2 - ариф метический блок; на фиг. 3 - блок регистрации; наффиг. 4 - блок управления; на фиг, 5 - таблица соответствия входных комбинаций шифратора выходным. 20Устройство содержит блок 1 моделирования топологии сети, блок 2 управления, арифметический блок 3 и блок 4 регистрации.Блок 1 моделирования топологии 25 сети содержит блок 5 памяти первой выходящей ветви, блок 6 памяти первой входящей ветви, блок 7 памяти выходящих ветвей, блок 8 памяти входящих ветвей, регистр 9 текущего узла, регистр 10 конечного узла, регистр 11 текущего адреса, узел 12 сравнения, буферные регистры 13 и 14, триггер 15, элементы ИЛИ 16 и 17.Вход 18 элемента ИЛИ 17 и вход 19 регистра 10 конечного узла являются входными полюсами устройства,Входы 20 и 21 соответственно в ячейки памяти 5 и 6 являются управляю щими топологическими входами считыва нияаВходы 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 - выход свершения узла 1 арифметического блока 3, соответствующий ему входу 73 блока 2 управления.Выходы 74-75 - управляющие выходы 1операционных меток арифметического блока 3, соответствующие им входы 76-77 блока 2 управления.Вьпсоды 78-79 - вьмоды свершения блока 4 регистрации, соответствующие им входы 80-81 блока 2 управления, выходной полюс 82 устройства.1Выходы 83 - 88 - группа управляющих выходов регистрации блока 2 управления, соответствующая ей группа входов 89 - 94 блока 4 регистрации, информационный вход 95 метки блока 4 регистрации. В блоках памяти первой вьмодящей 5 и первой входящей 6 ветвей по адресу номера узла содержится информация о номере соответствующих ветвей. В последнем информационном разряде блоков памяти первой входящей ветви 6 содержится метка. Число бло1206791 О 30 35 40 45 50 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, . 104 " 106 представляют собой регистры с параллельным приемом информации.На фиг. 3 приведена схема блока 4 регистрации, который содержит элемент ИЛИ 110, блок 111 памяти свер.шения ветвей, блок 112 памяти дерева длиннейших путей, блок 113 памяти ветвей длиннейшего пути, триггеры 114 и 115. Блок11 памяти сверше.ния ветвей по адресу номера ветви содержит информацию о завершении процесса временного моделирования ветви. Блок 112 памяти дерева длиннейших путей по адресу номера ветви содержит информацию о ветвях, завершивших последними процесс временного модели. рования для данного узла.Блок 113 памяти ветвей длиннейшего пути по адресу номера ветви содержит информацию о принадлежности ветвей длиннейшего пути. На фиг. 4 приведена схема блока 2 управления, который содержит триггер 116 прерывания, генератор 117 тактовых импульсов, регистр 118 состояния, шифратор 119.Регистр 118 состояний представляет собой регистр с параллельным приемом информации, выполненный на двойных триггерах типа "ведущий - ведомый" так, что принимаемая в 20 регистр информация имеет местона его выходах лишь после снятия синхронизирующего сигнала управления от генератора импульсов.Шифратор 119 преобразует комбина. ции кодов на его входе в определенные комбинации кодов на выходе в зависимости от состояния регистра 118.Шифратор выполнен на диодных сборках. До момента решения задачи на устройстве оператор в блоки памятипервой вьпсодящей ветви 5, первойвходящей ветви 6, выходящих ветвей7 и входящих ветвей 8 блока 1 формирования топологии заносит информациюо топологии сети, а в блоки памятидлительности 96 арифметического блока 3 - информацию о длинах ветвей.При этом выбор первых выходящейи входящей ветвей для каждого узла,а также формирование списков выходящих и входящих ветвей осуществляется оператором произвольно,Код конечного узла сети заносится в регистр 10 конечного узла, акод начального узла - через элементИЛИ 17 по управляющему сигналу свхода 24 от блока 2 управления с выхода 40 - в регистр 9 текущего узла. Все остальные регистры, счетчик,триггеры и остальные ячейки памятиустанавливаются в нулевое состояние. Топологическое моделированиезаключается в определении моментов"свершения" узла и подготовке квременному моделированию ветвей,исходящих из свершившегося узла.120675Для установления факта "свершения" узла необходимо, чтобы закончились все входящие в узел ветви, Это определяется опросом всего списка входящих в узел ветвей Опрос Качи кается с номера ветви, которая закончила процесс временного моделирования и, перебирая все элементы списка, проверяют свершения ветвей. По номеру последней в списке ветви счи О тывают номер узла, в который входят данные ветви. По номеру узла переходят в начало списка и продолжают процедуру опроса до появления номера ветви, с которого 15 начался процесс. Если в результате обнаружится, что все входящиев узел: ветви закончили процесс временного .моделирования своих длительностей, то узел считается "свершенным" и пере ходит к формированию списка ветвей, выходящих из данного узла, и временному моделированию.Подготовка к временному моделиро 25 ванию длительностей ветвей заключается в установлении связей между моделируемыми ветвями. Для этого по величине длительности ветви из блока 96 памяти и содержимого счетчика измерений суммированием определяют величину относительной длительности ,ветви, Максимально возможная длительи кость ветви в сети определяется 21, а полная емкость счетчика иэмеВ 13 трений равна 2 - 1, где в - число 35 ветвей в сети для случая, если сеть представляет собой последовательное соединение всех ветвей одна за другой в цепь. Далее, используя величину относительной длительности ветви 40 в качестве адреса, номер ветви записывается в блок 97 памяти длительности, а в й -й разряд информационного слова ставится метка, свидетельствующая о наличии в процессе вре менного моделирования ветви с данной относительной длительностью. В блоке . 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 относити, коммутаторобеспечивается управляющими сигнала.ми соответственно с входов 65, 63,66 арифметического блока 3 от блока ность. Далее считывается номер следующей ветви, имеющий такую же относительную длительность, и выполняетсяанализ "свершения" узла, в который2 управления соответственно с выходов 54, 52 и 55.По управляющему сигналу считывания с входа 59 арифметического блока Э с выхода 48 блока 2 управления иэ блока 97 памяти длительности поступает информация в буферный регистр 105 (в данный момент времени нулевая-информация). Далее по управляющим сигналам,записи с входов 58 и 60 арифметического блока 3, с выходов соответственно 47 и 49 блока 2. управления .заносится информация о номере ветви по адресу ее длины в блок 97 памяти длительности, и по адресу номера ветви в блок 98 памяти ветвей с входа 71 арифметического блока 3 из блока 2 управления с информационного выхода метки 70 в последние разряды заносится метка.Вновь по управляющему сигналу записи с входа 25 в регистр 11 текущего адреса заносится информация иэ буферного регистра 13 о номере следующей ветви в списке. Повторяется вся последовательность сигналов аналогичноизложенному.Процесс повторяется до тех пор, пока не обратится к ветви, последней в списке, связанном с данным узлом, и с выхода 27 блока 1 формирования топологии через вход 43 в блок 2 управления не поступит сигнал метки с последнего разряда буферного регистра 13.На этом заканчивается процесс подготовки к временному моделированию ветвей, выходящих из узла. В данном случае из начального узла сети. О 15 20 25тЗО 35 40 55 В процессе временного моделирования после каждого импульса, поданного в счетчик измерения, проводят считывание содержимого из блока 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текущего узла,и подается далее на45 50 55 По сигналу свершения узла осуществляется узлом 12 сравнения сравнение кодов номеров узлов в регистре 10 конечного узла и регистре 9 текущего узла, так как в последнем хранился номер анализируемого узла. В случае совпадения этих кодов с выхода 29 блока 1 Формирования топологии на вход 45 блока 2 управления подается сигнал окончания временного моделирования.После считывания информации из блока 96 памяти длительности на сумматоре 99 образуется и в регистр 101 относительной длительности заносится 06791 10адресные входы блока памяти первойвходящей ветви 6, Это обеспечиваетсяподачей управляющих сигналов с входов 24 и 21 блока 1 формирования топологии от блока 2 управления соответ.ственно с выходов 40 и 37.Далее, как и для случая спискавыходящих ветвей, блок 2 управления,используя информацию в блоке 6 памя-10 ти первой входящей ветви и в блоке 8памяти входящих ветвей и регистр 11текущего адреса, проверяет на сверше.ние список входящих ветвей (для номера узла, находящегося в регистре 15 текущего узла 9). При этом всякийраз аналогично осуществляется блоком 2 управления и блоком 4 регистрации проверка на "свершение" анализируемых ветвей. Кроме того, после 20 поступления через вход 44 в блок управления сигнала топологической метки информация о номере ветви в регистре 11 текущего адреса всякий раэсравнивается через выход 30 блока 1 25 формирования топологии и вход 31арифметического блока 3 узлом сравнения 103 с информацией; хранящейся;в регистре 102 считываемой длительности о номере ветви, с которой наЗ 0 чался анализ.Сигнал совпадения кодов в узле103 сравнения является сигналом свершения узла с выхода 72 арифметическо.го блока 3 в блок 2 управления навход 73. По этому сигналу и управляю.щему сигналу с выхода 85 блока 2 управления на вход 91 блока 4 регистра.ции заносится метка с входа 95 вячейки памяти дерева длиннейших пу 40 1 тей 112, так как именно данная ветвь окончила прОцесс моделирования последней среди всех ветвей, оканчивающихся в данном узле. .относительная длительность, равная сумме длины считываемой ветви и содержимого младших разрядов счетчика 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, будет соответствовать величине длиннейшего пути в сети.25 30 блока 1 формирования топологии на вход 43 блока 2 управления о том, что данная ветвь из списка выходящих из анализируемого узла последняя, следовательно, в регистре 11 текущего адреса - информация о номе".ре ее начального узла.Полученный номер начального узлаветви заносится в регистр 9 текущего узла, и организуется поиск ветви,40входящей в данный узел и принадлежа-.щей дереву длиннейших путей.Процесс определенияструктуры длин-нейшего пути продолжается до прихода в ч 45 начальный узелсети ипоявления навходе 42 блока 2 управления сединичноговыхода 26 трггера 15 нулевого сигнала,так каклншь уэтого уэлане имеетсясписка входящих в него ветвей.50 ,Ф о р м у л а изобретения1. Устройство для решения задачипоиска длиннейшего пути, содержащееблок моделирования топологии сети,выполненный в виде первого регистра, 55 выход которого подключен к первомувходу узла сравнения, второй входкоторого соединен с выходом второгоорегистра, третьего, четвертого и пя 5 10 15 20 Для определения ветвей, принадлежащих длиннейшему пути, т.е. определения его структуры, по номеру конечного узла сети в регистре 9 текущего узла из блока 6 памяти первой входящей ветви и блока 8 памяти входящих ветвей аналогично вызывается список свершившихся ветвей и находится по сигналу с входа 92 блока 4 регистрации от блока 2 управления с выхода 86 ветвь, свершившаяся в данном узле последней (в данный момент - в конечном узле). Об этом будет служить сигнал с единичного выхода 79 триггера 115. блока 4 ре" гистрации на вход 81 блока 2 управления, по сигналу с входа 93 блока 4регистрации от блока 2 управления с выхода 87 заносится сигнал метки с полюса 95 в ячейки памяти ветвейдлиннейшего пути 113,Номера ветвей будут содержаться в регистре 11 текущего адреса. По адресу номера данной ветви из блока 7 памяти выходящих ветвей считывается в регистр .11 текущего адреса номер следующей за ней ветви, из списка выходящих из данного узла.Процесс будет продолжаться до появления сигнала метки с выхода 2713 12 того регистров, блоков памяти, триггера элементов ИЛИ, о т л и ч а ю - щ е е с я тем, что, с целью упрощения функциональной схемы устройства, в него введены арифметический блок, блок, регистрации и блок управления, содержащий триггер, выход которого соединен с первым входом шифратора, первый и второй выходы которого подключены к соответствующим входам триггера, генератор тактовых импульсов, первый и второй выходы которого подключены к входам синхронизации шифратора и регистра, информационный вход которого соединен с третьим выходом шифратора, а в блоке моделирования топологии сети выход первого элемента ИЛИ подключен к информационному входу первого регистра, выход которого подключен к информационному- входу первого блока памяти, вьпсод которого соединен с первым входом второго элемента ИЛИ, выходы которого подключены к информационномувходу третьего регистра, выход которого подключен к входам второго и третьего блоков памяти, выходы которых соединены соответственно с информационными входами четвертого и пятого регистров, с первого по (тт -1)-й разрядные выходы четвертого и пятого регистров соединены соответственно с входами первой и второй групп второго элемента ИЛИ и подключены к входам первой и второй групп первого элемента ИЛИ, второй вход второго элемента ИЛИ соединен с первым выходом четвертого блока памяти, инфор. мационный вход которого соединен с выходом первого регистра, второй выход четвертого блока памяти соединен с входом триггера, причем входы синхронизации первого, третьего, четвер. того и пятого регистров блока формирования топологии сети, входы разрешения, записи первого и четвертого блоков памяти блока моделирования, топологии сети соединены соответственно с четвертым, пятым, шестью,лседьмым, восьмью и девятым выходами шифратора блока управления, третий, четвертый, пятый и шестой входы кото. рого подключены соответственно к выходам узла сравнения, трйггера, тт -м разрядным выходам четвертого и пятого регистров блока моделирования топологии сети, группа выходов шифратора соединена с группой входов ариф.14 0679,1 40 4550 55 5 ТО Т 5 20 25 30 35 метического блока, информационныйвход которого подключен к десятомувыходу шифратора блока управления,одиннадцатый выход которого подключенк входу управления записью арифметического блока и входу управления за,писью блока регистрации, информационная группа входов шифратора блокауправления соединена с группой выхо 1дов арифметического блока, второйинформационный вход которого объединен с первым информационным входомблока регистрации и подключен к выходу третьего регистра блока модели.рования топологии сети, выход арифметического блока подключен к второму информационному входу блока регистрации и к входам третьей группывторого элемента ИЛИ блока моделирования топологии сети, группа управляющих входов блока регистрации соединена с второй, группой выходов шифратора блока управления, седьмой ивосьмой входы которого подключены квыходам блока регистрации, причемарифметический блок выполнен в видепервого и второго коммутаторов, узла сравнения, первого, второго,третъего, четвертого и пятого регистров, счетчика, сумматора, первого,второго и третьего блоков памятиэлементов ИЛИ, выход которого подключен к первому входу первого блока памяти, управляющий вход записикоторого соединен с управляющимивходами. записи второго и третьегоблоков памяти и подключен к входу управления записью арифметического блока, выход первого блока памятиподключен к входу первого регистра,выходы всех разрядов которого, кроме последнего, соединены с первыминформационным входом первого коммутатора, второй информационныйвход которого подключен ко всемразрядам, кроме последнего, второгорегистра, вход которого соединен свыходом второго блока памяти, выходпервого коммутатора соединен с информационным входом третьего регистра, выход которого соединен с первыми входами узла сравнения и элемента ИЛИ, второй вход узла сравнения соединен с вторым входом элемента ИЛИ, с первыми входами второго и третьего блоков памяти и подключен к второму информационному входу арифметического блока, выход третье15 12 го блока памяти соединен с информа- . ционным входом четвертого регистра, выход которого соединен с первым входом сумматора, второй вход которого соединен с первым информационным входом второго коммутатора и подключен к выходу счетчика, счетный вход которого соединен с первым информационным входом арифметического блока, выход сумматора подключен к информационному входу пятого регистра, выход которого соединен с вторым информационным входом второго коммутатора, выход которого соединен с вторым входом второго блока памяти, . выходы всех разрядов, кроме послед" . Мего, второго регистра соединены с ;вторым входом первого блока памяти, управляющие входы первого и второго. коммутаторов, третьего, четвертого и пятого регистров, входы выборки адреса первого, второго и третьего бло,ков памятны входы разрешения записи "первого и второго блоков памяти подключены к группе входов арифметичес.кого. блока, выходы последних разрядов первого и второго регистров и выход узла сравнения подключены к группе выходов арифметического блока, выход 06791 16третьего регистра подключен к инфор-мационному выходу арифметическогоблока.2. Устройство по п. 1,.о т л и -ч а ю щ е е с я тем, что блок регист.рации выполнен в виде первого и второго триггеров, первого, второго и третьего блоков памяти н элемента ИЛИ,причемвыход элемента ИЛИ подключен к первому 10 входу первого блока памяти, выход которого соединен с входом первого триггера,входы управления записью всех блоковпамяти объединены и подключены к входууправления записью блока регистрации, 15 первый вход. элемента ИЛИ соединен садресными входами второго и третьегоблоков памяти и подключен к первомуинформационному входу блока регистрации, второй вход элемента ИЛИ подклю чен к второму информационному входублока регистрации, выход второго бло.ка памяти соединен с входом второготриггера, второй вход первого блокапамяти, первый и второй входы второ го и третьего блоков памяти подключены к группе входов блока регистрации, выходы первого и второго триггеров соединены с первым и вторым вы.ходами блока регистрации.