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

 

, 1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее перв5по группу из ij регистров, образунхцих треугольную наддиагональную : мaтipицy(i « 1, №.-1; J- i+l ,т), пер-i вую группу элементов ИЛИ, блок управления и вторую группу регистров, j-ro регистров JBTOpoft группы .подключены к первым «ходам j-x элементов И Первой группы, :вторые входы которых соединены с соответствуювдам разрядом первой выходной шины блока управления,, j-й разряд второй выходной шины которого подключен к первым входам J-X элементов И второй группы выходи кото1 ых соединены с входами j-ro регистра второй групшд, о т л и ч а, ю вд ее с я тем, что, с целью повшаения быстродействияв него введены сумматор, блок формирователей пути,, блок выбор.а. максимального кода, вторая группа элементов ИЛИ, третья группа регистров, третья четвертая и пятая групгал элементов И, элементыИ и элемент ИЛИ, выход , которого подключён к первым входам элементов И, вторые входы которых соединены с соответствуквдимиу разрядами первой выходной шины блоки управления выход i-го элемента И подключен к первым входам i-x элементов И третьей группй, выходы которых соединены с вых одами i-ro регистра треть ейГруппы, выход которого подключены к первым входам i-x элементов И четвертой группы, выходы которых соединены с входаюг i-Й группы блока выбора-, максимального кОда, выходы netJвой группы которого, подключены ж вторым входам соответствующих элементов И второй группа, выходы второй группы блока выбора максимального кода соединены с входами первой группы блока формирователей пути входы второй группы которого прдклю- . чены к соответствукадим разрядам второй ВЫХОДНОЙ шины блока управления , первый клход которого соединен с входе блока формирователей пути, ; установочные входы реги.стров третьей ГР5ГППЫ подключены к второму выходу блока управления, третий 5выхсщ icoio, рого соединен с вторыми входами зле-. ментов И четвертой группы, выходы ij-ro рёгисфра первой группы подключены к первым входам ij-x элементов И пятой группы-, выходы которых соединены с ij-мй входами соответсойую- «их элементов ИЛИ первой группы, выходы которых подключены к входам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторыми входами соответствуюОР щих элементов Итретьей группы, ij-й разряд третьей выходной шины блока ф ф ел управления подключен к вторым входам i}-x элементов И пятой группы, выходам элементов И первой группы соединены с j-ми входами соответствуй1цих элементов ШШ второй группы, выходаа которых подключены к входам второй группы сумматора, четвертый вход блока управления является управляющим входом уст|ройства. 2. Устройство по п.1, о т л и чающееся тем, что, блок формирователей пути содержит регистр, первую и вторую группу элементов ИЛИ и треугольную наддиагональную матрицу формирователей пути, каждый ii-й (, j i+1 ,т) Формирова

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

СОЦИАЛИСТИЧЕСНИХ .. РЕСПУБЛИК

)(у) G 06 Г. 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВ е== ее. «й.(21) 3341571/18-24 (22) .09 ° 07.81 (46) 23. 04.83." Бюль 9 15 (72) В.A. Титов, С.и. Баженов и

В К, Лев в (53) 681.333(088 ° 8) (56) 1.. Авторское свидетельство СССР

Р 525454, кл. 6 06 F 15/20, 1977.

2. Рвторское свидетельство СССР . no заявке Р 2830339/18-24, кл. G 06. F 15/20, 27.07.79 (прото-, тип). (54) (57), 1. УСТРОЯС АБО ДЛЯ ИщдЛИР()-.

ВАНИЯ СЕТЕВЫХ Х"РАФОВ, содержащее первую группу из ij регистров,. обра- . вуниаих треугольнуи нандиагональнум-матрицу (i < 1, й-1;1., 1+1,m), пер-. ., вую группу элементов ИЛИ, блок управ- ления и вторую группу регистров, вы-:

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

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

„„SU„„103 3965 A подключены к первым входам i-х элементов И четвертой группы, выходы которых соединены с входами 1-й группы блока выбора.максимального кода, выходы первой группы которого,подключены кк вторым входам соответствующих элементов И второй группй, выходы второй группы блока выбора максималь- . ного кода соединены с входами первой группы блока формирователей пути» входы второй группы которого подклю- . чены к соответствующим разрядам ° второй выходной шины блока .Управле- ния, первый выход которого соединен с входом блока. формирователей пути, установочные входы регистров третьей группы подключены к второму выходу Я блока управления," третий выход которого соединен с вторымИ входами эле- . ментов И четвертой группы, выходы

