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

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

ющим выходам первого регистра блока управления, входы которого соединены с выходами элементов И второй группы блока управления, вторые входы которых подключены к соответствующим выходам; второго регистра блока управления, выход первого элемента И первой группы блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления и является вторым выходом блока управления, выход второго элемента И первой группы блока управления соединен со вторыми входами первого и второго элементов И блока управления, выход третьего элемента И первой группы блока.управления подключен к первым входам шестого, седьмого, восьмого и девятого элементов И блока управления, выход четвертого элемента И первой группы блока управления соединен со вторыми входами третьего, четвертого и пятого элементов И блока управления, выход пятого элемента И первой группы блока управления подключен к первым входам десятого и одиннадцатого элементов И блока управления, выход шестого элемента И первой группы блока управления соединен с первым входом третьего элемента ИЛИ блока управления и вычитакнцим «входом реверсивного счетчика блока зшравления, нулевой выход второго дешифратора блока управления подключен ко вторым входам десятого и одиннадцатого элементов И блока управления,М й выход Ггде N - число дуг ветвей графа) второго дешифратора блока управления соединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, вьиод первого элемента И блока управления соединен со вторьм входом первого элемента ИЛИ блока управления, выход которого подключен к первому входу шифратора блока управления, выходы второго и третье го элементов И блока управления соединены со входами четвертого элемента 1ШИ блока управления, выход которого подключен к суммирующему ВХОДУ реверсивного счетчика блока управления и второму входу шифратора блока управления, выход ( шестого элемента И блока управления является четвертым выходом блока i управления и подключен к третьему входу шифр;атора блока управления, ;выходы четвертого и седьмого элементов И блока управления соединены соответственно со вторым и третьим входами третьего элемента ИЛИ блока управления, выход которого подключен к четвертому входу шифратора блока управления, выход девятого элемента И блока управления соединен с единичным входом триггера переполнения стековой памяти, выходы пятого и восьмого элементов И блока управлени соединены соответственно со вторьм и третьим входами второго элемента ИЛИ блока управления, выход которого является первым выходом блока управления, выхьд десятого элемента И блока управления соединен с нулевым

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

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ НА ГРАФЕ, содержащее модели ветвей, соединенные в , соответствии с топологией,исследуемого графа, каждая из которых содержит входной и выходной триггеры, два элемента И, развязывающий диод, элемент НЕ, причем вход модели ветви соединен с первым единичным выходом входного триггера выход первого элемента И подключен к единичному входу выходного триггера, единичный выход которого соединен с анодом развязывающего диода, катод которого является выходом модели ветви и подключен через элемент НЕ к первому входу второго элемента И и нулевому входу входного триггера, отличающееся тем, что, с целью повышения быстродействия и точности работы устройства и расширения его функциональных возможностей за счет полу- , чения упорядоченных номеров ветвей кратчайшего, пути, в него дополнительно введены триггер начала пути, триггер конца пути, аналоговый ключ, ограничительный резистор, шифратор, группа элементов И, стековая память, блок управления, содержащий генератор тактовых импульсов, первую и вторую группы элементов И, два регистра, два дешифратора, шифратор, реверсивный счетчик, триггер отсутствияинформации в стековой памяти, триггер переполнения стековой памяти, линию задержки, одиннадцать элементов И и ,четыре элемента ИЛИ, в каждую модель ветви дополнительно введены регистр цифроаналоговый преобразователь, схема сравнения, аналоговый ключ, ограничительный резистор, триггер состояния ветви и интегратор, причем «9 информационные входы регистров моделей ветвей являются информационными входами устройства, выход регистра каждой модели ветви соединен со входом цифроаналогового преобразователя, выход которого подключен к первому входу схемы сравнения, i второй вход которой соединен с ьыходом интеграто1)а, вход которого подключен к единичному выходу входного триггера модели ветви, выход DO 4аь схеъш сравнения соединен с первым входом первого элемента И модели to ветви, второй вход которого подклю4ib 4i чен к первому входу второго элемента И и второму единичному входу входного триггера модели ветви, единичный выход выходного триггера модели ветви соединен с единичным входом триггера состояния ветви, еднничнь } выход которого соединен со вторым входом второго элемента И модели ветви, выход которого является выходом индикации модели ветви и подключен к управляющему входу

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

