Устройство для моделирования сетевых графов
УСТРОЙСТВО ДЛЯ МОДЕЛИРОВА- . НИЯ СЕТЕВЫХ ГРАФОВ, содержащее треугольную матричную модель графа, ij-fi Узел которой включает регистр, выходы которого соединены с первым входом блока элементов И (где 4 1, m - 1, ) у + 1,т , m максимальное количество вершин в графе) , первую группу элементов ИЛИ, блок управления, первую группу регистров, блок формирователей пути , блок выбора максимального кода, вторую группу элементов ИЛИ, первую, вторую, третью, четвертую, пятую группы элементов И и .элемент ИЛИ, выход J-го peг ;cтpa первой, группы подключен к первому входу j-го элемента И первой группы, второй вход которого соединен с соответствующим разрядом первой выходной ыины блока управления, j -и разряд второй выходной шины которого подключен к первому входу j -го элемента И второй группы, выход которого соединен с входом J-го регистра первой группы , выход элемента ИЛИ подключен к первым входам элементов И пятой группы, вторые входы элементов И пятой группы соединены с соответствующими разрядами первой выходной шины блока управления, выход -4 -го элемента И пятой группы подключен к первому входу ( -го элемента И третьей группы, выход которого соединен с входом i-го регистра второй группы, выход которого подключен к первому входу i -го элемента И четвертой -группы, выход которого соединен с i -м входом группы блока выбора максимального кода, первая группа выходов которого подключена к вторым входам соответствующих элементов И второй группы, вторая группа выходов блока выбора максимального кода соединена с первой группой входов блока формирователей пути, вторая группа входов которого подключена к соответствуьацим разря-. дам второй выходной шины блока управления , первый Быход которого соеi динен с входом блока формирователей пути, .установочные входы регист ров второй группы подключены к втоpojvty выходу блока управления, третий выход которого соединен с вторыми входаил элементов И четвертой группы, выход ij -го блока элементов И треугольной катричной модели графа соединен с ni -м входом соответствуицего элемента ИЛИ первой группы, выходы элементов ИЛИ первой группы х :л эо :л эо подключены к входам элемента ИЛИ, j-ft разряд третьей выходной шины блока управления подключен к второму входу ij -го блока элементов И треугольной матричной модели графа, выход j-го элемента И первой группы i соединен с j -м входом соответствующего элемента ИЛИ второй группы, отличающееся тем, что, с целью повышения быстродействия, в него введен блок умножения, первый выход которого подключен к вторым входам элементов И третьей группы, второй выход блока умножения соединен с первым входом блока управления , j -и разряд первой выходной шины которого подключен к первому входу блока умножения, выход элемента ИЛИ соединен с вторым входом
СОЮЗ СОВЕТСКИХ
И
РЕСПУБЛИК (?% (И) 3+@ G 06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н ABTOPCHCNVIV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ ИОТНРЫТМЙ
21 ) 3411698/18-24
° °
22) 24.03.82 (46) 07.01.84. Бюл, Р 1 (72 ) В.A. Òèòoâ, С.t?. Áàæåíîâ и В.К.Левашов (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР
Р 842842, кл. G 06 G 7/122, 1981.
2. Авторское свидетельство СССР по заявке Р 3341571/24, кл. G 06 ? 15/20, 1981 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВА-:
НИЯ СЕТЕВЫХ ГРАФОВ, содержащее треугольную матричную модель графа, «« -и узел которой включает регистр, выходы которого соединены с первым входом блока элементов И (где
m 1, 1=;+ m, mмаксимальное количество вершин в графе), первую группу элементов
ИЛИ, блок управления, первую группу регистров, блок формирователей пути, блок выбора максимального кода, вторую группу элементов HJIH, первую, вторую, третью, четвертую, пятую группы элементов И и .элемент ИЛИ, выход « -го регистра первой группы подключен к первому входу « -го элемента И первой группы, второй вход которого соединен с соответствующим разрядом перной выходной шины блока управления, ? -й разряд второй выходной шины которого подключен к первому входу -го элемента И второй группы, выход которого соединен с входом «- го регистра первой группы, выход элемента ИЛИ подключен к первым входам элементов И пятой группы, вторые входы элементов И пятой группы соединены с соответствукщими разрядами первой выходной шины блока управления, выход .« -го элемента И пятой группы подключен к первому входу < -го элемента И третьей группы, выход которого соединен с входом j -го регистра второй группы, выход которого подключен к первому входу i --го элемента И четвертой .группы, выход которого соединен с « -м входом группы блока выбора максимального кода, первая группа выходов которого подключена к нторым входам соотнетстнующих элементов И второй группы, вторая группа выходов блока выбора максимального кода соединена с первой группой входон блока Формирователей пути, вторая группа входоь которого подключена к соответствующим разря. — .: дам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, .устаноночные входы регист ров второй группы подключены к второму выходу блока управления, третий выход которого соединен с вторы° А ми входами элементов И четвертой группы, выход «) -ro блока элементов
И треугольной матричной модели графа соединен с «« -и входом соответствующего элемента ??Л?? первой группы, выходы элементов ??ЛИ первой группы подключены к входам элемента ИЛИ, ! °
«1-й разряд третьей выходной шины блока управления подключен к второму входу «« -ro блока элементов И треугольной матричной модели графа, выход g -го элемента И первой группы
;соединен с ? -м входом соответствующего элемента ИЛИ второй группы, отличающееся тем,что, с целью повышения быстродействия, в него введен блок умножения, первый выход которого подключен к вторым входам элементов И третьей группы, второй выход блока умножения соединен с первым входом блока управления, « -й разряд первой выходной шины которого подключен к первому входу блока умножения, выход элемента ИЛИ соединен с вторым входом
1065858
55 блока умножения, третий и четвертый входы которого подключены соответИзобретение относится к вычисли-/ тельной технике и может быть использовано при исследовании парамет ров сетевых графов, а также при моделировании надежности сложных систем.
Задача определения вершин, обра-. зующих путь максимального произведения длин соответствукщих дуг, возникает при определении вероятности безотказной работы сложных систем, надежность которых зависит от топологии соединения комплектующих модулей.
Известно устройство для моделиро вания сетевых графов, содержащее блок управления, матричную модель графа, генератор тактовых импульсов по числу строк и столбцов матрицы формирователи дуг в составе счетчика и триггера, дифференцирующие цепочки, по числу столбцов матрицы фор>иронатели дуг в составе счетчика и триггера, дифференцирующие цепочки, по числу столбцов матрицы элементы ИЛИ, первую группу тригге рон, группу элементов hE, первую и вторую группы элементов И, третью и четвертую группы элементов И, группу схем сравнения, первую и вторую группы счетчиков и вторую группу триггеров )1) .
Наиболее близким к предлагаемому является устройство для моделирования сетевых графов, содержащее первую группу из ij регисТров, образуюанх треугольнго натьтнагональнуе натрааг (= 1 m— - 1; j =+ ò), первую группу элементов ИЛИ, блок управления и втору(б группу регистров, выходы g -го регистра второй группы подключены к первым входам $ -x элементов И первой группы, вторые входы которых подключены к соотьетстнукщим разрядам первой выходной шины блока управления, -й разряд второй выходной шины которого подключен к первым входам -х элементов И второй группы, выходы которых соединены с входами -ro регистра второй группы, сумматор, блок формирователей пути, блок выбора максимальногс кода, вторая группа элементон ИЛИ, третья группа регистров, третья, четвертая и пятая группы .элементов И, элементы И
50 ственно к выходам элементов ИЛИ первой и второй групп. и элемент ИЛИ, выход которого подключен к первым входам элементов И, вторые входы которых соединены с соответствующими разрядами первой выходной шины блока управления, выход i -го элемента И подключен к первым входам i -х элементов И треть ° ей групйы, выходы которых соединены с входами -го регистра третьей группы, выходы которых подключены к первым входам < -х элементов И, четвертой группы, выходы которых соединены с входами i -й группы блока выбора максимального кода, выходы парной группы которого подключены к вторым входам соответствуюцих элементов И второй группы, выходы второй группы блока выбора максимального кода соединены с :âõoäàèè первой группы блока формирователей пути, входы второй группы которого подключены к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров третьей группы подключены к второму выходу блока управления, третий выход которого соединен с вторыми входами элементов И четвертой группы, выходы « -ro регистра первой группы подключены к первым входам j -х элементов И пятой группы, выходы которых соединены с -ми входами соответствующих элементов
ИЛИ первой группы, выходы ксторых подключены к нходам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторыми входами соответствующих элементон
И третьей группы, -й разряд третьей выходной шины, блока управления подключен к вторым входам i -х элементов И пятой грыппы, выходы -х элементов И первой группы соединены с -ми входами соответствуицих элемен-. тов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, первый вход блока управления является управляющим вхо- дом устройства.
Блок формирователей пути. содержит регистр, перную и вторую группу элементов ИЛИ и треугольную наддиагональную матрицу фо ми ователей пути, каждый ) -й (1 =, Nl - 1
1065856
1,п1) формирователь пути содержит три элемента И и триггер, вход которого соединен.с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего
5 элементов И соответственно, выход третьего элемента И (, + 1) -го формирователя пути соедине. с вторыми входами второго и третьего элементов И (i + 1, ) + 1) -го формирователя пути, вход третьего элемента H (I, j + 1) -го формирователя пути подключен к входу g -ro элемента ИЛИ первой группы, выход которого соединен с вторыми входами второ- 15
ro и третьего элементов И формирователя пути, выход второго элемента
И j,I -го формирователя пути подключей к входу i -ro элемента ИЛИ первой группы и к входу j -го элемента
ИЛИ второй группы, выход которого соединен с входом одноименного разряда регистра, выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вто- 25 рые входы второго и третьего элементов И (1,ln)-ro формирователя пути соединены с входом блока, -й вход первой группы входов которого подключен к первым входам первых элементов И форьжрователей пути 1 -й строки, I -й вход второй группы входов блока подключен к вторым входам первых элементов И формирователей
I пути ) -го столбца.
Блок управления содержит N + 2 триггера, элемент ИЛИ, элемент И, инвертор, регистр, четыре группы элементов И, группу инверторов, счетчик, схему сравнения, дешифратор 4р и генератор, выход которого подклю- . чен к первому входу элемента И, второй вход которого соединен с первым входом блока, выход элемента И подключен к синхронизируюцим входам триггеров, выход (m+ 2)-ro триггера соединен с вторым входом блока, с информационным входом первого триггера и с счетным входом счетчнка, выходы которого подключены к входам первой группы схемы сравнения 5О и к входам дешифратора, (< -й (i
1, Ф вЂ” 1) выход дешифратора соединен с первым входом 1 -го (1 = 1 +
+ 1, ъ) элемента И первой группы, с первыми входами i,1 -х элементов И 55 второй группы, с первым входом i -го элемента И третьей группы и через -й инвертор группы — с первым входом
6-го элемента И четвертой группы, выход которого подключен к информа- Я) ционному входу (+ 1)-гo триггера, выхо -, < -го триггера соединен. с вторыми входами -х элеиентов И третьей и четвертой группы, с вторыми
BxolLIt&f <,) --:х элементов И второй группы и с 1 -м разрядом первой вы- ходной шины блока, выход (, -го элемента И второй группы подключен к i, j -му разряду третьей выходной шины блока, выхоцы элементов И третьей группы и выход nl -го триггера соединены с соответствующими входами элемента ИЛИ, выход которого подключен к информационному входу lnl+
+ 1) -го триггера, выход KOToporo соединен с информационным входом (Ф+ 2)-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствущцим раврядам второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сравнения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И (2) .
Недостатками известного устройства являются невозможность определения в моделируемом графе вершин, образующих путь максимального произведения длин соответствующих дуг, необходимость в этом возникает при определении вероятности безотказной работы сложных систем, и недостаточное быстродействие.
Цель изобретения — повышение быстродействия устройства.
Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее треугольную матричную модель графа, j1 -й узел которого включает регистр, выходы которого соединены с первым входом блока элементов И (где i
1, Yn — 1; y = i+ 1,In; rh — максимальное количество вершин в графе), первую группу элементов ИЛИ, блок управления, первую группу регистров, блок формирователей пути, блок выбора максимального кода, вторую группу элементов ИЛИ, первую, вторую, третью, четвертую, пятую группы элементов И н элемент ИЛИ, выход -ro регистра первой группы подключен к первому входу 1 -го элемента И первой группы, второй вход которого соединен с соответствующим разрядом первой выходной шины блока управления, 1 -й разряд второй выходной шины которого подключен к первому входу 1 -го элемента И второй группы, вы::од которого соединен с входом -го регистра первой группы, выход элемента ИЛИ подключен к первым входам элементов И пятой группы, вторые входы элементов И пятой группы соединены с соответствукицими разрядами первой выходной шины блока управления, выход j -го элемента И пятой группы подключен к первому входу q -ro элемента И третьей группы, вы::од которого соединен с вхо1065858 дом j -го регистра второй группы, выход которого подключен к первому входу < -го элемента И четвертой группы, выход которого соединен с -м входом группы блока выбора максимального кода, первая группа выходов которого подключена к вторым входам соответствующих элементов И второй груцпы, вторая группа выходов блока выбора максимального кода соединена с первой группой входоц блока формирователей пути, вторая группа.входов которого подключена к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров второй группы, подключены к второму выходу блока управления, третий выход которого соединен с вторыми входами злемен- 20 тов И четвертой группы, выход <,-го блока элементов И треугольной матричной модели графа соединен с )-м входом соответствующего элемента
HJIH первой группы, выходы эдементов 25
ИЛИ первой группы подключены к входам элемента ИЛИ, И первой группы соединен с j -и входом соответствующего элемента ИЛИ второй группы, введен блок умножения, первый выход которого подключен 35 к вторым входам элементов И третьей группы, второй выход блока умноже-ния соединен с первым входом блока управления, ) -й разряд первой выходной шины которого подключен к 4О первому входу блока умножения, выход элемента ИЛИ соединен с вторым входом блока умножения, третий и четвертый входы которого подключены соответственно к выходам элементов ИЛИ первой и второй групп. На фиг. 1 представлена структурная схема устройства для моделирования сетевых графов; на фиг. 2 — то же, блока управления; на фиг. 3 то же, блока формирователей пути; иа фиг. 4 — то же, блока умножения; на фиг. 5 - то же, шифратора. Устройство для моделирования сетевых графов содержит (фиг. Ц треугольную матричную модель 1 графа, состоящую из регистров 2 2, 2,. 2(, „,@ и блоков элементов И 3)7 ..., 3(Q g), где (и максимальное количество вершин в графе, первую группу элементов ИЛИ 4,60 блок 5 умножения, элемент ИЛИ б, вторую группу регистров.74, 72, 7щ,(, третью группу элементов И 8q, 82, ..., 8, пятую группу элементов И 91, 92, ..., 9щ 1 чет 65 вертую группу элементов И 103 10 10 „.< вторую группу элементов ИЛИ 11, первую группу регистров 122, 123, ..., 12,„ первую и вторую группы элементов И 132, 13, ..., 13щ и 14 2, 14>, ...,, 14(1,, блок 15 формирователей пути, шифратор 16, блок 17 управления. Блок 17 управления (фиг. 2) включает счетчик 18, регистр 19, генератор 20 тактовых импульсов, дешифратор 21 схему 22 сравнения, элемент HE 23, элементы И 24 и 25, триггеры 26(, 262, ..., 26щqg, элементы И 27, 272, ..., 27рр <, элементы HE 281, ° ° ° ц 28 1, элементы И 29, 292, ..., 29 щ-q, элемент ИЛИ 30, элементы И 31 <2, 31, ..., 31(„,,) „„. и 322,, 323, ..., 32» выходы 331, 33„,, ..., Зз(„,,1,„, 34, 34-,, 34„„, 35, Зб и 37, входы 38 и 39. Блок 15 формирователей пути (фиг. 3) включает элементы И 40 2, 40,3, ..., 40(.4), 417, 413 41 л ).. л, триггеры 42 (2, 42 (, ..., 42() ... элементы H 43(3 4314 43(1) Al элементы ИЛИ 441, 442, ..., 44 п q 45ц,..., 45, регистр 46, входы 47, 48(48г I ° ° ° 48 rn. и 492 493 ° ° ° у 49щ. Блок 5 умножения (фиг. 4) в ключает элементы И 50 - 5 3, группы элементов И 54 — 56, триггеры 57 - 59, сдвигающие регистры 60 и 61, счетчик 62, сумматор 63 накапливающего типа, входы 64 — 68, выходы 69 и 70. шифратор (фиг. 5) включает элементы ИЛИ-НЕ 711, 712, ..., 71п, где П - число разрядов в кодах, узлы 721, 722 ..., 72 . анализа разрядов, состоящие из схем поразрядного переноса 73(3 73, ..., 73(„„ 1, в состав которых входят элементы ИЛИ 74 и элементы И 75, выходы 76, 767, ..., 76п и 77, 77у, ..., 77,„, входы 78ц, 7812, ..., 70 . Устройство для моделирования сетевых графов работает следующим об.разом.. is исходном состоянии триггер 26 блока 17 установлен в единичное состояние, остальные триггеры 26„ (= 1, ..., (л + 1) - в нулевое состояние. Сигналом с выхода триггера 26р +2 в младший разряд счетчика 18 записывается единица, в результате только на первой выходной шине дешифратора 21 устанавливается высокий потенциал, который поступает на первые входы элементов И 274, 31 2 и 322 и на вход элемента HE 28 (. Одновременно сигналом с выхода триггера 26,:п 2 по выходу 35 устанавливаются в нулевое состояние триггеры регистров 71, 7q, 7 1065858 хода триггера 57 высокий потенциал по выходу 70 подается на вход 38 45 блока 17 (фиг. 2) и на вход триггера 58, который находится в единичном состоянии. С выхода триггера 58 высокий потенциал подается на тре-, тий вход элемента 53 и на группы 59 .элементов И 54 и 56. Высокий потенциал с выхода 33 блока 17 поступает по входу 68, в результате чего записывается единица в старший разряд регистра 61 и высокий потенциал поступает также на второй вход элемента И 53. По .сигналу с выхода 33,ц код, записанный на регистре 242 (если он нулевой}, поступает по входу 64 и через откры« 60 тый элемент И 56 записывается на регистр 60. С выхода элемента 6 вы" сокий потенциал поступает на вход 67 и через элемент И 53 устанааливается в единичное состояние триггер 7» » . На регистр 19 блока 17 записывается код числа вершин в моделируемом графе, на регистры 242, 2, ..., 2(л,. »1 < матрицы 1 з аписываются коды "весов" соответствующих дуг графа. Если дуги между какими-либо вершинам» графа отсутствуют, то на соответствующих регистрах записаны коды нуля. Триггеры регистра 46 блока 15 установлены в нулевое состояние. Устройство начинает работу после подачи входного сигнала по шине 39 блока 17. Этот сигнал через элемент И 25 поступает на второй вход элемента И 24, и тактовые импульсы с выхода генератора 20 поступают на входы триггеров 26. С приходом первого импульса триггер 26-» устанавливается в единичное состояние, при этом на выходе 33 4» появляется высокий потенциал, который поступает на вход элемента И 9», а с выхода 33»2 высокий потенциал поступает на входы группы 3»д . В результате код с регистра 2» через открытую группу 3», группу элементов ИЛИ 4 пос-. тупает на вход блока 5 и подается также на вход элемента 6. В зависимости от содержимого регистра 2 у на на выходе элемента 6 формируется высокий или низкий потенциал, запрещаккций или разрешающий работу блока умножения н запись на регистры 7 результатов умножения. Если код на регистре 2»д ненулевой, то на выходе элемента б формируется высокий потенциал, и наоборот. Блок 5 умножения функционирует следуюцим образом. В исходном состоянии триггер 57 находится в нулевом состоянии. С прямого выхода этого триггера низкий потенциал подается на второй вход элемента И 52. С инверсного вы10 57. С инверсного выхода этого триггера низкий потенциал подается на вход триггера 58 и по выходу 70 поступает на вход 38 блока 17, а с прямого выхода высокий потенциал подается на первый вход элемента И 52. Следующий тактовый импульс с генератора 20 по выходу 37 блока 17 поступает на вход 66 и через открытый элемент- И 52 записывает единицу в счетчик 62, устанавливает триггер со счетным входом 59 в единичное состояние, а триггер 58 — a нулевое состояwe, с выхода которого нулевой потенциал подается на третий вход элемента И 53. С прямого выхода триггера 59 высокий потенциал подается на вход элементов И 50 н 51, На второй вход элемента И 50 пода ется высокий потенциал с триггера старшего разряда регистра множителя 61. На выходе элемента И 50 появляется высокий потенциал, поступакщий на элемент И 55. Иножнмое, находящееся на регистре 60, через открытый элемент И 55 поступает на вход сумматора 63, где происходит сложение кодов. fia первый и второй входы элемента И 51 поступают сигналы с второго по старшинству триггера регистра 61 и нулевого триггера регистра 60. Если эти триггеры будут находиться в единичном состоянии, то с выхода элемента И 51 в дополнительный разряд сумматора записывается единица. С приходом следующего тактового импульса к со.держимому счетчика 62 приставляется единица и триггер 59 устанавливается в нулевое состояние. С инверсного выхода этого триггера высокий потенциал поступает в цепи сдвига геристров 60 и 61, причем содержимое регистра 60 сдвигается на один разряд в сторону младших разрядов, а содержимое регистра 61 — в сторону старших разрядов. Умножение продолжается до прихода (n + 1) -ro тактового импульса, при этом на выходе счетчика 62 появляется едини- ца переполнения. Данный сигнал устанавливается в нулевое состояние триггер 57 и подается в дополнительный разряд сумматора 63 для округления результата умножения. С прямого выхода триггера 57 низкий потенциал подается на второй вход элемента И 52, а с инверсного выхода этого элемента высокий потенциал подается на вход триггера 58 и по выходу 70 поступает на вход 38 блока 17, тем саьым разрешая тактовым импульсам через элемент 24 проходить в блок 17 управления. Если код, считываемый с регистра 2»2 нулевой, то на выходе элемента 6 формируется сигнал низкого уровня, 1065858 который по входу 67 поступает на вход элемента И 53, запрещая работу блока умножения. Результат умножения парафазным кодом через открытый элемент 8 записывается на регистр 7 . В блохе 17 сигнал логической едйницы с выхода триггера 264 через элементы 27 и 30 поступает на вход триггера 26<« . С приходом следующего тактового импульса данный триггер устанавливается в единичное состояние, а триггер 26 — в нулевое. При этом на выходе 34 появляется высокий потенциал, который поступает на элемент 10 (фкг, 1). В результате пря- 15 мые коды чисел, записанные на регист рах 6, поступают на входы шифратора 16. шифратор 16 функционирует следуюцим образом. 20 На входные шины 78 поступает(л — 1) чисел с выходов элементов 10. B первый момент анализируются старшие разряды. Если хотя бы один из старших разрядов чисел равен едини- 25 це, то на выходе элемента ИЛИ-НЕ 71у появляется низкий потенциал, который запрещает анализ остальных разрядов тех кодов, старшие разряды которых, равны нулю. Остальные разряды ко- 30 .дов, старшие разряды которых равны едккице, проходят через элементы И 75 узла 72 . Если старшие разряды всех кодов равны нулю, то на выходе. элемента 71 формируется высокий потенциал и все остальные разряды кодов проходят через узел 72 для дальнейшего анализа. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д. В результате на выходах 77, 77> ..., 77 щ „ будет сформирован позиционный код номера максимального числа, а на выходах 764, 76,..., 76 п — обратный код максимального числа из записанных на регист- 45 рах 7. В рассматриваемом случае код максимального числа записан на регистре 7 (триггеры остальных регистров 7„, где a = 2, ..., Yh — 1, находят- 50 ся в нулевом состоянии), поэтому пос ле анализа обратный код этого числа будет сформирован на выходах 76, а на выходе 774 появится сигнал логической единицы, сигнализирующий о 55 том, что максимальный код записан на регистре 7 . Одновременно с появлением сигнала ка выходе 34 блока 17 появится высокий потенциал на выходе 34, бр который поступает на вход элемента 14 (фкг. 1), в результате чего обратный код максималького числа с выхода блока 16 записывается (парафазным кодом) на регистр 122. Сигнал с выхода 34 также поступает по входу 49 на элемент 40, блока 15, на первый вход которого поступает сигнал по входу 48< с шифратора 16. В результате .триггер 42 устанавливается в единичное состояние. С приходом следующего тактового импульса триггер 26 +„ устанавливается в нулевое, а триггер 26yn+g в единичное состояние. Сигналом с выхода элемента 26„1+д устанавливаются в нулевое состояние триггеры регистров 7 и содержимое счетчика 18 увеличивается на единицу, после чего высокий потенциал появляется на втором выходе дешифратора 21. С приходом очередного тактового импульса триггер 26 устанавливается в единичное состояние, поэтому высокие потенциалы появятся на выходах 33 и 33 3 и результат умножения кода, содержащегося на регистре 2 матрицы 1 (если код ненулевой ) в данном случае на единицу, будет записан на регистр 7 . С приходом следующего тактового импульса триггер 26 устанавливается в нулевое, а триггер 26 q — единичное состояние, в результате высокие потенциалы устанавливаются на выходах 33 2 и 33 . РезУльтат умножения кода, находящегося на регистре 2 матрицы 1, с кодом, находяцимся на регистре 12 2 (по сигналу 33 открывается элемент 13>, подключенный к инверсным выходам триггеров регистра 12 ), будет записан н;; регистр 7 . С приходом следующего тактового импульса триггер 26 бдока устанавливается в нулевое, а триггер 26 л+ — в единичное состоячие. B результате высокие потенциалы появятся на выходах 34 к 34, которые обеспечат выдачу кодов с регист ров 7 в блок 16, запись обратного кода максимального из них на регистр 12> и установку в единичное состояние одного из триггеров 42 или 42 блока 15 в зависимости от того, на каком кз регистров 7 или 7 был записан больший код. С приходом очередного тактового импульса триггер 26 л будет уста" новлен в нулевое состояние„ а триггер 26д + — в единичное, в результате триггеры регистров 7 будут установлены в нулевое состояние и будет добавлена единица в младший разряд счетчика 18, а ка третьем выходе дешифратора 21 сформируется сигнал высокого уровня. Далее работа устройства происходит аналогично. Например, в -м цик- ле работы будет произведено перемножение содержимого регистров 2 (+ 1) -го столбца матрицы 1 с со1065858 12 держим м регистров 12, 12,..., 12 (содержимое регистра 2 (j tq) умножается на единицу), далее будет определено максимальное произведение и обратный код его будет записан на регистр 12(4t1)r а один из триггеров 42 (» tg) 422(;t1), ..., 421 (t<1) блока 15 будет установлен в единич-с ное состояние. Работа устройства продолжается аналогичным образом.до тех пор, пока содержимое счетчика 18 не станет равным коду, записанному на регистре 19. В этом случае на выходе схемы 22 появляется высокий потенциал, а на выходе элемента НЕ 23 — низкий, поэтому импульсы с генератора 20 перестанут поступать на входы триггеров 26. Сигнал с выхода схемы 22 является сигналом опроса блока 15 для определения максимального пути. Этот сигнал с выхода 36 поступает по входу 47 блока 15 (фиг. 3) на входы элементов 41 щ н 03q . Единичные выходы триггеров 42 соединены с, первыми входами элементов И 41, а нулевые выходы « с первыми входами элементов И 43. Таким образом, если триггер 42 установлен в единичное состояние, то соответствукщ и ему элемент 41 открыт, а элемент 43 закрыт, и наоборот ° Сигнал опроса с входа 47 проходит через открытые элементы 43 „ 43дщ, ..., 43 „, т.е. сначала опрашиваются триггеры щ-го столбца блока 15, пока не будет найден триггер 4 2„z, установленный s единичное состояние, у котОрого закрыт элемент 43 „, и открыт элемент 41 . Высоким потенциалом с выхода элемента 41, через элемент ИЛИ 45 m будет установлен в единичное состояние tn-й триггер регистра 46. Это означает, что п-я вершина моделируемого графа входит в максимальный путь, и через элемент 44(-1) -й сигнал опроса пройдет на опрос (i— — 1} -ro столбца блока 15, т.е. поступит на вторые входы элементов 41„(» — 1) и 43 (— 1) . Если же в в-м столбце матрицы 15 ни один иэ триггеров 42 не будет находиться в единичном состоянии, то высокий потенциал с выхода элемента 43(, „ через элемент 44 t -i) поступит на опрос (m - 1j -го столбца, т.е. посЩ тупит на вторые входы элементов 41, и 43 I(m-i) . Аналогичным образом опрос будет продолжаться до тех пор, пока не будет найден триггер 42, установленный в единичное 25 состояйие. Это означает, что j -й вершин в первую вершину сформирован максимальный путь. В этом случае будут установлены в единичное состояние -й и первый триггеры регистра 46, что свидетельствует об окончании работы устройства. Предлагаемая совокупность блоков и связей между ними позволила повысить точность моделирования. 1065858 1065858 1065858 1065850 1065858 Составители И. Дубинина Редактор С„Квятковская Техред Т. Маточка Корректор A.Tÿñêî Эакаэ 11047/50 Тираж 70б Подписное ЭНИИПН Государственного комитета СССР по делам изобретений и открытий 113035, 11осква, У:.-35, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4