Ц-го регистра первой группы.. подключены к первым входам ij.-х элементов

H пятой группы; выходы..которых сое- Я дииены с ij-ми входами соответстаую щих элементов ИЛИ первой группы, вы ходы которых подключейы к входам элемента ИЛИ и к входам первой гру пы сумматора, выходы которого соеди иены с вторыми входами соответствую щих элементов И третьей группы, Цразряд третьей выходной шины:- .блока управлейия подключен к вторым входам

ij-х элементов И пятой группы, выхо

1+х элементов:И первой группы соеди нены с j-ми входами соответствующих элементон ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, четвертый вхой блока управления является управляющим входом устройства.

2. Устройство по п.1, о т л и -. ч а ю щ е е с я тем, что, . блок формирователей пути содержит регистр, первую и вторую группу элементов

ИЛИ и треугольную наддиагональную матрилу йорьирователей пути, квилый

i1-й (i=1, - аа1; j= i+1,ю) формирова-

10139á5

10 тель пути содержит три элемента И и триггер, вход которого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента И (i j+1 )-ro формирователя пути соединен с вторыми входами второго и третьего элементов И (i+1, j+1 )-ro формирователя пути, выход третьего элемента И (j j+1 )-го формирователя пути подключен к входу j-го элемента ИЛИ первой группы,, выход которого соединен с вторыми входами второго и третьего элементов И (1,j )-ro формирователя пути, выход второго элемента И (i j )-го формирователя пути подключен к входу i-го элемента ИЛИ первой группы и к входу i-ro элемента ИЛИ второй группы, выход которого соединен с входом одноименного разряда регистра, выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вторые входы второго и третьего элементов И (1,m )-го формирователя соединены с входом блока, Х-й вход первой группы входов которого подключен к первым входам первых элементов И формирователей пути i-й строки, j-й вход второй группы входов блока подключен к вторым входам первых элементов И формирователей пути i-го столбца.

3. Устройство по п.1 о т л и ч а ю щ е е с я тем, что блок управления содержит й+2 триггера; четыре группы элементов И, группу инверторов, элемент ИЛИ, элемент И, инвертор, регистор, счетчик, схему управления, дешифратор и генератор, выход которого подключен к первому входу элемента"И, второй вход которого соедиИзобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.

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

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

И, элемент ИЛИ, узел опроса, два регистра кода адреса, буферный и выходной регистры С13. нен с четвертым входом блока, выход элемента И подключен к синхронизирующим входам триггеров, выход (m+2 )-го триггера соединен с вторым входом блока, с информационным входом первого триггера и со счетным входом счетчика, выходы которого подключены к входам первой группы схемы сравнения и к входам дешифратора, — i и (i= 1, в=1 ) выход дешифратора соединен с первым входом j — го (j= i+1, m ) элемента И первой группы, с первыми входами (i, j )-х элементов Й второй группы, с первым входом i-ro элемента И третьей группы и через i-й инвертор группы с первым входом i-го элемента

И четвертой группы, выход которого подключен к информационному входу (i+1 )-го триггера, выход i-ro триггера соединен с вторыми входами i-x элементов И третьей и четвертой группы, с вторыми входами (i j )-x элементов И второй группы и с i-м разрядом первой выходной шины блока, выход (i,j )-Го элемента И второй группы подключен к (i,j )-му разряду третьей выходной шины блока, выходы элементов И третьей группы и выход щ-го триггера соединены,с соответствующими входами элемента ИЛИ, выход которого подключен к информационному входу (m+1 )-го триггера, выход которого соединен с информационным входом (m+2 )-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сравнения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И °

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

Наиболее близким техническим решением к изобретению является устройство, содержащее первую группу из регистров, образующих треугольную наддиагональную матрицу (i= 1,m-1;

j= i:+1,m ),.ïåðâóþ группу элементов ИЛИ, блок управления и вторую группу регистров,выходы j-ого регистра второй .группы подключены к первым входам

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

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