Известно устройство для определения кратчайших путей на графе, соде)жащеё модели ветвей с источниками напряжения и диодами П

Однако это устройство сложно и не обеспечивает решения задачи с требуемой точностью.

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

Недостатки данного устройства низкое быстродействие |время необходимое для переполнения счетчика, может исчисляться тысячами машинных тактов , низкая надежность работы, отсутствие- возможности получить

упорядоченные номера дуг кратчайшего пути в памяти ЭВМ.

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

Эта цель достигается тем, что в - устройство для определения кратчайшего пути на графе, содержащее модели ветвей, соединенные в соответствии с топологией исследуемого графа, каждая из которых соДержит входной

и выходной триггеры, два элемента И, развязывающий диод, элемент НЕ, причем вход модели ветви соединен с первым единичным выходом входного триггера, выход первого элемента И подключен к единичному входу выходного триггера, единичный выход которого соединен с анодом развязывающего диода, катод которого является выходом модели ветви и подключен через

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

3

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

349444

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

10 стековой памяти, адресный вход которой соединен с третьим выходом блока управления, вход- записи и вход чтения - соответственно с четвертым и пятым выходами блока управления, а

I j информационные выходы являются выходами устройства, первые входы первого и второго элементов И блока управления объединены и являются первым входом блока управления,

jf. первые входы третьего,: четвертого и пятого элемеитов И блока, управления объединены и являются вторым входом блока управления, вход пуска устройства соединен с входом сброса

2J реверсивного счетчика, первого регистра блока управления и через .линию задержки с входом генератора тактовых импульсов первый и второй выходы которого соединены с первыми входами элемеитов И соответственно первой и второй групп блока управления, вторые входы элементов И первой группы блока управления соединены с соответствунмдими выходами первого дешифратора блока управления, входы которого подключены к соответствующим выходам первого регистра блока управления, входы которого соединены с выходами элемеитов И второй группы блока управ 0 ления, вторые вхсз1ды которых подключеш | к соответствующим выходам второго регистра блока управления, выход первого элемента И первой группы блока управления соединен с

