Устройство для определения маршрута
Изобретение относится к области вычислительной техники и может быть использовано при решении задач определения на графах маршрутов между ддумя заданными вершинами. Изобретение позволяет идентифицировать вершины, вошедшие в данный маршрут. Устройство содержит группу ключей, группу триггеров матрк-. цу из NifN моделей ветвей дерева, причем каждая модель ветви дерева выполнена в виде триггера, группу . элементов ИЛИ, группу-счетчиков, группу элементов И, блок сравнения, регистр, триггер, распределитель импульсов, генератор импульсов, I ил. ел
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
А1
„, Я0„„251049
1511 4 G .06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
C е
ГОСУДАРСТВЕННЬ1Й НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3857177/24-24 (22) 07.12.84
-(46) 15.08.86. Бюл. 1Ф 30 (72) Ю.M.Êîïòåâ и M.M.Îâ÷èííèêîâ (53) 681.333 (088.8 ) (56) Авторское свидетельство СССР
N - 329538, кл. G 06 G 7/48, 1970.
Авторское свидетельство СССР
N - 679998, кл, G 06 G 7/48, 1977. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАРШРУТА (57) Изобретение относится к области вычислительной техники и может быть использовано при решении задач определения на графах маршрутов между двумя заданными вершинами.
Изобретение позволяет идентифицировать вершины, вошедшие в данный маршрут. Устройство содержит группу ключей, группу триггеров матри-. цу из ИхН моделей ветвей дерева, причем каждая модель ветви дерева выполнена в виде триггера, группу элементов KIH группу. счетчиков, группу элементов И, блок сравнения, регистр, триггер, распределитель импульсов, генератор импульсов. 1 ил.
1 251049
Изобретение относится к вычислительной технике и может быть исl5
30 пользовано при решении задач определения на графах маршрутов между двумя заданными вершинами дерева. 5
Цель изобретения — расширение функциональных возможностей за счет идентификации вершин, вошедших в заданный маршрут, На чертеже изображена функцио- 10 нальная схема устройства для определения маршрута.
Устройство содержит группу ключей 1, группу триггеров 2, матрицу
3 из И М моделей ветвей (дерева), причем каждая модель ветви выполнена в виде триггера 4, группу элементов ИЛИ 5, группу счетчиков 6, группу элементов И 7, блок 8 сравнения, регистр 9, триггер 10, распределитель Il импульсов, генератор
12 импульсов.
Устройство работает следующим образом.
Для приведения его в исходное 25 состояние включают два счетчика 6 с номерами, соответствующими двум вершинам, между которыми нужно найти маршрут . Хроме того, обнуляют регистр 9, счетчики 6, триггеры 2 и 10 и распределитель ll, в матрице 3 включают те триггеры 4, на соответствующих которым позициях матрицы графа смежности стоят единицы (т.е. имеются соответствующие
35 ребра), за исключением триггеров главной диагонали, которые в работу не включаются. Нулевыми потенциалами с выходов триггеров 2 открыты ключи 1.
С подачей сигнала на вход устройства генератор 12 начинает выдачу импульсов на вход распределителя 11, который поочередно выдает импульсы на первый второй и т.д. выходы.
Первый импульс распределителя 11 поступает на единичные входы триггеров
4 первого столбца матрицы 3, единичные сигналы с выходов триггеров через элементы ИЛИ 5 поступают на счетные входы соответствующих счетчи50 нов 6, которые увеличивают свои показания на "1".
Аанлогичные процессы происходят при выдаче распределителем 11 импульсов по второму, ..., N-у выходам.
I I T I
Каждый счетчик 6 имеет емкость 2 . и при отсчете двух импульсов выдает единичный потенциал переполнения до поступления сигнала на его установочный вход (независимо от числа поступивших на его счетный вход импульсов после поступления первых двух импульсов). После прохождения N импульсов на выходе первого разряда счетчиков в одноименных этим счетчикам строках матрицы 3 в работу включен всего один триггер 4, и присутствует единичный потенциал, у остальных счетчиков на выходе первого разряда присутствует нулевой потенциал, а на выходе второго разряда — единичный потенциал (переполнение).
Пусть на выходе первого разряда
i-го счетчика 6 присутствует единичный потенциал, поступающий на второй вход элемента И 7, Тогда (N + 1)-й импульс распределителя Il проходит через элемент И 7; на единичный вход триггера 2,, который выдачей единичного потенциала закрывает ключ l; (N + 2)-й импульс распределителя не проходит через закрытые ключи на нулевые входы триггеров 4 и установочные входы счетчиков 6, вследствие чего триггеры 4 соответствующих столбцов матрицы 3, соответствующие счетчики 6 и триг— геры 2 остаются до конца работы устройства в том состоянии, в которое они перешли после прохождения первых N импульсов распределителя 11, У тех счетчиков 6, которые переполнились после прохождения первых
N импульсов распределителя 11, единичный потенциал присутствует на выходе второго разряда и подается на соответствующие входы регистра 9, который записывает "1" в ячеики памяти после того, как (N + 1)-й импульс распределителя 11 перебросит в единичное состояние триггер 10, и он выдает сигнал на вход записи регистра 9.Поскольку на выходе первого разряда этих счетчиков имеется нулевой потенциал, то соответствующие элементы И 7 закрыты для прохождения импульса с (N + 1)-го выхода распределителя, поэтому соответствующие триггеры 2 остаются в нулевом положении и не закрывают одноименные ключи 1.
Импульс с (N + 2)-го выхода распределителя 11 проходит через те ключи 1, которые остались сткрытыми, на нулевые входы триггеров 4 соответствующих столбцов матрицы 2 и перебрасывает их в исходное (ну3
1 левое) положение. Этот импульс проходит также на установочные входы соответствующих счетчиков 6, которые сбрасывают свои показания в "0".
Этим заканчивается первый цикл работы устройства.
Во втором цикле работы устройства распределитель 11 также поочередно выдает импульсы на первый, второй и т.д. выходы. Эти импульсы перебрасывают те триггеры 4, которые были возвращены в нулевое положение (N + 2) ì импульсом распределителя 11, в единичное состояние.
Счетчики 6, которые были установлены в нулевое состояние импульсом с (N + 2)-го выхода распределителя 11 в первом цикле, ведут счет поступающих на их входы импульсов. При этом на вход j-го счетчика 6, в соответствующей которому j-й строке матрицы 3 после первого цикла не было возвращено в исходное состояние
r триггеров 4, поступит меньшее (на r) количество импульсов. Поэтому в общем случае некоторые из счетчиков 6 после прохождения N импульсов распределителя 11 во втором цикле уже не достигнут состоя— ния переполнения и отсчитывают толь) ко один импульс. Тем самым триггеры
4 соответствующих столбцов матрицы 3 по окончании второго цикла не будут возвращены в исходное нулевое состояние, а сами эти счетчики не будут установлены в "0". Импульс с (N + 1)-го выхода распределителя )1 перебрасывает в нулевое положение триггер 10, единичный сигнал с инверсного выхода которого поступает на управляющий вход блока 8. Последний осуществляет поразрядное сравнение сигналов, поступающих на его первую и вторую группы информационных входов, и выдает на выход сигнал лишь при условии, что на обе группы информационных входов поступают одинаковые сигналы.
Работа устройство продолжается до того момента, пока по окончании какого-то цикла у блока 8 на обоих группах информационных входов не будут одинаковые сигналы. Тогда блок
8 выдает на выход сигнал, поступающий на вход генератора 12 и прекращающий его работу. Номера вершин, через которые проходят маршрут между двумя выбранными вершинами дерева, определяют по номерам счетчиков
25)049 4
6, на выходах вторых разрядов которых присутствует потенциал переполнения.
ЗО
Формула и з обретения
Устройство для определения маршрута, содержащее матрицу из ХхИ моделей ветвей (где Х вЂ” число вершин дерева), каждая модель ветви выполнена в виде триггера, группу элементов ИЛИ по числу строк матрицы моделей ветвей, группу ключей по числу столбцов матрицы моделей ветвей, группу счетчиков по числу строк матрицы моделей ветвей и блок сравнения, каждый информационный вход первой группы которого подключен к выходу второго разряда соответствующего счетчика группы, о т л и ч а— ю щ е е.с я тем, что, с целью расширения функциональных возможностей за счет идентификации вершин, вошедших в заданный маршрут в него введены группа элементов И, группа триггеров, регистр, триггер, распределитель импульсов и генератор им пульсов, вход запуска которого является входом запуска устройства, а вход останова генератора импульсов подключен к выходу блока сравнения, выход генератора импульсов соединен с входом распределителя импульсов, N выходов которого подключены соответственно к входам установки в "1" триггеров одноименного столбца матрицы моделей ветвей, (М + 1)-й выход распределителя импульсов соединен с первыми входами элементов И группы и входом триггера,(N + 2)-й выход распределителя импульсов подключен к информационным входам ключей группы, управляющие входы которых соединены с выходами одноименных триггеров группы, выход каждого ключа группы подключен к входам установки в "0" всех триггеров одноименного столбца матрицы моделей ветвей и к установочному входу одноименного счетчика группы, выход первого разряда которого соединен с вторым входом одноименного элемента И группы, выход каждого элемента И группы подключен к входу одноименного триггера группы,. выход второго разряда каждого из счетчиков группы подключен к одноименному информационному разрядному входу регистра, разряд1251049
Составитель Т.Сапунова
Техред Э. Чинар Корректор Л.Пилипенко
Редактор Е.Копча
Заказ 4410/44
Тираж б71 Поцписное
BHHHIIH Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб,, д,4/5
Производственно-полиграфическое предприятие, г,Ужгород, ул.Проектная,4 ные выходы которого подключены к соответствующе информационным входам второй группы блока сравнения, вход разрешения записи регистра соединен с прямым выходом триггера, инверсный выход которого подключен к входу синхронизации блока сравнения, выход каждого элемента
ИЛИ группы соединен со счетным входом одноименного счетчика группы выход каждого 1.I -го триггера моделей ветвей матрицы подключен к 1-му входу 1 --го элемента ИЛИ группы (где i, j = 1,2, ..., М).
