Устройство для моделирования графов

 

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

СОЮЗ COBETCKNX

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

РЕСПУБЛИК (я)з G 06 F 15/419

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1399755 . (21) 4741980/24 (22) 04,07.89 (46) 30.01.92. Бюл. N 4 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев и В.Л, Баранов (53) 681.333(088.8) (56) Авторское свидетельство СССР

N 1399755, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ

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

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

Ж 1709346 А2 (57) Изобретение относится к .вычислительной технике и может быть использовано для моделирования задач о кратчайшем и длиннейшем пути. Цель изобретения — расширение функциональных возможностей устройства за счет моделирования входящих и исходящих ветвей узлов графа. В процессе моделирования из начального узла графа посылается информационное сообщение, которое попадает в модель конечного узла графа по кратчайшему или длиннейшему пути и, i проходя по цепям индикации от конечного к начальному узлу графа, обеспечивает определение искомого пути. 3 ил. распределителя импульсов, генератор одиночных импульсов, четыре коммутатора, три триггера, три элемента ИЛИ, элемент ИЛИ-

НЕ, даа элемента НЕ, четыре элемента И и два элемента задержки.

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

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

Поставленная цель достигается тем, что устройство для моделирования графов в модели узла дополнительно содержит четвертый регистр сдвига, второй сумматор, третий и четвертый элементы И, четвертую группу из m элементов И (где m — количество, исходящих ветвей узла графа), группу из m элементов ИЛИ, группу из m элементов индикации. Блок управления содержит пятый коммутатор, информационный вход которого соединен с выходом второго элемента И

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

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

Устройство для моделирования графов содержит регистры 1-3 сдвига, сумматор 4, вычитатель 5, коммутатор 6, триггеры 7 и 8, группу триггеров 9(1) — 9(m), элементы И 10 и

11, три группы элементов И 12(1) — 12(m), 13(1)-13(m), 14(1) — 14(m), элементы ИЛИ 15— группу элементов 32(1)-32(m) индикации, 10 где m — количество моделируемых ветвей

25

35

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

55 единицу триггеров 9(1) — 9(m), прямые выхо-. ды которых соединены соответственно с

18, ключи 19 и 20, блок 21 управления, регистр 22 сдвига, сумматор 23, элементы

И 24 и 25, группу элементов И 26(1) — 26(m), группу элементов ИЛИ 27(1) — 27(m), информационные входы 28(1) — 28(m), информацио н ы е выходы 29(1) — 29(m), входы

30(1.1) — 30(1.m)...30(m.1)-30(m,m) и выходы