65 второй выходной шины которого подклвчен к первым входам j-х элементов И второй группы, выходы которых соеди-, нены с входами j-го регистра второй группы f2).

Недостатком известного устройства является низкое быстродействие из-за необходимости двоекратного заполнения счетчиков "весов" дуг матричной модели тактовыми импульсами и последующего сравнения результатов двух просчетов.

Целью изобретения является повышение быстродействия устройства. Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее первую группу из ij регистров, образующих треугольную наддиагональную матрицу(i= 1,m-1; j= i+1,m), первую группу элементов ИЛИ, блок управления и вто-20 рую группу регистров, выходы i- ro регистра второй группы подключены к первым входам j-х элементов И первой группы,.вторые входы которых соедине-. ны с соответствующим разрядом первой 25 выходной шины блока управления, j-й разряд второй выходной шины которого подключен к первым входам j-х элементов И второй группы, выходы которых соединены с входами j -го регистра второй группы, введены сумматор, блок. формирователей пути, блок выбора максимального кода, вторая группа элементов ИЛИ,.третья группа регистров,: третья, четвертая и пятая группы элементов И, элементы И .и элемент ИЛИ, выход которого подключен к первым входам элементов И, вторые входы ко- торых соединены с соответствующими разрядами первой выходной шины блока. управления, выход i-го элемента И под40 ключен к первым входам i-х элементов

И третьей группы, выходы которых .соединены с входами i-ro регистра третьей группы, выходы которого подключены к первым входам i-х элемен- 45 тов И червертой группы, выходы кото-. рых соединены с входами i-й группы блока выбора максимального кода, выходы первой группы которого подключены к вторым входам соответствующих элементов И второй группы, выходы второй группы блока выбора максимального кода соединены с входами, первой группы блока формирователей пути, входы второй группы которого подключены к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров третьей группы подключены 60 к второму выходу блока управления, третий выход которого соединен с вторыми входами элементов И четвертой группы, выходы ij-ro регистра первой группы подключены к первым входам ij-х элементов И пятой группы, выходы которых соединены с ij-ми входами соответствукицих элементов ИЛИ первой группы, выхОды которых подключены к входам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторыми входами соответствующих элементов И третьей группы, ij-й разряд третьей выходной шины блока управления подключен к вторым входам ij-х элементов И пятой группы, выходы 1-х элементов;И первой ".руппы соединены с j-ми входами. соответствующих элементов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, четвертый вход блока управления является управляющим входом устройства.

Кроме того, блок формирователей пути содержит регистр, первую и вторую группу элементов ЙЛИ и треугольную наддиагональную матрицу формирователей пути, каждый Ц-й (i= 1, m-,1;

j= i+1,m ) форьырователь пути содержиттри элемента И и триггер, вход которого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента

И (i,j+1 )-го формирователя пути соединен с вторыми входами второго и третьего элементов И (i+1),j+1 )-ro формирователя пути, выход третьего элемента И (j i+1 )-ого формирователя пути подключен к входу j-го элемента

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

Причем блок управления содержит

m+2 триггера, четыре группы элемен1013965 триггеров, выход (m+2 )-ro триггера соединен с вторым входом блока, с информационным входом первого триггера и со счетным входом счетчика, выходы которого подключены к входам первой группы схемы сравнения и к входам дешифратора, i-й. (i= 1.,m-1) выход дешифратора соединен с первым входом j -ro (j= i+1,m ) элемента И первой группы, с первыми входами (i,j )-х элементов И второй группы, с первым входом i-ro элемента И третьей группы и через i-ый инвертор группы с первым входом i-ro элемента И четвертой группы, выход которого подключен к информационному вхо-15 ду (i+1 )-ro триггера, выход i-ro триггера соединен с вторыми входами

i-х элементоВ И третьей и четвертой группы, с вторыми входами (i,j )-х элементов И второй группы и с i-м 20 разрядом первой выходной шины блока, выход (i j )-го элемента И второй группы подключен к (i,j )-му разряду третьей выходной шины блока, выходы элементов И третьей группы и. выход 25

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

