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

Союз Советских Социалистицеских РеспубликОП ИСАНИЕИЗОБРЕТЕН ИЯИ аВтОРСКОМ СВИДЕтЕЛЬСтеа(45) Дата опубликования описания 26,04.77(51) М. Кл. 506 Р 15/20 Государственный комитет Совета Министров СССР по делам изобретений и открытий(71) Заявитель Московский институт инженеров гражданской авиации(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КОДА КРАТЧАЙШЕГО ПУТИ В ЦИФРОВОЙ СЕТИ СВЯЗИ Изобретение относится к проектированиюустройств обработки данных в вычислительной технике.Известны устройства для определениякратчайших путей между узлами сети, содержащие элементы НЕ, ИЛИ, схему. упорядоченной выборки номеров ветвей кратчайшего пути, диоды, цепи задержки 11, 2.Ввиду сравнительно высокой аппаратурнойизбыточности быстродействие известных ана Ологов является низким, что делает затруднительным их использование в цифровых сетяхсвЯзи, требующих высоких темпов обменаинформацией (данными) .Наиболее близким по сущности техническим решением задачи является устройстводля поиска путей направленного графа 31,содержащее генератор, первую группу элементов И, выходной регистр, первая группавходов которого соединена с выходами буферного регистра,Такое устройство имеет значительнуюаппаратурную избыточность, поскольку дополнительно содержит управляемый и программирующий переключатели, столбец буферных 25 2регистров, столбец сдвоенных входных ключей задания начального узла искомых путей и строку сдвоенных выходных ключей задания начального узла искомых путей и строку сдвоенных выходных ключей задания конечного узла искомых путей.Целью изобретения является повышение быстродействия устройства формирования кратчайших путей в сети связи при незначительной аппаратурной сложности устройства.Это достигается тем, что в устройство введены счетчик, две группы элементов И, элемент ИЛИ, узел опроса, два регистра кода адреса, причем выход генератора соединен со входом счетчика, выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, управляющий вход которого через элемент ИЛИ соединен с выходами элементов И первой группы, вторые входы которых соединены с выходами элементов И второй группы, входы которых соединены с выходами элементов И третьей группы, входы которых соединены с выходами регистров кода адреса, информационные входы которых547770 45Использование в качестве исходной информации для процедуры формирования кодакратчайшего пути только кодов адресов узлаотправителя и узла - получателя приводит 50к сокращению объема памяти устройства иповышению скорости его работы,55Устройство для формирования кода крач- чайшего пути в цифровой сети связи, содеял жащее генератор, первую группу элементов И, выходной регистр, первая группа входов 60которого соединена с выходами буферного регистра, о т л и ч а ю щ е е с я тем,соединены со входами устройства, Управляющий вход второго регистра кода адреса соединен с выходом генератора, вход которого соединен с выходом элемента ИЛИ, выход узла опроса - со входом выходного 5 регистра, вторая группа входов которого соединена с выходами первого регистра ко даадреса, а выход - с выходом устройства.Использование исходной информации в цифровой форме в виде кодов адресов узлов сети 1 О позволяет повысить быстродействие устройства, существенно сократить объем его программирующей части (запоминающие регистры).На чертеже изображена блок-схема предлагаемого устройства, 15Оно содержит генератор 1 (тактовых импульсов), счетчик 2 (импульсов), первой, второй и третьей группы элементы И 3-5, соответственно, элемент 6 ИЛИ, узел 7 опроса, первый и второй регистры 8, 9 кода адреса, соответственно, буферный регистр 10, выходной регистр 11.Работа устройства происходит следующим образом.Исходное состояние регистров 10, 11, 25 счетчика 2 тактовых импульсов, узла 7 опроса является нулевым, а по входу устройства в регистры 8 и 9 произведена запись кодов адресов узла-отправителя и узла-получателя, соответственно.30Тактовым импульсом с выхода генератора 1 осуществляется сдвиг содержимого регистра 9 на один разряд вправо, в результате чего производится запись разряда кода узла-получателя в регистр 10, Одновременно количество тактов фиксируется счетчиком 2 тактовых импульсов и узлом 7 опроса. Элементы И третьей группы 5 осуществляют поразрядное сравнение символов кодов регистров 8 и 9 на равенство, а элементы 40 И второй группы 4 фиксируют одновременное равенство символов всех сравниваемых разрядов. Если одновременное равенство ра рядов наступает после первого сдвига регистра 9, то наличие "единичного потенциала на выходе первого элемента И второй группы 4 позволяет прохождение тактового импульса, появившегося на первом выходе счетчика 2 импульсов, через соотвечствующий элемент И первой группы 3 на вход элемента 6 ИЛИ.При несовпадении производится следующий сдвиг содержимого регистра 9, после чего, если вышеописанная ситуация совпадения наблюдается, то на вход элемента 6 ИЛИ поступает тактовый импульс со второго вьиода счетчика 2 импульсов, прошедший через соответствующий элемент И первой группы 3 и так как вплоть до того момента, когда после ( 11 - 1 )-ого сдвига(и -число разрядов кода адреса узла) одновременное совпадение всех сравниваемых разрядов не произошло, а в результате и -госдвига тактовый импульс с последнего выхода счетчика 2 импульсов поступает непосредственно на вход элемента 6 ИЛИ.Каждый из тактовых импульсов, поступивших на вход элемента 6 ИЛИ и прошедших на его выход, выполняет следующиефункции: останавливает генератор 1 тактовых импульсов, запускает узел 7 опроса,число тактов работы которого определяетсячислом тактовых импульсов, записанных внего со счетчика 2, увеличенным на значение и,Узел 7 опроса осуществляет считываниесодержимого регистров 8 и 10 в регистр11 и выдачу содержимого, в результате чегона выходе устройства появляется последовательность символов кода кратчайшего путииз узла-отправителя в узел-получатель.Последним импульсом с выхода узла 7опроса осуществляется возврат всего устройсства в исходное состояние.Таким образом, если одновременного совпадения всех сравниваемых разрядов кодов,записанных в регистрах 8 и 9, не наблюдается, то производится серия последовательныхсдвигов вправо содержимого регистра 9вплоть до того момента, когда совпадениенаступает, после чего работа устройства поформированию кода кратчайшего пути прекращается, а узел 7 опроса производит считывание содержимого регистров 8 и 10 врегистр11 и выдачу содержимого регистра 11 ввиде последовательного кода кратчайшегопути на выход устройства.Условие равенства сравниваемых разрядовкодов регистров 8 и 9 является необходимым и достаточным для формирования кодакратчайшего пути в цифровой сети связи,узлы которой имеют адреса, представленныев виде кодовых последовательностей длины ТВ формула изобретения547770 Тираж 818 ЦНИИПИ Заказ 877/101 Подписное Филиал ППП Патент", г. Ужгород, ул. Проектная, 4 5что, с целью повышения быстродействия устройства, в него введены счетчик, две группы элементов И, элемент ИЛИ, узел опроса, два регистра кода адреса, причем выход генератора соединен с входом счетчика, выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, управляющий вход которого через элемент ИЛИ соединен с выходами элементов И первой группы, 10 вторые входы которых соединены с выходами элементов И второй группы, входы которых соединены с выходами элементов И третьей группы, входы которых соединены с выходами регистров кода адреса, информа ционные входы которых соединены со входом устройства, управляющий вход второго регистра кода адреса соединен с выходом генератора, вход которого соединен с выходомэлемента ИЛИ, выход узла опроса соединенсо входом выходного регистра, вторая группа входов которого соединена с выходамипервого регистра кода адреса, а выход - свыходом устройства. Источники информации, принятые вэ внимание при экспертизе; 1, Авторское свидетельствэ СССР% 238902, М.Кл. О 06 О 7/48, 10.03.69 г. 2. Авторское свидетельство СССР288422, М.Кл. б 06 Ь 7/48, 03.12,70 г. 3. Авторское свидетельство СССР М 271907, М,Кл, Ь 06 Ь 7/48, 26.05.70