Устройство для определения маршрута

(53) 681,333 ( 2 бь юл. У 30 и М.М.Ов88.8 ) ников во СССР 1970. СССР видетельс 06 С 7/48 идетельств 06 С 7/48 ДЛЯ ОПРЕДЕ 1977.ЛЕНИЯ к облас и может относитсой техник ГОСУДАРСТВЕННЬ 1 Й НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(57) Изобретенити вычислитель ть использовано при решении задач определения на графах маршрутов между двумя заданными вершинами.Изобретение позволяет идентифицировать вершины, вошедшие в данный маршрут. Устройство содержит группу ключей, группу триггеров матри-. цу из ИхН моделей ветвей дерева, причем каждая модель ветви дерева выполнена в виде триггера, группу элементов ИЛИ, группу. счетчиков, группу элементов И, блок сравнения, регистр, триггер, распределитель импульсов, генератор импульсов. 1 ил.Изобретение относится к вычислительной технике и может быть ис 15 30 пользовано при решении задач определения на графах маршрутов между двумя заданными вершинами дерева. 5Цель изобретения - расширениеФункциональных возможностей за счетидентификации вершин, вошедших взаданный маршрут,На чертеже изображена функцио- Ональная схема устройства для определения маршрута,Устройство содержит группу ключей 1, группу триггеров 2, матрицу3 из ЮкМ моделей ветвей (дерева),причем каждая модель ветви выполнена в виде триггера 4, группу элементов ИЛИ 5, группу счетчиков 6,группу элементов И 7, блок 8 сравнения, регистр 9, триггер 10, распределитель 11 импульсов, генератор12 импульсов,Устройство работает следующимобразом.Для приведения его в исходное 25состояние включают два счетчика 6с номерами, соответствующими двумвершинам, между которыми нужнонайти маршрут . Хроме того, обнуляютрегистр 9, счетчики 6, триггеры 2и 10 и распределитель 11, в матрице 3 включают те триггеры 4, насоответствующих которым позицияхматрицы графа смежности стоят единицы (т,е, имеются соответствующие35ребра), за исключением триггеровглавной диагонали, которые в работу не включаются. Нулевыми потенциалами с выходов триггеров 2 открытыключи 1.С подачей сигнала на вход устройства генератор 12 начинает выдачу импульсов на вход распределителя 11,который поочередно выдает импульсына первый второй и т.д. выходы.У45Первый импульс распределителя 11 поступает на единичные входы триггеров4 первого столбца матрицы 3, единичные сигналы с выходов триггеровчерез элементы ИЛИ 5 поступают насчетные входы соответствующих счетчи 50нов 6, которые увеличивают свои показания на "1",Аанлогичные процессы происходятпри выдаче распределителем 11 импульсов по второму, , И-у выходам.551 1Каждый счетчик 6 имеет емкость 2и при отсчете двух импульсов выдаетединичный потенциал переполнения до поступления сигнала на его установочный вход (независимо от числа поступивших на его счетный вход импульсов после поступления первых двух импульсов). После прохождения И импульсов на выходе первого разряда счетчиков в одноименных этим счетчикам строках матрицы 3 в работу включен всего один триггер 4, и присутствует единичный потенциал, у остальных счетчиков на выходе первого разряда присутствует нулевой потенциал, а на выходе второго разряда - единичный потенциал (переполнение).Пусть на выходе первого разряда х-го счетчика 6 присутствует единичный потенциал, поступающий на второй вход элемента И 7, Тогда (И + 1)-й импульс распределителя 11 проходит через элемент И 7, на единичный вход триггера 2 который выдачей единичного потенциала закрывает ключ 1;, (И + 2)-й импульс распределителя не проходит через закрытые ключина нулевые входы триггеров 4 и установочные входы счетчиков б, вследствие чего триггеры 4 соответствующих столбцов матрицы 3, соответствующие счетчики б и триггеры 2 остаются до конца работы устройства в том состоянии, в которое они перешли после прохождения первых И импульсов распределителя 11,У тех счетчиков б, которые переполнились после прохождения первых И импульсов распределителя 11, единичный потенциал присутствует на выходе второго разряда и подается на соответствующие входы регистра 9, который записывает "1" в ячейки памяти после того, как (И + 1)-й импульс распределителя 11 перебросит в единичное состояние триггер 10, и он выдает сигнал на вход записи регистра 9.Поскольку на выходе первого разряда этих счетчиков имеется нулевой потенциал, то соответствующие элементы Изакрыты для прохождения импульса с (М + 1)-го выхода распределителя, поэтому соответствующие триггеры 2 остаются в нулевом положении и не закрывают одноименные ключи 1.Импульс с (1 + 2)-го выхода распределителя 11 проходит через те ключи 1, которые остались сткрытыми, на нулевые входы триггеров 4 соответствующих столбцов матрицы 2 и перебрасывает их в исходное (ну 31левое) положение. Этот импульс проходит также на установочные входысоответствующих счетчиков 6, которые сбрасывают свои показания в "0".Этим заканчивается первый цикл работы устройства.Во втором цикле работы устройства распределитель 11 также поочередно выдает импульсы на первый,второй и т.д. выходы. Эти импульсыперебрасывают те триггеры 4, которые были возвращены в нулевое положение (И + 2)-м импульсом распределителя 11, в единичное состояние.Счетчики 6, которые были установленыв нулевое состояние импульсом с(И + 2)-го выхода распределителя 11в первом цикле, ведут счет поступающих на их входы импульсов. Приэтом на вход 1-го счетчика 6, всоответствующей которому -й строкематрицы 3 после первого цикла не было возвращено в исходное состояниег триггеров 4, поступит меньшее(на г) количество импульсов. Поэтому в общем случае некоторые изсчетчиков 6 после прохождения Мимпульсов распределителя 11 во втором цикле уже не достигнут состояния переполнения и отсчитывают только один импульс. Тем самым триггеры4 соответствующих столбцов матрицы3 по окончании второго цикла не будут возвращены в исходное нулевоесостояние, а сами эти счетчики небудут установлены в "0". Импульс с(Н + 1)-го выхода распределителя 11перебрасывает в нулевое положениетриггер 10, единичный сигнал с инверсного выхода которого поступаетна управляющий вход блока 8. Последний осуществляет поразрядноесравнение сигналов, поступающихна его первую и вторую группы информационных входов, и выдает на выходсигнал лишь при условии, что на обегруппы информационных входов поступают одинаковые сигналы,Работа устройство продолжаетсядо того момента, пока по окончаниикакого-то цикла у блока 8 на обоихгруппах информационных входов небудут одинаковые сигналы. Тогда блок8 выдает на выход сигнал, поступающий на вход генератора 12 и прекращающий его работу, Номера вершин,через которые проходят маршрут между двумя выбранными вершинами дерева, определяют по номерам счетчиков2510496, на выходах вторых разрядов которых присутствует потенциал переполнения,30 40 10 15 20 25 35 45 50 55 Формула изобретения Устройство для определения маршрута, содержащее матрицу из ХхИ моделей ветвей (где Х - число вершин дерева), каждая модель ветви выполнена в виде триггера, группу элементов ИЛИ по числу строк матрицы моделей ветвей, группу ключей по числу столбцов матрицы моделей ветвей, группу счетчиков по числу строк матрицы моделей ветвей и блок сравнения, каждый информационный вход первой группы которого подключен к выходу второго разряда соответствующего счетчика группы, о т л и ч а - ю щ е е.с я тем, что, с целью расширения функциональных возможностей за счет идентификации вершин, вошедших в заданный маршрут в него введены группа элементов И, группа триггеров, регистр, триггер, распределитель импульсов и генератор им пульсов, вход запуска которого является входом запуска устройства, а вход останова генератора импульсов подключен к выходу блока сравнения, выход генератора импульсов соединен с входом распределителя импульсов, М выходов которого подключены соответственно к входам установки в "1" триггеров одноименного столбца матрицы моделей ветвей, (М + 1)-й выход распределителя импульсов соединен с первыми входами элементов И группы и входом триггера,(И + 2)-й выход распределителя импульсов подключен к информационным входам ключей группы, управляющие входы которых соединены с выходами одноименных триггеров группы, выход каждого ключа группы подключен к входам установки в 0 всех триггеров одноименного столбца матрицы моделей ветвей и к установочному входу одноименного счетчика группы, выход первого разряда которого соединен с вторым входом одноименного элемента И группы, выход каждого элемента И группы подключен к входу одноименного триггера группы,. выход второго разряда каждого из счетчиков группы подключен к одноименному информационному разрядному входу регистра, разрядПоцпого комитета СССРий и открытий по делам изобрете13035, Москва, Ж,ушская наб Производственн лиграфическое предприятие, г,ужгород, ул.Проектна ные выходы которого подключены ксоответствующйм информационным входам второй группы блока сравнения,вход разрешения записи регистрасоединен с прямым выходом триггера,инверсный выход которого подключен к входу синхронизации блока сравнения, выход каждого элементаИЛИ группы соединен со счетным входом одноименного счетчика группывыход каждого 1, -го триггера моделей ветвей матрицы подключен к 1-мувходу 1 -го элемента ИЛИ группы