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

 

Союз Советских

Социалистических

Республик

ОП ИСАЫИЕ

ИЗОБРЕТЕЫ ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (11) 547770 (61) Дополнительное к авт. свид-ву— (22) Заявлено 28.04.75 (21) 2129036/24 с присоединением заявки № (23) Приоритет (43) Опубликовано 25.02.77 Бюллетень № 7 (45) Дата опубликования описания 26.04.77 (51) М. Кл.

С,06 F 15/20

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681- З (088.8) (72) Авторы изобретения

В. И. Васильев, В. М. Коновалов и Л. Я. Заманский (71) Заявитель Московский институт инженеров гражданской авиации (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КОДА КРАТЧАЙШЕГО

ПУТИ В ЦИФРОВОЙ СЕТИ СВЯЗИ

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

Известны устройства для определения кратчайших путей между узлами сети, содержащие элементы НЕ, ИЛИ, схему. упорядоченной выборки номеров ветвей кратчайшего пути, диоды, цепи задержки flj, (2).

Ввиду сравнительно высокой аппаратурной избыточности быстродействие известных ана- 1О логов является низким, что делает затруднительным их использование в цифровых сетях свЯзи, требующих высоких темпов обмена информацией (данными) .

Наиболее близким по сущности техническим решением задачи является устройство для поиска путей направленного графа (3), содержащее генератор, первую группу элементов И, выходной регистр, первая группа входов которого соединена с выходами буферного регистра.

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

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

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

Это достигается тем, что в устройство введены счетчик, две группы элементов И, элемент ИЛИ, узел опроса, два регистра кода адреса, причем выход генератора соединен со входом счетчика, выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, управляющий вход которого через элемент ИЛИ соединен с выходами элементов

И первой группы, вторые входы которых соединены с выходами элементов И второй группы, входы которых соединены с выходами элементов И третьей группы, входы которых соединены с выходами регистров кода адреса, информационные входы которых

547770

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

50 к сокращению объема памяти устройства и повышению скорости его работы.

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

И, выходной регистр, первая группа входов

60 которого соединена с выходами буферного регистра, о т л и ч а ю щ е е с я тем, соединены со входами устройства. Управляющий вход второго регистра кода адреса соединен с выходом генератора, вход которого соединен с выходом элемента ИЛИ, выход узла опроса — со входом выходного 5 регистра, вторая группа входов которого соединена с выходами первого регистра ко да адреса, а выход — с выходом устройства.

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

На чертеже изображена блок-схема предлагаемого устройства. 15

Оно содержит генератор 1 (тактовых импульсов), счетчик 2 (импульсов), первой, второй и третьей группы элементы И 3-5, соответственно, элемент 6 ИЛИ, узел 7 onроса, первый и второй регистры 8, 9 кода адреса, соответственно, буферный регистр 10, выходной регистр 11.

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

Исходное состояние регистров 10, 11, счетчика 2 тактовых импульсов, узла 7 опроса является нулевым, а по входу устройства в регистры 8 и 9 произведена запись кодов адресов узла-отправителя и узла-получателя, соответственно.

З0

Тактовым импульсом с выхода генератора

1 осуществляется сдвиг содержимого регистра 9 на один разряд вправо, в результате чего производится запись разряда кода узла-получателя в регистр 10. Одновременно количество тактов фиксируется счетчиком

2 тактовых импульсов и узлом 7 опроса.

Элементы И третьей группы 5 осуществляют поразрядное сравнение символов кодов регистров 8 и 9 на равенство, а элементы 40

И второй группы 4 фиксируют одновременное равенство символов всех сравниваемых разрядов. Если одновременное равенство ра рядов наступает после первого сдвига регистра 9, то наличие "единичного потенциала на выходе первого элемента И второй группы 4 позволяет прохождение тактового импульса, появившегося на первом выходе счетчика 2 импульсов, через соответ» ствующий элемент И первой группы 3 на вход элемента 6 ИЛИ.

При несовпадении производится следующий сдвиг содержимого регистра 9, после чего, если вышеописанная ситуация совпадения наблюдается, то на вход элемента 6

ИЛИ поступает тактовый импульс со второго выхода счетчика 2 импульсов, прошедший через соответствующий элемент И первой группы 3 и так как вплоть до того момента, когда после (tl - 1)-ого сдвига

4 (т -число разрядов кода адреса узла) одновре« менное совпадение всех сравниваемых разрядов не произошло, а в результате и -го сдвига тактовый импульс с последнего выхода счетчика 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

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

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

Источники информации, принятые во внимание при экспертизе:

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

¹ 238902, М.Кл. G 06 G 7/48, 10.03.69г.

2. Авторское свидетельство СССР № 288422, М.Кл. G. 06 G 7/48, 03.1 2.70 г.

3. Авторское свидетельство СССР № 271907, М,Кл . G 06 G 7/48, 26.05.70 (IIPo TOTNII) .