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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК ае (и) 4(51) G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЦТЗФ (21) 3534471/24-24 (22) 07.01.83 (46) 15.01.85. Бюл. Н 2 (72) -Д.Н.Чимитов, Ю.Ф.Мухопад и В.К.Попков (71) Восточно-Сибирский технологический институт (53) 681.333(088.8). (56) 1. Авторское свидетельство СССР

У 231903, кл. G 06 G 7/48, 1.967.

2. Васильев В.В., Додонов А.Г. Гибридные модели задач. оптимизации.

Киев, "Наукова Думка", 1974, с. 93, рис. 54(прототип). (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ НА .ГРАФЕ, содержащее модели ветвей, соединеннйе в соответствии с топологией, исследуемого графа, каждая из которых содержит входной и выходной триггеры, два элемента И, развязывающий диод, элемент НЕ, причем вход модели ветви соединен с первым единичным выходом входного триггера выход первого элемента И подключен к единичному входу выходного триггера, единичный выход которого соединен с анодом развязывающего диода, катод которого является выходом модели ветви и подключен через элемент НЕ к первому входу второго элемента И и нулевому входу входного триггера, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия и точности работы устройства н расширения его функциональных возможностей за счет получения упорядоченных номеров ветвей кратчайшего. пути, в него дополнительно введены триггер начала пути, триггер конца пути, аналоговый ключ, orраничительный резистор, шифратор, группа элементов И, стековая память, блок управления, содержащий генератор тактовых импульсов, первую и вторую группы элементов И, два регистра; два дешифратора, шифратор, реверсивный

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

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

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

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

И блока управления, выход третьего элемента И первой группы блока.управления подключен к первым входам шестого, седьмого, восьмого и девятого элементов И блока управления, выход четвертого элемента И первой группы блока управления соединен со вторыми входами третьего, четвертого и пятого элементов И блока управления, выход пятого элемента И первой группы блока управления подключен к первым входам десятого и одиннадцатого элементов И блока управления, выход шестого элемента И первой группы блока управления соединен с первым входом третьего элемента ИЛИ блока управления и вычитающим -входом реверсивного счетчика блока управления, нулевой выход второго дешифратора блока управления подключен ко вторым входам десятого и одиннадцатого элементов И блока управления, К -й выход (где Н вЂ” число дуг ветвей графа ) второго дешифратора блока управления ! соединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, выход первого элемента И блока управления соединен со вторым входом первого элемента ИЛИ блока управления, выход которого подключен к первому входу шифратора блока управления, выходы второго итретьего элементов И блокауправления соединены со входами четвертого элемента ИЛИ блока управления, выход которого подключен к суммирующему входу реверсивного счетчика блока управления и второму входу шифратора блока управления, выход ( шестого элемента И блока управления является четвертым выходом блока управления и подключен к третьему входу шифратора блока управления, выходы четвертого и седьмого эле!

434944

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

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

ИЛИ блока управления, выход которого является первым выходом блока управ" ления, выход десятого элемента И блока управления:соединен с нулевым

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

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

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

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

25 триггера, вход второй схемы И соединен .с выходом схемы НЕ, вход схемы НЕ соединен с катодом диода(2).

Недостатки данного устройства—

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

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

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

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

134944

1$

М

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

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

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

;элементов И блока управления, N -й . выход (где М вЂ” число дуг ветвей графа) второго дешифратора блока управления соединен со вторыми входами шестого, седьмого, восьмого и девятого элементов И блока управления, выход первого элемента И блока управления соединен со вторым входом первого элемента ИЛИ блока управления, выход которого подключен к первому. входу шифратора блока управления, выходы второго и третьего элементов И блока управления соединены со входами четвертого элемента ИЛИ блока управления, выход которого подключен к суммирующему входу реверсивного счетчика блока " управления и второму входу Шифратора блока управления, выход шестого элемента И блока управления является четвертым выходом блока управления и подключен к третьему входу

:шифратора блока управления, выходы четвертого и седьмого элементов И блока управления соединены соответственно со вторым и третьим входами третьего элемента ИЛИ блока управле- 40 ния, выход которого подключен к четвертоыу входу шифратора блока управления, выход девятого элемента

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

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

На фиг. 1 представлена стуктурная схема предлагаемого устройства; на фиг. 2 - функциональная схема модели ветви; на фиг. 3 — граф, для которого приводится описание работы устройства; на фиг. 4 — график, поясняющий принцип работы модели ветви;на фиг. 5 — временная диаграмма работы модели ветви; на фиг. 6 — микропрограмма работы устройства управления; на фиг, 7 — граф автомата, описываю.щий закон функционирования устройства управления согласно микропрограмме ,приведенной на фиг. 6; на фиг. 8— временная диаграмма работы генератора тактовых импульсов устройства. управления; на фиг. 9 — функциональная . схема устройства управления; на фиг. 10 — комбинаццонная схема форми" рования сигналов состояний; на фиг. 11 — комбинационная схема формирования сигналов унравления.

Устройство содвржит стековую память 1, блок управления 2, шифра тор" 3, "руппу элементов И 4, триггер

5 конца пути, ключ 6, модели ветвей 7 графа, триггер 8 начала пути, шины индикации 9.

Модель -ветви графа содержит регистр 10, цифроаналоговой преобразователь(ЦАП) 11, схему сравнения 12, интегратор 13, входной триггер 14, диод 15, триггер 16 состояния ветви; выходной триггер 17 элемент И

)8, элемент НЕ 19,элемент И 20, ключ 21, вход 22 модели ветви, информационный вход 23, выход 24 модели ветви, выход индикации 25, резисторы 26. Аналогичный резистор 27 имеет ключ 6.

Стековая память 1 имеет шину 28 вывода данных, входную шину 29 адреса, соединенную с третьим выходом блока управления, вход ЗО для сигнала записи(У ), поступающего с четвертого выхода блока управления

) вход 31 для сигнала чтения(У ), поступающего с пятого выхода блока управления . Блок управления 2 сос113494

