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

1

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

Цель изобретения - упрощение процесса моделирования гр афон,

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

Устройство для моделирования графов содержит регистр 1 сдвига, сумматор 2j блок 3 управления триггер 4, группу триггеров 5(1) - ); элементы ,И 6-8, первую группу элементов И 9(1) -.9(ni)j вторую группу элементов И 10(1) - 10(vn)5 третью группу элементов И 11(1) - 1 ) элементы ИЛИ 12-14j ключевые элементы 15 и 16, информационные входы 17(1) - 17 () моделей ветвей, выход 18°модели узла индикационные зходь 19 (1) - 19 (|т) моделей ветвей, индикационные выходы 20(1) - 20 (ьп) моделей ветвей.

Блок 3 управления (фиг. 2) содержит генератор 2 импульсов, распределители 22 и 23 импульсов, генератор 24 одиночных, импульсов, первый и второй кнопочные коммутаторы 25 и 26, переключатели 27 и 28,, триггер 29, элементы И 30 и 31„ элементы ИЛИ 32 и 33, элемент НЕ 34.

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

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

Генератор 21 импульсов блока 3 управления (фиг. 2) вырабатывает последовательность тактовых импульсов частоты t , из которых распреде;гител 22 импульсов формирует ь, последовательностей импульсов ча стоты С /v j

461102

где h - количество разрядов представ- j le.Hi-Dt весов моделей ветвей, сдвинутых друг относительно друга на время 1/{. Из последовательности импуль5 сов h-го разряда распг)ед,елителя 22 импульсов распределитель 23 импульсов формирует Н-, последовательностей импульсов длительностью гл/f 5 действующих с частотой I /1-г,.л I-I с/ винутых

10 ДРУГ относительно д.руга на время h /f . Б режиме ввода весов моделей ветрей в регистр 1 сдвига пеаеключате- .пем 27 блока 3 управления подключается выход генератора 24 одиночных

is импульсов к единичному зходу триггера 29. С помощью коммутатора 25 и 26- блока 3 у::равления задается до- (толнительаый пвоичный код веса модели ветви и номер модели ветви йоот;-;0 ветственно, Коьмутатор 25 подключает Б единичнь х разрядах дополнргтель- нот о двоичного кода веса модели ветви соответствующие выходы распределителя 22 имтульсов к входам элемента

7:5 ИЛИ 32, и-а выходе -которог о формируется последовательный /дополнительный СОД веса модели ветви. Например если вес модели .ветзи равен пяти (дополнительный дво 1чнь:й код

ЗП 1 i .... 101 1J5 то всех разрядоЗд .лроме третьего разряда, распределителя 22 BMnyjrbcoB Г одключа отся ком: ;утатором 25 к входам элемента ИЛИ 32,

/ С помощью коммутатора 26 блока

- управления задается: номер модели . Например,, если выполняется Бвод веса в седьмую модель ветви, то вькод седьмого разряда распреде- .патепя 23 импульсов подключается к лходу элемента }-ШИ 33,, на выходе ко- торо)Ч) формируегся импульсный сигнал д.пительностью / s совпадшощий по фазе с временем сдвига с выхода регистра 1 сдвига под действием гзктовьк импульсов генератора 21 . HMnyjFbcoB h -разрядного двоичного кода веса для седьмой модели ветви. Вгфд последовательного допол- ните,г ьного кода веса модели в регистр 1 сдвига осуществляется после: подачи единичного сигнала с въкоцг элементов НЕ 34 через переключатель 28 на управляющий БХОД гене;;| тора 24 единичных и fпyлгJCoв, который выделяет из последовательности импульсов элемент И 30, дей- ствук1щих с частотой / /i-o-v, ., одиночный импульс, устанавливающий через пеsiO

S3

3

реключатель 27 триггер 29 и единичное состояние на время i-n-h/J.

Триггер 29 сбрасывается в нулевое состояние следующим импульсом последовательности сигналов элемента И 30. Триггер 29 в единичном состоянии открывает сигналом единичного выхода элемент И 31, через который на управляющий вход регистра 1 сдвига поступает одиночный импульсный сигнал с выхода элемента ИЛИ 33, задающий номер модели ветви. Под действием тактовых импульсов генератора 21 импульсов блока 3 управления последовательньм дополнительный двоичный код веса модели ветви записывается с выхода элемента ИЛИ 32 последовательно во времени, начиная с младших разрядов, в регистр 1 сдвига во время действия на выходе элемента ИЛИ 33 импульса, задающего номер модели ветви.

Одиночньш импульс 24 одиночных импульсов через переключатель 27 устанавливает также триггеры 4 и 5 в нулевое состояние.