На фиг. 1 показана структурная 4О схема"устройства для моделирования сетевых графов; на фиг. 2 — структурная схема блока формирователей пути; на фиг. 3 - структурная схема блока выбора максимального кода; на Фиг.4 -45 структурная схема блока управления. устройство,цля моделирования сетевых графов (фиг. 1 ) содержит треугольную наддиагональную матрицу 1, состоящую из первой группы регистров 2„,2„,. ° .,2(„, „>„„"и пятой группы элементов И 3, 3,,...,3(„„ ...где

m — максимальное колйчество вершин в графе, первую группу элементов ИЛИ

4, сумматор 5, элемент ИЛИ б, третью

rpynny реГистрОВ 7< ° 7>,:р р° °, 7 щ 1 р третью группу элементов И 8р,8,... ...,8 „,, элементы И 9 р9 р...,9„; четвертую группу элементов И 10„, 10,..., 10 m x, вторую группу элементов ИЛИ 11, вторую группу регистров . 6О

122р12у,...,12щр первую и вторую группы элементов И 13,13 р...,13щ и 14рр14 р...р14»„ р блок 15 формирователей йути, блок 16 выбора максимального Иода, Ьлок 17 управления. 65

Блок 15 формирователей пути (фиг. 2 ) имеет ту же форму и размерность, что матрица 1 и включает триггеры 18„,18., °,18(,„ рр„первые, вторые и третьи элементы И 19, р19,...

° ° °, 19(„„-0р„, 20рйр 20 3р... р 20(„, Ор„и

21„,,21+ р...,21(„, 1,„, первую и вторую группу элементОВ ИЛИ 22 .2.2а. ° .22@, и 23, 234, ° ° °, 23<щ, регистр 24.

Блок выхода максимального кода (фиг. 3 ) включает элементы ИЛИ-НЕ

25,25@,...25„, где n — число разрядов в кодах, узлы 26 р2@,... р2би анализа разрядов, состоящие из схем

27+„27А р..., 27(gg) р поразрядного переноса, в состав которых входят элементы ИЛИ 28 и элементы И 29, ВыхОДы 30 р 30 р ° °, 30(рр.,)и 3 14 р 3 1 р ...,31

Блок 17 управления (фиг. 4 ) вклЮчает триггеры 32 р32 р...р32щ+рр третью и четвертую группу элементов

И 331 р332 ° ° ер33ур .(и 34,рр 34 р ° ° °

34, группу инверторов (элементов НЕ )

35,,35,. ° .,35„„».„, элемент ИЛИ 36, вторую и первую группы элементов

И 37Л,р 37 р... р 37(„р,рад и 38 р 38з р... р

38„„, счетчик 39, дешифратор 40, регистр 41, схему 42 сравнения, инвертор 43, элемент И 44, генератор

45 тактовых импульсов, выходы 461р, 46,..., 46(рр - )р, 47., ..., 47щ

48 и 49, вход 50.

В исходном состоянии триггер 32 + блока 17 установлен в единичное состояние, остальные триггеры 32 - в нулевое. Сигналом с выхода триггера

32„„+ в младший разряд счетчика 39 записывается единица. В результате только на первой выходной шине дешифратора 40 устанавливается сигнал логической единицы, поступающий на первые входы элементов 33,, 37р,р и 38 р35 .. Одновременно сигналом с . выхода триггера 32 по выходу 48 устанавливаются в единичное состояние триггеры регистров 7,,7 ... °,7 на регистре 41 блока 17 записывается код количества вершин в моделируемом графе, на регистрах +«2,...,2(z, матрицы 1 записываются коды "весов соответствующих дуг графа. Если дуги между какими-либо вершинами графа отсутствуют, на соответствующих регистрах записываются коды нуля. Триггеры регистров 12„,12«...12 щ, а также регистра 24 матрицы 15 устанавливаются в нулевое состояние.

С подачей входного сигнала по шине

50 на второй вход элемента 44, с выхода генератора 45 на триггеры 32 начинает поступать последовательность импульсов. С приходом первого импульса триггер 32„ устанавливается В единичное состояние, при этом на выходе 46„„ блока 17 Формируется сигнал логйческой единицы, поступающий

1013965

20 на вход вентиля 9, а на выходе 46+ появляется высокий потенциал, поступающий на входы вентильной группы

З . В результате код, записанный на регистре 2«, через открытую вентильную группу З ó поступает через

5 группу элементов ИЛИ 4 на первый вход сумматора 5 и элемент ИЛИ б.

В зависимости от содержимого регистра 2„ на выходе элемента ИЛИ б

Формируется высокий или низкий !О потенциал, разрешающий или запрещающий запись результата суммирования в регистры 7. Если код ненулевой, на выходе элемента ИЛИ 6 формируется сигнал логической единицы, разре- 15 шающий запись результата, если .код нулевой - Фбрмируется сигнал логического нуля, запрещающий запись результата. На второй вход сумматора

5 с выхода элемента 11 поступает в данном случае код числа нуль.. Результат суммирования (если на регистре 2« ненулевой код), парафазным кодом через открытую вентильную группу 8 записывается на регистр

7 -. В блоке 17 сигнал логической единицы с выхода триггера 32 через элемент 33„ и элемент 36 поступает на вход триггера 32,„,, С приходом второго тактового импульса триггер

32щ Аустанавливается в единичное состояйие, а триггер 32. - в нулевое.

На выходе 47 блока появляется высо4 кий потенциал, поступающий на входы вентильных групп 10, в результате обратные коды чисел, записанных на регистрах 7» поступают на входы узла

26 блока 16.

Блок 16 работает следующим образом.

На. входы элементов .ИЛИ 28 и. И 29 схем 27+,,27,...,27(f8.ô поступает 40 (m-1 ) кодов, каждый из которых представлен и разрядами, с обратных выходов триггеров регистров 7 через вентильные группы 10. В первый момент анализируются старшие разряды 45 всех кодов. Если хотя бы один из старших разрядов кодов равен 1, на выходе элемента ИЛИ-НЕ 25.(появ.ляется низкий потенциал (код О Т, который соответствует сигналу запре- 5р та при анализе остальных разрядов кодов, старшие разряды которых равны

О. Этй сигналы формируются на выходах элементов ИЛИ 28 и поступают на входы элементов И 29. Те коды, старшие раз-55 ряды которых равны 1, проходят через элементы И 29 узла 26 . Если старшие разряды всех чисел равны О, на выходе элемента ИЛИ-НЕ 25 формируется

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

И 29 узла 26 .. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д, в результате чего на выходах ЗО, 30, 65

ЗОщ q, Формируется позиционный код номера максимального кода, а на выходах 31,31,...,31 формируется обратный код максимального из всех анализируемых кодов, .т.е. код минимального из чисел. записанных на регистрах 7. В рассмотренном случае код минимального числа был записан на регистре 7, поэтому после айа- лиза этот.код формируется на выходах

311,31 7 ° -.,31и блока 16, а на выходе ЗО формируется код- 1, сигнализирующий о том, что минимальный код записан на регистре 77 .

Одновременно с появлением высокого потенциала на выходе 47 блока 17 формируется сигнал 1 на выходе 47

27 который поступает на вход вентильной группы 14, в результате чего код минимального числа с выходов 31 блока 16 записывается (парафазным кодом) .на регистр 12 и на вход элемента И 19 матрицы 15. На другие входы элементов И 19 поступает сигнал с выход 30 блока 16, в результате триггер 18А.7 матрицы 15 устанавливается в единичное состояние.

С приходом следующего тактового импульса триггер 32,„+ блока 17 устанавливается в нулевое состояние, а триггер 3". — в единичное, сигнал с выхода которого устанавливает в единичное состояние триггеры регистров

7 и поступает на вход счетчика 39, содержимое которого увеличивается на единицу. В результате на второй . выходной шине дешифратора 40 появляется высокий потенциал. С приходом очередного импульса триггер 32 бло1 ка 17 устанавливается в единичное состояние, поэтому на выходах 46( и 46„5 высокие потенциалы, результат суммирования кода, записанного на регистре 2,(матрицы 1 (если этот код . не нулевой), .с кодом, образуемым на выходе группы элементов 11, записывается на регистр 7 . С приходом следующего импульса триггер 32 блока

17 устанавливается в единичное состояние, и высокие потенциалы на выходах 46 и 46 . Результат суммирования кода с выхода регистра 2 матрицы 1 с кодом регистра 12, (no сигналу

46 открывается вентильная группа

13 1записывается на регистр 77 .

С приходом следующего тактового импульса триггер 327, блока 17 устанавливается в нулевое состояние, а триггер 32 + - в единичное. В результате высокие потенциалы появляются на выходах 47, и 47 . Эти потен циалы обеспечивают выдачу обратных кодов с регистров 7 в блок 16, запись кода минимального из этих кодов на регистр 13 и установку в единич-.

Ъ ное состояние одного из триггеров 183 или 18щ, в зависимости от того, на

1013965

5 4 О О 0 О

О 3 -3 О О

2 О 6 О

4 3 7

О 5 каком из регистров 7 или 7 записы2 вается меньший код.

С приходом очередного тактового импульса триггер 32 устанавливается в нулевое состояйие, а триггер

32m+ в единичное, в результате триг5 геры регистров 7 устанавливаются в единичное состояние и добавляется единица в младший разряд счетчика 39 и на третьем выходе дешифратора 40 формируется сигнал 1. 10

Далее работа устройства происходит аналогично рассмотренному. Например, в i-ом цикле работы устройства производят суммирование содержимого регистров 2 (i+1 }-го столбца 15 матрицы 1 с содержимым регистров

122,12 12,; (содержимое регистра 2<(>суммируется с кодом нуля), .определяют минимальную из сумм и код ее записывают на регистр 12(„ «), а один из триггеров 181(„«),18yi«....18„ („ „ ) блока 15 (или несколько триггеров в случае, если на некоторых из регистров 7,7,...,7„ записаны одинаковые коды,.что означает — через данные вершины исследуемого графа проходят одинаковые по величине минимальные пути) устанавливается в единичное состояние.

Работа устройства продолжается аналогичным образом до тех пор, пока содержимое счетчика 39 не становится равным коду, записанному на регистре 41. В этом случае на выходе схемы 42 появляется высокий потенциал, а на выходе элемента 43 низкий, поэтому импульсы с генератора 45 не поступают на входы триггеров 32. Сигнал с выхода схемы 42 является также сигналом опроса блока 15 для определения кратчайше- 40 го пуФи. Этот сигнал с выхода 49 поступает на выходы вентилей 20 „, и 21,„ блока 15.

Единичные выходы триггеров 18 соединены с первыми входами элемента 20, а нулевые выходы — с первыми входами элементов 21. Таким образом,, если триггер 18 установлен в единичное состояние, то соответствующие ему элемент 20 открыт, а элемент 21 закрыт, и наоборот. Сигнал опроса с выхода 49 проходит через открытые вентили 21,,2Q 21„„„, т.е. сначала опрашиваются триггеры m-ro столбца блока 15, пока не.находится первый триггер 18 щ, установленный в единичное состояние, у которого закрыт элемент 21„„„ и открыт элемент

20 . Высоким потенциалом с выхода элемента 20„ через элемент 23д, устанавливается в единичное состояние

m-й триггер регистра 24.. Это означает, что m-я вершина исследуемого графа, входит в кратчайший путь, и через элемент 22j g сигнал опроса проходит на опрос (1-1 )-го столбца блока 15, т.е. поступает на вторые входы элементов 20(„„>и 21 (,„). Если же в m-oM столбце матрицы 15 ни один из триггеров 18 не находится в единичном состоянии, высокий потенциал с выхода элемента 21(щ„ „через элемент

22 поступает на опрос (m-1 )-го столбца, т.е. поступает на вторые входы элементов 20 и 21„< ).

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

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

В этом случае устанавливаются в единичное состояние j-ый и 1-ый триггеры регистра 24, что сигнализирует об окончании моделирования.

Пример. Пусть задан однонаправленный граф с нагруженными дугами, описываемый матрицей где элементы а„ = О, если нет дуги из i-ой в j-ую вершину.

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

2„" матрицы 1 заносятся коды "весов" дуг графа,,соответствуницие значениям а . Bce триггеры регистров 7 устанавливаются в единичное состояние ° В блоке 17 управления на регистр 41 заносится код числа 7, триггер 32>+ устанавливается в единичное состояние, на счетчик 39 заносится код единицы. Все .остальные триггеры блока 17 установлены в .нулевое состояние..

В блоке 15 все триггеры 18 и триггеры регистра 24 установлены в нулевое состояние. Все триггеры всех остальных регистров устройства установлены в нулевое состояние.

Работа устройства начинается с подачей управляющего сигнала на вход

50 блока 17.

На первом шаге (после поступления первых трех тактовых импульсов) происходит суммирование содержимого регистра 2„ (кода числа 5) с кодом нуля и занесение результата на регистр 7, далее через блок 16 — на регистр 12 . Триггер.18, блока 15 устанавливается в единичное состояние.

На втором шаге (после поступления очередных четырех тактовых импульсов) происходит суммирование содержимого регистра 2 (кода числа 4) с кодом нуля и занесение результата на

1013965

12 регистр 7, затем суммирование содержимого регистра 2 „(кода числа О) с содержимым регистра 12 (кодом числа 3), но так как на регистре 2> код нуля, результат суммирования не заносится на регистр 7>. Далее проис5 ходит занесение результата суммирования с регистра 7„через блок 16 на регистр 12 и установка в единичное состояние триггера 18 блока 15.

На третьем шаге, после поступления очередных пяти импульсов, происходит суммирование содержимого реги-. стра 2 4(код 0 ) с кодом нуля — результат никуда не заносится- содержимого

7 регистра 224(код числа 3) с содержи- 15 мым регистра 1241(код числа 5) и занесение.результата (код числа 8) на регистр 7, содержимого регистра 234 (код числа 2) с содержимым регистра

12 (код числа 4) и занесение результата (код числа 6) на регистр 7 .

Далее происходит выбор минимального из кодов, занесенных на регистры 7 (код числа 6 на регистре 7 ) с помощью блока 16, занесение его на регистр 124.и установка в единичное состояние триггера 18 4.

С приходом очередного импульса с выхода генератора 45 работа устройства происходит аналогично.

После выполнения четвертого шага на регистр 12 заносится код числа 8 и триггер 18, блока 15 устанавливается в единичное состояние..

После выполнения пятого шага на регистр 12 заносится код числа 9 и триггер 184,6блока 15 устанавливается в единичное состояние.

После выполнения шестого шага на регистр 127 заносится код числа 12 и триггер 1867блока 15 устанавливается в единичное состояние; на выходе схемы 42 сравнения формируется высокий потенциал, запрещающий дальнейшее поступленйе импульсов с выхода 45 генератора. 45 на входы .триггеров 32 блока 17 и служащий сигналом опроса триггеров блока 15. сигнал опроса проходит через открытые элементы И 21 блока 15 на входы элементов И 20 7 и 2167, к первым входам которых подключены соответственно прямой и инверсный выходы триггера 18 7. Высокий потенциал с выхода элемента 20 7 поступает на один из входов элемента 237, с выхода которого устанавливается в единичное состоя-.. ние триггер седьмого разряда регистра 24. Далее происходит опрос триггеров шестого столбца, в котором установлен в единичное состояние триггер 1846. Сигнал опроса проходит через открытые элементы 21 шестого столбца и через открытый элемент 20 поступает на один из входов элемента 23, сигналом с выхода которого устанавливается в единичное состояние триггер шестого разряда регистра 24, и д -атее на опрос четвертого столбца, в котором установлен в единичное состояние триггер 18 4. Сигналом с выхода элемента 204 устанавливается через элемент 234 триггер четвертого разряда регистра 24, и продолжается опрос. В третьем столбце установлен в единичное состояние триггер 18, поэтому сигналом с выхода элемента 204 через .элемент 233 устанавливается в единичное состояние триггер третьего разряда регистра 24, а через элемент 22 — триг-. гер первого разряда регистра 24.

Процесс поиска минимального пути на этом заканчивается.

Таким образом, на регистр 127 заносится код длины минимального пути в седьмую вершину графа (на остальные регистры 12, °,12д заносятся коды длины минимального пути в соответствующие вершины). В регистре 24 устанавливаются в единичное состояние триггеры, номера которых соответствуют номерам вершин графа, образующих кратчайший пусть, т.е. триггеры 1,3,4,6,7.

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

10 13965

Фиг 1

1013965

1013965

ФигЗ

Составитель A. Яицков

Редактор А.Иишкина Техред.К.Мыцьо Корректор И. Шулла

Заказ 3006/58 Тираж 704 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4