Устройство для исследования связности сетей

Устройство для исследования связности сетей

Иллюстрации

Показать все

Реферат

 

О П И g A Н И Е 1н1 443394

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 31.01.72 (21) 1741396/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.09.74. Бюллетень № 34

Дата опубликования описания 04.06.75 (51) М. Кл. G 06@ 7!48

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

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

П. М. Рыбаков, Л. А. Снежкова и Б. Г. Спиридонов

Таганрогский радиотехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ

СЕТЕЙ

Изобретение относится к области вычислительной техники и может быть использовано при построении специализированных вычислителей, решающих задачи определения п; связности сетей. 5

Недостаток известных устройств для исследования связности сетей заключается в значительном объеме оборудования, пропорциональном п2 (где n — число вершин сети), а также в малой надежности. 10

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

Эта цель достигается тем, что предлагаемое устройство содержит два регистра сдви- 15 га, шины сдвига которых соединены с блоком управления и соответственно с первым и вторым счетчиками, соединенными со своими схемами сравнения, выходы которых подключены к блоку управления, а другие входы 20 схем сравнения подключены соответственно к разрядным выходам первого через схему «И» к блоку управления и к разрядным выходам второго регистров, причем входы пометки моделей начальной и конечной вершин, число 25 которых пропорционально п, соединены соответственно с выходами первого и второго счетчиков, выходы пометки моделей начальной и конечной вершин — соответственно со вторым и первым регистрами, а каждый раз- 30 ряд регистра сдвига — со входом выбора пометки модели вершины сети.

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

«И», входы которой соединены с блоком управления и входом выбора пометки вершины; выходы вторых схем «И» соединены с выходами пометки модели вершины, причем единичный вход триггера модели начальной вершины — непосредственно, а модели конечной вершины — через схему «ИЛИ», другой вход которой подключен к соответствующему входу управления модели вершины, соединены с выходом четвертой схемы «И», первый вход которой соединен с первым входом модели вершины, а второй — с закольцованным ре443394 гистром сдвига, подключенным входами управления ко входу управления модели вершины и через схему инверсии и пятую схему

«И», другой вход которой соединен с отдельным входом управления модели вершины, подключен ко входу выбора пометки модели вершины.

На фиг. 1 изображено предлагаемое устройство для исследования связности сетей.

Оно содержит п моделей 1 начальных вершин, п моделей 2 конечных вершин, и схем 3 запоминания и переработки столбца матрицы смежности, и схем 4 запоминания и переработки столбца единичной матрицы, счетчики 5, 6, имеющие по log2 и разрядов каждый, и-разрядные закольцованные сдвиговые регистры 7, 8, регистры 9, 10, содержащие по logq и разрядов, схемы сравнения 11, 12, блок управления 13, схемы «И»

14 — 18.

Блок управления 13 имсет следующие выходы: выход 19 кода конечной вершины, выход 20 импульса считывания конечной пометки элементов матриц, выход 21 импульса переработки элементов матриц, выход 22 импульса считывания начальной пометки. Далее некоторые входы и выходы именуются входными и выходными шинами.

Схема 23 пометки и просмотра начальной вершины состоит (фиг. 2) из выхода 24 фиксации конечной вершины, входов 25 пометки модели вершины, выхода 26 модели вершины, входа 27 выбора пометки, входа 28 импульса считывания пометки, выходов 29 пометки модели вершины, входа 30 сброса модели вершины, входа 31 модели вершины, цепи 32 сигнала наличия ветви, схем «И» ЗЗ, регистра

34, схем «И» 35, схемы сравнения 36, схемы

«ИЛИ» 37, триггера 38, дифференцирующей цепи 39, схемы «И» 40.

Схема 3 запоминания и переработки столбца единичной матрицы (фиг. 2) содержит вход 41 сигнала переработки элемента столбца, вход 42 записи начального столбца, вход

43 установки нуля, схему инверсии 44, закольцованный регистр сдвига 45, схему

«И» 46.

Схема 47 пометки и просмотра конечной вершины имеет входы 48 пометки модели вершины, вход 49 выбора пометки, вход 50 импульса считывания пометки, выходы 51 пометки модели вершины, вход 52 сигналов возбуждения начальной вершины, цепь 53 сигнала наличия ветви и состоит из схем «И» 54, регистра 55, схем «И» 56, схемы сравнения

57, схемы «ИЛИ» 58, триггера 59, схемы