Аналогичным образом в регистр .1 сдвига записывают дополнительные двоичные коды весов всех моделей ветвей с первой по tn -ю. Устройство (фйг.1) моделирует ет, моделей ветвей графа, входящих в модель одного узла, С делью моделирования сложных графов устройства коммутируют между собой в соответствии с топологией решаемой задачи, формируя структуры, моделирующие графы. Например, выход 18 модели одного узла графа подключают к информационным входам 17 моделей ветвей других узлов графа. При этом индикационные выходы 20 моделей одних ветвей подключаются к индикационным входам 19 моделей других ветвей.

о

Пример модели графа, содержащей три модели узла, каждая из которых содержитbrt моделей ветвей, изображен на фиг. 3 (на фиг. 3 а изображен моделируемый граф, на фиг.З S - устройство, его моделирующее).

В режиме моделирования переключателем 27 блока 3 управления (фиг.2 подключается выход генератора 24 одиночных импульсов к входу ключевого элемента 16, с помощью которого задается начальная модель узла. Пуск устройства осуществляется переключателем 28, с помощью которого на

46110 ,

управляющий вход генератора 24 одиночных импульсов подается единичиьм сигнал выхода элемента НЕ 34. Одиночный импульс генератора 24 оди- 5 ночных импульсов блока 3 управления поступает через ключевой элемент 16 и элемент ИЛИ 12 на единичный вход тригг ера 4 модели начального узла и устанавливает его в единичное состо10 яние. Единичный сигнал прямого выхода триггера 4 поступает по шине 18 на информационные входы 17 моделей ветвей других узлов.

Предположим, что на первый инфор15 мационный вход 17 первой модели ветви поступил единичный сигнал с единичного выхода триггера 4 предыдущей модели. В этом случае через первый элемент И 9 данной модели про20 ходит последовательность импульсов первого разряда распределителя 23 импульсов блока 3 управления. Последовательность импульсов с выхода первого элемента И 9 поступает на

5 выход элемента ИЛИ 14, выходной сигнал которого открывает элемент И 7 во время фазы сдвига с выхода регистра 1 сдвига (под действием тактовых импульсов генератора 21 импуль0 сов блока 3 управления) дополнительного двоичного кода веса первой модели ветви.

Последовательность импульсов первого разряда распределителя 22 им5 пульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2, на другой вход.которого сдвигается с выхода регистра 1 сдвига дополнительный двоичный код веса пер0 вой модели ветви. Сумматор 2 выполняет последовательно во времени, начиная с младших разрядов, суммирование дополнительного двоичного кода веса первой модели ветви с последо5 вательностью единиц младшего разряда, представленных, последователь-. ностью импульсов выхода элемента И 7. За время hn.b, тактов дополнительный двоичный код веса первой модели вет0 ви увеличивается на единицу младшего, разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 21 импульсов блока 3 управления

5 в регистр 1 сдвига.

Спустя времяр.т-п тактов, где Р, вес первой модели ветви, на выходе переноса сумматора 2 сформиру- ,

5.

ется сигнал переноса из и -го разряда текущего двоичного кода первой модели ветви, которьш через элемент И 8, тактируемый последовательностью импульсов К:.-го разряда распредели- теля 22 импульсов, поступает через элемент ИЛИ 12 на единичньш .вход триггера и через первый элемент И 11, открытый в это время сигналом первого разряда распределителя 23 импульсов блока 3 управления, на единичный вход первого триггера 5.Триггер 4 модели узла и первый триггер 5 первой модели ветви устанавливаются в единичные состояния. Триггер 4 в единичном состоянии блокирует сигналом инверсного выхода элемент И 7, и процесс суммирования в сумматоре 2 прекращается.

В том случае, когда на все инфор- мационные входы 17 моделей ветвей одновременно поступают единичные сигналы с выходов 18 моделей других узлов графа, чер.ез элементы И 9 и ИЛИ -14 последовательно во времени- поступают последовательности импульсов с выходов всех разрядов распределителя 23 импульсов, которые открывают .элемент И 7. Последовательность импульсов первого разряда распредели- теля 22 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных, кодов весов всех моделей ветвей. Каж- Mbie«-iTh тактов допо1лнительные коды весов hn моделей ветвей после;дователь но во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сум- матера 2 вновь записываются в регистр 1 сдвига. Спустя время Р, тактов, где Р| - наименьший вес из всех моделей ветвей, принадлежащий, например., 1 -и модели ветви,, на вы- ходе сумматора 2 из текущего дополнительного двоичного кода веса t-и модели ветви сформируется сигнал переноса из - -го разряда, который через элементы И 8, ИЛИ 12 и элемент И 8, I-и элемент И 11 поступает соответственно на единичные входы триггеров 4 и i -го триггера 5, устанавливая их в единичные состояния. Триггер 5 запоминает номер мо- дели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае i-и модели ветви). Триг5

61

5 0 S

0 0 5 0 5 0 5

106

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

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

