Устройство для определения маршрута Советский патент 1986 года по МПК G06F15/173 

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

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

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

Устройство содержит rjpynny ключей 1, группу триггеров 2, матрицу

3из NisN моделей ветвей (дерева), причем каждая модель ветви выполнена в виде триггера 4, группу элементов ИЛИ 5, группу счетчиков 6, группу элементов И 7, блок 8 сравнения, регистр 9, триггер 10, распределитель 1 импульсов, генератор 12 импуль сов,

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

Для приведения его в исходное состояние включают два счетчика 6 с номерами, соответствуюш;ими двум вершинам, между которыми нужно найти маршрут.- Кроме того, обнуляют регистр 9, счетчики 6, триггеры 2 и 10 и распределитель И, в матрице 3 включают те триггеры 4, ria соответствующих которым позициях матрицы графа смежности стоят единицы (т.е. имеются соответствзпющие ребра), за исключением триггеров главной диагонали, которые в работу не включаются. Нулевыми потенциалами с выходов триггеров 2 открыты ключи 1.

С подачей сигнала на вход устройсва генератор 12 начинает вьщачу импульсов на вход распределителя 11, которьй поочередно выдает импульсы на первый, второй и ТоД. выходы. Первый импульс распределителя 11 пос TjTiaeT на единичные входы триггеров

4первого столбца матрицы 3 единичные сигналы с выходов триггеров через элементы ИЛИ 5 поступают на счетные входы соответствующих счетчиков 6, которые увеличивают свои показания на .

Аанлогичные процессы происходят при вьщаче распределителем 11 импульсов по второму, ..., N-y выходам. Каждый счетчик 6 имеет емкость 2 и при отсчете двух импульсов выдает единичный потенциал переполнения до

поступления сигнала на его установочный вход (независимо от числа поступивших на его счетный вход импульсов после поступления первых двух импуль-сов). После прохождения N импульсов на выходе первого разряда счетчиков в одноименных этим счетчикам строках матрицы 3 в работу включен всего один триггер 4, и присутствует единичньй потенциал, у остальных счетчиков на выходе первого разряда присутствует нулевой потенциал, а на выходе второго разряда - единичный потенциал (переполнение),

Пусть на выходе первого разряда i-ro счетчика 6 присутствует единичный потенциал, поступающий на второй вход элемента И 7, Тогда (N + 1)-й импульс распределителя 11

проходит через элемент И 7; на единичный вход триггера 2 , который вьщачей единичного потенциала, закрывает ключ 1;, , (N + 2)-й импульс распределителя не проходит через закрытые ключи 1 на нулевые входы триггеров 4 и установочные входы счетчиков 6, вследствие чего триггеры 4 соответствующих столбцов матрицы 3, соответствующие счетчики 6 и триггеры 2 остаются до конца работы устройства в том состоянии, в которое они перешли после прохождения .первых N импульсов распределителя 1 I .

У тех счетчиков 6, которые переполнились после прохождения первых N импульсов распределителя 11, единичный потенциал присутствует на выходе .второго разряда и подается на соответствующие входы регистра 9,

который записывает 1 в ячейки памяти после того, как (N + 1)-й импульс распределителя 1I перебросит в единичное состояние триггер 10, и он вьщает сигнал на вход записи регистра 9оПоскольку на выходе первого разряда этих счетчикозз имеется нулевой потенциал, то соответствующие элементы И 7 закрыты для про- холодения импульса с (N + 1)-го выхода распределителя, поэтому соответствующие триггеры 2 остаются в нулевом положении и не закрывают одноименные ключи 1.

Импульс с (N + 2)-го выхода распределителя 11 проходит через те ключи I, которые остались открытыми, на нулевые входы триггеров 4 соответствующих столбцов матрицы 2 и перебрасывает их в исходное (

левое) положение. Этот импульс проходит также на установочные входы соответствующих счетчиков 6, которые сбрасывают свои показания в О Этим заканчивается первый цикл ра- боты устройства.