SS тоит из реверсивного счетчика 32, являющегося.указателем стека, дешифратора 33, комбинационной схемы 34 формирования сигналов(Д изменений состояния автомата, комбинационной схемы 35 формирования управляющих сигиалоа(р;1, шифратора 36, рагистров 37 и 38, дешифратора 39, первой и второй групп элементов И 40 и 41, выхода 42 (X4) и 43 дешифратора 33, IÎ первого и,второго входов 44(XI(, 45 ,X2) блока управления 2, второго выхода 46(У ) р первого выхода 47(У ) блока управления 2, входа 48 "Пуск", линии задержки 49, генератора 50 15 тактовых импульсов и 2, шины 51 л сигналов 1 изменений состояния автомата, шины 52 сигналов(У1, У, У, У ) управления, триггера 53 отсутствия информации в стеке, триггера 54 пере- 2р полнения стека. Комбинационная схема

34 формирования сигналов изменений состояний автомата(фиг. 10)содержит элементы И 55-62, элемент ИЛИ 63-65.

Дешифратор 39 имеет выходы 66-71 (фиг. 9 и 10)сигналов 6 — g . Комбинационная схема 34(фиг. 10} имеет выходы 72-77 сигналов fg- Eg изменения состояний. автомата. Комбинат ционная схема 35 формирования управ, ляющих сигналов фйг. 11) содержит эле" менты И 78-80, элемент ИЛИ 81, выходы

82-85 сигналов(У,1, У, У, У ) управления.

На графике, поясняющем принцип . работы ветви(фиг. 4), через 01<,.U<

35 обозначены сигналы на выходе ЦАП 11, соответствующие разным кодам регистра 10, через UI1 обозначен сигнал на выходе интегратора l3 который является линейным напряжением с заданным углом наклона. На временной диаграмме(фиг. 5) через Ul обозначен сигнал на выходе элемента с номером К, Например, Lily — сигнал на выходе схемы сравнения 12.

Микропрограмма на фиг. 6 записана на структурно-функциональном языке.

В микропрограмме применены следующие сокращения:

ПрСПП вЂ” признак "Стек переполнен";

АрСпуст - признак "Стек пуст";

УС вЂ,указатель стека,, Ф

С УС) — содержимое ячейки с адресом равным указателю стека;

N — количество ячеек в стеке;

ШЗ (1 : nj- значение выходного и-разрядного кода на выходе шифратора 3;

4 8

Ш28(1: п1- и-разрядная шина 28 вывода из стековой памяти 1.

В микропрограмме индикаторы микроопераций и логических условий имеют следующие функциональные зна" чения:

У ) Тг8:=Π— установить в нуль триг1 гер 8;

У ) Тг5:=Π— установить в нуль триггер 5;

У ) УС:=УС-I — увеличить содержимое

