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

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

На фиг,1 изображена функциональная схема предлагаемого устройства для моделирования графов; на фиг.2 - функциональная схема блока управления; на фиг.З пример моделирования графа.

Устройство для моделирования графов содержит регистру 1-3 сдвига, сумматор 4, вычитатель 5, коммутатор б, триггеры 7 и 8, группу триггеров 9(1)-9(т), элементы И 10 и 11, три группы элементов И 12(1)-12(т), 13(1h13(m), 14(1)-14(m), элементы ИЛИ ISIS, ключи 19 и 20, блок 21 управления, регистр 22 сдвига, сумматор 23, элементы И 24 и 25, группу элементов И 2б(1)-26(т), группу элементов ИЛИ 27(1)-27(т), информацибнные входы 28(1)-28(т), информационые выходы 29(1)-29(т), входы 30(1.1)-30(1.m)...30(m.1)-30(m.m) и выходы 31{1)-31(т) признака экстремального пути и группу элементов 32(1}-32(т) индикации,

где m - количество моделируемых ветвей графа.

Блок 21 управления (фиг.2) содержит генератор 33 тактовых импульсов, распределители 34 и 35 импульсов, генератор 36

одиночных импульсов, коммутаторы 37-41, триггеры 42-44, элементы ИЛИ 45-47, элемент ИЛИ-НЕ 48, элементы- НЕ 49 и 50, элементы И 51-54, элементы 55 и 56 задержки, управляющие входы 57(1)-57(К), где К количество моделируемых узлов графа.

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

Выход регистра 1 сдвига соединен со своим информационным входом и с первым информационным входом сумматора 4, выход которого соединен с информационным входом регистра 2 сдвига и с входом уменьшаемого вычитателя 5. Вход регистра 2 сдвига соединен с первым информационным входом коммутатора 6, второй информационный вход которого соединен с выходом регистра 3 сдвига. Выход коммутатора 6 соединен с информационным входом регистра 3 сдвига и входом вычитаемого вычитателя 5. Вход установки в единицу триггера 7 соединен с выходом элемента И 10, первый вход которого соединен с выходом элемента ИЛИ 16. Управляющий вход коммутатора 6 соединен с прямым выходом триггера 8, вход установки в единицу которого соединен с выходом элемента И 11. Выходы элементов И 12{1)-12(т) соединены

с входами элемента ИЛИ 16, выход которого соединен с вторым информационным входом сумматора 4.

Выходы элементов И 13(1h13(m) соединены соответственно с входами установки в

единицу триггеров 9(1)-9(т), прямые выхо-,ды которых соединены соответственно с первыми входами элементов И 14(1)-14(т), выходы которых являются выходами 31(1)-31(т) признака экстремального пути. Вторые входы элементов И 14(1)-14(т)

соединены с выходом элемента ИЛИ 15, m входов которого соединены соответственно с выходами элементов ИЛИ 27{1}-27(т). Выходы ключей 19 i/ 20 соединены соответ ственно с т+1-м входом элемента ИЛИ 15 и вторым входом элемента ИЛИ 18. Информационные входы 28(1 )-28(т)устройства соединены соответственно с первыми входами элементов И 12(1)-12(т), вторые входы которых соединены соответственно с первого по т-й разряды распределителя 35 импульсов блока 21 управления. Входы установки в ноль триггеров 9(1)-9(т) соединены с выходом элемента ИЛИ 17, первый и второй входы которого соединены соответственно с выходам элемента И 11 и первым выходом коммутатора 39 блока 21 управления, выход первого разряда распределителя 34 импульсов которого соединен с входом установки в ноль триггера 7 и вторым входом элемента И 10. Выход п-го разряда распределителя 34 импульсов соединен с входом установки в ноль триггера 8 и первым входом элемента И 11, второй и третий входы которого соединены соответственно с прямым выходом триггера 7 и выходом вычитатеяя 5. РЫХОД генератора 33 импульсов блока 21 управления соединен с входами синхронизации регистров 1-3 и 22 сдвига. Выход элемента И 52 блока 21 управления соединен через коммутатор 41 с .управляющими входами регистров 1 и 3 сдвига, установочные входы которых соединены соответственно с выходами элементов ИЛИ 45 и ИЛИ-НЕ 48 блока 21 управления, выход элемента НЕ 50 которого соединен с входами признака разрешения переноса сумматоров 4 и 23 и признака разрешения вычитания вычитателя 5. .Информационные входы ключей 19 и 20 соединены соответственно с инверсным выходом триггера 44 и выходом элемента И 54 блока 21 управления. Выход элемента И 11 срединен с одним из входов элемента ИЛИ 47 блока управления и с первыми входами элементов И 13(1)-13(т), вторые входы которых соединены соответственно с первого по т-й разряды распределителя 3 импульсов блока 21 управления. Выход регистра 22 сдвига соединен с входом первого слагаемого сумматора 23, входвторого слагаемого которого соединен с выходом элемента И 24. Выход сумматора 23 соединен с информационным входом регистра 22 сдвига и первым входом элемента ИЛИ 18, третий вход которого соединен с выходом элемента И 25. Прямой выход триггера 17 соединен с первым входом элемента И 24, второй вход которого соединен с выходом коммутатора 6. Выход

элемента МЛИ 18 соединен с первыми входаМи группы элементов И 26(1)-26(т), выходы которых являются информационными выходами 29(1)-29(т) устройства. Выходы 5 группы элементов ИЛИ 27(1)-27(т) соединены соответственно с входами группы, элементов 32(1)-32(т) индикации. Входы группы элементов ИЛИ27(1у-27{т) являются группой вход;ов 30(1.1)-30(1.m)...30(m.1)0 30(m.m) признака экстремального пути устройства. Вторые входы группы элементов И 26(1)-26(т) соединены соответственно с выходами разрядов с первого по т-й расп| еделителя 35 импульсов блока 21 уп5 равления. Управляющий и установочный

входы регистра 22 сдвига соединены соот ветственно с вторым выходом коммутатора

41 и выходом элемента ИЛИ 45 блока 21

управления. Выход элемента И 24 соединен

0 с первым входом элемента И 25, второй вход которого соединен с выходом первого разряда распределителя 34 импульсов блока 21 управления.

Выход генератора 33 импульсов (фиг.2)

5 соединен с входом распределителя 34 импульсов, выходы которого с первого по п-й, где п - количество разрядов представления весов ветвей, соединены через коммутатор 37 с входами элемента ИЛИ 45 блоки

0 21 управления. Выход п-го разряда рас(пределителя 34 импульсов соединены, с входом распределителя 35 импульсов, выходы которого с первого по т-й, где m количество моделируемых ветвей, соедине5 ны через коммутатор 38 с входами элемента ИЛИ 46 блока 21 управления. Тактовый вход генератора 36 одиночных импульсов соединен с выходом элемента И 51, пер- . вый и второй входы которого соединены

0 соответственно через элемент 55 задержки с выходом п-го разряда распределителя 34 импульсов и непосредственно -с выходом т-го разряда распределителя 35 импульсов. Выход генератора 36 одиночных

5 импульсов соединен с входом коммутатора 39, первый выход которого соединен с входом установки в единицу триггера 42, вход установки в ноль которого соединен с выходом элемента И 51. Прямой выход триггера

0 42 соединен с первым входом элемента И

52,второй вход которого соединен с выходом элемента ИЛИ 46 Управляющий вход Генератора 36 одиночных импульсов соединен через коммутатор 40 с выходом элеУиен5 та НЕ 49, вход которого соединен с нулевой шиной устройства. Второй выход коммутатора 39 соединен с входом установки в единицу триггера 44, вход установки в-ноль которого соединен с выходом элемента И

53.Выход элемента И 51 соединен с первым

входом элемента И 53 и входом элемента 56 задержки, выход которого соединен с входом установки в ноль триггера 43. Выход элемента ИЛИ 47 соединен с входом установки в единицу триггера 43, инверсный выход которого соединен с вторым входом элемента И 53. Выходы первого, п-1-го и п-го разрядов распределителя 34 импульсов соединены с входами элемента И,ЛИ-НЕ 48. Выход первого разряда распрёДелителя 34 импульсов соединен с входом элемента НЕ 50. Прямой выход триггера 44 и выход первого разряда распределителя 34 импульсов соединены с входами элемента И 54. Информационный вход коммутатора 41 соединен с выходом элемента И 52.

Входы элемента ИЛИ 47 соединены с управляющими входами 57(1)-57(К) блока 21 управления. Выходы (1.1)-(1.т) блока 21 управления соединены соответственно с выходами первого - т-го разрядов распределителя 35 импульсов. Первый выход коммутатора 39 соединен с выходом (2) блока 21 управления, выход (3) которого соединен с выходом первого разряда распределителя 34 импульсов. Выход п-го разряда распределителя 34 импульсов соединен с выходом (4) блока 21 управления, выход (5) которого соединен с первУм выходом коммутатора 41. Выход элемент.а И 54 соединен С выходом (6) блока 21 управления, выход (7) которого соединен с выходом элемента ИЛИ 45. Выход элемента ИЛИ-НЁ 48 соединен с.выходом (8) блока 21 управления, выходы (9),(10),(11) и (12) которого соединены соответственно с выходами генератора 33 импульсов, элемента НЕ 50, с инверсным выходом триггера 44 и вторым выходом коммутатора 41.

В качестве регистров 1-3 и 22 сдвига могут быть применены любые последовательные запоминающие устройства либо динамические регистры сдвига на линиях задержки, любых типов (магнитострикционной, ультразвуковой, электромагнитной и т.п.).

в качестве сумматора 4 и 23 и вычитателя 5 могут быть использованы любые последовательные двоичные сумматоры-вычитатели.

Устройство (фиг.1) моделирует m ветвей графа, входящих в вершину и m ветвей графа исходящих из неё, т.е. является моделью узла графа, из которых формируется модель сети путем соединения моделей узлов согласно топологии графа. Пример моделирования графа на моделях трех узлов изображен на фиг.З.

Коммутация моделей узлов в соответствий с топологией моделируемого графа выполняется так, что информационные входы 28(1)-28(т) моделей одних узлов подключают к информационным выходам 29(1)-29(т) моделей других узлов, выходы 31(1)-31(т) признака экстремального пути которых подключают к входам 30(1.1)-30(1.m)...30(m.1)30(m.m) признака экстремального пути предыдущих моделей узлов. Неиспользованные входы 30{1.1)-30(1.m)...30(m.1)30{m.m) признака экстремального пути соединяются с шиной логического нуля. Блок 21 управ/1ения дЛя всех моделей узлов является общим.

Устройство позволяет моделировать графы как с положительными так и с отрицательными весами. Для представления весов используется п двоичных разрядов. Младший разряд отводится для хранения маркера, выполняющего функцию запуска процесса моделирования в модели узла, Старшие п и n-1-e разряды являются знаковыми, а остальные разряды, с второго по П-2-Й включительно, предназначены для представления величины веса модели ветви. Поло)(ительный вес представляется в двоичном коде, а отрицательный - в дополнительном коде . Регистры 1 и 22 сдвига содержат m.n двоичных разрядов и предназначены для хранения m последовательных двоичных кодов по п разрядов в каждом. В регистр 1 сдвига записывают m двоичных кодов веса ветвей, входящих в узел, а в регистр 22 сдвига - вес m ветвей, исходящих из узла. Регистр 2 сдвига содержит п разрядов и предназначен для промежуточного запоминания одного .г1-разрядного кода. Регистр 3 сдвига содержит п разрядов и предназначен для хранения минимального значения алгебраической суммы весов.

Устройство для моделирования графов работает следующим образом.

Генератор 33 импульсов блока 21 управления (фиг,2) вырабатывает последователь: ность тактовых импульсов частоты f, из которых распределитель 34 импульсов формирует п последовательностей импульсов частоты f/n, сдвинутых одна относительно другой на время 1/f, где п - количество разрядов представления весов ветвей. Из последовательности импульсов п-го разряда распределителя 34 импульсов распределитель 35 импульсов формирует m последЪвательностей импульсов длительно,стью n/f, действующих с частотой f/m-n и сдвинутых одна относительно другой на время n/f.

В режиме ввода весов ветвей в регистры 1 и 22 сдвига коммутатором 39 (выполненным, например, в виде переключателяна два положения) блока 21 управления подключают выход генератора 36 одиночных импульсов к входу установки в единицу триггера 42. С помощью коммутаторов 37 и . 38 (выполненных, например, в виде клавишных переключателей) блока 21 управления 5 задают двоичный коД веса ветви и номер ветви соответственно. Коммутатор 37 подключает в единичных разрядах прямого или дополнительного кода веса ветви соответствующие выходы распределителя 34 импуль- 10 сов к входам элемента ИЛИ 45, на выходе которого формируется последовательный двоичный код веса ветви. Например, если положительный вес ветви равен пяти, 101, то значение двоичного кода набирается с 15 второго разряда (первый разряд отводится под маркер, который вводится в режиме моделирования), т.е. выходы второго и четвертого разрядов распределителя 34 импульсов подключают коммутатором 37 к 20 входам злемента ИЛИ 45. Если отрицательный вес равен пяти, то, начиная с второго разряда по п-й разряд распределителя 34 импульсов, набирается дополнительный код 11.11... 1011, где в n-1-M и п-м знаковых 25 разрядах набирается единичный код, т.е. выходы всех разрядов, кроме первого и четвертого, распределителя 34 импульсов подключают коммутатором 37 к входам злемента ИЛИ 45. Выбор регистров 1 или 22 30 выполняется с помощью коммутатора 41 блока 21 управления.

Коммутатором 38 блока 21 управления задают номер ветви. Например, если выполняется ввод веса в седьмую ветвь, то выход 35 седьмого разряда распределителя 35 импульсов подключают к входу элемента ИЛИ 46, на выходе которого формируется импульс длительностью n/f, совпадающий по фазе с временем сдвига с выхода регист- 40 ров 1 и 22 сдвига под действием тактовых импульсов генератора 33 импульсов п-разрядного двоичного кода веса для седьмой ветви.

Ввод последовательного кода веса 45 ветви в регистр 1 или 22 сдвига осуществляется после подачи с помощью коммутатора 40 (выполненного, например, в виде кнопочного переключателя) единичного сигнала с выхода элемента НЕ 49 на управляющий 50 вход генератора 36 одиночных импульсов. Последний выделяет из последовательности импульсов выхода элемента И 51, действующих с частотой f/m-n, одиночный-импульс,

устанавливающий через коммутатор 39 триг- 55 гер 42 в единичное состояние на время m-n/f. Триггер 42 сбрасывает в нулевое еебТР ние еледующим импульеом последо18тейьнееть ттт элемента И11,,

формируется из последовательности разряда расйределителя 34 импульсов, задержанной элементом 55 задержки на время длительности тактового импульса генератора 33 импульсов, и последовательности т-го разряда распределителя 35. Триггер 42 в единичном состоянии открывает элемент И 52, через который на управляющие входы регистров 1 или 22 сдвига (в зависимости от состояния коммутатора 41) поступает одиночный импульс выхода элемента ИЛИ 46, задающий номер ветви. Под действием тактовых и 1пульсов генератора 33 тактовых импульсов блока 21 управления последовательный двоичный код веса ветви записывается с выхода злемента ИЛИ 45 последовательно во времени, начиная с младших разрядов, & регистр 1 или 22 сдвига во время действия на выходе элемента ИЛИ 46 импульса, задающего номер ветви. Аналогичным образом в регистры 1 и 22 сдвига записывают двоичные коды положительных и отрицательных весов для всех ветвей с первой по т-ю каждого узла моделирующей структуры.

В процессе ввода весов в регистры 1 и 22 сдвига импульс, формируемый на выходе элемента И 52 блока 21 управления, поступает на управляющий вход регистра 3 сдвига, в который под действием тактовых импульсов генератора 33 импульсов блока 21 управления записывается двоичнь1й код максимального веса 00.111...10, формируемый на выходе элемента ИЛИ-НЕ 48 блока 21 управления из последовательностей импульсов п-го, П-1-ГО и первого разрядов распределителя 34 импульсов. Коммутатор 6 при нулевом сортоянии тригггера 8 подключает информационный вход регистра 3 сдвига к его выходу, что обеспечивает динамическое хранение кода максимального веса путем его циркуляции под действием тактовых импульсов генератора 33 импульсов блока 21 управления.

Триггеры 7 и 8 находятся в режиме ввода весов в нулевом состоянии вследствие действия соответственно последовательностей первого и п-го разрядов распределите-. ля 34 импульсов на их входах установки в ноль.

В режиме ввода весов первый выходной импульс генератора 36 одиночных импульсов блока 21 управления через коммутатор 39 и элемент ИЛИ 17 устанавливает все триггеры 9(1)-9(т) в нулевое состояние.

Триггеры 43 и 44 блока 21 управления также находятся в нулевом состоянии. Триггер 43 устанавливается р нулевое сдетояние пеелед§1§тельн§етк о еихеда элемен Mi Ц, к§тер§я Hgpis элемент ii з§д§ржкм на

длительность тактового импульса генератора 33 импульсов поступает на вход установки в ноль триггера A3. Триггер 44 устанавливается в нулевое состояние последовательностью импульсов выхода элемента И 51, которая через элемент И 53 поступает на вход установки в ноль триггера 44.

В режиме моделирования коммутаторюм 39 блока 21 управления подключают выход генератора 36 одиночных импульсов к входу установки в единицу триггера 44. Подключая выход элемента И 54 блока 21 управления к входу элeмeнta ИЛИ 18 с помощью ключа 20, задают начальный узел графа. Конечный узел графа задают ключом 19, который подключает инверсный выход триггера 44 блока 21 управления к одному из входов элемента ИЛИ 1В.

Пуск устройства осуществляют коммутатором 40 блока 21 управления, с помощью которого на управляющий вход генератора 36 одиночных импульсов подают единичный сигнал выхода элемента НЕ 49. Выходной импульс генератора 36 одиночных импульсов блока 21 управления поступает через коммутатор 39 на вход установки в единицу S-триггера 44 и устанавливает его в единичное состояние. Триггер 44 единичным сигналом прямого выхода открывает элемент И 54, на выход которого поступает последовательность импульсов первого разряда распределителя 34 импульсов.

Последовательность импульсов с выхода элемента И 54 блока 21 управления поступает через ключ 20, элемент ИЛИ 18 и элементы И 26(1)-26(т) на информационные выходы 29(1)-29(т) модели, содержащей начальный узел моделируемого графа. Так как информационные выходы 29(1)(т) модели начального узла соединены с информационными входами 28(1)-28(т) других моделей узлов моделирующей структуры, то последовательность импульсов первого разряда распределителя 34 импульсов блока 21 управления, действующая на информационных выходах 29(1)-29(т) модели начального узла, действует на информационных входах 28(1)-28(т) других узлов моделирующей структуры.

Предположим, что информационные выходы 29(1)-29(т) модели начального узла соединены соответственно с информационными входами 28(1)-28(т) рассматриваемого узла моделирующей структуры. В этом случае на всех информационных входах 28(1)-28(т) рассматрив аемого узла действует последовательность импульсов первого разряда распределителя 34 импульсов блока 21 управления, которая через элементы

И 12(1)-12{т), управляемые последовательностями импульсов разрядов распределителя 35 импульсов блока 21 управления, и элемент ИЛИ 16 поступает на первыйвход

элемента И lOi тактируемый той же последовательностью импульсов первого разряда распределителя 34 импульсов. На выходе элемента И 10 формируется последовательность импульсов, первый импульс которой

0 устанавливает S-триггер 7 в единичное состояние. Триггер 7 единичным сигналом прямого выхода снимает блокировку элемента И 11.

В исходном состоянии в регистре 1

5 сдвига в первых разрядах двоичных кодов весов всегда содержится нулевой сигнал. После запуска устройства в режиме моделирования на выходе элемента ИЛИ 16, как было ранее описано, формируется последовательность импульсов первого разряда распределителя 34 импульсов блока 21 управления, которая через сумматор 4 запись вается в регистр 2 сдвига под действием тактовых импульсов генератора 33 импульсов блока 21 управления. В сумматоре 4 и вычитателе 5 во время прохождения последовательностей импульсов первого разряда распределителя 34 импульсов блокируются соответственно цепи переноса и цепи

0 займа по управляющему входу, на котором действует инвертированная элементом НЕ 50 21 управления последовательность импульсов первого разряда распределителя 34 импульсов.

5 После прохождения маркера первого разряда через сумматор 4 с выхода регистра . 1 сдвига под действием тактовых импульсов генератора 33 И1у1пульсов блока 21 управления последовательно, начиная с

0 младшего разряда, сдвигается двоичный код веса первой входящей ветви графа, который проходит через сумматор 4 без изменения, поступает на вход уменьшаемого вычитателя 5 и записывается под действием

5 тактойых импульсов в регистр 2 сдвига. В это. время с выхода регистра 3 сдвига под действием тактовых импульсов генератора 33 импульсов блока 21 управления сдвигается двоичный код максимального

0 веса, который последовательно во времени, начиная с младшего разряда, поступает через коммутатор 6 на вход вычитаемого вычитателя 5, который.вычитает из двоичного кода веса первой ветви двоичный код

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

равнения на первом входе элемента И 11 на выходе вычитателя 5 действует единичный сигнал знакового п-го разряда дополнительного кода разности. Импульс последовательности п-го разряда распределителя 34 импульсов блока 21 управления проходит через элемент И 11 и устанавливает S-триггер 8 в единичное состояние, при котором коммутатор 6 переключается и соединяет информационный вход регистра 3 сдвига с выходом регистра 2 сдвига. Двоичный код веса первой ветви вместе с импульсом маркера первого разряда сдвигается под действием тактовых импульсов с выхода зегистра 2 сдвига и через коммутатор 6 записывается под действием тактовых импульсов в регистр 3 сдвига и поступает также на вычитающий вход вычитателя 5, на вход уменьшаемого которого в это время под действием тактовых импульсов с выхода регистра 1 сдвига через сумматор 4 сдвигается двоичный код веса второй ветви графа.

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

В том случае, когда вес второй ветви графа меньше веса первой ветви, на выходе вычитателя 5 формируется дополнительный код отрицательной разности, в п-м знаковом разряде которого действует единичный дигнал, открьшающий элемент VI 11. В этом случае импульс последовательности п-го разряда распределителя 34 импульсов через элемент И 11 устанавливает триггер 8 в единичное состояние, при котором коммутатор б подключает выход,, регистра 2 сдвига к информационному входу регистра 3 сдвига. Двоичный код веса второй ветви, который к этому моменту времени под действием тактовых импульсов переписался с выхода регистра 1 сдвига через сумматор 4 в регистр 2 сдвига начинает сдвигаться с выхода регистра 2 сдвига через коммутатор 6 в регистр 3 сдвига. В этом случае в регистр 3 сдвига записывается

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

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

0 с начальным узлом.

Номер минимальной ветви рафа запоминается одним из триггеров 9(1)-9(т) следующим образом. Каждый раз, когда с выхода регистра 1 сдвига поступает двоичный код ветви с меньшим весом, чем Тот, который к этому моменту времени хранится в регистре 3 сдвига, на выходе вычитателя 5 формируется дополнительный код отрицательной разности, знаковый п-й разряд

0 которого открывает элемент ИИ. Последовательность импульсов п-го разряда распределителя 34 импульсов блока 21 управления через элементы И 11, ИЛИ 17 поступает на входы устанрвки в ноль всех триггеров

5 9(1)-9(т) и через один из элементов И 13 (I), открытый в это время для 1-й ветви i-м разрядом распределителя-35 импульсов блок 21 управления, - на вход установки

f единицу S-триггера 9(1), который устанавивается в единичное состояние. Остальные триггеры 9(1)-9(т), кроме триггера 9(1), сбрасываются в нулевое состояние. Триггер 9(1) запоминает текущий 1-й номер наименьшей ветви графа.

5 Двоичный код наименьшей входящей ветви, циркулирующий под действием тактовых импульсов с выхода регистра 3 сдвига на его вход, поступает через коммутатор 6 и элемент И 24, открытый единичным сигналом прямого выхода триггера 7,: на вход сумматора 23. На другой вход сумматора 23 под действием тактовых импульсов генератора 33 блока 21 управления из регистра

22сдвига поступают последовательно, начиная с младшего разряда, двоичные коды

весов ветвей, исходящих из рассматриваемого узла графа. За время т-п тактов на выходе сумматора 23 сформируются га двоичных кодов алгебраической суммы весов m 0 исходящих ветвей и двоичного кола наименьшей входящей ветви. Двоичные коды сумм с первой по т-ю с выхода сумматора

23под действием тактовых импульсов записываются в регистр 22 сдвига, а также

5 поступают через элемент ИЛИ 18 и элементы И 26(1)26(т), управляемые выходами разря дов распределителя 35 импульсов блока 21 управления, на соответствующие информационные выходы 29(1)-29(rh) рассматриваемой модели узла.

В сумматоре 23 во время действия импульсов первого разряда рвгспределителя 34 импульсов блока 21 управления блокируются цепи переноса по входу признака разрешения переноса сигналом, формируемым на выходе элемента НЕ 50 блока 21 управления. Для прохождений маркера первого разряда на информационные выходы 29(1)-29(т) модели узла служит элемент И 25, управляемый импульсами первого разряда распределителя 34 импульсов блока 21 управления. Маркер первого разряда под действием тактовых имлульсов генерируется через каждыеп тактов на выходе регистра 3 сдвига и через коммутатор 6. элементы И 24 и 25, ИЛИ 18, И 26(1)-26(т) поступает на cooтвeтctвyющиe информационные выходы 29(1)-29(т) модели данного узла и далее согласно топологии моделируемого графа - на информационные входы 28(1)-28(т) других узлов моделирующей структуры.

Рассмотрим случай, когда все информационные входы 28(1)-28(т} модели узла соединены соответственно с информационными выходами 29(1}-29(т) предыдущей модели узла. В этом случае двоичные коды, формируемые на информационных, выходах 29(1)-29(т) предыдущей модели узла последовательно во времени по сигналам разрядов распределителя 35 импульсов блока 21 управления поступают соответственно через элементы И 12(1)12(т) рассматриваемой модели узла и элемент ИЛИ 16 на вход сумматора 4. Так как двоичные коды начинают поступать с младшего разряда, то сигнал маркера в первом разряде кода через элемент И 10 устанав ливает триггер 7 в единичное состояние. На другой вход сумматора 4 с выхода регистра 1 сдвига поступают под действием тактовых импульсов двоичные коды весов входящих ветвей, с первой по т-ю, рассматриваемой модели узла. За время п тактов сумматор 4 выполняет сложение двух последовательных кодов, например двоичного кодэ действующего на информационном входе 28(1), с двоичным кодом веса первой ветви, входящей в рассматриваемый узел.

ЕСЛИ сумма весов ветвей графа вдоль этого пути меньше двоичного кода регистра 3 сдвига, то на выходе вычитателя 5 формируется единичный сигнал в п-м знаковом разрядеГкоторый открывает элемент И 11. Триггер 8 данной модели устанавливается выгодным импульсом элемента И 11 единичн@@ §§@т§яйи@ И п@р1ключ§@ к§ммута f§p @ i б§бтвяии§, при к§т@рзм д§вичный кбц наим@ньш§й еуммы §@б§1 е@тв€й

вдоль анализируемого пути с выхода сумматора 4 через регистр 2 сдвига и коммутатор 6 сдвигается под действием тактовых импульсов в регистр 3 сдвига. Одновременно

выходной импульс элемента И 11 через элемент И 13(1), открытый в это время импульсом первого разряда распределителя 35 импульсов блока 21 управления, устанавливает триггер 9(1) в единичное состояние, а

0 триггеры 9(2)-9(т) через элемент ИЛИ 17 сбрасываются в нулевое состояние.

3ia определенное время тактов выполняется анализ всех путей, проходящих через ветви данного модуля. В результате,

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

0 триггер 9(j) устанавливается в единичное состояние, а в регистре 3 сдвига запоминается минимальная алгебраическая сумма весов ветвей графа вдоль экстремального пути, начинающегося в начальном узле

5 графа и проходящего через j-ю ветвь данного модуля.

Двоичный код минимальной суммы весов графа, вдоль экстремального пути циркулирующий в регистре 3 сдвига под

0 действием тактовых импульсов, поступает через коммутатор 6 и элемент И 24, открытый единичным сигналом прямого выхода триггера .7, на один из входов сумматора 23. На другой вход сумматора 23 под дей5 ствием тактовых импульсов из регистра 22 сдвига поступают последовательно двоичные коды веса исходящих ветвей, с первой по т-ю. За время т-п тактов на выходе сумматора 23 формируется m даричных кодов алгебраической суммы, которые под действием тактовых импульсов записываются в регистр 22 сдвига и поступают через элементы ИЛИ 18 и И 26(1)-26(т) на информационные выходы 29(1)-29(т) модели узла. Сигнал маркера, действующий в первом разряде двоичного кода, сдвигается под действием тактовых импульсов с выхода регистра 3 сдвига и поступает че рез коммутатор 6, элементы И 24 и 25, ИЛИ

0 18, И 2б(1)-26(т) на информационные выходы 29(1)-29(т) рассматриваемой модели узла и согласно топологии моделируемого графа --на информационные-входы 28(1)28(т) других моделей узла.

5 Таким образом, устройство работает до тех пор, пока щ блоке 21 управления триггер 44 не установится в нулевое состояние. Это

преи§м§дмт п§ §§§ рш§ним §нал짧1 ig§x путей, 61ЯЗЫ§§ЮЩИ ИИМЗЛЬИЫЙ и М§Д@ЛИРУ@М@Г§ РрЗфЗ, Д|ЙёТ§ИТ@ЛЬ|И@,

б процессе выполнения анализа на выходе вычитателя 5 моделей узлов моделирующей структуры формируется в течение m.n тактов единичный сигнал в п-м знаковом разряде, который открывает элемент И 11 хотя бы в Одной модели узла моделирующей структуры. Импульс последовательности пго разряда распределителя 34 импульсов блока 21 управления через злемент И 11 модели, в которой выполняется анализ, поступает на один из входов 57(1)) блока 21; управления, где К - количество моделей узлов моделирующей структуры, и через элемент ИЛИ 47 устанавливает триггер 43 в единичное состояние. Сигнал инверсного выхода триггера 43 при единичном состоянии блокирует элемент И 53 и, следовательно, триггер 44 сохраняет единичное состояние, в которое он быдустановлен при пуске устройства.

Если процесс анализа во всех узлах МОДели сети завершился, то в регистрах 3 сдвига всех моделей узла содержатся двоичные коды минимальных сумм весов графа вдоль экстремальных путей. Тогда на выходах вычитателей 5 всех моделей узла отрицательная разность ие может быть сформирована и элементы И 11 во всех узлах модели сети будут закрыты. В этом случае на выходе элемента ИЛИ 47 блока 21 управления формируется нулевой сигнал. Последовательность импульсов выхода элемента И 51 блока 21 управления через элемент 56 задержки на длительность тактового импульса сбрасывает триггер 43 в нулевое состояние, при котором открывается элемент И 53. Следующий импульс последовательности элемента И 51 проходит через элемент И 53 и сбрасывает триггер 44 в нулевое состояние, единичный сигнал инверсного выхода которого через ключ 19 модели, содержащей конечный узел моделируемого графа, поступает на вход элемента ИЛИ 15. Единичный сигнал выхода элемента ИЛИ 15 открывает один Из элементов И 14(1)-14(т), управляемый, например, триггером 9(1), который запоминает номер 1-й ветви, пр11надлежащей экстремальному пути. С выхода элемента И 14(1) единичный сигнал индикации экстремального пути поступает на выход 31(1) модели, содержащей конечный узел графа, и далее поступает на входы 30(1)-30(т) тех моделей узла, информационные выходы 29(1)--29(т) которых соединены с информационными входами 28(1)-28(гп) модели, содержащей конечный узел.

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

графа к начальному узлу. В случае необходимости визуальной индикации конфигурации экстремального пути на моделируемом графе (например, в процессе использования устройства в автоматизированных системах управления технологическими процессами) выходы 31{1)-31(т) устройства нагружаются на элементы индикации. Этой же цели служат индикационные элементы 32(1)-32(т).

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

0 Функциональные возможности предлагаемого устройства позволжот моделировать дискретные аналоги дифф еренциальных игр, в которых входящим ветвям графа соответствует переход состояния игры под

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

Ожидаемый экономический эффект от использования изобретения составляет 221000 руб/год.

5

Формула изобретения Устройство Для моделирования графов по авт.св. Ns 1399755, отличающееся . тем, что, с целью расширения функциональных возможностей устройства путем моделирования входящих и исходящих ветвей узлов графа, в каждую модель узла устройства введены четвертый регистр сдвига, второй сумматор, третий и четвертый элементы И, четвертая группа из m элементов И (где m - количество исходящих ветвей узловграфа), группа из m элементов ИЛИ и группа из m элементов индикации, а в блок управления введен пятый коммутатор,

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для моделирования задач о кратчайшем и длиннейшем пути. Цель изобретения - расширение функциональных возможностей устройства за счет моделирования входящих и исходящих ветвей узлов графа. В процессе моделирования из начального узла графа посылается информационное сообщение, кото^ рое попадает в модель конечного узла графа по кратчайшему или длиннейшему пути и^ проходя по цепям индикации от конечного к начальному узлу графа, обеспечивает определение искомого пути. 3 ил.Изобретение относится к цифровым вычислительным машинам, в частности к устройствам обработки информации специального назначения, может быть использовано как специализированное вычислительное устройство для научно-исследовательских целей и моделирования задач о длийнейшем и кратчайшем Г1ути, дискретных вариационных задач, задач оптимального управления и дифференциальных игр, а также для управления технологическими процессами в различных отраслях промышленности и является усовершенствованием известного устройства по основному авт.св. № 1399755.Известно устройство, содержащее модель сети, состоящей из моделей узлов, соединенных в соответствии с топологией графа и содержащих три регистра сдвига, сумматор, вычитатель, коммутатор, два триггера, группу триггеров, два элемента И, три группы элементов И, четыре элемента ИЛИ, два ключа и блок управления, содержащий генератор тактовых импульсов, двараспределителя импульсов, генератор одиночных импульсов, четыре коммутатора, три триггера, три элемента ИЛИ, элемент ИЛИ- НЕ, два элемента НЕ, четыре элемента И и два элемента задержки.Недостатком этого устройства является ограничение его функциональных возможностей моделированием только ветвей графа, входящих в узел.Цель изобретения - расширение функциональных возможностей за счет моделирования входящих и исходящих- ветвей узлов графа.Поставленная цель достигается тем, что устройство для моделирования графов в модели узла дополнительно содержит четвертый регистр сдвига, второй сумматор, третий и четвертый элементы И, четвертую группу из m элементов И (где m - количество исходящих ветвей узла графа), группу из m элементов ИЛИ, группу из m элементов индикации. Блок управления содержит пятый коммутатор, информационный вход которого соединен с выходом второго элемент!а ИслсV4 О Ю СА>&4^ Qs>& N3

аэ,