«ИЛИ» 60, дифференцирующей цепи 61, схемы «И» 62.

Схемы 4 запоминания и переработки столбца матрицы смежности (фиг. 3) содержит вход 63 сигнала переработки элемента столбца, вход 64 записи начального столбца, схему инверсии 65, закольцованный регистр сдвига 66, схему «И» 67. 68 — цепь установки устройства в исходное состояние.

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

Подачей импульса на выходы 68, 43 устройство приводится в и сходное состояние, при этом в закольцованных сдвиговых регистрах 7, 8 записывается «1» в нулевой разряд и «О» в остальные разряды. Теперь в устройство необходимо занести информацию о конфигурации расширенного графа. С этой целью в закольцованные регистры сдвига 45 и 66 с помощью схем «И» 46 и 67 заносятся столбцы исходной и единичной матриц смежности.

В блок управления 13 заносится номер конечной вершины. Подачей единичного импульса на один из входов 52 схемы 47 — пометки и просмотра конечной вершины триггер 59 перебрасывается в единичное состояние, что соответствует пометки начальной вершины. Так как в это время счетчик 6 находится в нулевом состоянии, импульс со схемы «ИЛИ» 60 начальной вершины не изменит нулевого кода в регистре 55. Для осуществления пометок и просмотров вершин начинают работать счетчики 5, б и синхронно связанные с ними регистры 7, 8, 45, 66. При появлении кода начальной вершины на шинах схемы 47 на выходе схемы «ИЛИ» 58 появляется импульс, который с выхода 31 модели вершины поступает на входы схем

«И» 40. В тех начальных вершинах, у которых в цепи 32 появился единичный импульс, поступающий из регистра 45, на выходе схемы «И» 40 появляется импульс, перебрасывающий триггер 38 в единичное состояние, что соответствует пометке начальной вершины.

При этом в регистр 34 записывается код конечной вершины. Одновременно потенциал с выхода триггера 38 подается на схемы сравнения 36, подготавливая их к срабатыванию, и с выхода 24 фиксации конечной вершины— в блок управления 13.

В тот момент, когда в счетчике 5 будет число, соответствующее номеру помеченной начальной вершины, на выходе схемы сравнения 36 появится импульс, который поступает на входы 26 модели вершины всех конечных вершин. При этом помечаются только те конечные вершины, в цепи которых имеется единичный импульс. Процесс пометок и просмотров вершин продолжается до тех пор, пока не пометится последняя начальная вершина. Если номер последней начальной вершины появится в счетчиках 5, б (n — 1) раз и рассматриваемая вершина останется непомеченной, то пометить ее нельзя, и устройство управления, прекращает определение степени связности пары вершины. При этом степень связности равна числу пометок последней начальной вершины.

При пометке последней начальной вершины блок управления 13 переписывает ее код в регистр 9. Из-за несовпадения кода, записанного в регистре 9, и кода на выходе счетчика 5, схема сравнения 11 не срабатывает, и блок управления 13 продолжает подавать

443394

10 па счетчик 5 последовательность тактовых импульсов до тех пор, пока коды не совпадут.

Как только произошло совпадение, схема сравнения 1! через блок управления

13 прекращает подачу импульсов на счетчик 5, регистр 7 и схему 4 запоминания и переработки столбца единичной матрицы. Последние останавливаются, фиксируя номер строки последней начальной вершины и номеп сточбца смежной ей конечной верштттттт.,Ла.чее блок управления 13 подает имп.лье п0 птине 20 HB входы всех схем «И» 15.

О,чна из ттттх, а именно та, которой соответствует единица в остановившемся регистре 7 (указываютцая номер столбца), сработает и выдаст по шине 28 импульс, который перепишет пометку начальной вершины (номер смежной конечной вершины) из регистра 34 через схемы «И» 35 по шинам выхода 29 пометки модели вершины в регистр 10. Ввиду рассогласоваттття кодов теперь уже на схеме сравнения 12 б.чок управления посылает тактовую серию на счетчик 6, регистр 8 и схему 3 запоминания и переработки столбца матрицы смежности до тех пор, пока коды не совпачут. Затем указанные узлы останавливаются, фиксируя номер столбца начальной вершины и номер строки конечной вершины.

Теперь можно осуществить переориентацию ветви, соединяющей эти вершинь.. Блок управления 13 по шине 21 выдает на схемы