1/

УС на "1";

У4) СИНУС):=ШЗ (I:и)- записать и-разрядный выходной код с шифратора . 3 в ячейку стека

1 с адресом равным УС;

У ) ПрСПП:=1 — установить в "I" ПрСПП;

У) ПрСПустр:=1 — установка в "1" ь)

ПрСПуст;

У ) УС:=УС-1 — уменьшить содержимое

-1)

УС на "l"

У) Ш28 fI:а):=С(УС)- внести С(УС) по шине 28;

Х1) Тг5 0 — проверка условия Tr5=0;

Xg) Тг8=0 — проверка условия Тг8=0;

Х УС= К - проверка условия УС=.Й;

Х ) УС=Π— проверка условия УС=О, - В микропрограмме1фиг. 6) входы вершин, следующих за операторными, отмечены символами Ао, а, а2, а, .а, а . Микропрограмма, приведенная на фиг. 6, служит основой для пере хода к графу функционирования устройства управления(фиг. 7).

На фиг. 7 узлы графа обозначают состояние автомата 1т.е. БУ), ветви графа обозначают переход из одного состояния в другое, причем в числителе надписи ветви пишутся логическое условие Х и сигнал состояния рт а в знаменателе - управляющие сигналы (операторы}У, Уе . Например, рассмотрим переход из состояния "2" в состояние "4". На ветви 2 4 нади

° j пись Х1 /y< р У< означает р что пеРе ход из состояния "2" в "4" возможен при выполнении условия Х9 и при наличии тактирующего сигнала состояния н ъ н л .2-, при этом на выходе комбинационной схемы 35 появляются управляющие сигналы У2, У .

Для синтеза схемы 34 использованы выражения функций переходов, которые получены иэ графа на фиг. 7;

1134944

10 р — ) = ") "e3 " "а "а5 ) и 5=rh "а0

Для синтеза схемы 35 использованы выражения управляющих сигналов, полученных нэ графа на фиг.7: и, lq ™ "а = 21 и л

Ця 4 аi а3

20 управления фиг. 6} . Состояние этих

В данном примере конкретного применения устройство рассчитано для работы на положительную логику, т.е. логической единице соответствует высокий положительный потенциал, логическому нулю — низкий(близкий к потенциалу общей шины}.

В каждой модели ветви триггер 14 принимает входной сигнал, триггер

17 выдает выходной сигнал модели ветви, элемент И .18 служит для блокировки при появлении высокого уровня в узле на выходе 24, элемент И 20 . †. для индикации ветви, диоды 15 моде- 3$ лей ветвей образуют элемент ИЛИ при соединении выходов моделей1 элемент

НЕ 19 - для индикации ветвй.

Нулевой вход триггера 14 соединен

40 с выходом 24 модели ветви, а выход элемента НЕ 19 соединен с единичным входом триггера 14 для того, чтобы отключить интегратор 13 при появлении сигнала единицы на выходе в узле

24. Интегратор 13, схема сравнения

13, регистр 10, ЦАП 1 1 предназначены для повышения быстродействия устройства.В модели дуги эти элементы обеспечивают цифровое управление величиной задержки появления сигнала единицы на выходе 24 относительно входа 22 (фиг. 5) .

