Изобретепие относится к области вычислительной техники и может быть использовано при построении специализированных вычислителей, решающих задачи определения rt,-jсвязности сетей.
Недостаток известных устройств для исследования связности сетей заключается в значительном объеме оборудования, пропорциональном П2 (где п - число вершин сети), а также в малой надежности.
Целью изобретения является устранение указанных недостатков.
Эта цель достигается тем, что предлагаемое устройство содержит два регистра сдвига, шины сдвига которых соединены с блоком управления и соответственно с первым и вторым счетчиками, соединенными со своими схемами сравнения, выходы которых подключены к блоку управления, а другие входы схем сравнения подключены соответственно к разрядным выходам первого через схему «И к блоку управления и к разрядным выходам второго регистров, причем входы пометки моделей начальной и конечной вершин, число которых пропорционально п, соединены соответственно с выходами первого и второго счетчиков, выходы пометки моделей начальной и конечной вершин - соответственно со вторым и первым регистрами, а каждый разряд регистра сдвига - со входом выбора пометки модели вершины сети.
При этом устройство содержит лишь модели вершин расширенного графа, состоящие
из регистра, входы которого соединены с выходами первых схем «И, первые входы которых подключены ко входам пометки модели вершины н входам схемы сравнения, соединенной с первым выходом модели вершины, а вторые входы первых схем «И соединены через дифференцирующую цепь со входом управления схемой сравнения и с единичным входом триггера, нулевой вход которого подключен ко входу сброса модели
вершины и входу сброса регистра, разрядные выходы которого соединены с первыми входами вторых схем «П, вторые входы которых подк.;1ючепы к выходу третьей схемы «И, входы которой соединены с блоком управлепия и входом выбора пометки вершины; выходы вторых схем «И соединены с выходами пометки модели вершины, причем единичный вход триггера модели начальной вершины - непосредственно, а модели конечной
вершины - через схему «ИЛИ, другой вход которой подключен к соответствующему входу управления модели вершины, соединены с выходом четвертой схемы «И, первый вход которой соединен с первым входом модели
вершины, а второй - г акольцованным регистром сдвига, подключенным входами управления ко входу управления модели вершины и через схему инверсии и пятую схему «И, другой вход которой соединен с отдельным входом управления модели вершины, подключен ко входу выбора пометки модели вершины. На фиг. 1 изображено предлагаемое устройство для исследования связности сетей. Оно содержит п моделей 1 начальных вершин, п моделей 2 конечных вершин, п схем 3 запоминания и переработки столбца матрицы смежности, п схем 4 запоминания и переработки столбца единичной .матрицы, счетчики 5, 6, имеющие по Iog2 разрядов каждый, «.-разрядные закольцованные сдвиговые регистры 7, 8, регистры 9, 10, содержащие по logs п разрядов, схемы сравнения 11, 12, блок управления 13, схемы «И 14-18. Блок управления 13 имеет следующие выходы: выход 19 кода конечной вершины, выход 20 импульса считывания конечной пометки элементов матриц, выход 21 импульса переработки элементов матриц, выход 22 импульса считывания начальной пометки. Далее некоторые входы и выходы именуются входными и выходными шипами. Схема 23 пометки и просмотра начальной вершины состоит (фиг. 2) из выхода 24 фиксации конечной вершины, входов 25 пометки модели вершины, выхода 26 модели вершины, входа 27 выбора пометки, входа 28 импульса считывания пометки, выходов 29 пометки модели вершины, входа 30 сброса модели вершины, входа 31 модели вершины, цепи 32 сигнала наличия ветви, схем «И 33, регистра 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, 6. и синхронно связанные с ними регистры 7, 8, 45, 66. При появлении кода начальной вершины на схемы 47 на выходе схемы «ИЛР1 58 появляется имнульс, который с выхода 31 модели вершины поступает на входы схем «И 40. В тех начальных вершинах, у которых в цепи 32 появился единичный импульс, поступающий из регистра 45, на выходе схемы «И 40 появляется и.мпульс, перебрасывающий триггер 38 в единичное состояние, что соответствует пометке начальной вершины, При этом в регистр 34 записывается код копечной вершины. Одновременно потенциал с выхода триггера 38 подается па схемы сравнения 36, подготавливая их к срабатыванию, и с выхода 24 фиксации конечной вершины - в блок управления 13. В тот момент, когда в счетчике 5 будет число, соответствующее номеру помеченной начальной вершины, на выходе схемы сравнения 36 появится импульс, который ностунает на входы 26 модели верщины всех конечных вершин. При этом помечаются только те конечные вершины, в цени которых имеется единичный импульс. Процесс пометок и просмотров вершин продолжается до тех пор, пока пе пометится последняя начальная вершина. Если номер последней начальной верщины появится в счетчиках 5, 6 (п-1) раз и рассматриваемая вершина останется неномеченной, то пометить ее нельзя, и устройство управления .прекращает определение степени связности пары вершины. При этом степень связности равна числу пометок последней начальной вершины. При пометке последней начальной вершины блок управления 13 переписывает ее код в регистр 9. Из-за несовпадения кода, записанного в регистре 9, и кода на выходе счетчика 5, схема сравнения 11 не срабатывает, н блок управления 13 продолжает подавать
на счетчик 5 последовательность тактовых импульсов до тех пор, пока коды не совпадут. Как только произошло совпадение, схема сравнения 11 через блок управления 13 прекращает подачу импульсов на счетчик 5, регистр 7 и схему 4 запоминания и переработки столбца единичной матрицы. Последние останавливаются, фиксируя номер строки последней начальной вершины и номеп столбца смежной ей конечной вершины. Далее блок управления 13 подает ИМПУЛЬС по птине 20 на входы всех схем «И 15. O.uia из них, а именно та, которой соответствует единица в остаиовившемся регистре 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. Таким образом, пооисходит перрориентацня ветви, направленной из нячальной вершины в конечную. Далее пронесс повторяется для новой начальной вершины, затем опять .цля конечной и заканчивается, когда будет достигнута исходная вершина. При этом сработает схема «И 14 н блок управ.ления 13 увеличит на единицу число независимых путей, подаст серию тактовых импульсов на все узлы устройства, и иачнется процесс достройки нового цути, а затем описанная процедура переориентации повторяется. Когда будут построены все пути (т. е. за (п-1) итерацию
пометок и просмотр конечная вершина не будет достигнута), блок управления 13 перейдет к определению связности следующей пары вершин. По окончании работы в блоке управления 13 будет храниться информация о связности всех пар вершин.
Предмет изобретения
10
1. Устройство для исследования связности сетей, содержащее блок управления, соединенный со входами управления и сброса и выходами фиксации конечной вершины моделей начальных и конечных вершин сети, цервые пходы которых объединены и иодключены соответственно к первым входам моделей конечных и начальных вершин сети, отличающееся тем, что, с целью повышения
надежности и сокращения оборудования, оно содержит регистры сдвига, шины сдвига которых соединены с блоком управления и соответственно с первым и вторым счетчиками, соединенными со своими схемами сравнения,
выходы которых подключены к блоку управления, а другие входы схем сравнения подключены соответственно к разрядным выходам первого через схему «И к блоку управления и к разрядным выходам второго регистров. причем входы пометки моделей начальной и конечной вершин соединены соответственно с выходами первого и второго счетчиков, выходы пометки начальной и конечной вершин - соответственно со вторым и
первым регистрами, а каждый разряд регистра сдвига - со входом выбора пометки модели вершины сети.
2. Устройство по п. 1, отличающееся тем, что модель вершины сети содержит регистр, входы которого соединены с выходами первых схем «И, первые входы которых подключены к входам ппметки модели вершины и входам схемы сравнения, соединенной с первым выходом модели вершины, а вторые
входы иервых схем «И соединены через дифференцируюшзЮ цепь со входом управления схемы сравнения и с единичным выходом триггера, иулевой вход которого подключен ко входу сброса модели вершины и входу
сброса регистра, разрядные выходы которого соединены с первыми входами вторых схем «И, вторьте входы которых подключены к вы«оду третьей схемы «И, входы которой соединены со входом управления и входом
выбора иометки модели вершины; выходы вторых схем «И соединены с выходами пометки модели вершины, причем единичный вход триггера модели начальной вершины - непосредственно, а модели конечной вершины - через схему «ИЛИ, другой вход которой подключен к соответствующему входу управления модели вершины, соединены с выходом четвертой схемы «И, первый вход которой соединен с первым входом модели вершины, а второй - с закольцованным регист7 ром сдвига, подключенным входами управления ко входу управления модели вершины и через схему инверсии и пятую схему «И, дру8гой вход которой соединен с отдельным входом управления модели вершины, подключен ко входу выбора пометки модели вершины.
26 о 28
Лоi-i
50
Ч
Lj
J