В режиме индикации кратчайшего пути, выделяемого из дерева кратчайших путей, в модели конечного узла с помощью ключевого элемента 15 подключается единичньм выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13. Единичный сигнаш с выхода триггера 4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10, вторые входы которых управляются триггерами 5 моделей ветвей. Из всей группы элементов И 10 откроется элемент И 10 той модели ветви, для которой триггер 5 находится в единичном состоянии. Единичный сигнал триггера 5 модели ветви, принадлежащей кратчайшему пути, проходит через соответствующий элемект И 10 ка индикационный выход 20 модели ветви и далее поступает на индикационные входы 19 других моделей узлов, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути.

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

Устройство для моделирования графов, содержащее триггер, первый, второй и третий элементы И, первый, второй и третий элементы ИЛИ, первый и второй ключевые элементы, единичный и нулевой ВЫХ.ОДЫ триггера подключены к первым входам соответ- CTBeHifo первого и второго элементов И; единичный вход триггера соединен с выходом первого элемента ИЛИ,первый вход которого подключен к выходу третьего элемента И, выход второго элемента ИЛИ соединен с вторым входом второго элемента И, о т л и ч а- ю D( е е с я тем-, что, с целью упрощения процесса моделирования графов, в него введены блок управления, включающий генератор импульсов, первый и второй распределители импульсов, генератор одиночных импульсов, первый и втор ой кнопочные коммутаторы, первый и второй переключа- тели, триггер, первый и второй элементы И, первый и второй элементы ИЛ и элемр1нт НЕ, а также регистр сдвига сумматор, .группа триггеров и три группы элементов И по trr. элементов в ка5кдой, где пч количество ветвей моделируемого графа, причем выход генератора импульсов блока управления соединен с входом первого распределителя импульсов блока управления, выходы которого с первого по п -и (h - количество разрядов представления весов ветвей графа) соединены через первый кнопочный коммутатор с соответствующими входами первого элемента ИЛИ блока управления,и -и выход первого распределителя импульсов блока управления соединен с входом второго распределителя импульсов блока управления, первыми входами первого элемента И блока управления третьего элемента И устройства, выходы второго распределителя импульсо блока управления с первого соединены через второй кнопочный ком мутатор блока управления с соответствующими входами второго элемента ИЛИ блока управления,m-и выход второго распределителя импульсов блока управления подключен к второму входу первого элемента И блока управления, выход которого соединен с тактовым входом генератора одиночных импульсо блока управления и нулевым входом триггера блока управления, выход ге- нератора одиночных импульсов блока управления через размыкающий контакт первого переключателя блока управления соединен с единичным входом триггера блока управления, единичный выход которого подключен к первому входу второго элемента И блока управления, второй вход которого соединен с выходом второго элемента.или блока.управления, управляющий вход генератора одиночных импульсов блока управления через второй переключатель соединен с выходом элемента НЕ блока управления, вход которого подключен к нулевой шине устройства, выход генератора импульсов,блока управления соединен с входом синхронизации регистра сдвига, информационный .и управляющий входы которого подключены соответственно к выходам первого элемента ИЛИ и второго элемента И блока управления, первые входы элементов И первой группы являются информационными входами устройства, вторые входы элементов И первой группы соединены с соответствующими выходами второго распределителя импульсов блока управления выходы элементов И первой группы соединены с входами третьего элемента ИЛИ, выход которого подключен к второму входу второго элемента И

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

. чевой элемент соединен с вторьгм входом первого элемента ИЛИ устройства

и I ) яи

Изобретение относится к области цифровых вычислительных машин, а именно к устройствам для обработки цифровых данных. Изобретение может быть использовано в автоматике и в специализированньгх вычислителях . для решения задач о кратчайшем пути, дискретных вариационных задач, задач оптимального управления и дифференциальных игр. Цель изобретения - упрощение процесса моделирования графов. Устройство содержит блок управления, триггер, три элемента И, три элемента ИЛИ, два ключевых элемента,- регистр сдвига, сумматор, группу триггеров и три группы элементов И. Изобретение позволяет моделировать т ветвей с разными весами. В процессе построения сложных однородных вычислительных структур, содержащих множество соединенных ,. между собой ячеек из моделей узлов и моделей ветвей, эффект упрощения процесса моделирования увеличивается пропорционально количеству ячеек однородных вычислительных структур, причем блок,управления является общим для всех ячеек однородной вычислительной структуры. 3 ил. i (Л ьо 4; 9)

Z0{

.

ZOlfl,

pt/ei/Ko №1

/7f2;

S

Составитель С.Назаров Редактор Н Тупица Техред О,Гортвай Корректор А.Обручар

Заказ 4003/43 Тираж 671 , Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная. 4

1/5W/

20(2)20(1)

204

wV;

/ rt

/Sfmj -о

Ж

mz;

/7Ы J№J

;- y-2Wm;

m/j

20/2

Ячейка

Щг

-тбР -Z-O

/9(w;

-о /в

(2;

Ячейка

J3(lh}9(2}

Щт) 18

17(2) 17(m)

. 3