Триггер 16 является триггером состояния ветви и предназначен для надежной работы элемента И 20, нредяазначенного для обеспечения работ — л 2 -"i""аi хг " ) з ХЗ" аг i

Pl л ) Л (* "а0 ) gg ас " "а + Х а

l\ / 1 л

3 "З "аа q Ч ь "4 "аф= о > Ч "а5

38 Х а% - 6 ° узла индикации. Триггер 17 не может выполнить непосредственно функцию триггера 16 — это снижает надежность работы второго элемента И 20. Аналоговый ключ 21 предназначен для надежной работы входного триггера 14 °

Резисторы 26 и 27 предназначены для устойчивой работы триггеров 17

"предыдущих ветвей в пути. Стековая память 1, блок управления 2, шифратор

3, группа элементов И 4, шина 9, триггер 5 конца пути, аналоговый ключ 6, триггер 8 начала пути предназначеньг для расширения функциональных возможностей — получения упорядоченных номеров дуг кратчайшего пути для вывода из устройства по шине .28.

Назначение триггеров 5 и 8 ясны из микропрограммы работы блока триггеров определяют следующие этапы работы устройства: (Tr8=0) h (Tr5=0) — начало процесса моделирования; (Tr8=0l < (Tr5=1) — конец процесса моделирования, начало процесса записи кратчайшего пути в стек; (Tr8 1)h (Tr5=1) - конец процесса записи кратчайшего пути; (Tr8=1) P (Tr5 0) — начало процесса вывода результата из стековой памяти по шине 28.

Кроме того, триггер 5 управляет ключом 6, который предназначен для подачи низкого уровня напряжения в узел Б. Триггер 5 открывает входные элементы И 4 для записи в стековую память 1 номеров Дуг кратчайшего пути. Шифратор 3 предназначен для

t преобразования кодов соответствующих дугам Кратчайшего пути.

Реверсивный счетчик 32(фиг. 9) служит указателем свековой памяти 1, дешифратор 33.предназначен для выборки ячейки из стековой памяти 1.

Выходы дешифратора 33 образуют шину 29 адреса. Регистры 37 и 38 предназначены для запоминания состояния автомата. Комбинационная схема 35 предназначена для генерирования управляющих сигналов У -У, комбинационная схема 34 предназначена для организации переходов автомата из одного состояния в другое.

11349

В исходном состоянии триггеры !

4, 17, 16, 5 установлены в нуль, на интегратор 13 заданы начальные нулевые условия, триггер 8 установлен в единицу низким потенциалом, который подан в узел А. Ключи 6 и ) 2 разом— кнуты. Значения длин ветвей записаны в соответствующие регистры 10 по шинам 23, на выходах ЦАП 11 устанавливаются постоянные напряжения

И;)

Значения содержимого счетчика 32 и регистра 38 равны нулю.

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

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

)О, ЦАП 11. Код длины ветви записывается по шине 23 в регистр 10, после чего на выходе ЦАП 11 устанав.ливается напряжение, пропорциональное коду регистра 10. Интегратор 13 вырабатывает линейно возрастающее напряжение(ЛВН)с заданным углом наклона .(фиг. 4) . Момент равенства напряжений на выходах интегратора 13 и

ЦАП 11 фиксирует схема сравнения 12.

Сигнал единицы со схемы сравнения