31(1) — 31(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(m) соединены с входами элемента ИЛИ 16, выход которого соединен с вторым информационным входом сумматора 4. первыми входами элементов И 14(1)-14(m), выходы которых являются выходами

31(1) — 31(m) признака экстремального пути. Вторые входы элементов И 14(1) — 14(m) 1709346 сдвига, установочные входы которых соединены соответственно с выходами элементов ИЛИ 45 и ИЛИ-НЕ 48 блока 21 управления, выход элемента Н Е 50 которого соединен с входами признака разрешения переноса сумматоров 4 и 23 и признака разрешения вычитания вычитателя 5.,Информационные входы ключей 19 и 20 соединены соответственно с инверсным выходом триггера 44 и выходом элемента И 54 блока 21 управления. Выход элемента И 11 соединен с одним из входов элемента ИЛИ 47 блока управления и с первыми входами элементов И 13(1) — 13(m); вторые входы которых соединены соответственно с первого по m-й разряды распределителя 3 импульсов блока 21 управления.

Выход регистра 22 сдвига соединен с входом первого слагаемого сумматора 23, вход второго. слагаемого которого соединен с выходом элемента И 24, Выход сумматора 23 соединен с информационным входом регистра 22 сдвига и первым входом элемента ИЛИ 18, третий вход которого соединен с выходом элемента И 25. Прямой выход триггера 17 соединен с первым входом элемента И 24, второй вход котОрого соединен с выходом коммутатора 6. Выход

50 соединены с выходом элемента ИЛИ 15, m входов, которого соединены соответственно с выходами элементов ИЛИ 27(1)-27(m).

Выходы ключей 19 и 20 соединены соотвемтвенно с m+1-м входом элемента 5

ИЛИ 15 и вторым входом элемента ИЛИ 18.

Информационные входы 28(1) — 28(m) устройства соединены соответственно с первыми входами элементов И 12(1)-12(m), вторые входы которых соединены соответственно с 10 первого по m-й разряды распределителя 35 импульсов блока 21 управления. Входы установки в ноль триггеров 9(1) — 9(m) соединены с выходом элемента ИЛИ 17; первый и второй входы которого соединены соответ- 15 ственно с выходом элемента И 11 и первым выходом коммутатора 39 блока 21 управления, выход первого разряда распределителя 34 импульсов которого соединен с входом установки в ноль триггера 7 и 20 вторым входом элемента И 10. Выход n-ro разряда распределителя 34 импульсов соединен с входом установки в ноль триггера 8 и первым входом элемента И 11, второй и третий входы которого соединены соответ- 25 ственно с прямым выходом триггера 7 и выходом вычитателя 5. выход генератора ЗЗ импульсов блока 21 управления соединен с входами синхронизации регистров 1 — 3 и 22 сдвига. Выход элемента И 52 блока 21 уп- 30 равления соединен через коммутатор 41 с управляющими входами регистров 1 и 3 элемента.ИЛИ 18 соединен с первыми входами группы элементов И 26(1) 26(rn), выходы которых являются информационными выходами 29(1) — 29(m) устройства. Выходы. группы элементов ИЛИ 27(1)-27(в) соединены соответственно с входами группы, элементов 32(1)-32(m) индикации. Входы группы элементов ИЛИ 27(1)-27(m) являются группой входов 30(1,1)-30(1;m)...30(m.1)30(в.m) признака экстремального пути устройства. Вторые входы группы элементов И 26(1)-26(m) соединены соответственно с выходами разрядов с первого no m-й распределителя 35 импульсов блока 21 управления. Управляющий и установочный входы регистра 22 сдвига соединены соответственно с вторым выходом коммутатора

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

Выход генератора 33 импульсов (фиг.2) соединен с входом распределителя 34 импульсов, выходы которого с первого no n-й, где и — количество разрядов представления весов ветвей, соединены через коммутатор 37 с входами элемента ИЛИ 45 блока

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

34 импульсов и непосредственно — с выходом m-го разряда распределителя 35 импульсов. Выход генератора Зб одиночных импульсов соединен с входом коммутатора

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

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

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

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

1709346 8 входом элемента И 53 и входом элемента 56 задержки, выход которого соединен с входом установки в ноль триггера 43. Выход

Входы элемента ИЛИ 47 соединены .с управляющими входами 57(1)-57(К) блока

21 управления. Выходы (1.1)-(1 m) блока 21

20 управления соединены соответственно с выходами первого — m-ro разрядов распределителя 35 импульсов. Первый выход коммутатора 39 соединен с выходом (2) блока 21 управления, выход (3) которого соединен с

25 выходом первого разряда распределителя

34 импульсов. Выход и-ro разряда распределителя 34 импульсов соединен с выходом (4) блока 21 управления, выход (5) которого соединен с первым выходом коммутатора 41. Выход элемента И 54 соединен

30 с выходом (6) блока 21 управления, выход (7) которого соединен с выходом элемента

ИЛИ 45. Выход элемента ИЛИ-НЕ 48 соединен.с:выходом (8) блока 21 управления, вы- 35 ходы (9),(10),(11) и (12) которого соединены соответственно с выходами генератора 33 импульсов, элемента НЕ 50, с инверсным выходом триггера 44 и вторым выходом коммутатора 41.

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

В качестве сумматора 4 и 23 и вычитателя

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

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

Коммутация моделей узлов в соответствии с топологией моделируемого графа выэлемента ИЛИ 47 соединен" с входом установки в единицу триггера 43, инверсный 5 выход которого соединен с вторым входом элемента И 53. Выходы первого, и-1-го и и-ro разрядов распределителя 34 импульсов соединены с входами элемента .

ИЛИ-НЕ 48. Выход первого разряда рас- 10 пределителя. 34 импульсов соединен с входом элемента НЕ 50. Прямой выход триггера 44 и выход первого разряда распределителя 34 импульсов соединены с входами элемента И 54. Информационный 15 вход коммутатора 41 соединен с выходом элемента И 52. полняется так, что информационные входы

28(1)-28(m) моделей одних узлов подключают к информационным выходам 29(1) — 29(m) моделей других узлов, выходы 31(1) — 31(m) признака экстремального пути которых подключают к входам 30(1.1)-30(1.m)...30(m.1)—

30(m,m) признака экстремального пути предыдущих моделей узлов. Неиспользованные входы ЗО(1.1) — 30(1.m)...30(m.1)30(m.m) признака экстремального пути соединяются с шиной логического нуля.

Блок 21 управления для всех моделей узлов является общим.

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

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

Старшие и и п-1-,е разряды являются знаковыми, а остальные разряды, с второго по и-2-й вкл ючител ьно, и редназначен ы для представления величины веса модели ветви. Положительный вес представляется в . двоичном коде, а отрицательный — в дополнительном коде. Регистры 1 и 22 сдвига содержат m.ï двоичных разрядов и предназначены для хранения. m последовательных двоичных кодов по и разрядов в каждом.

В регистр 1 сдвига записывают m двоичных кодов веса ветвей, входящих в узел, а в регистр 22 сдвига — вес m ветвей, исходящих из узла. Регистр 2 сдвига содержит и разрядов и предназначен для промежуточного запоминания одного,ri-разрядного кода.

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

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

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

В режиме ввода весов ветвей в регистры 1 и 22 сдвига коммутатором 39 (выполненным, например, в виде переключателяна два положения) блока 21 управления под1709346

10 ключают выход генератора 36 одиночных импульсов к входу установки в единицу триггера 42. С помощью коммутаторов 37 и

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

Коммутатором 38 блока 21 управления задают комер ветви. Например, если выполкяется ввод веса в седьмую ветвь, то выход седьмого разряда распределителя 35 импульсов подключают к входу элемента

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

Ввод последовательного кода веса ветви в регистр 1 или 22 сдвига осуществляется после подачи с помощью коммутатора

40 (выполненного, например, в виде кнопочного переключателя) единичного сигнала с выхода элемента НЕ 49 на управляющий вход генератора 36 одиночных импульсов.

Последний выделяет из последовательности импульсов выхода элемента И 51, действующих с частотой f/m и, одиночный импульс, устанавливающий через коммутатор 39 триггер 42 в единичное состояние на время

m n/f. Триггер 42 сбрасывает в нулевое водтояние следующим импульсом последо-. мт©аьнюють введя аммента И 51,, @тария формируется из последовательности n-.ro разряда распределителя 34 импульсов, saдержанной элементом 55 задержки на время длительности тактового импульса генератора 33 импульсов, и последовательности а-го разряда распределителя

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

В процессе ввода весов в регистры 1 и

22 сдвига импульс, формируемый на выходе элемента И 52 блока 21 управления, поступает на управляющий вход регистра 3 сдвига, в который под действием тактовых импульсов генератора 33 импульсов блока

21 управления записывается двоичный код максимального веса 00.111...10, формируемый на выходе элемента ИЛИ-НЕ 48 бло25

35 ка 21 управления из последовательностей импульсов n-ro, и-1-ro и первого разрядов распределителя 34 импульсов. Коммутатор 6 при нулевом состоянии тригггера 8 подключает информационный вход регистра 3 сдвига к его выходу, что обеспечивает

40 динамическое хранение кода максимального веса путем его циркуляции поддействием тактовых импульсов генератора 33 импульсов блока 21 управления.

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

50 ноль

В режиме ввода весов первый выходной импульс генератора 36 одиночных импульcos блока 21 управления через коммутатор

39 и элемент ИЛИ 17 устанавливает все

55 триггеры 9(1)-9(m) в нулевое состояние.

Триггеры 43 и 44 блока 21 управления также находятся в нулевом состоянии. Триггер 4Д устанавливается р нулевое состояние

ЮСМДЮМТМЬНЮЮТЬФ РНХЮДв ЭЛВМЮКТФ И

51, gmepyg через элемент 56 аддерщкн иа

20 элемента ИЛИ 46 импульса, задающего но1709346 триггера 44 блока 21 управления к одному из входов элемента ИЛИ 15.

Пуск устройства осуществляют комму- 20

$-триггера 44 и устанавливает его в единичное состояние. Триггер 44 единичным сигналом прямого выхода открывает элемент И 30

40 последовательность импульсов первого разряда распределителя 34 импульсов бло- 45 ка 21 управления, действующая на. инфор50

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

В режиме моделирования коммутатором 39 блока 21 управления подключают выход генератора 36 одиночных импульсов к входу установки в единицу триггера 44.

Подключая выход элемента И 54 блока 21 управления к входу элемента ИЛИ 18 с помощью ключа 20, задают начальный узел графа. Конечный узел графа задают ключом

19, который подключает инверсный выход татором 40 блока 21 управления, с помощью которого на управляющий вход генератора

36 одиночных импульсов подают единичный сигнал выхода элемента НЕ 49. Выходной импульс генератора 36 одиночных импульсов блока 21 управления поступает через коммутатор 39 на вход установки в единицу

54, на выход которого поступает последовательность импульсов первого разряда распределителя 34 импульсов.

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

28(1)-28(m) рассматриваемого узла действует последовательность импульсов первого разряда распределителя 34 импульсов блока 21 управления, которая через элементы

И 12(1)-12(m), управляемые последовательностями импульсов разрядов распределителя 35 импульсов блока 21 управления, и элемент ИЛИ 16 поступает на первый вход элемента И 10, тактируемый той же последовательностью импульсов первого разряда распределителя 34 импульсов. На выходе элемента И 10 формируется последовательность импульсов, первый импульс которой устанавливает S-триггер 7 в единичное состояние, Триггер 7 единичным сигналом прямого выхода снимает блокировку элемента И 11.

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

50 блока 21 управления последовательность импульсов первого разряда распределителя

34 импульсов.

После прохождения маркера первого разряда через сумматер 4 с выхода регистра

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

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

Двоичный код веса первой ветви вместе с импульсом маркера первого разряда сдвигается под действием тактовых импульсов с выхода-регистра 2 сдвига и через комму- 15 татор 6 записывается под действием тактовых импульсов в регистр 3 сдвига и поступает также на вычитающий вход вычитателя 5, на вход уменьшаемого которого в это время под действием тактовых импуль- 20 сов с выхода регистра 1 сдвига через сумматор 4 сдвигается двоичный код веса второй ветви графа.

Если вес второй ветви графа больше веса первой ветви, то на выходе вычитателя 25

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

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

B том случае, когда вес второй ветви графа меньше веса первой ветви, на выходе вычитателя 5 формируется дополнительный код отрицательной разности, в п-м знаковом разряде которого действует 45 единичный сигнал, открывающий элемент

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

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

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

9(1)-9(m) и через один из элементов И 13 (1), открытый в это время для 1-й ветви l-м разрядом распределителя. 35 импульсов блок 21 управления, — на вход установки в единицу S-триггера 9(!), которыйустанавливается в единичное состояние. Остальные триггеры 9(1) — 9(m), кроме триггера 9(i), сбрасываются в нулевое состояние. Триггер 9(!) запоминает текущий l-й номер наименьшей ветви графа.

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

23 под действием тактовых импульсов генератора 33 блока 21 управления из регистра

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

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

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

1709346

В сумматоре 23 во время действия импульсов первого разряда распределителя

34 импульсов блока 21 управления блокируются цепи переноса по входу признака разрешения переноса сигналом, формируемым на выходе элемента НЕ 50 блока 21 управления. Для прохождения маркера первого разряда на информационные выходы

29(1) 29(m) модели узла служит элемент И

25, управляемый импульсами первого разряда распределителя 34 импульсов блока

21 управления, Маркер первого разряда под действием тактовых импульсов генерируется через каждые n тактов на выходе регистра 3 сдвига и через коммутатор. 6, Элементы И 24 и 25, ИЛИ 18,.И 26(1)-26(m) поступает на соответствующие информационные выходы 29(1)-29(а) модели данного узла и далее согласно топологии моделируемого графа — на информационные входы

28(1) 28(m) других узлов моделирующей структуры.

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

На другой вход сумматора 4 с выхода регистра 1 сдвига поступают под действием .тактовых импульсов двоичные коды весов входящих ветвей, с первой по m-ю, рассматриваемой модели узла. 3а время и тактов сумматор 4 выполняет сложение двух последовательных кодов, например двоичного кода, действующего на информационном входе 28(1), с двоичным кодом веса первой ветви, входящей в.рассматриваемый узел.

Если сумма весов ветвей графа вдоль этого пути меньше двоичного кода регистра

3 сдвига, то на выходе вычитателя 5 формируется единичный сигнал в и-м знаковом разрядекоторый открывает элемент И 11.

Триггер 8 данной модели устанавливается

Юыходным импульсом элемента И 11 в едиНИЧНЮЮ OOOTO$lHNO И МДЮМЮЧФЮТ KOMM+1=

ТЮр 6 В ЮЮЮТЮЯНИЮ1 ИДИ КОТ®ЮМ ДВОИЧНЫЙ

КЮД НЮИМЮНЬФЮЙ ЩММН IOOOI IOTIOA ГДФфЮ

15

23. На другой вход сумматора 23 под дей35 ствием тактовых импульсов из регистра 22 сдвига поступают последовательно двоич40

50 графа — на информационные входы 28(1)28(m) других моделей узла.

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

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

6 сдвигается под действием тактовых импульсов в регистр 3 сдвига. Одновременно выходной импульс элемента И 11 через элемент И 13(1), открытый в это время импульсом первого разряда распределителя 35 импульсов блока 21 управления, устанавливает триггер 9(1) в единичное состояние, а триггеры 9(2)-9(m) через элемент ИЛИ 17 сбрасываются в нулевое состояние. . За определенное время тактов выполняется анализ всех путей, проходящих через ветви данного модуля. В результате, если экстремальный путь, вдоль которого алгебраическая сумма положительных и отрицательных весов ветвей графа минимальна, проходит через J-ю ветвь данной модели узла моделирующей структуры, то триггер 9(J) устанавливается в единичное состояние, а в регистре 3 сдвига запоминается минимальная алгебраическая сумма весов ветвей графа вдоль экстремального пути, начинающегося в начальном узле графа и проходящего через J-ю ветвьданного модуля.

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

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

44 не устаНЮвится в нулевое состояние. Это йф©ИФКЮДИТ Ю МЮЮЯЯЮНИИ ЮНМИМ ЮЮЮХ OP

ТЮИ1 ЮВЯФНЮЮВЩИХ НФЧФЛЬННЙ И КЮНЮЧНЫЙ

УУН МЮДЮаИРУЮМЮЮ ГРЮфЮ, ДЮЙЮТЮИТЮДЬНЮ, 1709346

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

Если процесс анализа во всех узлах модели сети завершился, то в регистрах 3 сдвига всех моделей узла содержатся двоичные коды минимальных сумм весов графа вдоль экстремальных путей. Тогда на вы- 25 ходах вычитателей 5 всех моделей узла отрицательная разность не может быть сформирована и элементы И 11 во всех уз- лах модели сети будут закрыты. В этом случае на выходе элемента ИЛИ 47 блока 21 30 управления формируется нулевой сигнал.

Последовательность импульсов выхода элемента И 51 блока 2.1 управления через элемент 56 задержки на длительность тактового импульса сбрасывает триггер 43 в 35 нулевое состояние, при котором открывается элемент И 53. Следующий импульс после довательности элемента И 51 проходит через элемент И 53 и сбрасывает триггер 44 в нулевое состояние, единичный сигнал ин- 40 версного выхода которого через ключ 19 модели, содержащей конечный узел моделируемого графа, поступает на вход элемента ИЛИ 15. Единичный сигнал выхода элемента ИЛИ 15 открывает один из эле- 45 ментов И 14(1)-14(m), управляемый, например, триггером 9(!), который запоминает номер l-й ветви, принадлежащей экстремальному пути. С выхода элемента И 14(!) единичный сигнал индикации экстремаль- 50 ного пути поступает на выход 31(l) модели, содержащей конечный узел графа, и далее поступает на входы 30(1) — 30(m) тех моделей узла, информационные выходы 29(1)-29(m)

° которых соединены с информационными 55 входами 28(1)-28(m) модели, содержащей конечный узел.

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

Этой же цели служат индикационные элементы 32(1) 32(m).

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

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

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

221000 руб/год.

Формула изобретения

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

И (где m — количество исходящих ветвей узлов-графа), группа из m элементов ИЛИ и группа из m элементов индикации, а в блок управления введен пятый коммутатор, информационный вход которого соединен с выходом второго элемента И блока управления, причем выход четвертого регистра сдвига модели узла соединен с входом первого слагаемого второго суМматора той же модели узла, вход второго слагаемого которого соединен с выходом" третьего элемента И той же модели узла, выход второго сумматора модели узла — с . информационным входом .четвертого .реги- . стра сдвига и с первым входом четвертого

19

1709346

20 элемента ИЛИ той же модели узла, третий вход которого соединен с выходом четвертого элемента И той же модели узла, прямой выход первого триггера модели узла — с первым входом третьего элемента И той же модели узла, второй вход которого сое; динен с выходом коммутатора той же модели узла, выход четвертого элемента

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

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

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

1709346

Фиг.2 1709346

Составитель В. Васильев

Редактор М, Петрова Техред М.Моргентал Корректор А. Осауленко

Заказ 428 . Тираж .. Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101