«И» 16, 17 импульс, который, пройдя по шинам 41 и 63 через схемы инверсии 44 тт 65 соответственно, инвертирует содержимое первых разрядов регистров 45 и 66, в которых записаны координаты ветви. После этого по шине 22 блок управ.че»ия 13 выдает импульсы на все схемы «И» 18. О тна из них, соответствующая единице в регистре 8, сработает и по шине 50 откроет схемы «И» 56, тем самым перезаписывая со ержимое регистра 55 в регистр 9. Счетчик 5 схемы 4 запоминания и пепеработки столбца единичной матрицы и регистр 7 опять отрабатывают до совпадения кодов на схеме сравнения 11. Затем из блока управления 13 по шинам 21 опять почаются импульсы на все схемы «И» 16 и 17. Пройдя только через чче из них, а также по шинам

41 и 63 через схемы инверсии 44 и 65, они изменяют на противоположные,чвоичные числа, записанные в первых разрядах закольцованпьтх пегттстроч сдвига 45 и 66. Таким образом, ппоисходит и П-.ориентация ветви. направленттой ттз начачьттотт вершины в конечную. Да,чее про»есс повторяется пля новой начальной вершппь.. затем опять для ко»ечной и заканчивается, когда будет достигнута исхочная вершина. Пртт этом сработает схема «И» !4 и блок управления 13 увеличит па ечиницу число и"зависимых путей, подаст сепию тактовых и.,тпучьсов па все узлы устройства, v начнется процесс достройки нового пути, а затем описанная процедура переориентации повторяется. Когда будут построены все пути (т. е. за (n — 1) итерацито

65 пометок и просмотр конечная вершина не будет достигнута), блок управления 13 пе- рейдет к определению связности следующей пары вершин. По окончании работы в блоке управления 13 будет храниться информация о связности всех пар вершин.

Предмет изобретения

1. Устройство для исследования связности сетей, содержащее блок управления, соединенный со входами управ,чения и сброса и выходами фиксации конечной вершины моделей начальных и конечных вершин сети, первые входы которых объединены и подключены соответственно к первым входам моделей конечных и начальных вершин сети, о т л ич 1 то щ е р с я тем. что, с целью повышения надежности и сокращения оборудования, оно содержит ретчтстры сдвига, шины сдвига которьтх соединены с блоком управления и соответственно с первым и вторым счетчиками, соединенныMè со своими схемами сравнения, выходы которых подключены к блоку управления, а чругие входы c åì сравнения подключены соответственно к разрядным выходам первого через схему «И» к блоку управления и к разрядным выходам второго регистров. причем входы пометки моделей начальной и конечной вершин соединены соответственно с выходами первого и второго счетчиков, выходы пометки начальной и конечной вершин — соответственно со вторым и первым регистрами, а каждый разряд регистра счвига — со входом выбора пометки мочели вепшины сети.

2. Устройство по п. 1, отлича ющееся тем, что модель вершины сети содержит регистп, входы которого соединены с выходами первых схем «И», первые входы которых подключеньт к вхочам пометки модели вершины и входам схемы сравнения, соединенной с первым выходом модели вершины, а вторые входы первых схем «И» соечиттены через дифФеренттируютттуто цепь сп входотм управления схемы сравнения и с единичным выходом триггера, нулевой вход которого подключен ко входу сбпоса модели вершины и входу сброса пегистпа, разря.чные выходы которого соединены с первыми входами вторых схем

«И», втопт,тс вхпчьт котопьтх ппдк.чточены к вы оду третьей схемы «И». входы которой соедпне»bT со входом управления и входом выбора пометки модели вершины; выходы вторых схем «И» соединены с выходами пометки модели верни.ны, причем единичный вход триггера модели начальной вершины— непосредственно, а модели конечной вершины — через схему «ИЛИ», другой вход которой подключен к соответствующему входу управления модели вершины, соединены с выходом четвертой схемы «И», первый вход которой соединен с первым входом модели вершины, а второй — с закольцованным регист443394 ром сдвига, подключенным входами управления ко входу управления модели вершины и через схему инверсии и пятую схему «И», другой вход которой соединен с отдельным входом управления модели вершины, подключен ко входу выбора пометки модели вершины.

443394

Р5

Б?

2Б

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

Техред Н. Куклина

Корректоры: В. Петрова и О. Данишева

Редактор Б. Нанкина

Подписное

Типография, пр. Сапунова, 2

Заказ 1206/6 Изд. № 1273 Тираж 624

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

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