Устройство для определения кратчайшего пути на графе

(51) С 06 ПИСАНИЕ ИЗОБРЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ НИ 34471/24-24.01.85.Н.Чимитопковсточио-Сибиринститут1.333(088,8) Бюл. В 2ов, Ю.Ф.Мухопад огии те о ССС7. идетельств7/48, 196Додонов Ач. оптимиз1974, с Авторское сц 3, кл. С 06 С асильев В.В., ые модели зад Наукова Думка прототип),ации 93разочен к схе ран нени первого второй ервому второму о единен с первымнта И моделиоторого подклювторого элеменчному входудели ветви,одного триггеран с единичнымя ветви,соединенэлемента Ирого являетели ветвияющему входу вход ветв эле ход ен ка И ход еди входного триггер единичный выход в модели ветви соед входом триггера с единичный выход к со вторым входом модели ветви, вых ся выходом индикаи подключен к упр ых е остояни оторого второго од кото ции мод ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЦТЮ(54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ НА .ГРАФЕ, содержащее модели ветвей, соединенные в соответствии с топологией, исследуемого графа, каждая из которых содержит входной и выходной триггеры, два элемента И, развязывающий диод, элемент НЕ, причем вход модели ветви соединен с первым единичным выходом входного триггера выход первого элемента И подключен к единичному входу выходного триггера, единичный выход которого соединен с анодом развязывающего диода, катод которого является выходом модели ветви и подключен через элемент НЕ к первому входу второго элемента И и нулевому входу входного триггера, о т л и ч а ю - щ е е с я тем, что, с целью повышения быстродействия и точности работы устройства н расширения его функцио нальных возможностей за счет получения упорядоченных номеров ветвей кратчайшего. пути, в него дополнительно введены триггер начала пути, триггер конца пути, аналоговый ключ, ограничительный резистор, шифратор, группа элементов И, стековая память, блок управления, содержащий генератор тактовых импульсов, первую и вторую группы элементов И, два регистра; два дешифратора, шифратор, реверсивный счетчик, триггер отсутствия информации в стековой памяти, триггер переполнения стековой памяти, линию задержки, одиннадцать элементов И и четыре элемента ИЛИ, в каждую модель ветви дополнительно введены регистр, цифроаналоговый преобразователь, схема сравнения, аналоговый ключ, ограничительный резистор, триггер состояния ветви и интегратор, причем информационные входы регистров моделей ветвей являются информационными входами устройства, выход регистра каждой модели ветви соединен со входом цифроаналогового преоб вателя, выход которого подклю первому входу схемы сравнения, ,второй вход которой соединен е ьыходом интегратора, вход которого подключен к единичному выходу входного триггера модели ветви, выходаналогового ключа модели ветви, первый вход которого соединен со . входом модели ветви, а второй вход через ограничительный резистор - с шиной нулевого потенциала устройства, входы моделей ветвей, образую" щих начальный узел исследуемого графа, соединены со входами триггера начала пути и первым выходом блока управления, выходы моделей ветвей, образующих конечный узел исследуемо" го графа, соединены с единичным входом триггера конца пути и первым входом аналогового ключа, управляющий вход которого соединен с единичным выходом триггера конца пути, а второй вход через ограничительный резистор - с шиной нулевого потен" циала устройства, выходы индикации каждой модели ветви соединены с первыми входами элементов И группы, вторые входы которых объединены и подключены к нулевому выходу триггера конца пути и первому входу блока управления, второй вход которого соединен с выходом триггера начала пути, а второй выход - с нулевым входом .триггера конца пути, выходы элементов И группы подключены к соответствующим входам шифратора, выход которого соединен с информа-ционным входом стековой памяти, адресный вход которой соединен с третьим выходом блока управления, вход записи и вход чтения - соотввтственно с четвертым и пятым выходами блока управления, а информационные выходы являются выходами устройства, первые входы первого и второгоэлементов И блока управления объединены и являются первым входом блока управления, первые входы третьего, четвертого и пятого элементов Иблока управления объединены и являются вторым входом блока управления, вход пуска устройства соединен с входом сброса реверсивного счетчика,первого регистра блока управленияи через линию задержки с входомгенератора тактовых импульсов,первый и второй выходы которого соединены с первыми входами элементовИ соответственно первой и второйгруппы блока управления, вторыевходы элементов И первой группы блока управления соединены с соответствующими выходами первогодешифратора блока управления, входыкоторого подключены к соответству" ющим выходам первого регистра блока управления, входы которого соединены с выходами элементов И второй группы блока управления, вторые ,входы которых подключены к соответствующим выходам; второго регистра блока управления, выход первого элемента И первой группы блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления и является вторым выходом блока управления, выход второго элемента И первой группы блока управления соединен со вторыми входами первого и второго элементов И блока управления, выход третьего элемента И первой группы блока.управления подключен к первым входам шестого, седьмого, восьмого и девятого элементов И блока управления, выход четвертого элемента И первой группы блока управления соединен со вторыми входами третьего, четвертого и пятого элементов И блока управления, выход пятого элемента И первой группы блока управления подключен к первым входам десятого и одиннадцатого элементов И блока управления, выход шестого элемента И первой группы блока управления соединен с первым входом третьего элемента ИЛИ блока управления и вычитающим -входом ревер" сивного счетчика блока управления, нулевой выход второго дешифратора блока управления подключен ко вторым входам десятого и одиннадцатого элементов И блока управления, Н -й выход (где Н - число дуг ветвей графа ) второго дешифратора блока управлениясоединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, выход первого элемента И блока управления соединен со вторым входом первого элемента ИЛИ блока управления, выход которого подключен к первому входу шифратора блока управления, выходы второго итретьего элементовИ блокауправления соединены со входами четвертого элемента ИЛИ блока управления, выход которого подключен к суммирующему входу реверсивного счетчика блока управления и второму входу шифратора блока управления, выход шестого элемента И блока управления является четвертым выходом блока управления и подключен к третьему входу шифратора блока управления, выходы четвертого и седьмого эле434944 1 О ментов И блока управления соединенысоответственно со вторым и третьимвходами третьего элемента ИЛИ блокауправления, выход которого подключенк четвертому входу шифратора блокауправления, выход девятого элементаИ блока управления соединен с единичным входом триггера переполнениястековой памяти, выходы пятого ивосьмого элементов И блока управлениясоединены соответственно со вторыми третьим входами второго элементаИЛИ блока управления, выход которогоявляется первым выходом блока управ"ления, выход десятого элемента Иблока управления:соединен с нулевым Изобретение относится к вычислительной технике и может быть использовано при автоматизации управленияпотоками информации на сетях связи,управления структурой сетей связи,при решении транспортных задач.и решеиия комбинаторных задач на графах.Известно устройство для определения кратчайших путей на графе, содержащее модели ветвей с источникаминапряжения и диодами Ц .Однако это устройство сложно ине обеспечивает решения задачи стребуемой точностью,Наиболее близким к данному изобретению является устройство для. определения кратчайшего пути награфе на основе счетчиковых структурв котором модель ветви содержит навходе входной триггер, а на выходе -выходной триггер, две схемы И, диод,схему НЕ, причем вход модели ветвисоединен с единичным входом входноготриггера, а выход первой схемы Исоединен с единичным входом выходного25триггера, вход второй схемы И соединен .с выходом схемы НЕ, входсхемы НЕ соединен с катодом. диода 2. Недостатки данного устройства -1низкое быстродействие время необходимое для переполнения счетчика, может исчисляться тысячами машинных тактов, низкая надежность работы, отсутствие возможностй получить входом шифратора блока управления и единичным входом триггера отсутствия информации в стековой памяти, выход одиннадцатого элемента И блокаФуправления подключен к пятому входу шифратора блока управления и является пятым выходом блока управления, выходы реверсивного счетчика блока управления соединены со входами второго дешифратора блока управления,выходы которого являются третьимвыходом блока управления, а выходы шифратора блока управления соединены с соответствующими входами второго регистра блока управления. упорядоченные номера дуг кратчайшего пути в памяти ЭВИ.Цель изобретения - повышение быстродействия, надежности работы и расширение функциональных возможнос" тей устройства за счет получения упорядоченных номеров дуг кратчайшего пути графа. Эта цель достигается тем, что в " устройство для определения кратчайшего пути на графе, содержащее моде" ли ветвей, соединенные в соответствии с топологией исследуемого графа, каждая из которых соДержит входной и выходной триггеры, два элемента И, развязывающий диод, элемент НЕ, причем вход модели ветви соединен с пер" вым единичным выходом входного триггера, выход первого элемента И подключен к единичному входу выходного триггера, единичный выход которого соединен с анодом развязывающего диода, катод которого является выходом модели ветви и подключен через элемент НЕ к первому входу второго элемента И и нулевому входу входно-го триггера, дополнительно введены триггер начала пути, триггер конца пути, аналоговый ключ, ограничительный резистор, шифратор, группа элементов И, стековая память, блок управления, содержащий генератор тактовых импульсов, первую и вторую группы элементов И, два регистра, 3два дешифратора, шифратор, реверсивный счетчик, триггер отсутствия информации в стековой памяти, триггер переполнения стековой памяти, линию задержки, одиннадцать элементов И и четыре элемента ИЛИ, в каждую модель ветви дополнительно введены регистр, цифроаналоговый преобразователь, схема сравнения, аналоговый ключ, ограничительный резистор, триггер состояния ветви и интегратор, причем информационные входы регистров моделей ветвей являются информационными входами устрой . ства, выход регистра каждой модели ветви соединен со входом цифроаналогового преобразователя, выход которого подключен к первому входу схемы сравнения, второй вход которой соединен с выходом интегратора, вход которого подключен к единичному выходу входного триггера модели ветви, выход схемы сравнения соединен с первым входом первого элемента И модели ветви,. второй вход которого подключен к первому входу второго элемента И и второму единичному входу входного триггера модели ветви, единичный выход выходного триггера модели ветви.соединен с единичным входом триггера состояния ветви, единичный выход которого соединен со вторым входом второго элемента И модели ветви, выход которого является выходом инди. кации модели ветви и подключен к управляющему входу аналогового ключа модели ветви, первый, вход которого соединен со входом модели ветви, а второй вход через ограничительный резистор - с шиной нулевого потенциала устройства, "входы моделей ветвей, образующих начальный узел исследуемого графа, соединены со входами триггера начала пути и первым выходом блока управления, выходы моделей ветвей, образующих конечный узел исследуемого графа, соединены с единичныи входом триггера конца пути и первым входои аналогового . ключа, управляющий вход которого соединен с единичныи выходои триггера конца пути, а второй вход через ограничительный резистор - с шиной нулевого потенциала устройства, выходы индикации каждой модели ветви соединены с первыми входами элементов И группы, вторые входы которых объединены и подключенык134944 10 15 М 35 50 55 нулевому выходу триггера конца пути и первому входу блока управления, второй вход которого соединен с выходом триггера начала пути, а второй выход - с нулевым входои триггера конца пути, выходы элементов И группы подключены к соответствующим входам шифратора, выход которого соединен с информационным входом стековой памяти, адресный вход которой соединен с третьии выходом блока управления, вход записи и вход чтения - соответственно с четвертым н пятым выходаии блока управления, а информационные выходы являются выходами устройства, первые входы первого и второго элементов И блока управления объединены и являются первым входом блока управления, первые входы третьегочетвертого и пятого элементов И блока. управления объединены и являются вторым входом блока управления, вход пуска устройства соединен с входом сброса реверсивного счетчика, первого регистра блока управления н черезлинию задержки с входом генераторатактовых йипульсов, первый и второй выходы которого соединены с первыми входами элементов И соответ" ственно первой и второй групп блока управления, вторые входы элементов И первой группы блока управления соединены с соответствующими выходамн первого дешифратора блока управления, входы которого подключены к соответствующим выходам первого регистра блока управления, входы которого .соединены с выходами элементов И второй группы блока управления, вторые входы которых подключены к соответствующим выходам второго регистра блока управления, выход первого элемента И первой группы блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления и является вторым выходом блока управления, выход второго элемента И первой. группы блока управления соединен со вторыми входаии первого и второго элементов И блока управления, выход третьего элемента И . первой группы блока управления подключен к первым входаи шестого, седьмого, восьмого и девятого элементов И блока управления, выход четвертого элемента И первой группы блока управления соединен со вторыми входа11349 ми третьего, четвертого и пятого элементов И блока управления, выход пятого элемента И первой группы блока управления подключен к первым входам десятого и одиннадцатого элементов И блока управления, выход шестого элемента И первой. группы блока управления соединен с первым входом третьего элемента ИЛИ блока управления и вычитающим входом ревер сивного счетчика блока управления, нулевой выход второго дешифратораблока управления подключен ко вторым входам десятого и одиннадцатого ;элементов И блока управления, М -й . выход (где 11 - число дуг.ветвей графа) второго дешифратора блока управления соединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, выход первого элемента И блока управления соединен со вторым входом первого элемента ИЛИ блока управления, выход которого подключен к первому. входу шифратора блока управления, выходы второго и третьего элементов И блока управления соединены со входами четвертого элемента ИЛИ блока управления, выход которого подключен к суммирующему входу реверсивного счетчика блока "управления и второму входу Шифратора блока управления, выход шестого элемента И блока управления является четвертым выходом блока управления и подключен к третьему входу шифратора блока управления, выходы четвертого и седьмого элементов И блока управления соединены соответственно со вторым и третьим входами третьего элемента ИЛИ блока управле- фО ния, выход которого подключен к четвертоыу входу шифратора блока управления, выход девятого элемента И блока управления соединен с еди-. ничнымвходом триггера переполнения 45 стековой памяти, выходы пятого и восьмого элементов И блока управления соединены соответственно со вторым и третьим входами второго элемента ИЛИблока управления, выход которого явля- Ыется первым выходом блока управления,выход десятого элемента И блока управления соединен с нулевым входом, шифратора блока управления и единичным входом триггера отсутствия инфор-бмации в стековой памяти, выход один 1надцатого элемента И блока управленияподключен к пятому входу шифратора 44 6,блока управления и является пятым выходом блока управления, выходы реверсивного счетчика блока управления соединены со входами второго дешифратора блока управления, выходы которого являются третьим выходом блока управления, а выходы шифратора блока управления соединены с соответствующими вхОдамн второго регистра блока управления.На фиг.представлена.стуктурная схема предлагаемого устройства; на фиг. 2 - функциональная схема модели ветви; на фиг. 3 - граф, для которого приводится описание работы устройства; на фиг. 4 - график, поясняющий принцип работы модели ветви;на фиг. 5 - временная диаграмма работы модели ветви; на фиг. 6 - микропрограмма работы устройства управления; на фиг, 7 - граф автомата, описываю.щий закон функционирования устройства управления согласно микропрограмме ,приведенной на фиг. 6; на фиг. 8 - временная диаграмма работы генератора тактовых импульсов устройства. управления; на фиг. 9 - функциональная . схема устройства управления; на фиг, 10 - комбинаццонная схема форми" рования сигналов".состояний; на фиг. 11 - комбинационная схема формирования сигналов унравления.Устройство содвржит стековую память 1, блок управления 2, шифратор" 3, группу элементов И 4, триггер 5 конца пути, ключ 6, модели ветвей 7графа, триггер 8 начала пути, шины индикации 9.Модель ветви графа содержит регистр 1 О, цифроаналоговой преобразователь(ЦАП) 11, схему сравнения 12, интегратор 13, входной триггер 14, диод 15, триггер 16 состояния ветви; выходной триггер 17, элемент И18, элемент НЕ 19,элемент И 20, ключ 21, вход 22 модели ветви, информационный вход 23, выход 24 модели ветви, выход индикации 25, резисторы 26. Аналогичный резистор 27 имеет ключ 6. Стековая память 1 имеет шину 28 вывода данных, входную шину 29 адреса, соединенную с третьим выходом блока управления, вход ЗО для сигнала записи(У, поступающего с четвертого выхода блока управления) вход 31 для сигнала чтенияУ), поступающего с пятого выхода блока управления . Блок управления 2 сос13494 тоит из реверсивного счетчика 32, являющегося.указателем стека, дешифратора 33, комбинационной схемы 34 формирования сигналов 1 Д изменений состояния автомата, комбинационной 5 схемы 35 формирования управляющих сигналовр;1, шиФратора 36, рагистров 37 и 38, дешифратора 39, первой и второй групп элементов И 40 и 41, выхода 42,Х 4) и 43 дешифратора 33, 10 первого и,второго входов 44,Х) р 45 Х 2) блока управления 2, второго выхода 46 У) р первого выхода 47(У) блока управления 2, входа 48 "Пуск", линии задержки 49, генератора 50 15 тактовых импульсови 2 , шины 51лсигналов 1 изменений состояния автомата, шины 52 сигналов(У 1, Ур У, Ут) управления, триггера 53 отсутствия информации в стеке, триггера 54 пере р полнения стека. Комбинационная схема 34 формирования сигналов изменений состояний автомата(фиг. 10)содержит элементы И 55-62, элемент ИЛИ 63-65. Дешифратор 39 имеет выходы 66-71 (фиг. 9 и 10)сигналов а в. Комбинационная схема 34(фиг. 10) имеетвыходы 12-77 сигналов 1- 1 изменения состояний, автомата. КомбинаГ ционная схема 35 формирования управ, ляющих сигналов фйг, 11 Г содержит эле" менты И 78-80, элемент ИЛИ 81, выходы82-85 сигналов(У,1 р У, У р У.1 Управления.На графике, поясняющем принципрабогы ветви(фиг. 4), через О,.р35 обозначены сигналы на выходе ЦАП 11, соответствующие разным кодам регистра 10, через 01 обозначен сигнал на выходе интегратора 13, который является линейным напряжением с заданным углом наклона. На временной диаграммефиг. 5) через О обозначен сигнал на выходе элемента с номером К, Например, 0 - сигнал на выходе схемы сравнения 12. Микропрограмма на фиг. 6 записана на структурно-функциональном языке. В микропрограмме применены следующие сокращения:БО ПРСПП - признак "Стек переполнен"; АрСпуст - признак "Стек пуст"; УС в ,указатель стекаФрС УС) - содержимое ячейки с адресом равным указателю стека;55 Н - количество ячеек в стеке; ШЗ 11 : п- значение выходного и-разрядного кода на выходе шифратора 3,4 8Ш 281: г- и-разрядная шина 28 вывода из стековой памяти 1.В микропрограмме индикаторы микроопераций и логических условий имеют следующие функциональные зна" чения:У ) Тг 8:=0 - установить в нуль триггер 8;У) Тг 5:=0 - установить в нуль триггер 5;У ) УС:=УС- увеличить содержимое /УС на "1";У 4) СИНУС):=ШЗ :п 1- записать и-разрдный выходнойкод с шифратора. 3 в ячейку стека1 с адресом равным УС; УД ПРСПП:=1 - установить в ПрСПП; У) ПРСПустр:=1 - установка в "1" ь)ПРСПуст; У ) УС:=УС- уменьшить содержимое )УС на "1"У) Ш 28 11: а: =СУС)- внести С ,УС) пошине 28; Х) Тг 5 0 - проверка условия Тг 5=0; Ху) Тг 8=0 - проверка условия Тг 8=0 ра Х УС= 11 в проверка условия УС=.Й; Х 4) УС=О - проверка условия УС=О,. В микропрограммефиг. 6) входы вершин, следующих за операторными, отмечены символами Ао, ар а 2 р а, ар а. Микропрограмма, приведенная на фиг. 6, служит основой для перегхода к графу функционирования устройства управленияфиг. 7). На фиг. 7 узлы графа обозначают состояние автомата т.е. БУ), ветви графа обозначают переход из одного состояния в другое, причем в числителе надписи ветви пишутся логическое условие Хи сигнал состояния гта в знаменателе - управляющие сигналы операторы)У р Уе а Например, рассмотрим переход из состояния "2 п в состояние "4". На ветви 2 4 над рлись Х 1 /ур у 2 означает что переход из состояния "2" в "4" возможен при выполнении условия Х 9 и при наличии тактирующего сигнала состояния 1 ън Л.2- при этом на выходе комбинационн 3 й схемы 35 появляются управляющие сигналы У 2, Уд. Для синтеза схемы 34 использованывыражения функций переходов, которыеполучены иэ графа на фиг. 7;Для синтеза схемы 35 использованы выражения управляющих сигналов, полученных нэ графа на фиг.7: лХьа а 20 управленияфиг, 6) . Состояние этих В данном примере конкретного при.менения устройство рассчитано для работы на положительную логику, т.е. логической единице. соответствует высокий положительный потенциал, логическому нулю - низкий(близкий к потенциалу общей шины). В каждой модели ветви триггер 14 принимает входной сигнал, триггер 17 выдает выходной сигнал модели ветви, элемент И .18 служит для блокировки при появлении высокого уровня в узле на выходе 24, элемент И 20 . в . для индикации ветви, диоды 15 моде лей ветвей образуют элемецт ИЛИ при соединении выходов моделей 1 элемент НЕ 19 - для индикации ветвй. Нулевой вход триггера 14 соединен4 ф с выходом 24 модели ветви, а выход элемента НЕ 19 соединен с единичным входом триггера 14 для того, чтобы отключить интегратор 13 при появлении сигнала единицы на выходе в узле45 24. Интегратор 13, схема сравнения 13, регистр 10, ЦАП 1 предназначены для повышения быстродействия устройства.- В модели дуги эти элементы обеспечивают цифровое управление величиной задержки появления сигнала единицы на выходе 24 относительно входа 22 (фиг. 5).Триггер 16 является триггером состояния ветви и предназначен для надежной работы элемента И 20, нред- яазначенного для обеспечения работ лХ 4оа; 1="ао+ "ал2 фХ "аф "г оъХаг,Ъл л - Лл г 1 л3 "Ъ "аа р Ч 6 "4 "аф= оЧ ф "а 538 "ХФ фа% 5узла индикации. Триггер 17 не может выполнить непосредственно функцию триггера 16 - это снижает надежность работы второго элемента И 20. Аналоговый ключ 21 предназначен для надежной работы входного триггера 14Резисторы 26 и 27 предназначены для устойчивой работы триггеров 17 "цредыдущих ветвей в пути. Стековая память 1, блок управления 2, шифратор 3, группа элементов И 4, шина 9, триггер 5 конца пути, аналоговый ключ 6, триггер 8 начала пути предназначеньг для расширения функциональных возможностей - получения упорядоченных номеров дуг кратчайшего пути для вывода из устройства по шине 28.Назначение триггеров 5 и 8 ясны из микропрограммы работы блока триггеров определяют следующие этапы работы устройства:(Тг 8=0) (Тг 5=0) - начало процессамоделирования; (Тг 8=0 Ь 4 (Тг 5=1) - конец процессамоделирования,начало процессазаписи кратчайшего пути в стек; (Тг 81)1 (Тг 5=) - конец процессазаписи кратчайшего пути; (Тг 8=1)(Тг 5 0) - начало процессавывода результатаиз стековой памятипо шине 28. Кроме того, триггер 5 управляет ключом 6, который предназначен для подачи низкого уровня напряжения в узел Б. Триггер 5 открывает входные элементы И 4 для записи в стековую память 1 номеровДуг кратчайшего пути. Шифратор 3 предназначен для преобразования кодов соответствующих дугам Кратчайшего пути.Реверсивный счетчик 32(фиг. 9) служит указателем свековой памяти 1, дешифратор 33 предназначен для выборки ячейки из стековой памяти 1. Выходы дешифратора 33 образуют шину 29 адреса. Регистры 37 и 38 предназначены для запоминания состояния автомата. Комбинационная схема 35 предназначена для генерирования управляющих сигналов У -У, комбинационная схема 34 предназначена дляорганизации переходов автомата из одного состояния в другое.11349 В исходном состоянии триггеры4, 17, 16, 5 установлены в нуль,на интегратор 13 заданы начальныенулевые условия, триггер 8 установ лен в единицу низким потенциалом, который подан в узел А, Ключи 6 и 12 разом -кнуты. Значения длин ветвей записаны в соответствующие регистры 1 Опо шинам 23, на выходах ЦАП 11 устанавливаются постоянные напряжения"ю)Значения содержимого счетчика 32и регистра 38 равны нулю.Устройство работает следующимобразбм. 15В качестве моделей ветвей исполь-,зуется цифроуправляемые линии задержки время задержки соответствуетлдлине ветви. Задержка в моделиветви, соответствующая длине ветви,обеспечивается интегратором 13,схемой сравнения 12, регистром10, ЦАП 11. Код длины ветви записывается по шине 23 в регистр 10,после чего на выходе ЦАП 11 устанав.ливается напряжение, пропорциональноекоду регистра 10, Интегратор 13 вырабатывает линейно возрастающее напряжениеЛВН)с заданным углом наклона.(фиг, 4) . Момент равенства напряжений на выходах интегратора 13 иЦАП 11 фиксирует схема сравнения 12.Сигнал единицы со схемы сравнения12 поступает на выход 24 модели ветви.,Модели ветвейсоединяются согласнотопологии графа(фиг. 11. Э 5На вершину А модели графафиг. 1).подается положительный потенциал,который означает начало процессамоделирования. Сигнал логическойединицы, появившийся на входе 22модели ветви, появляется на выходе24 модели ветви через интервал времени, пропорциональный коду длиныВетви, который хранится в регистре10(фиг, 4 и 5) . Такая цифроуправляемая задержка обеспечивается схемойсравнения 12, регистром 1 О; ЦАП 11,интегратором 13, Линейно возрастающее напряжение на выходе интегратора 13 достг.ает значения напряжения на выходе ЦАП 11 через время,.пропорпиональное коду регистра 1 О(фиг. 4). В момент, равенства напряжения на выходе интегратора 13 и навыходе ЦАП 11, на выходе схемы 55сравнения 12 появляется сигнал логической единицы, которая проходитчерез открытый элемент И 18 и 44 12устанавливает триггер 17 в единицу.В узле 24 появляется "1". Появившийся в узле 24 сигнал логической единицы устанавливает в "0" триггеры14, блокируя при этом единичныевходы триггеров 14 через элементыНЕ 19 всех ветвей, которые заходят(оканчиваются в данном узле.Таким образом, вовремя отключаются интеграторы 13 пройденных дуг;Также блокируются элементы И 8,ветвей, заходящих в данную вершину.После установки в 1 триггера 17устанавливается в "1" триггер 16,Таким образом, сигналы .логическихединиц начинают распространятьсяпо всей среде из моделей ветвейфиг. 1) .При проявлении "1" в узле Б устанавливается в "1" триггер 5, которыйоткрывает элемент И группы 4, передает сигнал в:.блок управления 2 обокончании процесса моделирования всреде, о начале процесса индикациии записи наикратчайшего пути изамыкает ключ 6, В узле В появля-ется низкий потенциал, которыйозначает начало процесса индикации изаписи. Низкий потенциал имеется навыходах 24 у всех ветвей 7, окончивающихся в узле Б. Низкий потенциал, инвертируясь элементом НЕ 19,превращается в высокий потенциали проходит надежно через элемент И20 только у той ветви, у которойтриггер. 16 установлен в "1",Индикационный сигнал по проводу25 поступаетшина 9) на соответствую-щий вход элемента И группы 4 и черезшифратор 3 записывается в стек 1,Одновременно сигнал логической единицы с выхода элемента И 20 включаетключ 21, который подает в предшествующий узел среды низкий уровень.Процесс этот продолжается до техпор, пока высокий уровень не появит"ся в узле А и не установит триггер8 в положение, которое означаетВконец записи кратчайшего пути в стек1. Таким образом, в стековой памяти1 будут записаны номера ветвей,принадлежащих кратчайшему путиМикропрограмма работы блока уп"равления 21 фиг. 6)полностью описывает работу устройства. При поступлении сигналафиг, 9)на входыэлементов И 41 с генератора 50 сигл,нал ьдпоявляется на одном из выходов 66-7 дешифратора 39 и поступа1 О Рассмотренный пример соотвешет. - вует наихудшему случаю. При той же элементной базе ,увеличение точности в 4 раза по сравнению с рассмотренным примером 112-разрядная сетка модели дуги приведет к выигрышу в , быстродействии в 8 раз, а при 18разрядах более чем в 500 раэ.IИспользование изобретения расширяет функциональные возможности устройства.Введение в устройство стековой памяти, шифратора, триггера начала .пути, триггера конца пути, аналогового ключа обеспечивает получение упорядоченных номеров ветвей кратчайшего пути, что, неосуществимо в прототипе. 13 11349 ет на один из входов схем 34 и 35. В зависимости от значений логических условийХ-Х )на входах 42 - 45 схема 34 генерирует сигнал 1; следующего состояния автомата, который через шифратор 36 записывается в регистр 37. В зависимости от значений логических условий (Х -ффиг. 11 и 91 на входах 44 и 45 блока управления 2, выходах 42 и 43, дешифратора 33 и сигналов (1 - 1 Д на выходах 72-77 схемы 34 схема 35 генерирует управляющие сигналы(У 1 -Ув) на выходах 30 31, 46, 47, 82, 83, 84, 85.Использование предлагаемого устройства для определения кратчайшего пути на графе позволяет обеспечить всравнении с прототипом повышение быстродействия и точности работы устройства.20Предположим, что прототип вьптолнен на ИС серии К 155. Для этой серии предельная частота равна 5 Мгц и период последовательных импульсов .принимают равным 0,2 мкс. При 10-разрядном счетчике для моделирования ветви максимальной длины потребуется 1024 импульсов, а время моделирования равно 204,8 мкс,Если максимальну 1 о длину ветви обозначим через 1 ,то цена младшего значащего разряда равна 1. /1024. Это равносильно моделировайию с точностью до 0,13.Рассмотрим предлагаемое устройство. 35 44 14В настоящее время имеется многосхем сравнения, имеющие времена установления выходного сигнала 1от 0,003 до 0,1,мкс.,Возьмем наихудший случай=0,1 мкс,Тогда для обеспечения точности0,17 время развертки напряженияЛВН от ОВ до Ивы,она выходеинтегратора 13 должно равняться100 мкс, Задержка 100 мкс будет со.ответствовать максимальной длиневетви.Значит в рассматриваемом примереданного устройства быстродействиев два раза вышее, чем у прототипа.