45 первыми входами первого и Второго элементов ИЛИ блока управления и является вторым выходом блока управления, выход второго элемента И первой группы блока управления соединен со вторыми входами первого и элементов И блока управления, выход третьего;элемента И первой группы блока управления подключен к первю входам шестого, седь$5 мого, восьмого и девятого элементов И блока управления, выход четвертого элемента И первой группы блока управления соединен со вторыми входами третьего, четвертого и пятого элементов И блока управления, выход пятого элемента И первой группы блока управления подключен к первым входам десятого и одиннадцатого элементов И блока управления, выход шестого элемента И первой.группы блока управления соединен с первым входом третьего элемента ШШ блока управления и вычитающим входом ревер сивного счетчика блока управления, нулевой выход второго дешифратора блока управления подключен ко вторым входам десятого и одиннадцатого /элементов И блока управления,N -и ВЫХОД (гдеН - Число дуг ветвей графа)второго дешифратора блока управления соединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, выход первого элемента И блока управления соединен со вторым входом первого элемента ИЛИ блока управления, выход которого подключен к первому, входу шифратора блока управления, выходы второго и третьего элементов И блока управления соединены со входами четвертого элемента ИЛИ блока управления, выход которого подключен к суммирующему вхбду реверсивного счетчика блок управления и второму входу йифратора блока управления, выход шестого элемента И блока управления является четвертым выходом блока управления и подключен к третьему входу шифратора блока управления, выходы четвертого и седьмого элементов И блока управления соединены соответ;ственно со вторым и третьим входами третьего элемента ИЛИ блока управления, выход которого подключен к четвертому входу шифратора блока управления, выход девятого элемента И блока правления соединен с единичным входом триггера переполнения стековой памяти, выходы пятого и восьмого элементов И блока управлени соединены соответственно со вторым и третьим входами второго элемента ИЛИ блока управления, выход которого является первым выходом блока управлени выход десятого элемента И блока управления соединен с нулевым входом .шифратора блока управления и единичным входом триггера отсутствия инфор мации в стековой памяти, выход одиннадцатого элемента И блока управлени подключен к пятому входу шифратора 46 блока управления и является пятым выходом блока управления, выходы реверсивного счетчика блока управления соединены со входами второго дешифратора блока управления, -выходы которого являются третьим выходом блока управления, а выходы шифратора блока управления соединены с соответствующими входами второго регистра блока управления. На фиг. I представлена,стуктурная схема предлагаемого устройства; на фиг. 2 - функциональная схема модели ветви; на фиг. 3 - граф, для которого приводится описание работы устройства; на фиг. 4 - график, поясняющий принцип работы модели ветви;на фиг. 5 - временная диаграмма работы модели ветви; на фиг. 6 - микропро - рамма работы устройства управления; на фиг. 7 -, граф автомата, описывающий закон функционирования устройства управления согласно микропрограмме, приведенной на фигi 6; на фиг. 8 временная диаграмма работы генератора тактовых импульсов устройства, управления; на фиг. 9 - функциональная схема устройства управления; на фиг. 10 - комбинационная схема формирол аник сигналов-СОСТОЯНИЙ; на фиг. М- комбинационная схема формирования сигналов управления. Устройство содержит стековую память 1, блок управления 2, щифратор 3, труппу элементов И 4, триггер 5 конца пути, ключ 6, модели ветвей 7 графа, триггер 8 начала пути, шины индикации 9. модель ветви графа содержит регистр 10, цифроаналоговой преобра зователь(ЦАП)11, схему сравнения 12, интегратор 13, входной триггер 14, диод 15, триггер 16 состояния ветви, выходной триггер 17, элемент И 18, элемент НЕ 19,элемент И 20, ключ 21, вход 22 модели ветви, информационный вход 23, выход 24 модели ветви, выход индикаций 25, резисторы 26. Аналогичный резистор 27 имеет ключ 6. Стековая память 1 имеет шину 28 вывода данных, входную шину 29 адреса, соединенную с третьим вьрсодом блока управления, вход 30 для сигнала записи(у поступающего с четвертого выхода блока управления, вход 31 для сигнала чтения(yg), поступающего с пятого выхода блока управления .Блок управления 2 соетоит из реверсивного счетчика 32, являющегося.указателем стека, дешифраторй 33, комбинационной схемы 34 формирования сигналов |}1 изменений состояния автомата, комбинационной схемы 35 формирования управляющих сигналовГи;t, шифратора 36, регистров 37 и 38, дешифратора 39, первой и второй групп элементов И 40 и 41, выхода 42(Х) и 43 дешифратора 33, первого и .второго входов 44(X;(j , 45 (Х 5) блока управления 2, второго выхода 4б{У, , первого выхода 47(У2 блока управления 2, входа 48 Пуск, линии Задержки 49, генератора 50 тактовых импульсов и С , шины 51 сигналов i изменений состояния авто мата, шины 52 сигналов(У , У, У , У управления, триггера 53 отсутствия информации в стеке, триггера 54 пере полнения стека. Комбинационная схема 34 формирования сигналов изменения состояний автомата(фиг. Ю)содержит элементы И 55-62, элемент ИЛИ 63-65. Дешифратор 39 имеет выходы 66-71 (фиг. 9 и 10)сигналов ( с 5 . Комбинационная схема 34(фиг. 10 имеет выходы 72-77 сигналов изме- нения состояний.автомата. Комбинационная схема 35 формирования управляющих сигналов/Pir. 11)) содержит эле менты И 78-80, элемент ИЛИ 81, выход 82-85 сигналов(У,, У., У , У) управления. На графике, поясняющем принцип ,. работы вётви(фиг. 4), через обозначены сигналы на выходе ЦАП 11 соответствующие разным кодам регистра 10, через U15 обозначен сигнал на выходе интегратора 13, который является лнйейным напряжением с заданнь1м углом наклона. На временной диаграмме (фиг. 51 через U | обозначен сигнал на выходе элемента с номером Например, - сигнал на выходе cxe№ сравнения 52. Микропрограмма на фиг. 6 записан на структурно-функциональном языке. В микропрограмме применены следующи сокращения: ПрСПП признак Стек переполнен ; АрСпуст - признак Стек ус -,указатель стека :, (УС) - содержимое ячейки с адресом равным указателю стека; N - количество ячеек в стеке; ШЗ l : t|- значение выходного п-разрядного кода на выходе шифратора 3; 1 4 rJ- п-разрядная шина 28 вывода из стековой памяти 1. В микропрограмме индикаторы микроопераций и логических условий имеют следующие функциональные значения:У|) - установить в нуль триггер 8; У) - установить в нуль триггер 5; y/i) - увеличить содержимое УС на У) С (УС) | :п}- записать п-разр; дный выходной код с шифратора 3 в ячейку стека 1 с адресом равным УС; У ПрСПП: 1 -установить в I ПрСПП; 1 - установка в 1 njjCIIycTp ПрСПуст; У) -уменьшить содержимое УС на (УС)- внести С (УС) по 3) Ш28 I : л шине 28; Х( - проверка условия Х) - проверка условия Х. проверка условия УС.М ; Х) - проверка условия , -В микропрограмме фиг. 6}входы вершин, следующих за оп.ераторными, отмечены символами Ад, а, а, а, а, а. Микропрограмма, приведенная на фиг. 6, служит основой для перехода к -графу функционирования устройства управления(фиг. 7). На фиг. 7 узлы графа обозначают . состояние автомата (т.е. БУ), ветви графа обозначают переход из одного состояния в другое, причем в числителе надписи ветви пишутся логическое условие и сигнал состояния i-aj , а в знаменателе - управляюпще сигналы (операторы)у ,Уе, Например, рассмотрим переход из состояния 2 в состояние 4. На ветви 2,4 надпись X igj/yy, Уя означает, что переход из состояния 2 в 4- возможен при выполнении условия Х и при нали ии тактирующего сигнала состояния ; при этом на выходе комбннаой схемы 35 появляются управляющие сигналы У2, У. Для синтеза схемы 34 использованы выражения функций переходов, которые получены из графа на фиг. 7; 9 ./ . V л « ) J 2 I aИz ai J M }aaJ 5 4О4 Для синтеза схемы 35 использованы выражения управляющих сигналов полученных из графа на фиг.7: 4 ао) Ч2- ас J (j,--K,2a,-x,1ia,aj, , ,, , 46 4 a4--io, , Ijg Ig . В данном примере конкретного пр менения устройство рассчитано для работы на положительную логику, т. логической единице, соответствует высокий положительный потенциал, логическому нулю - низкий(близкий к потенциалу общей шины). В каждой модели ветви триггер 14 принимает входной сигнал, триггер 17 вьщает выходной сигнал модели ветви, элемент И .18 служит для блок ровки при появлении высокого уровня в узле на выходе 24, элемент И 20 для индикации ветви, диоды 15 моделей ветвей образуют элемент ИЛИ при соединении выходов моделейj Элемент НЕ 19 - для индикации ветви. Нулевой вход триггера 14 соедин с выходом 24 модели ветви, а выход элемента НЕ 19 соединен с единичны входом триггера 14 для того, чтобы отключить интегратор 13 при появле нии сигнала единицы на выходе в уз 24. Интегратор 13, схема сравнения 13, регистр 10, ЦАП 11 предназначе для повышения быстродействия устройства.В модели дуги эти элементы обес печивают цифровое управление величиной задержки появления сигнала единицы на выходе 24 относительно вх9Да 22 (фиг. 5). , Триггер 16 является триггером состояния ветви и предназначен для |1адежной работы элемента И 20, пред азначенного для обеспечения работ 4° узла индикации. Триггер 17 не может вьтолнить н епосредственно функцию триггера 16 - это снижает надежность работы второго элемента И 20, Аналоговый ключ 21 предназначен для надежной работы входного триггера 14. Резисторы 26 и 27 предназначены для устойчивой работы триггеров I7 цредьщущих ветвей в пути. Стековая память 1, блок управления 2, шифратор 3, группа элементов И 4, шина 9, триггер 5 конца пути, аналоговый ключ 6, триггер 8 начала пути предназначены для расширения функциональных возможностей - получения упорядоченных номеров дуг кратчайшего пути для вывода из устройства по шине 28. Назначение триггеров 5 и 8 ясны из микропрограммы работы блока управления(фиг. б) . Состояние этих триггеров определяют следующие этапы работы устройства: ()4 () - начало процесса моделирования; ( () - конец процесса моделирования, начало процесса записи кратчайшего пути в стек; ()А () - конец процесса записи кратчайшего пути; ()Л () - начало процесса вывода результата из стековой памяти по шине 28. Кроме того, триггер 5 управляет ключом 6, который предназначен для подачи низкого уровня напряжения в узел Б. Триггер 5 открывает входные элементы И 4 для записи в стековую память 1 номеров Дуг кратчайшего пути. Шифратор 3 предназначен для преобразования кодов соответствующих дугам Кратчайшего пути. Реверсивный счетчик 32(фиг. 9) служит указателем са ековой памяти 1, дешифратор 33 предназначен для выборки ячейки из стековой памяти 1. Выходы дешифратора 33 образуют шину 29 адреса. Регистры 37 и 38 предназначены для запоминания состояния автомата. Комбинационная схема 35 предназначена для генерирования управляющих сигналов У, -Yg , комбинационная схема 34 предназначена для организации переходов автомата из одного состояния в другое. в исходном состоянии триггеры 14, 17, 16, 5 установлены в нуль, на интегратор I3 заданы начальные нулевые успови, триггер 8 установлен в единицу низким потенциалом,кото рый подан в узел А Ключи 6 и 12 разомкнуты. Значения длин ветвей записаны в соответствующие регистры 10 по шинам 23, на выходах ЦАП 11 уста навливаются постоянные напряжения Значения содержимого счетчика 32 и регистра 38 равны нулю. Устройство работает следующим образбм. В качестве моделей ветвей испол зуется цифроуправляемые линии задержки время задержки соответствуе длине ветви. Задержка в модели ветви, соответствующая длине ветви обеспечивается интегратором 13, схемой сравнения 12, регистром 10, ЦАП 11. Код длины ветви записьшается по щтлне 23 в регистр 10, после чего на выходе ЦАП 11 устанав ливается напряжение, пропорциональн коду регистра 10. Интегратор 13 вы батывает линейно возрастающее напряжение (лвн) с заданным углом наклон (фиг. 4). Момент равенства напряжений на выходах интегратора 13 и ЦАП 11 фиксирует схема сравнения 12 Сигнал единицы со схемы сравнения 12 поступает на выход 24 модели вет ,Модели ветвей 7 соединяются согласн топологии графа (фиг. l). На вершину А модели графа (фиг. l подается положительный потенциал, который означает начало процесса моделирования. Сигнал логической единицы, появившийся на входе 22 модели ветви, появляется на выходе 24 модели ветви через интервал времени, пропорциональный коду длины /бетви, который хранится в регистре . 4 и 5) . Такая цифроуправляе мая задержка обеспечивается схемой сравне,ция 12, регистром 0,ЦАП П, интегратором 13. Линейно возрастающее напряжение на выходе интегратора 13 дости ает значения напряжения на выходе ЦАП И через время,, пропорциональное коду регистра 10 ((фиг. 4). Б момент равенства напряже ния на выходе интегратора 13 и на выходе ЦАП 11, на выходе схемы сравнения 12 появляется сигнал лог ческой единицы, которая проходит через открытый элемент И 18 и 42 устанавливает триггер 17 в единицу. В узле 24 появляется 1. Появившийся в узле 24 сигнал логической единицы устанавливает в О триггеры 14, блокируя при этом единичные входы триггеров 14 через элементы НЕ 19 всех ветвей, которые заходят (оканчиваются; в данном узле. Таким образом, вовремя отключаются интеграторы 13 пройденных дуг. Также блокируются элементы И 18, ветвей, заходящих в данную вершину. После установки в 1 триггера 17 устанавливается в 1 триггер 16. Таким образом, сигналы .логических единиц начинают распространяться по всей среде из моделей ветвей (фиг. 1) . При проявлении 1 в узле Б устанавливается Б 1 триггер 5, который открывает элемент И группы 4, передает сигнал в. .блок управления 2об окончании процесса моделирования в среде, о-начале процесса индикации и записи наикратчайшего пути и замыкает ключ 6. В узле В появляегся низкий потенциал, который означает начало процесса индикации и записи. Низкий потенциал имеется на выходах 24 у всех ветвей 7, окончивающихся в узле Б. Низкий потенциал, инвертируясь элементом НЕ 19, превращается в высокий потенциал и проходит надежно через элемент И 20 только у той ветви, у которой триггер. 16 установлен в 1. Индикационный сигнал по проводу 25 поступает(шина 9) на соответствующий вход элемента И группы 4 и через шифратор 3 записывается в стек I . Одновременно сигнал логической единиЫ с выхода элемента И 20 включает ключ 21, который подает в предшествующий узел среды низкий уровень. Процесс этот продолжается до тех пор, пока высокий уровень не появится в узле А и не установит триггер 8 в положение, которое означает конец записи кратчайшего пути в стек I. Таким образом, в стековой памяти I будут записаны номера ветвей, принадлежащих кратчайшему пути. Йикропрограмма работы блока управления 2(фиг. б)полностью описывает работу устройства. При поступлении сигнала С (фиг. 9)на входы элементов И 4I с генератора 50 сигнал {)л, появляется на одном из выходов 66-71 дешифратора 39 и поступа13

ет на один из входов схем 34 и 35. В зависимости от значений логически условий (Х( входах 42 - 45 схем 34 генерирует сигнал i следующего состояния автомата, который через шифратор 36 записывается в регистр 37. В зависимости от значений логических условий (х,-Х)(фиг. О и 9 на входах 44 и 45 блока управления 2, вьрсодах 42 и 43, дешифратора 33 и сигналов ( нз выходах 72-77 схемы 34 схема 35 генерирует управлющие сигналы(У(-У0| на выходах 30 31, 46, 47, 82, 83, 84, 85.

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

Предположим, что прототип выполнен на ИС серии К 155. Для этой серии предельная частота равна 5 Мг.ц и период последовательных импульсов принимают равным 0,2 мкс. При 10-разрядном счетчике для моделирования ветви максимальной длины потребуется 1024 импульсов, а время моделирования равно 204,8 мкс Если максимальну110 длину ветви обозначим через L ,то цена младшего значащего разряда равна .L /1024. Это равносильно моделированию с точностью до Ojl%.

Рассмотрим предлагаемое устройство. .

494414 ,

В настоящее время имеется много схем сравнения, имеющие времена установления выходного сигнала i от 0,003 до 0,1 мкс. 5 Возьмем наихудший случай i 0,1 мкс.

Тогда для обеспечения точности 0,1% время )азвертки напряжения ЛВН от ОБ до Hg m gjjHa выходе to интегратора 13 должно равняться

100 мкс. Задержка 100 мкс будет соответствовать максимальной длине ветви.

Значит в рассматриваемом примере е данного устройства быстродействие в два раза вьщ1е, чем у прототипа.

Рассмотренный пример соотвегствует аихудщему случаю. При той же элементной базе увеличение точности в 4 раза по сравнению с рассмотренным примером О2-разрядная сетка модели дуги приведет к вьшгрышу в I быстродействии в 8 раз, а при 18 разрядах более чем в500 раз.

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

Введение в устройство стековой

памяти, шифратора, триггера начала :пути, триггера-конца пути, аналогового ключа обеспечивает получение упорядоченных номеров ветвей кратчайшего пути, ЧТО; неосуществимо в

;прототипе.

W/

В //

6pgHH

t t

Фиг.4 6ыхо921 IffaSuxofe 4 Фи.$

Фиг.7

Фиг.д AV%/x

Фц.9

« 3 68 6В 70 44 4Ъ 72 74 76

Фи9.40