Пристрій для моделювання графів
Номер патенту: 86039
Опубліковано: 25.03.2009
Автори: Баранов Георгій Леонідович, Жуков Ігор Анатолійович, Мартинова Оксана Петрівна, Баранов Володимир Леонідович
Формула / Реферат
1. Пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить три регістри зсуву, суматор, комутатор, два тригери, першу групу з m тригерів, де m - кількість гілок вузла графа, три групи з m елементів І, два елемента І, чотири елементи АБО і два ключі, причому перша група виходів блока керування з'єднана з першими входами першої і другої груп елементів І, інформаційні входи з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І, виходи яких з'єднані з входами першого елемента АБО, вихід першого регістра зсуву з'єднаний із своїм інформаційним входом і з першим інформаційним входом суматора, другий інформаційний вхід якого з'єднаний з виходом першого елемента АБО, перший і другий інформаційні входи комутатора з'єднані з виходами другого і третього регістрів зсуву, другий вихід блока керування з'єднаний з першим входом другого елемента АБО, вихід якого з'єднаний з входами скидання першої групи тригерів, третій вихід блока керування з'єднаний з входами скидання першого тригера і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом першого елемента АБО, вихід першого елемента І з'єднаний з встановлювальним входом першого тригера, прямий вихід якого з'єднаний з першим входом другого елемента І, четвертий вихід блока керування з'єднаний з другим входом другого елемента І і з входом скидання другого тригера, прямий вихід якого з'єднаний з керуючим входом комутатора, п'ятий вихід блока керування з'єднаний з керуючим входом першого регістра зсуву, індикаційні входи з першого по m-й моделі вузла з'єднані відповідно з першого по m-й входами третього елемента АБО, m+1-й вхід якого з'єднаний з виходом першого ключа, перший вхід другого ключа з'єднаний з шостим виходом блока керування, встановлювальний вхід першого регістра зсуву з'єднаний з сьомим виходом блока керування, восьмий вихід якого з'єднаний з встановлювальним входом другого регістра зсуву, входи синхронізації першого, другого і третього регістрів зсуву з'єднані з дев'ятим виходом блока керування, десятий вихід якого з'єднаний з входом блокування переносу суматора, вихід комутатора з'єднаний з інформаційним входом другого регістра зсуву, вихід четвертого елемента АБО з'єднаний з інформаційним виходом моделі вузла, виходи другої групи елементів І з'єднані відповідно з встановлювальними входами першої групи тригерів, прямі виходи яких з'єднані відповідно з першими входами третьої групи елементів І, вихід третього елемента АБО з'єднаний з другими входами третьої групи елементів І, виходи яких з'єднані з індикаційними виходами моделі вузла, інформаційний вхід третього регістра зсуву з'єднаний з виходом суми суматора, який відрізняється тим, що додатково введений блок багатошляхової маршрутизації, а в модель вузла додатково введені блок оптимізації, друга група з m тригерів, де m - кількість гілок вузла графа, третій тригер, третій і четвертий елементи І, п'ятий елемент АБО, група з m елементів індикації, причому перший і другий інформаційні входи блока оптимізації з'єднані відповідно з виходом суми суматора та з виходом комутатора, третій вихід блока керування з'єднаний з входом скидання блока оптимізації, керуючий вхід якого з'єднаний з виходом другого елемента І, восьмий вихід блока керування з'єднаний з входом блокування блока оптимізації, вихід якого з'єднаний з входом скидання блока керування та з встановлювальними входами другого і третього тригерів, треті входи першої групи елементів І з'єднані відповідно з інверсними виходами другої групи тригерів, другий вихід блока керування з'єднаний з першим входом п'ятого елемента АБО, вихід якого з'єднаний з входом скидання третього тригера, другий вихід блока керування з'єднаний з входами скидання другої групи тригерів і з першим входом блока багатошляхової маршрутизації, перший вихід якого з'єднаний з керуючим входом блока керування, виходи третьої групи елементів І з'єднані відповідно з входами групи елементів індикації і з встановлювальними входами другої групи тригерів, вихід блока оптимізації з'єднаний з другими входами другої групи елементів І і з другим входом другого елемента АБО, прямий вихід третього тригера з'єднаний з першим входом третього елемента І, другий вхід якого з'єднаний з виходом комутатора, входи четвертого елемента АБО з'єднані з виходами третього і четвертого елементів І, перший вихід другого ключа з'єднаний з першим входом четвертого елемента І, другий вхід якого з'єднаний з другим виходом блока багатошляхової маршрутизації, третій вхід другого елемента АБО, другий вхід п'ятого елемента АБО і керуючий вхід другого регістра зсуву з'єднані з третім виходом блока багатошляхової маршрутизації, четвертий вихід якого з'єднаний з входом першого ключа, четвертий вихід блока керування з'єднаний з другим входом блока багатошляхової маршрутизації, третій і четвертий входи якого з'єднані відповідно з одинадцятим і дванадцятим входами блока керування, вихід третього елемента АБО з'єднаний з другим входом другого ключа, другий вихід якого з'єднаний з п'ятим входом блока багатошляхової маршрутизації.
2. Пристрій за п. 1, який відрізняється тим, що блок багатошляхової маршрутизації містить лічильник, комутатор, два тригери, два елементи І, елемент АБО, елемент НІ та елемент затримки, причому перший вхід блока багатошляхової маршрутизації з'єднаний з керуючим входом лічильника і першим входом елемента АБО, другий вхід якого з'єднаний з виходом переповнення лічильника, вхід скидання першого тригера з'єднаний з другим входом блока багатошляхової маршрутизації, третій вхід якого з'єднаний з першим входом першого елемента І, встановлювальні входи першого і другого тригерів з'єднані з четвертим входом блока багатошляхової маршрутизації, п'ятий вхід якого з'єднаний з лічильним входом лічильника і з входом елемента затримки, встановлювальні входи лічильника з'єднані відповідно з виходами комутатора, перший і другий входи якого з'єднані відповідно з виходом елемента НІ і з шиною логічного нуля, вхід елемента НІ з'єднаний з шиною логічного нуля, перший вихід блока багатошляхової маршрутизації з'єднаний з виходом другого елемента І, перший вхід якого з'єднаний з виходом елемента затримки, вихід елемента АБО з'єднаний з входом скидання другого тригера, прямий вихід якого з'єднаний з другими входами першого і другого елементів І, інверсний вихід першого тригера з'єднаний з другим виходом блока багатошляхової маршрутизації, третій вихід якого з'єднаний з прямим виходом першого тригера, вихід першого елемента І з'єднаний з четвертим виходом блока багатошляхової маршрутизації.
3. Пристрій за п. 1, який відрізняється тим, що блок оптимізації містить тригер, три елементи І, елемент АБО і два елементи НІ, причому перший інформаційний вхід блока оптимізації з'єднаний з входом першого елемента НІ і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом другого елемента НІ, другий інформаційний вхід блока оптимізації з'єднаний з входом другого елемента НІ і з першим входом другого елемента І, другий вхід якого з'єднаний з виходом першого елемента НІ, вхід блокування блока оптимізації з'єднаний з третім входом першого елемента І і з третім входом другого елемента І, вихід якого з'єднаний з встановлювальним входом тригера, вхід скидання блока оптимізації з'єднаний з першим входом елемента АБО, другий вхід якого з'єднаний з виходом першого елемента І, вихід елемента АБО з'єднаний з входом скидання тригера, прямий вихід якого з'єднаний з першим входом третього елемента І, керуючий вхід блока оптимізації з'єднаний з другим входом третього елемента І, вихід якого з'єднаний з виходом блока оптимізації.
Текст
1. Пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить три регістри зсуву, суматор, комутатор, два тригери, першу групу з m тригерів, де m - кількість гілок вузла графа, три групи з m елементів І, два елемента І, чотири елементи АБО і два ключі, причому перша група виходів блока керування з'єднана з першими входами першої і другої груп елементів І, інформаційні входи з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І, виходи яких з'єднані з входами першого елемента АБО, вихід першого регістра зсуву з'єднаний із своїм інформаційним входом і з першим інформаційним входом суматора, другий інформаційний вхід якого з'єднаний з виходом першого елемента АБО, перший і другий інформаційні входи комутатора з'єднані з виходами другого і третього регістрів зсуву, другий вихід блока керування з'єднаний з першим входом другого елемента АБО, вихід якого з'єднаний з входами скидання першої групи тригерів, третій вихід блока керування з'єднаний з входами скидання першого тригера і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом першого елемента АБО, вихід першого елемента І 2 (19) 1 3 86039 4 ми входами другого і третього тригерів, треті входи першої групи елементів І з'єднані відповідно з інверсними виходами другої групи тригерів, другий вихід блока керування з'єднаний з першим входом п'ятого елемента АБО, вихід якого з'єднаний з входом скидання третього тригера, другий вихід блока керування з'єднаний з входами скидання другої групи тригерів і з першим входом блока багатошляхової маршрутизації, перший вихід якого з'єднаний з керуючим входом блока керування, виходи третьої групи елементів І з'єднані відповідно з входами групи елементів індикації і з встановлювальними входами другої групи тригерів, вихід блока оптимізації з'єднаний з другими входами другої групи елементів І і з другим входом другого елемента АБО, прямий вихід третього тригера з'єднаний з першим входом третього елемента І, другий вхід якого з'єднаний з виходом комутатора, входи четвертого елемента АБО з'єднані з виходами третього і четвертого елементів І, перший вихід другого ключа з'єднаний з першим входом четвертого елемента І, другий вхід якого з'єднаний з другим виходом блока багатошляхової маршрутизації, третій вхід другого елемента АБО, другий вхід п'ятого елемента АБО і керуючий вхід другого регістра зсуву з'єднані з третім виходом блока багатошляхової маршрутизації, четвертий вихід якого з'єднаний з входом першого ключа, четвертий вихід блока керування з'єднаний з другим входом блока багатошляхової маршрутизації, третій і четвертий входи якого з'єднані відповідно з одинадцятим і дванадцятим входами блока керування, вихід третього елемента АБО з'єднаний з другим входом другого ключа, другий вихід якого з'єднаний з п'ятим входом блока багатошляхової маршрутизації. 2. Пристрій за п.1, який відрізняється тим, що блок багатошляхової маршрутизації містить лічильник, комутатор, два тригери, два елементи І, елемент АБО, елемент НІ та елемент затримки, причому перший вхід блока багатошляхової маршрутизації з'єднаний з керуючим входом лічильника і першим входом елемента АБО, другий вхід якого з'єднаний з виходом переповнення лічильника, вхід скидання першого тригера з'єднаний з другим входом блока багатошляхової маршрутизації, третій вхід якого з'єднаний з першим входом першого елемента І, встановлювальні входи першого і другого тригерів з'єднані з четвертим входом блока багатошляхової маршрутизації, п'ятий вхід якого з'єднаний з лічильним входом лічильника і з входом елемента затримки, встановлювальні входи лічильника з'єднані відповідно з виходами комутатора, перший і другий входи якого з'єднані відповідно з виходом елемента НІ і з шиною логічного нуля, вхід елемента НІ з'єднаний з шиною логічного нуля, перший вихід блока багатошляхової маршрутизації з'єднаний з виходом другого елемента І, перший вхід якого з'єднаний з виходом елемента затримки, вихід елемента АБО з'єднаний з входом скидання другого тригера, прямий вихід якого з'єднаний з другими входами першого і другого елементів І, інверсний вихід першого тригера з'єднаний з другим виходом блока багатошляхової маршрутизації, третій вихід якого з'єднаний з прямим виходом першого тригера, вихід першого елемента І з'єднаний з четвертим виходом блока багатошляхової маршрутизації. 3. Пристрій за п.1, який відрізняється тим, що блок оптимізації містить тригер, три елементи І, елемент АБО і два елементи НІ, причому перший інформаційний вхід блока оптимізації з'єднаний з входом першого елемента НІ і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом другого елемента НІ, другий інформаційний вхід блока оптимізації з'єднаний з входом другого елемента НІ і з першим входом другого елемента І, другий вхід якого з'єднаний з виходом першого елемента НІ, вхід блокування блока оптимізації з'єднаний з третім входом першого елемента І і з третім входом другого елемента І, вихід якого з'єднаний з встановлювальним входом тригера, вхід скидання блока оптимізації з'єднаний з першим входом елемента АБО, другий вхід якого з'єднаний з виходом першого елемента І, вихід елемента АБО з'єднаний з входом скидання тригера, прямий вихід якого з'єднаний з першим входом третього елемента І, керуючий вхід блока оптимізації з'єднаний з другим входом третього елемента І, вихід якого з'єднаний з виходом блока оптимізації. Винахід відноситься до обчислювальної техніки і може бути використаний для моделювання обчислювальних мереж з метою рішення задач багатошляхової маршрутизації при передачі даних між ЕОМ. Відомий пристрій для моделювання графів, який містить блок синхронізації, блок перераховування маршрутів, блок перевірки виконання умови вибору маршруту і блок реєстрації [1]. Основний недолік відомого пристрою полягає в виборі на графі маршрутів з заданими параметрами, які в задачі багатошляхової маршрутизації невідомі. Відомий пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, причому модель вузла міс тить чотири регістри зсуву, два суматори, віднімач, комутатор, два тригери, групу з m тригерів, де m кількість гілок вузла графа, чотири групи з m елементів І, чотири елемента І, групу з m елементів АБО, чотири елемента АБО, групу елементів індикації і два ключі [2]. Недоліки відомого пристрою полягають в складності його реалізації і в обмеженості функціональних можливостей, які дозволяють знайти лише один найкоротший шлях в мережі. Найбільш близьким до винаходу є пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить три регістри зсуву, суматор, віднімач, комутатор, два тригери, групу з m 5 тригерів, де m - кількість гілок вузла графа, три групи з m елементів І, два елемента І, чотири елемента АБО і два ключі [3]. Основний недолік прототипу викликаний вузькими функціональними можливостями, які дозволяють знайти лише один найкоротший шлях в мережі, яка моделюється. Задача багатошляхової маршрутизації вимагає знайти між початковим і кінцевим вузлами мережі декілька найкоротших шляхів, які не мають загальних гілок графа. В основу винаходу поставлена задача вдосконалення пристрою для моделювання графів за допомогою багатошляхової маршрутизації, яка дозволяє знайти між початковим і кінцевим вузлами графа K шляхів найменшої довжини L1£L2£....£Lk, де k£m, або K шляхів найбільшої довжини L1³L2³...³Lk які не мають загальних гілок графа. Поставлена задача вирішується тим, що в пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить три регістри зсуву, суматор, комутатор, два тригери, першу групу з m тригерів, де m - кількість гілок вузла графа, три групи з m елементів І, два елемента І, чотири елементи АБО і два ключі, причому перша група виходів блоку керування з'єднана з першими входами першої і другої груп елементів І, інформаційні входи з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І, виходи яких з'єднані з входами першого елемента АБО, вихід першого регістра зсуву з'єднаний із своїм інформаційним входом і з першим інформаційним входом суматора, другий інформаційний вхід якого з'єднаний з виходом першого елемента АБО, перший і другий інформаційні входи комутатора з'єднані з виходами другого і третього регістрів зсуву, другий вихід блоку керування з'єднаний з першим входом другого елемента АБО, вихід якого з'єднаний з входами скидання першої групи тригерів, третій вихід блоку керування з'єднаний з входами скидання першого тригера і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом першого елемента АБО, вихід першого елемента І з'єднаний з встановлювальним входом першого тригера, прямий вихід якого з'єднаний з першим входом другого елемента І, четвертий вихід блоку керування з'єднаний з другим входом другого елемента І і з входом скидання другого тригера, прямий вихід якого з'єднаний з керуючим входом комутатора, п'ятий вихід блоку керування з'єднаний з керуючим входом першого регістра зсуву, індикаційні входи з першого по m-й моделі вузла з'єднані відповідно з першим по m-й входами третього елемента АБО, m+1-й вхід якого з'єднаний з виходом першого ключа, перший вхід другого ключа з'єднаний з шостим виходом блоку керування, встановлювальний вхід першого регістра зсуву з'єднаний з сьомим виходом блоку керування, восьмий вихід якого з'єднаний з встановлювальним входом другого регістра зсуву, входи синхронізації першого, другого і третього регістрів зсуву з'єднані з дев'ятим виходом блоку керування, десятий вихід якого 86039 6 з'єднаний з входом блокування переносу суматора, вихід комутатора з'єднаний з інформаційним входом другого регістра зсуву, вихід четвертого елемента АБО з'єднаний з інформаційним виходом моделі вузла, виходи другої групи елементів І з'єднані відповідно з встановлювальними входами першої групи тригерів, прямі виходи яких з'єднані відповідно з першими входами третьої групи елементів І, вихід третього елемента АБО з'єднаний з другими входами третьої групи елементів І, виходи яких з'єднані з індикаційними виходами моделі вузла, інформаційний вхід третього регістра зсуву з'єднаний з виходом суми суматора, згідно з винаходом додатково введений блок багатошляхової маршрутизації, а в модель вузла додатково введені блок оптимізації, друга група з m тригерів, де m - кількість гілок вузла графа, третій тригер, третій і четвертий елементи І, п'ятий елемент АБО, група з m елементів індикації, причому перший і другий інформаційні входи блоку оптимізації з'єднані відповідно з виходом суми суматора та з виходом комутатора, третій вихід блоку керування з'єднаний з входом скидання блоку оптимізації, керуючий вхід якого з'єднаний з виходом другого елемента І, восьмий вихід блоку керування з'єднаний з входом блокування блоку оптимізації, вихід якого з'єднаний з входом скидання блоку керування та з встановлювальними входами другого і третього тригерів, треті входи першої групи елементів І з'єднані відповідно з інверсними виходами другої групи тригерів, другий вихід блоку керування з'єднаний з першим входом п'ятого елемента АБО, вихід якого з'єднаний з входом скидання третього тригера, другий вихід блоку керування з'єднаний з входами скидання другої групи тригерів і з першим входом блоку багатошляхової маршрутизації, перший вихід якого з'єднаний з керуючим входом блоку керування, виходи третьої групи елементів І з'єднані відповідно з входами групи елементів індикації і з встановлювальними входами другої групи тригерів, вихід блоку оптимізації з'єднаний з другими входами другої групи елементів І і з другим входом другого елемента АБО, прямий вихід третього тригера з'єднаний з першим входом третього елемента І, другий вхід якого з'єднаний з виходом комутатора, входи четвертого елемента АБО з'єднані з виходами третього і четвертого елементів І, перший вихід другого ключа з'єднаний з першим входом четвертого елемента І, другий вхід якого з'єднаний з другим виходом блока багатошляхової маршрутизації, третій вхід другого елемента АБО, другий вхід п'ятого елемента АБО і керуючий вхід другого регістра зсуву з'єднані з третім виходом блоку багатошляхової маршрутизації, четвертий вихід якого з'єднаний з входом першого ключа, четвертий вихід блоку керування з'єднаний з другим входом блоку багатошляхової маршрутизації, третій і четвертий входи якого з'єднані відповідно з одинадцятим і дванадцятим входами блоку керування, вихід третього елемента АБО з'єднаний з другим входом другого ключа, другий вихід якого з'єднаний з п'ятим входом блоку багатошляхової маршрутизації, блок багатошляхової маршрутизації містить лічильник, комутатор, два тригери, два елемента І, елемент АБО, 7 елемент НЕ та елемент затримки, причому перший вхід блоку багатошляхової маршрутизації з'єднаний з керуючим входом лічильника і першим входом елемента АБО, другий вхід якого з'єднаний з виходом переповнення лічильника, вхід скидання першого тригера з'єднаний з другим входом блоку багатошляхової маршрутизації, третій вхід якого з'єднаний з першим входом першого елемента І, встановлювальні входи першого і другого тригерів з'єднані з четвертим входом блоку багатошляхової маршрутизації, п'ятий вхід якого з'єднаний з лічильним входом лічильника і з входом елемента затримки, встановлювальні входи лічильника з'єднані відповідно з виходами комутатора, перший і другий входи якого з'єднані відповідно з виходом елемента НЕ і з шиною логічного нуля, вхід елемента НЕ з'єднаний з шиною логічного нуля, перший вихід блоку багатошляхової маршрутизації з'єднаний з виходом другого елемента І, перший вхід якого з'єднаний з виходом елемента затримки, вихід елемента АБО з'єднаний з входом скидання другого тригера, прямий вихід якого з'єднаний з другими входами першого і другого елементів І, інверсний вихід першого тригера з'єднаний з другим виходом блоку багатошляхової маршрутизації, третій вихід якого з'єднаний з прямим виходом першого тригера, вихід першого елемента І з'єднаний з четвертим виходом блоку багатошляхової маршрутизації, блок оптимізації містить тригер, три елемента І, елемент АБО і два елемента НЕ, причому перший інформаційний вхід блоку оптимізації з'єднаний з входом першого елемента НЕ і з першим входом першого елемента І, другий вхід якого з'єднаний з виходом другого елемента НЕ, другий інформаційний вхід блоку оптимізації з'єднаний з входом другого елемента НЕ і з першим входом другого елемента І, другий вхід якого з'єднаний з виходом першого елемента НЕ, вхід блокування блоку оптимізації з'єднаний з третім входом першого елемента І і з третім входом другого елемента І, вихід якого з'єднаний з встановлювальним входом тригера, вхід скидання блоку оптимізації з'єднаний з першим входом елемента АБО, другий вхід якого з'єднаний з виходом першого елемента І, вихід елемента АБО з'єднаний з входом скидання тригера, прямий вихід якого з'єднаний з першим входом третього елемента І, керуючий вхід блоку оптимізації з'єднаний з другим входом третього елемента І, вихід якого з'єднаний з виходом блоку оптимізації. На Фіг.1 представлена структурна схема пристрою для моделювання графів і функціональна схема моделі вузла. На Фіг.2 представлена функціональна схема блоку керування. На Фіг.3. зображена функціональна схема блоку багатошляхової маршрутизації. На Фіг.4 показано функціональну схему блоку оптимізації. На Фіг.5 наведено приклад моделювання графа на моделях чотирьох вузлів. Цифрами в скобках, які слідують за номером позиції без скобки, позначені порядкові номера однакових по технічному виконанню і призначенню блоків, вузлів і елементів. Цифрами в скобках, які 86039 8 розташовані у контурі відповідного блока вузла або елемента, зображені порядкові номери входів і виходів цього блока, вузла або елемента. Пристрій (Фіг.1) моделює m гілок графа, які заходять у вершину графа, в моделі 1 (і) вузла, де і=1, 2, 3, ..., N. Модель мережі, яка містить N вершин, формується з'єднанням N моделей вузлів відповідно до топології графа, який моделюється. Приклад моделювання графа на моделях чотирьох вузлів зображений на Фіг.5. З'єднання моделей вузлів відповідно до топології графа виконується таким чином, що інформаційні входи 30 (l) 30 (m) моделей одних вузлів з'єднуються з інформаційними виходами 31 моделей попередніх вузлів, індикаційні входи 32 (l) - 32 (m) яких з'єднуються з індикаційними виходами 33 (l) - 33(m) наступних моделей вузлів. Невикористанні індикаційні входи 32 (l) - 32 (m) з'єднуються з шиною 58 логічного нуля пристрою. Блок 2 керування і блок 3 багатошляхової маршрутизації є загальними для всіх моделей вузлів. Пристрій для моделювання графів фіг.1 містить моделі 1 (i) вузлів, де і=1, 2, 3, ..., N, N - кількість вершин графа, блок 2 керування і блок З багатошляхової маршрутизації. Модель 1(i) вузла (Фіг.1) містить блок 4 оптимізації, регістри 5-7 зсуву, суматор 8, комутатор 9, тригери 10-12, дві групи тригерів 13 (l) - 13 (m), 14(l) - 14(m), три групи елементів І 15 (l) - 15 (m), 16 (l) - 16 (m), 17 (l) - 17 (m), елементи 118-21, елементи АБО 22 - 26, елементи 27 (l) - 27 (m) індикації, ключі 28 і 29, інформаційні входи 30 (l) - 30 (m), інформаційний вихід 31, індикаційні входи 32 (l) - 32 (m) і індикаційні виходи 33 (l) - 33 (m). Перша група виходів блоку 2 керування з'єднана з першими входами першої і другої груп елементів І 15 (l) - 15 (m) і 16 (l) - 16 (m). Інформаційні входи 30 (l) - 30 (m) з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І 15 (l) - 15 (m), виходи яких з'єднані з входами першого елемента АБО 22. Вихід першого регістра 5 зсуву з'єднаний із своїм інформаційним входом і з першим інформаційним входом суматора 8, другий інформаційний вхід якого з'єднаний з виходом першого елемента АБО 22. Перший і другий інформаційні входи комутатора 9 з'єднані з виходами другого і третього регістрів 6, 7 зсуву. Другий вихід блоку 2 керування з'єднаний з першим входом другого елемента АБО 23, вихід якого з'єднаний з входами скидання першої групи тригерів 13 (l) - 13 (m), третій вихід блоку 2 керування з'єднаний з входами скидання першого тригера 10 і з першим входом першого елемента 118, другий вхід якого з'єднаний з виходом першого елемента АБО 22. Вихід першого елемента 118 з'єднаний з встановлювальним входом першого тригера 10, прямий вихід якого з'єднаний з першим входом другого елемента І 19. Четвертий вихід блоку 2 керування з'єднаний з другим входом другого елемента І 19 і з входом скидання другого тригера 11, прямий вихід якого з'єднаний з керуючим входом комутатора 9. П'ятий вихід блоку 2 керування з'єднаний з керуючим входом першого регістра 5 зсуву. Індикаційні входи 32 (l) - 32 (m) моделі 1 вузла з'єднані відповідно з першим по m 9 й входами третього елемента АБО 24, m+7-й вхід якого з'єднаний з виходом першого ключа 28. Перший вхід другого ключа 29 з'єднаний з шостим виходом блоку 2 керування. Встановлювальний вхід першого регістра 5 зсуву з'єднаний з сьомим виходом блоку 2 керування, восьмий вихід якого з'єднаний з встановлювальним входом другого регістра 6 зсуву. Входи синхронізації першого, другого і третього регістрів 5, 6, 7 зсуву з'єднані з дев'ятим виходом блоку 2 керування, десятий вихід якого з'єднаний з входом блокування переносу суматора 8. Вихід комутатора 9 з'єднаний з інформаційним входом другого регістра 6 зсуву. Вихід третього елемента І 20 з'єднаний з першим входом четвертого елемента АБО 25. Перший вихід другого ключа 29 з'єднаний з першим входом четвертого елемента І 21, вихід якого з'єднаний з другим входом четвертого елемента АБО 25, вихід якого з'єднаний з інформаційним виходом 31 моделі вузла. Виходи другої групи елементів І 16 (l) 16 (m) з'єднані відповідно з встановлювальними входами першої групи тригерів 13 (l) - 13 (m) , прямі виходи яких з'єднані відповідно з першими входами третьої групи елементів І 17 (l) - 17 (m). Інформаційний вхід третього регістра 7 зсуву з'єднаний з виходом суми суматора 8. Перший і другий інформаційні входи блоку 4 оптимізації з'єднані відповідно з виходом суми суматора 8 та з виходом комутатора 9. Третій вихід блоку 2 керування з'єднаний з входом скидання блоку 4 оптимізації, керуючий вхід якого з'єднаний з виходом другого елемента І 19. Восьмий вихід блоку 2 керування з'єднаний з входом блокування блоку 4 оптимізації, вихід якого з'єднаний з входом скидання блоку 2 керування, з встановлювальним входом другого тригера 11. Треті входи першої групи елементів І 15 (l) - 15 (m) з'єднані відповідно з інверсними виходами другої групи тригерів 14 (l) - 14 (m). Другий вихід блоку 2 керування з'єднаний з першим входом п'ятого елемента АБО 26 і з входами скидання другої групи тригерів 14 (l) - 14 (m). Вихід блоку 4 оптимізації з'єднаний з встановлювальним входом третього тригера 12, з другими входами другої групи елементів І 16(1) - 16 (m) і з другим входом елемента АБО 23. Вихід п'ятого елемента АБО 26 з'єднаний з входом скидання третього тригера 12, прямий вихід якого з'єднаний з першим входом третього елемента І 20. Вихід комутатора 9 з'єднаний з другим входом третього елемента І 20. Керуючий вхід блоку 2 керування з'єднаний з першим виходом блоку 3 багатошляхової маршрутизації, другий вихід якого з'єднаний з другим входом четвертого елемента І 21. Третій вихід блоку 3 багатошляхової маршрутизації з'єднаний з керуючим входом другого регістра 6 зсуву, з третім входом другого елемента АБО 23 і з другим входом п'ятого елемента АБО 26. Другий і четвертий виходи блоку 2 керування з'єднані відповідно з першим і другим входами блоку 3 багатошляхової маршрутизації, третій і четвертий входи якого з'єднані відповідно з одинадцятим і дванадцятим виходами блоку 2 керування. Вхід першого ключа 28 з'єднаний з четвертим виходом блоку 3 багатошляхової маршрутизації, п'ятий вхід якого з'єднаний з другим виходом другого ключа 86039 10 29. Вихід третього елемента АБО 24 з'єднаний з другими входами третьої групи елементів І 17 (l) 17 (m) і з другим входом другого ключа 29. Виходи третьої групи елементів І 17 (l) - 17 (m) з'єднані відповідно з встановлювальними входами другої групи тригерів 14 (l) - 14 (m), з входами групи елементів 27 (l) - 27 (m) індикації з індикаційними виходами 33 (l) - 33 (m) моделі 1 (i) вузла. Блок 2 керування (Фіг.2) містить генератор 34 імпульсів, розподільники 35 і 36 імпульсів, генератор 37 одиночного імпульсу, комутатори 38-42, тригери 43-45, елементи І 46-49, елементи АБО 50-52, елемент АБО - НЕ 53, елементи 54 і 55 затримки, елементи НЕ 56 і 57, шину 58 логічного нуля, керуючий вхід 59, входи 60 (l) - 60 (m) скидання і виходи 61-72. Вихід генератора 34 імпульсів з'єднаний з входом розподільника 35 імпульсів, виходи якого з першого по n-й, де n - кількість розрядів представлення ваги гілок, з'єднані через комутатор 38 з входами елемента АБО 50. Вихід n-го розряду розподільника 35 імпульсів з'єднаний з входом розподільника 36 імпульсів, виходи якого з першого по m-й, де m - кількість гілок, які моделюються, з'єднані через комутатор 39 з входами елемента АБО 51. Тактовий вхід генератора 37 одиночного імпульсу з'єднаний з виходом елемента І 46, перший і другий входи якого з'єднані відповідно через елемент 54 затримки з виходом n-го розряду розподільника 35 імпульсів і з виходом m-го розряду розподільника 36 імпульсів. Вихід генератора 37 одиночного імпульсу з'єднаний з входом комутатора 40, перший вихід якого з'єднаний з встановлювальним входом тригера 43, вхід скидання якого, з'єднаний з виходом елемента І 46. Прямий вихід тригера 43 з'єднаний з першим входом елемента І 47, другий вхід якого з'єднаний з виходом елемента АБО 51. Керуючий вхід генератора 37 одиночних імпульсів з'єднаний через комутатор 42 з виходом елемента НЕ 56, вхід якого з'єднаний з шиною 58 логічного нуля пристрою. Керуючий вхід 59 блоку 2 керування з'єднаний через комутатор 42 з керуючим входом генератора 37 одиночного імпульсу. Другий вихід комутатора 40 з'єднаний з встановлювальним входом тригера 45, вхід скидання якого з'єднаний з виходом елемента І 49. Вихід елемента І 46 з'єднаний з першим входом елемента І 49 і з входом елемента 55 затримки, вихід якого з'єднаний з входом скидання тригера 44. Вихід елемента АБО 52 з'єднаний з встановлювальним входом тригера 44, інверсний вихід якого з'єднаний з другим входом елемента І 49. Виходи першого і n-го розрядів розподільника 35 імпульсів з'єднані з входами елемента АБО - НЕ 53. Вихід першого розряду розподільника 35 імпульсів з'єднаний з входом елемента НЕ 57. Прямий вихід тригера 45 і вихід першого розряду розподільника 35 імпульсів з'єднані з входами елемента І 48. Інформаційний вхід комутатора 41 з'єднаний з виходом елемента І 47. Входи елемента АБО 52 з'єднані з входами 60 (l) 60 (N) скидання блоку 2 керування. Перша група виходів 61 (l) - 61 (m) блоку 2 керування з'єднана відповідно з виходами розрядів розподільника 36 імпульсів. Перший вихід комутатора 40 з'єднаний з 11 другим виходом 62 блоку 2 керування, третій вихід 63 якого з'єднаний з виходом першого розряду розподільника 35 імпульсів. Вихід n-го розряду розподільника 35 імпульсів з'єднаний з четвертим виходом 64 блоку 2 керування, п'ята група виходів 65 (l) - 65 (N) якого з'єднана з виходами комутатора 41. Вихід елемента І 48 з'єднаний з шостим виходом 66 блоку 2 керування, сьомий вихід 67 якого з'єднаний з виходом елемента АБО 50. Вихід елемента АБО - НЕ 53 з'єднаний з восьмим виходом 68 блоку 2 керування, дев'ятий, десятий і одинадцятий виходи 69, 70 і 71 якого з'єднані відповідно з виходами генератора 34 імпульсів, елемента НЕ 57 і з інверсним виходом тригера 45. Другий вихід комутатора 40 з'єднаний з дванадцятим виходом 72 блоку 2 керування. Блок 3 багатошляхової маршрутизації (Фіг.3) містить лічильник 73, комутатор 74, S-тригер 75, RS-тригер 76, елементи І 77-78, елемент АБО 79, елемент НЕ 80, елемент 81 затримки, перший п'ятий входи 82-86 відповідно, перший - четвертий виходи 87-90 відповідно. Встановлювальні входи лічильника 73 з'єднані з виходами комутатора 74, перший і другий входи якого з'єднані відповідно з виходом елемента НЕ 80 і з шиною 58 логічного нуля. Перший вхід 82 блоку 3 багатошляхової маршрутизації з'єднаний з керуючим входом лічильника 73 і з першим входом елемента АБО 79, другий вхід якого з'єднаний з виходом переповнення лічильника 73. Другий вхід 83 блоку 3 багатошляхової маршрутизації з'єднаний з входом скидання S-тригера 75. Третій вхід 84 блоку 3 багатошляхової маршрутизації з'єднаний з першим входом елемента І 77. Встановлювальні входи S-тригера 75 і RS-тригера 76 з'єднані з четвертим входом 85 блоку 3 багатошляхової маршрутизації, п'ятий вхід 86 якого з'єднаний з лічильним входом лічильника 73 і з входом елемента 81 затримки. Перший вихід 87 блоку З багатошляхової маршрутизації з'єднаний з виходом елемента І 78, перший вхід якого з'єднаний з виходом елемента 81 затримки. Інверсний і прямий виходи S-тригера 75 з'єднані відповідно з другим 88 і третім 89 виходами блоку 3 багатошляхової маршрутизації, четвертий вихід 90 якого з'єднаний з виходом елемента І 77. Вихід елемента АБО 79 з'єднаний з входом скидання RS-тригера 76, прямий вихід якого з'єднаний з другими входами елементів І 77 і 78. Вхід елемента НЕ 80 з'єднаний з шиною 58 логічного нуля. Блок 4 оптимізації (Фіг.4) містить тригер 91, елементи І 92-94, елемент АБО 95 і елементи НЕ 96 і 97, перший і другий інформаційні входи 98 і 99 відповідно, вхід 100 блокування, вхід 101 скидання, керуючий вхід 102, вихід 103. Встановлювальний вхід тригера 91 з'єднаний з виходом елемента І 93, перший і другий входи якого з'єднані відповідно з другим інформаційним входом 99 і з виходом елемента НЕ 96. Перший інформаційний вхід 98 з'єднаний з входом елемента НЕ 96 і з першим входом елемента І 92, другий вхід якого з'єднаний з виходом елемента НЕ 97. Вхід 100 блокування з'єднаний з третіми входами елементів І 92, 93. Вхід 101 скидання з'єднаний з першим входом елемента АБО 95, другий 86039 12 вхід якого з'єднаний з виходом елемента І 92. Вихід елемента АБО 95 з'єднаний з входом скидання тригера 91, прямий вихід якого з'єднаний з першим входом елемента І 94. Керуючий вхід 102 з'єднаний з другим входом елемента І 94, вихід якого з'єднаний з виходом 103 блоку 4 оптимізації. Другий інформаційний вхід 99 з'єднаний з входом елемента НЕ 97. Пристрій для моделювання графів працює наступним чином. Спочатку відмічаються початкова і кінцева вершини графа. Для цього замикають ключ 29 в моделі 1 (i) вузла, яка моделює початкову вершину графа і ключ 28 у моделі 1 (5) вузла, яка моделює кінцеву вершину графа. Початковий стан пристрою задається за допомогою комутатора 40 блоку 2 керування. В початковому стані комутатор 40 з'єднує вихід генератора 37 одиночного імпульсу з встановлювальним входом S-тригера 43 і з другим виходом 62 блоку 2 керування. Генератор 34 імпульсів блоку 2 керування виробляє послідовність тактових імпульсів частоти f, яка поступає на вхід розподільника 35 імпульсів. 3 послідовності тактових імпульсів розподільник 35 імпульсів формує по n паралельним каналам n послідовностей імпульсів частоти f/n, де n кількість двійкових розрядів зображення ваги моделей гілок графа разом з двома службовими розрядами. Послідовність імпульсів з n-го розряду розподільника 35 імпульсів надходить на вхід розподільника 36 імпульсів, який формує по m паралельним каналам m послідовностей імпульсів тривалістю n/f, які діють з частотою f/m×n і зсунуті друг відносно друга на час n/f. За допомогою комутаторів 38 і 39 блоку 2 керування задають відповідно двійковий код ваги моделі гілки і номер цієї гілки. Комутатори 38-42 виконуються, наприклад, як клавішні перемикачі, або як електронні комутатори керовані від ЕОМ. Регістр 5 зсуву має m×n двійкових розрядів і може запам'ятовувати динамічним способом m двійкових кодів по n розрядів в кожнім. В початковому стані в регістр 5 зсуву кожної моделі 1 вузла треба записати вагу m гілок графа, які моделюються, у вигляді двійкового коду їх ваги. Вибір моделі 1 (i) вузла, де і=1, 2, 3, ..., N, здійснюється за допомогою комутатора 41 блоку 2 керування, який може бути виконаний, наприклад, у вигляді клавішного перемикача на N напрямків, де N - кількість моделей 1 (i) вузлів. Вихід 65 (I) блоку 2 керування з'єднаний з керуючим входом регістра 5 зсуву моделі 1 (i) вузла, i=1, 2, ..., N. Тому вихід елемента І 47 блоку 2 керування з'єднується комутатором 41 блоку 2 керування з керуючим входом регістра 5 вибраної моделі 1 (i) вузла. Після вибору моделі 1 (i) вузла за допомогою комутатора 41 блоку 2 керування на комутаторі 38 задають двійковий код ваги гілки графа, а комутатором 39 здійснюють вибір номера гілки графа. Запис двійкового коду ваги гілки графа здійснюють за допомогою комутатора 42, виконаного, наприклад, у вигляді кнопкового перемикача. Комутатор 42 з'єднує вихід елемента НЕ 56 з керуючим входом генератора 37 одиночного імпульсу. Сигнал логічної одиниці з виходу елемента НЕ 56, вхід якого з'єднай з шиною 58 логічного нуля, запускає генератор 37 13 одиночного імпульсу, який формує на своєму виході одиночний імпульс з послідовності імпульсів, яка діє на виході елемента І 46 блоку 2 керування. Елемент І 46 формує послідовність імпульсів з послідовності імпульсів n-го розряду розподільника 35 імпульсів, яка затримується елементом 54 затримки на час рівний половині періоду тактової частоти f, і з послідовності імпульсів m-го розряду розподільника 36 імпульсів. Одиночний імпульс з виходу генератора 37 одиночного імпульсу через комутатор 40 встановлює S-тригер 43 у одиничний стан на час рівний m×n/f, тому, що наступний імпульс послідовності імпульсів з виходу елемента І 46, який надходить на вхід скидання S-тригера 43, поверне його у нульовий стан. Одиночний імпульс з виходу генератора 37 одиночних імпульсів проходить через комутатор 40 на другий вихід 62 блоку 2 керування, з якого він надходить на всі моделі 1 (i) вузла, і=1, 2, 3, ..., N, де встановлює у нульовий стан RS-тригер 12, S-тригери 13 (l) - 13 (m), 14 (l) - 14 (m). Тригер 43 в одиничному стані відкриває одиничним сигналом прямого виходу елемент І 47, через який на керуючі входи регістра 5 зсуву моделі 1 (i) вузла, вибраної за допомогою комутатора 41, поступає одиночний імпульсний сигнал з виходу елемента АБО 51, який задає номер моделі гілки графа. Під дією тактових імпульсів генератора 34 імпульсів блоку 2 керування, які діють на дев'ятому виході 69 блоку 2 керування, послідовний двійковий код ваги моделі гілки поступає з виходу елемента АБО 50 на сьомий вихід 67 блоку 2 керування і записується послідовно у часі, починаючи з молодшого розряду, в регістр 5 зсуву у час дії на виході елемента АБО 51 імпульсу номера моделі гілки графа. Аналогічним чином в регістр 5 зсуву усіх моделей 1 (i) вузлів, і=1, 2, 3, ..., N, записуються двійкові коди ваги усіх моделей гілок графа з першої по т-ту в усіх моделях 1 (i) вузлів, і=1, 2, 3, ..., N. Слід зазначити, що вага гілки представляється у вигляді n-2 розрядного двійкового коду. Це пов'язано з тим, що молодший перший розряд відводиться для маркера, який має службову функцію запуску моделей 1 (і) вузлів у робочий стан. Старший n-й розряд призначений для знакового розряда додаткового кода, коли вага гілки від'ємна. Максимальна вага гілки Рm повинна задовольняти умові Pm ×N
ДивитисяДодаткова інформація
Назва патенту англійськоюDevice for modeling graphs
Автори англійськоюZhukov Ihor Anatoliiovych, Martynova Oksana Petrivna, Baranov Volodymyr Leonidovych, Baranov Heorhii Leonidovych
Назва патенту російськоюУстройство для моделирования графов
Автори російськоюЖуков Игорь Анатольевич, Мартынова Оксана Петровна, Баранов Владимир Леонидович, Баранов Георгий Леонидович
МПК / Мітки
МПК: G06F 15/00, G06F 17/50
Мітки: пристрій, графів, моделювання
Код посилання
<a href="https://ua.patents.su/14-86039-pristrijj-dlya-modelyuvannya-grafiv.html" target="_blank" rel="follow" title="База патентів України">Пристрій для моделювання графів</a>
Попередній патент: Пристрій для створення розтягуючого зусилля у шпилькових і болтових з’єднаннях
Наступний патент: Похідні індолу, які мають активність антагоністів рецептора crth2
Випадковий патент: Вузол взаємодії рейкової колії та коліс колісних пар залізничного транспорту