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

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

3. Устройство поп.1 отличающееся тем, что блок управления содержит irt+Z триггера; четыре группы элементов И, группу инверторо элемент ИЛИ, элемент И, инвертор, регистор, счетчик, схему управления, дешифратор и генератор, выход которого подключен к первому входу элемента И, второй вход которого соединен с четвертым входом блока, выход элемента И подключен к синхронизирующим входам триггеров, выход {т+2 )-го триггера соединен с вторым входом блока,- с информационным входом первого триггера и со счетным входом счетчика, выходы которого подключены к входам первой группы схемы сравнени и к входам деишфратора, - ifi ( ) выход дешифратора соединен с первым входом j-ro fj i--1,m) элемента И первой группы, с первыми входа (i,j )-х элементов И второй группы, с первым входом i-ro элемента И третье группы и череэ i-й инвертор группы с первым входом i-ro элемента И четвертой группы, выход которого подключен к информационному входу (1 + 1 )-го триггера, выход i-ro триггера соединен с вторыми входами i-x элементов И третьей и четвертой группы, с вторыми входами (i,j }-х элементов И второй и с i-M разрядом первой выходной шины блока, выход Ci,j )-го элемента И второй груйпы подключен к (i,j)-му разряду третьей выходной шины блока,выходы элементов И третьей группы и выход т-го триггера соединены.с соответствующими входами элемента ИЛИ, выход которого подключен к информационному входу (т+1 )-го триггера, выход которого соединен с информационным входом (т + 2 )-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сравнения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И;

, 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 ,т) Формирова

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

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

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

,2

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