12 поступает на выход 24 модели ветви. ,Модели ветвей 7 соединяются согласно топологии графа(фиг. 11. 35

На вершину А модели графа(фиг. 1)подается положительный потенциал, который означает начало процесса моделирования. Сигнал логической единицы, появившийся на входе 22 модели ветви, появляется на выходе

24 модели ветви через интервал времени, пропорциональный коду длины

Ветви, который хранится в регистре

10(фиг. 4 и 5) . Такая цифроуправляе- 15 мая задержка обеспечивается схемой сравнения .12, регистром 10; ЦАП ll, интегратором 13. Линейно возрастающее напряжение на выходе интегратора 13 достг.ает значения напряжения на выходе ЦАП II через время,. пропорпиональное коду регистра 10 (фиг. 4). В момент, равенства напряжения на выходе интегратора 13 и на выходе ЦАП ll, на выходе схемы 55 сравнения 12 появляется сигнал логической единицы, которая проходит через открытый элемент И 18 и

44 устанавливает триггер 17 в единицу.

В узле 24 появляется "1". Появившийся в узле 24 сигнал логической единицы устанавливает в "0" триггеры

14, блокируя при этом единичные входы триггеров 14 через элементы

НЕ 19 всех ветвей, которые заходят (оканчиваются) в данном узле.

Таким образом, вовремя отключаются интеграторы 13 пройденных дуг;

Также блокируются элементы И 18, ветвей, заходящих в данную вершину.

После установки в I триггера 17 устанавливается в "1" триггер 16.

Таким образом, сигналы .логических единиц начинают распространяться по всей среде из моделей ветвей (фиг. )) .

При проявлении"!" в узле Б устанавливается в "1" триггер 5, который открывает элемент И группы 4, перед ает сигнал в:.блок управления 2 об окончании процесса моделирования в среде, о начале процесса индикации и записи наикратчайшего пути и замыкает ключ 6. В узле В появляется низкий потенциал, который означает начало процесса индикации и записи. Низкий потенциал имеется на выходах 24 у всех ветвей 7, окончивающихся в узле Б. Низкий потенциал, инвертируясь элементом HE 19, превращается в высокий потенциал и проходит надежно через элемент И

20 только у той ветви, у которой триггер. 16 установлен в "1".

Индикационный сигнал по проводу

25 поступает)шина 9) на соответствую- щий вход элемента И группы 4 и через шифратор 3 записывается в стек I, Одновременно сигнал логической единицы с выхода элемента И 20 включает ключ 21, который подает в предшествующий узел среды низкий уровень.

Процесс этот продолжается до тех пор, пока высокий уровень не появится в узле А и не установит триггер

8 в положение, которое означает

В конец записи кратчайшего пути- в стек

1. Таким образом, в стековой памяти

1 будут записаны номера ветвей, принадлежащих кратчайшему пути..

Микропрограмма работы блока уп" равления 2 (фиг. 6) полностью описывает работу устройства. При поступлении сигнала 2 )фиг. 9)на входыэлементов И 41 с генератора 50 сиги ,нал ьд„ появляется на одном из выходов 66-7! дешифратора 39 и поступа1О

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

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

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

13 11349 ет на один из входов схем 34 и 35.

В зависимости от значений логических условий(Х -Х )на входах 42 — 45 схема

34 .генерирует сигнал 1; следующего состояния автомата, который через шифратор 36 записывается в регистр

37. В зависимости от значений логических условий (Х -3ффиг. 1) и 91 на входах 44 и 45 блока управления 2, выходах 42 и 43, дешифратора 33 и сигналов (I - f ) на выходах 72-77 схемы 34 схема 35 генерирует управляющие сигналы(У1 -УВ) на выходах 30

31, 46, 47, 82, 83, 84, 85.

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

Предположим, что прототип выполнен на ИС серии К 155. Для этой серии предельная частота равна

5 Мгц и период последовательных импульсов .принимают равным 0,2 мкс.

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

Если максимальну1о длину ветви обозначим через .,то цена младшего зна чащего разряда равна L /1024.

Это равносильно моделировайию с точностью до 0,1Х, Рассмотрим предлагаемое устройство. 35

44 l4

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

=О, 1 мкс.

Тогда для обеспечения точности

0,1Ж время развертки напряжения

ЛВН от ОВ до И ы„„,д„на выходе интегратора 13 должно равняться

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

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

l l 34944

l 134944!!34944

jI34944

) 134944!

134944

1)34944

Фи8 Ю

Ж 88 7Р 44 43 92 7Й Ж

Фиг.М

ЯЩЗЩИ Заказ 1009l/42 TNPaa " ggg <, g умрррод,уа,йроактиаи, 4