Во втором цикле работы устройства распределитель 11 также поочередно выдает импульсы на первый, второй и т.д. выходы. Эти импульсы перебрасывают те триггеры 4, которые были возвращены в нулевое положение (N + 2)-м импульсом распределителя 11, в единичное состояние. Счетчики 6, которые были установлен в нулевое состояние импульсом с (N + 2)-го выхода распределителя 1 1 в первом цикле, ведут счет поступающих на их входы импульсов. При этом на вход счетчика 6, в соответствующей которому j-й строк матрицы 3 после первого цикла не было возвращено в исходное состояние г триггеров 4, поступит меньшее (на г) количество импульсов. Поэто- му в общем случае некоторые из счетчиков 6 после прохождения N импульсов распределителя 11 во втором цикле уже не достигнут состоя- |Ния переполнения и отсчитывают только один импульс. Тем самым триггеры 4 соответствующих столбцов матрицы i3 по окончании второго цикла не будут возвращены в исходное нулевое состояние, а сами эти счетчики не будут установлены в О, Импульс с (N + 1)-го выхода распределителя 11 перебрасывает в нулевое положение триггер 10, единичный сигнал с инверсного выхода которого поступает на управляющий вход блока 8. Пос- ледний осуществляет поразрядное сравнение сигналов, поступающих на его первую и вторую группы информационных входов, и выдает на выход сигнал лишь при условии, что на обе группы информационных входов поступают одинаковые сигналы.

Работа устройство продолжается до того момента, пока по окончании какого-то цикла у блока 8 на обоих группах информационных входов не будут одинаковые сигналы. Тогда блок 8 вьщает на выход сигнал, поступающий на вход генератора I2 и прекращающий его работу. Номера вершин, через которые проходят маршрут между двумя выбранными вершинами дерева, определяют по номерам счетчиков

5

о j о 5 5 0 5

0 5

0

0494

6, на выходах вторых разрядов которых присутствует потенциал переполнения.

Формула изобретения

Устройство для определения маршрута, содержащее матрицу из NxN моделей ветвей (где N - число вершин дерева), каждая модель ветви вьшолне- на в виде триггера, группу элементов ИЛИ по числу строк матрицы моделей ветвей, группу ключей по числу столбцов матрицы моделей ветвей, группу счетчиков по числу строк матрицы моделей ветвей и блок сравнения, каждый информационный вход первой группы которого подключен к выходу второго разряда соответствующего счетчика группы, о т л и ч а - ю щ е е.с я тем, что, с целью расширения функциональных возможностей за счет идентификации верщин, во- щедших в заданньй маршрут в него введены группа элементов И, группа . триггеров, регистр, триггер, распределитель импульсов и генератор им-г . пульсов, вход запуска которого ян-- ляется входом Запуска устройства, а вход останова генератора импульсов подключен к выходу блока сравнения, выход генератора импульсов соединен с входом распределителя импульсов, N выходов которого подключены соответственно к входам установки в 1 триггеров одноименного столбца матрицы моделей ветвей, (N + 1)-й выход распределителя импульсов соединен с первыми входами элементов И группы и входом триггера, (N -1- 2)-й выход распределителя импульсов подключен к информационным входам ключей группы, управляющие входы которых соединены с выходами одноименных триггеров груп- пы, выход каждого ключа группы подключен к входам установки в всех триггеров одноименного столбца матрицы моделей ветвей и к установочному входу одноименного счетчика группы, вьгход первого разряда которого соединен с вторым входом одноименного элемента И группы, выход каждого элемента И группы подключен к входу одноименного триггера группы,, выход второго разряда каж- дого из счетчиков группы подключен к одноименному информационному разрядному входу регистра, разряд 0

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

сравнения, вьгход каждого элемента ШШ группы соединен со счетным входом одноименного счетчика группы выход каждого .i -го триггера моделей ветней матрицы подключен к j-му входу i -г о элемента ИПИ группы ,(где i, j I,2, ...5 N).

Изобретение относится к области вычислительной техники и может быть использовано при решении задач определения на графах маршрутов между ддумя заданными вершинами. Изобретение позволяет идентифицировать вершины, вошедшие в данный маршрут. Устройство содержит группу ключей, группу триггеров матрк-. цу из NifN моделей ветвей дерева, причем каждая модель ветви дерева выполнена в виде триггера, группу . элементов ИЛИ, группу-счетчиков, группу элементов И, блок сравнения, регистр, триггер, распределитель импульсов, генератор импульсов, I ил. ел

Редактор Е.Копча

Составитель Т,Сапунова Техред Э.Чилсмар

Заказ 4410/44Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д,4/5

Производственно-полиграфическое предприятиеj г.Ужгород, ул.,Проектная,4

Корректор Л.Пклипенко