Наиболее близким техническим решением к изобретению является устройство, содержащее первую группу из ij регистров, образующих Треугольную н адди а го н аль ную матрицу (,т-1 ; j iti ,m ),. первую группу элементов ИЛИ блок управления и вторую группу регистров , выходы j-oro регистра второй .группы подключены к первым входам i-ых элементов И первой группы, вторые входы которых соединены с соответ ствующим разрядом первой выходной шины блока управления, j-й разряд второй выходной шины которого подключен к первым входам j-x элементов И второй группы, выходы которых соедииены с входами j-ro регистра второй группы 2J. Недостатком известного устройства является низкое быстродействие из-за необходимости двоекратного заполнения счётчиков весов дуг матричной модели тактовыми импульсами и последукщего сравнения результатов двух просчетов. Целью изобретения является повышение быстродействия устройства. Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее первую группу из ij регистров, образующих треугольную надциагональную матрицу. (,m-1; + T,m), первую группу элементов ИЛИ, блок уп равления и вто рую группу регистров,выходы i-ro регистра второй группы подключены к первым входам j-x элементов И первой группы, вторые входы которых соедине ны с соответствующим разрядом первой выходной шины блока управления, з-й разряд второй выходной шины которого подключен к первым входам элементов И второй группы, выходы которых соединены с входами j-ro регистра второй группы, введены сумматор, блок формирователей пути, блок выбор максимального кода, вторая группа эл ментов ИЛИ,.третья группа регистров, третья, четвертая и пятая группы эле ментов И, элементы И .и элемент ИЛИ, выход которого.подключен к первым входам элементов И, вторые входы которых соединены с соответствукмдими разрядами первой выходной шины блока управления, выход i-ro элемента И по ключей к первым входам i-x элементов И третьей группы, выходы которых .соединены с входами i-ro регистра третьей группы, выходы которого подключены к первым входам i-x элементов И червертой группы, выходы котог соединены с входами i-и группы блока выбора максимального кода, выходы первой группы которого подключены к вторым входам соответствующих элементов И второй группы, выходы второй группы бло ка выбора максимал.ьного кода соединены с входами .первой группы блока формирователей пути, входы второй группы которого подключены к соответ ствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока фор мирователей пути, установочные входы регистров третьей группы подключены к второму выходу блока управления, . третий выход которого соединен с вторыми входами элементов И четвертой группы, выходы ij-ro регистра первой группы подключены к первым входам ij-x элементов И пятой группы, выходы которых соединены с ij-ми входами соответствующих элементов ИЛИ первой группы, выходы 1 оторых подключены к входам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторыми sxoiciaMK соответствующих элементов И третьей группы, ij-й разряд третьей выходной шины блока управления подключен к вторым входам ij-x элементов И пятой группы, выходы j-x элементов .И первой группы соединены с j-ми входамисоответствующих элементов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, четвертый вход блока управления является управляющим входом устройства. Кроме того, блок формирователей пути содержит регистр, первую и вторую группу элементов .ИЛИ и треугольную наддиагональную матрицу формирователей пути, каждый ij-й (, m 1 ; + 1,m) форидарователь пути содержит три элемента И и триггер, вход которого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента И (i,j+1-)-ro формирователя пути соединен с вторыми входами второго и третьего элементов и (i+l),j+l)-го формирователя пути, выход третьего элемента И (j,i-«-1 )-ого формирователя . пути подключен к входу j-ro элемента ИЛИ первой группы, выход которого соединен с вторыми входами второго и третьего элементов И (i,j )-го формирователя пути, выход второго элемента И (i,j)-го формирователя пути подключен к входу i-ro элемента ИЛИ первой группы и к входу i-ro элемента ИЛИ второй группы, выход которого соединенс входом одноименного разряда регистра выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вторые входы второго и третьего элементов И (1,т)-го формирователя соединены с входом блока, i-и вход первой группы входов которого подключен к первым входам первых элементов И формирователей, пути i-й-строки, j-й вход второй группы входов блока подключен к вторым входил первых элементов И формирователей пути , j-ro столбца. , Причем блок управления содержи.т m-t-2 триггера, четыре группы элементов И, группу инверторов, элемент ИЛИ, элемент И, инвертор, регистор, счетчик, схему управления, дешифратор, и генератор, выход которого подключен к первому входу элемента И, второй вход которого соединен с четвертым . входом блока, выход элемента И подключен к синхронизирующим входам триггеров, выход (m+2 го триггера соединен с вторым входом блока, с информационным входом первого триггера и со счетным входом счетчика, выходы которогоподключены к входам первой группы схемы сравнения и к входам дешифратора, i-й. (,т-1) выход дешифратора соединен с первым входом j-ro (j i-«-1,m) элемента И первой группы, с первыми входами (i,j х элементов И второй группы, с первым входом i-ro элемента И третьей группы и через i-ый инвертор группы с первым входом i-ro эле мента И четвертой группы, выход кот рого подключен к информационному вх ду (i+1 -го триггера, выход i-ro триггера соединен с вторыми входами i-x элементов И третьей и четвертой группы, с вторыми входами ( )-х элементов И второй группы и с i-м разрядом первой выходной шины блока выход (i,j )-го элемента И второй группы подключен к (i,j му разряду третьей выходной шины блока, выходы элементов И третьей группы и выход т-го триггера соединены с соответст вующими входами элемента ИЛИ,выход которого подключен к информационному входу (т+1)-го триггера, выход которого соединен с информационным входом (т+2 )-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока выходы регистра соединены с второй группы схемы сравнения,, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И. На фиг. 1 показана структурная схема«Устройства для моделирования сетевых графов; на фиг. 2 - структур ная схема блока формирователей пути на фиг. 3 - структурная схема блока выбора максимального кода; на фиг.4 структурная схема блока управления. Устройство для моделирования сетевых графов (фиг. 1 ) содержит треугольную наддиагональную матрицу 1, состоящую из первой группы регистров 2 ,2 ,...,2)у 1и пятой группы элементов И 3,, 3,,,.. ., 3()-,где m - максимальное количество вершин в графе, первую группу элементов ИЛИ 4, сумматор 5, элемент ИЛИ б, третью группу регистров 7) . 7 , . .. 7 кч- i третью группу элементов И 8,,8, ,... 8 , элементы И 9 ,9, .., 9 четвертую группу элементов И 10,, Юг, ..., 10 wi- f вторую группу элемен тов ИЛИ 11, вторую группу регистров 122.,12з,... f 12г„, первую и вторую группы элементов И 132, ХЗд , ... ,13 и 142.,145,. . . ,14у„ , блок 15 формирователей Пути, блок 16 выбора максимального йода, блок 17 управления. Блок 15 формирователей пути (фиг. 2 ) имеет ту же форму и размерность, что матрица 1 и включает триггеры 18,18, ...,18(„.;, первые, вторые и третьи элементы И 191гД -/э / 19(m-«w 2Qfi 20i3,..., 20(,„,)„и 21,,21, .. .,21(.),„, первую и вторую группу элементов ИЛИ 22 ,22,.. .22 и 23,234.../ 23(т-), регистр 24. Блок выхода максимального кода (фиг. 3 ) включает элементы ИЛИ-НЕ 25 ,252., .. . 25и г где п - число разрядов в кодах, узлы 26 ,2б2,.../26ц анализа разрядов, состоящие из схем 27, 27, .. ., 2(,„,)и поразрядного переноса,, в состав которых входят элементы ИЛИ 28 и элементы И 29, выходы 30, , 30 , ..., 31 , 31, .. ., 31 .. Блок 17 управления (фиг. 4 ) включает триггеры 32 ,32,.. ., третью и четвертую группу элементов И 33 ,332,...,33у„ и 34, 34,..., 34 группу инверторов (элементов НЕ) 35 , 35, ,..., а5. , элемент ИЛИ 36, вторую и первую группы элементов И 37у2, ... , и 38, 38-,,.,, 38у„ , счетчик 39, дешифратор 40, регистр 41, схему 42 сравнения, инвертор 43, элемент И 44, генератор 45 тактовых импульсов, выходы , ., . . . , 46()fn; 47 , . .. , 47w, 48 и 49, вход 50. В исходном состоянии триггер 32 блока 17 установлен в единичное состояние, остальные триггеры 32 - в нулевое. Сигналом с выхода триггера . 32, младший разряд счетчика 39 записывается единица. В результате только на первой выходной шине дешифратора 40 устанавливается сигнал логической единицы, поступающий на первые входы элементов 33, 37 и 38, 35.. Одновременно сигналом с выхода триггера выходу 49 Устанавливаются в единичное состояние триггеры регистров 7 на регистре 41 блока 17 записываетсА код количества вершин в моделируемом графе, на регис-ррах , 2,,...,2(.i матрицы 1 записываются коды весов соответствующих дуг графа. Если дуги между какими-либо вершинами графа отсутствуют, на соответствующих регистрах записываются коды нуля. Триггеры регистров 12,12,...12м., а также регистра 24 матрицы 15 устанавливаются в нулевое состояние. С подачей входного сигнала по шине 50 на второй вход элемента 44, с выхода генератора 45 на триггеры 32 начинает поступать последовательность, импульсов.. С приходом первого импульса триггер 32-/I устанавливается н единичное состояние, при этом на выходе 46,, блока 17 формируется сигнал логической единицы, поступаюсвсий на вход вентиля 9 , а на выходе 46, появляется высокий потенциал, поступающий на входы вентильной группы . В результате код, записанный на регистре 2 , через открытую вентильную группу 2.ji поступает через Группу элементов -ИЛИ 4 на первый вход сумматора 5 и элемент ИЛИ б. В зависимости от содержимого регистра . на выходе элемента ИЛИ б формируется высокий или низкий потенциал,-разрешающий или запрещающий запись, результата суммирования в регистры 7. Если код ненулевой навыходе элемента ИЛИ б формируется сигнал логической единицы, разрешающий запись результата, если.кЬд нулевой - формируется сигнал логичес кого нуля, запрещающий запись результата. На второй вход сумматора 5 с выхода элемента 11 поступает в данном случае код числа нуль.. Результат суммирования (если на регистре 2 ненулевой код), парафазным кодом через открытую вентильную группу 8 записывается на регистр . В блоке 17 сигнал логической единицы с выхода триггера 32 через элемент 33 и элемент 36 поступает на вход триггера .. С приходом второго тактового импульса триггер 32 устанавливается в единичное со тояние, а триггер 32 - в нулевое. На выходе 4 блока появляется выс кий потенциал, поступающий на входы вентильньох групп 10, в результате обратные коды чисел, записанных на регистрах 7 г поступают на входы узл 26 блока 16. Блок 16 работает следукяцим образ На-входы элементов .ИЛИ 28 и, И 29 схем ,21,... ,21(.}у( поступает (т-1 ) кодов, каждый из которых пред ставлен п разрядами, с обратных выходов триггеров регистров 7 черей вентильные группы 10.- В первый момент анализируются старшие разряды всех кодов. Если хотя бы один из старших разрядов кодов равен 1, на выходе элемента ИЛИ-НЕ 25 появ.ляется низкий потенциал (код О Т, который соответствует сигналу запре та при анализе остальных разрядов кодов, старшие разряды которых равн 0.Эти сигналы формируютс,я на выход элементов ИЛИ 28 и поступают на вхо элементов И 29. Те коды, старшие ра ряды которых равны 1, проходят чере .элементы И 29 узла 26 . Если старши разряды всех чисел равны О, на выхо де элемента ИЛИ-НЕ 25 формируется 1,благодаря чему обеспечивается Ра решение на прохождение остальных разрядов всех кодов через элементы И 29 узла 26 .. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах 30-( , ЗОз., ..., 30 „,4 формируется позиционный код номера максимального кода, а на выходах 31,31,...,31 и формируется обратный код максимального из всех анализируемых кодов, .т.е. код минимального из чисел,записанных на регистрах 7.. В рассмотренном случае код минимального числа был записан на регистре 7, поэтому после анаЛИЗа этот.код формируется на выходах 31 ,З.,...,31f, блока 16, а на выходе 30 формируется код 1, сигнализирующий о том, что минимальный код записан на регистре 7.. Одновременно с появлением высокого потенциала на выходе блока 17 формируется сигнал 1 на выходе 472 который поступает на вход вентильной группы 142, результате чего код минимального числа с выходов 31 блока 16 записывается (парафазным кодом) на регистр 12. и на вход элемента И матрицы 15. На другие входы элементов И 19 поступает сигнал с выход 30 блока 16, в результате триггер 18 матрицы 15 устанавливается в единичное состояние. С приходом следующего тактового импульса триггер блока 17 устанавливается в нулевое состояние., а триггер 3.- в единичное, сигнал с выхода которого устанавливает в единичное состояние триггеры регистров 7 и поступает на вход счетчика 39, содержимое которого увеличивается на единицу. В результате на второй . выходной шине дешифратора 40 появляется высокий потенциал.- С приходом очередного, импульса триггер 32 блока 17 устанавливается в единичное состояние, ПОЭТОМУ на выходах 46 и 46 высокие потенциалы, результат суммирования кода, записанного на регистре 2,матрицы 1 (если этот код не нулевой), ,с кодом, образуемым на выходе группы элементов 11,- записывается на регистр 7 . С приходом следующего импульса триггер 32 блока 17 устанавливается в единичное состояние, и высокие потенциалы на выходах 462. Результат суммирования кода с выхода регистра 2 матрицы 1 с кодом регистра сигналу вентильная группа . ) записывается на регистр . С приходом следующего тактового импульса триггер 322v блока 17 устанавливается в нулевое .состояние, а триггер 32yin - в единичное. В результате высокие потенциалы появляются на выходах 47 и 47-. Эти потен- циалы обеспечивают выдачу обратных кодов с регистров 7 в блок 16, запись кода минимального из этих кодов на регистр 13 и установку в единичт ное состояние одного из триггеров 18э или 18ii3f в зависимости от того, на каком из регистров 7, или 7 записы вается меньший код. С приходом очередного тактового импульса триггер 32 устанавливае ся в нулевое состояние, а триггер 32 В единичное, в результате три геры регистров 7 устанавливаются в единичное состояние и добавляется единица в младший разряд счетчика 3 и на третьем выходе дешифратора 40 формируется сигнал 1. Далее работа устройства происходит аналогично рассмотренному. Например, в i-oM цикле работы устройства производят суммирование содержимого регистров 2 (i+1 )-го столбца матрицы 1 с содержимым регистров 12,2, 12-J, ... ,12 (содержимое регистра 2 (+) суммируется с кодом нуля) , определяют минимальную из сумм и ко ее записывают на регистр 12(, а один из триггеров 18(.18u(4-i. блока 15 (или несколько триггеров 3 случае, если на некоторых из регистров 7 , 7 , ..., записаны одинаковые коды,.что означает - через данные вершины исследуемого графа проходят одинаковые по величине минимальные пути) устанавливается в единичное состояние. Работа устройства продолжается аналогичным образом до тех пор, пока содержимое счетчика 39 не становится равным коду, записанному на регистре 41. В этом случае на выходе схемы 42 появляется высокий потенциал, а на выходе элемента 43 низкий, поэтому импульсы с генератора 45 не поступают на входы триггеров 32. Сигнал с выхода схемы 42 является также сигналом опроса блока 15 для определения кратчайшего nyfи. Этот сигнал с выхода 49 поступает на выходы вентилей 20 и 21;,у„ блока 15. Единичные выходы триггеров 18 соединены с первыми входами элемента 20, а нулевые выходы - с первыми входами элементов 21. Таким образом если триггер 18 установлен в единич ное состояние, то соответствующие ему элемент 20 открыт, а элемент 21 закрыт, и наоборот. Сигнал опроса с выхода 49 проходит через открытые вентили 21 ,, . .. , , т.е. сначала опрашиваются триггеры т-го столбца блока 15, пока не-находится первый триггер 18.)м, установленный в единичное состояние, у которого закрыт элемент и открыт элемен 20 уп- Высоким потенциалом с выхода элемента ,через элемент 23 у, уст навливается в единичное состояние т-й триггер регистра 24. Это означает, что т-я вершина исследуемого графа.входит в кратчайший путь, и через элемент сигнал опроса пр ходит на опрос (i-1 )-го столбца бло ка 15, т.е. поступает на вторые входы элементов 21(-. Если же в т-ом столбце матрицы 15 ни один из триггеров 18 не находится в единичном состоянии, высокий потенциал с вьохода элемента 21/ур.)через элемент 22 поступает на опрос (т-1 )-го столбца, т.е. поступает на вторые входы элементов 20., и 21.„ .ч..- ((И1Иу /Ц/л-1/ Аналогичным образом опрос продолжается до тех пор, пока не найдется триггер 18.( , установленный в единичное состояние. Это означает, что из j-и вершины в первую вершину исследуемого графа имеется кратчайший путь, В этом случае устанавливаются в единичное состояние j-ый и 1-ый триггеры регистра 24, что сигнализирует об окончании моделирования; Пример. Пусть задан однонаправленный граф с нагруженными дугами, описываемый матрицей 540000 03-300 где элементы О, если нет дуги из i-ой в j-ую вершину. В исходном состоянии на регистры матрицы 1 заносятся коды весов дуг графа,, соответствующие значениям а . Все триггеры регистров 7 устанавливаются в единичное состояние. В блоке 17 управления на регистр 41 заносится код числа 7, триггер 32(2 устанавливается в единичное состояние, на счетчик 39 заносится код единицы. Все-остальные триггеры блока 17 установлены в «нулевое состояние. В блоке 15 все триггеры 18 и триггеры регистра 24 установлены в нулевое состояние. Все триггеры всех остальных регистров устройства установлены в нулевое состояние. Работа устройства начинается с подачей управлякяцего сигнала на вход 50 блока 17. На первом шаге (после поступления первых трех импульсов) происходит суммирование содержимого регистра 2(кода числа 5 с кодом нуля и занесение результата н регистр 7- , далее через блок 16 - на регистр 12. Триггер. 18, блока 15 устанавливается в единичное состояние. На втором шаге (после поступления очередных четырех тактовых импульсов) происходит суммирование содеримого регистра (кода числа 4) с кодом нуля и занесение результата на

регистр 7 , затем с члмирование содержимого регистра 22(кода числа 0) с Содержимым регистра 12-2.(кодом числа 3), но так как на регистре 2,код нуля, результат суммирования не заносится на регистр 1. Далее происходит занесение результата суммирования с регистра 7 через блок 16 на регистр 123 и установка в единичное состояние триггера 18 блока 15.

На третьем шаге, после поступления очередных пяти импульсов, происходит cyм Iиpoвaниe содержимого реги-. стра (код О ) с кодом нуля - результат никуда не звноситсяj содержимого регистра 2(кор, числа З; с содержимым регистра 12,(v.oR числа Ь) и занесение-результата (код числа 8 на регистр 1 ; содержимого регистра 2 (.код числа 2У с содержимым регистра 12(код числа 4) и занесение результата ( код числа 6) на регистр 7 .

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

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

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

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

После выполнения шестого шага на регистр 12 заносится код числа 12 и триггер 18(, 15 устанавливается в единичное состояние; на выходе схемы 42 сравнения формируется вйсокий потенциал, запрещагадий дальнейшее поступление импульсов с выхода генератора 45 на йходы триггеров 32 блока 17 и служащий сигналом опроса триггеров блока 15.

сигнал опроса проходит через открытые элементы И 21 блока 15 на входы элементов И 21, к первым входам которых подключены сортветственно прямой и инверсный выходы триггера . Высокий потенциал с выхода элемента поступает на один из входов элемента 23т, с выхода которого устанавливается в единичное состоя-. . ние триггер седьмого разряда регистра 24. Далее происходит опрос триггеров шестого столбца, в котором установлен в единичное состояние триггер , Сигнал опроса проходит через открытые элементы 21 шестого 5 столбца и через открытый элемент 20 поступает на один из входов элемента 23 , сигналом с выхода которого устанавливается в единичное состояние триггер шестого разряда регистра 24, и дпее на опрос четвертого столбца, в котором установлен в еди. нйчное состояние триггер 1834. Сигналом с выхода элемента 20 устанавливается через элемент 23 триггер 5 четвертого разряда регистра 24, и продолжается опрос В третьем столбце установлен в единичное состояние триггер , поэтому сигналом с выхода элемента через .элемент 23 0 устанавливается в единичное состояние триггер третьего разряда регистра 24, а через элемент.22 - триггер первого разряда регистра 24.

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

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

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

si,

kj/

k5//i

J //r-/)

Ш

-3

SQt

27ii

llu,

27in

27ifn-f)

У)1

2S

272(П1)

21n

ФигЛ