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

 

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА, содержащее генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом элемента НЕ, вход которого подключен к выходу переполнения реверсивного счетчика, вычитающий вход которого соединен с выходом первого элемента И,, о т л ичающееся тем, что, с целью расширения функциональных возможностей устройства за счет, обеспечения возможности вычисления рангов вершин графа, в устройство введены второй элемент И, элемент задержки и п вычислительных блоков, каждый из которых состоит из регистра сдвига, блока ключей, первой и второй групп элементов И, первого и второго элементов ИЛИ, первого, второго и треть-, его дешифраторов, первого, второго реверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов И, блока информации , причем в каждом вычислительном блоке выходы блока ключей соединены с установочными входами разрядов регистра сдвига, выходы разрядов р егистра сдвига подключены к первь1м входам элементов И первой и второй групп, выходы элементов И первой группы соединены с входом первого элемента ИЖ, выход которого соединен с суммирующим входом первого реверсивного счетчика, выход которого через первый дешифратор соединен с входом первого элемента НЕ, выход которого подключен к первому входу первого элемента И вычислительного блока, выход которого соединен с вычитающим -входом первого реверсивного счетчика и с вторым входом соответствующего элемента И второй группы, выходы элементов И второй группы соединены с входами второго (Л элемента ИЛИ, выход которого подклю (Чен к информационному входу счетчика, выход которого.череэ второй дешифратор соединен с входом блока йндика-ции , выход последнего разряда регистра сдвига соединен с установочным входом его первого разряда и подключен к суммирующему входу второго реверсивного счетчика, вьгчитаюпщй вход которого соединен с выходом вто:«э рого элемента И вычислительного блоJi ка, первый вход которого соединен с выходом второго элемента НЕ, вход которого подключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивного счетчика, входы сдвига регистров сдвига всех вычислительных блоков подключены к выходу первого элемента И, выход третьего дешифратора каждого вычислительного элемента блока Соединен с соответствукнцим входом второго элемента И, выход которого соединен с вторым входом первого эле

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

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

РЕСПУБЛИК аа аи Ш G 06 F 15/20

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

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

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3569191/18-24 (22) 29.03.83 (46) 23. 10.84. Бюл. и 39 (72) Е.И.Бороденко, В.Е.Назаренко .и А.И.Семенов (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

Р 896630, кл. G 06 F 15/20, 1980.

2. Авторское свидетельство СССР

9 943738, кл. G 06 F 15/20, 1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ГРАФА, содержащее генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом элемента НЕ, вход которого подключен к выходу переполнения реверсивного счетчика, вычитающий вход которого соединен с выходом первого элемента И, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет. обеспечения воэможности вычисления рангов вершин графа, в устройство введены второй элемент И, элемент задержки и и вычислительных блоков, каждый из которых состоит из регистра сдвига, блока ключей, первой и второй групп элементов И, первого и второго элементов ИЛИ, первого, второго и третьего дешифраторов, первого, второго реверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов И, блока информации, причем в каждом вычислитель. ном блоке выходы блока ключей соединены с установочными входами разрядов регистра сдвига, выходы разрядов регистра сдвига подключены к первым входам элементов И первой и второй групп, выходы элементов И первой группы соединены с входом первого элемента ИЛИ, выход которого соединен с суммирующим входом первого реверсивного счетчика, выход которого через первый дешифратор соединен с входом первого элемента НЕ, выход которого подключен к первому входу первого элемента И вычислительного блока, выход которого соединен с вычитающим -входом первого реверсивного счетчика и с вторым входом соответствующего элемента И второй группы, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход которого подклю;чен к информационному входу счетчика, выход которого через второй дешифратор соединен с входом блока йндика.ции, выход последнего разряда регистра сдвига соединен с установочным входом его первого разряда и под, ключен к суммирующему входу второго реверсивного счетчика, вычитающий вход которого соединен с выходом второго элемента И вычислительного блока, первый вход которого соединен с выходом второго элемента НЕ, вход которого подключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивного счетчика, входы сдвига регистров сдвига всех вычислительных блоков подключены к выходу первого элемента

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

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

? 0341 каждого вычислительного блока соединен с:выходом генератора тактовых импульсов, выход второго элемента

И j-го вычислительного блока соединен с вторыми входами i -х элементов

И первой группы и вычислительных блоков, выход первого элемента И i ãî вычислительного блока соединен с вторыми входами -х элементов И второй группы и вычислительных блоков (где = 1, ..., и ), установочные входы регистров сдвига, счетчиков, первого и второго реверсивных счетчиков всех вычислительных блоков объединены и соединены с входом блока задержки,выход которого соединен с входами ми блока кюпчей вычислительных блоков.

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

:затрат при построении структурносложных систем, оценки значимости элементов при техническом диагностировании и т.д. f0

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

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

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

И, третий вход которого через эле— мент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, у-й (1= 1, 2, ..., и ) выход которого подключен через элемент задержки к управляющему входу элемента И первой группы i-го столбца, к управляющему входу элемента И -ro столбца и к первым входам элементов И дуг q-й строки, выход каждого триггера формирования дуги соединен с вторым входо . элемента И дуги, выход каждого из которых подключен к входу элемента ИЛИ одноименно— го i-го столбца, выход элемента ИЛИ соединен с управляющим входом элемента И второй группы i -r o столбца, выход которого подключен к соответствующему входу узла выбора максиму,ма, выход последнего соединен с пер,вым входом многовходового сумматора, выход которого подключен к информационным входам элементов И первой группы, выход элемента И первой груп. пы i-ro столбца соединен с вх6дом регистра i-го столбца, выход кото— рого подключен к информационному входу элемента И второй группы i-го столбца и к информационному входу элемента И третьей группы 1-го столбца, выходы элементов И третьей груп- пы соединены соответственно с входа341 з 112О ми элементов ИЛИ группы, выходы которых подключены к второму входу многовходового сумматора (? .

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

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

10 рангов вершин графа.

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

15 которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом элемента

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

ro, второго реверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов

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

И первой группы соединены с входом первого элемента ИЛИ, вьмод которо- 40

ro соединен с суммирующим входом первого реверсивного счетчика, выход которого через первый дешифратор соединен с входом первого элемента НЕ, выход которого подключен к первому 45 входу первого элемента И вычислительного блока, выход которого соединен с вычитающим входом первого реверсивного счетчика и с вторым входом соответствующего элемента И второй 50 группы, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход которого подключен к информационному входу счетчика, выход которого через второй дешифра- 55 тор соединен с входом блока индика- ции, выход последнего разряда регистра сдвига соединен с установочным входом его первого разряда и подключен к суммирующему входу второго реверсивного счетчика, вычитающий вход которого соединен с выходом второго элемента И вычислительного блока, первый вход которого соединен с выходом второго элемента НЕ, вход которого подключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивного счетчика, входы сдвига регистров сдвига всех вычислительных блоков подключены к выходу первого элемента И, выход третьего дешифратора каждого вычислительного блока соединен с соответствующим входом второго элемента И, выход которого соединен с вторым входом первого элемента И первого вычислительного блока, выход первого дешифратора каждого вычислительного блока, кроме последнего, подключен к второму входу первого элемента И последующего вычислительного блока, третий вход первого элемента И каждого вычислительного блока соединен с выходом генератора тактовых импульсов, выход третьего дешифратора каждого вычислительного блока, кроме последнего, соединен с вторым входом второго элемента И последующего вычислительного блока, второй вход второго элемента И первого вычислительного блока подключен к выходу реверсивного счетчика, третий вход второго элемента И каждого вычислительного блока соединен с выходом генератора тактовых импульсов, выход второго элемента И -го вычислительного блоI ка соединен с вторыми входами j -х элементов И первой группы П вычислительных блоков, выход первого элемента И i-ro вычислительного блока соединен с вторыми входами -х элементов И второй группы и вычислительных блоков (где = 1, ..., ь.), установочные входы регистров сдвига, счетчиков, первого и второго реверсивных счетчиков всех вычислительных блоков объединены и соединены с входом блока задержки, выход которого соединен с входами блока ключей вычислительных блоков.

Предлагаемое устройство осуществляет вычисление ранга вершин графа в соответствии с функцией

P (И,(1)Р (К)+...iP (ц, 1! 2П341

1 где P „(t) — количество путей длины идущих от элемента (вершины) 1 в fl .

На чертеже представлено предлагаемое устройство. 5

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

1 сдвига, блоки 2 1 — 2 ключей, первая группа элементов И 3 — Зп, вторая группа элементов И 41 — 4л, 10 первые элементы ИЛИ 51 — 5п, вторые элементы ИЛИ 61 — 6„; второй 7 -7, и первый 8„ — 8 ренерсивные счетчи ки, счетчики 9, — 9, вторые дешифраторы 1С„ — 1Г„, блоки 11 — 11, индикации, первые дешифраторы 12„

12» третьи дешифраторы 13 „ — 13» первые элементы НЕ 14„ — 14„, пер— вые элементы И 15 „ — 15„, вторые элементы НЕ 16„ — 16» вторые элемен->О ты И 17„ - 17„, второй элемент И 18, элемент 19 задержки, входная шина

20 "Сброс", шина 21 записи числа реверсивный счетчик 22, элемент

НЕ 23, элемент И 24, генератор 25 тактовых импульсов, входная шина 26

"Пуск", вычислительные блоки ?7.

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

Предварительно в реверсивный 30 счетчик 22 по входной шине 21 записывается число, соответствующее количеству разрядов в регистрах 1„ — 1„ сдвига. Количество этих разрядов также соотнетствует числу регистров т.е. и где и — максимальная размерность матрицы смежности. Затем при помощи блока 2 „ — 2„ ключей (например, перемычка, переключатель и т.д.) на вход разрядов регистров коммутируется выход элемента 19 задержки, причем коммутируются лишь те разряды регистров, которые соответствуют единичным элементам матрицы смежности исследуемого графа.

Каждый регистр сдвига соответствует одной соответствующей строке матрицы смежности, а 1-й разряд всех регистров соответствует 1-му столбцу этой матрицы. После коммутации соответствующих разрядов к выхо" ду элемента 19 задержки по входной шине 20 подается импульс сброса на еоответствующие входы сброса регистров 1 — 1„ сдвига, реверсивных счетчиков 7 „ - 7, ренерсивных счетчиков

8 — 8 счетчиков 9 — 9 для приве1 Ь1 1 дения их в нулевое состояние. Задержанный элементом 19 задержки импульс сброса записывает через скоммутированные ключи блока 2 — 2 ключей и в регистры 1 — 1 матрицу смежности исследуемого графа. После окончания этой операции устройство готово к работе.

При подаче разрешающего потенциала "Пуск" по входной шине ?6 на первый вход элемента И 24, на его выходе появляются тактовые импульсы с генератора 25 тактовых импульсов, так как на тратьем входе элемента

И 24 находится единичный потенциал с выхода элемента НЕ 23, который пропадает лишь при нулевом состоянии счетчика 2?, т.е. после n -ro тактового импульса„ Тактовые импульсы поступают на управляющие входы регистров 1 — 1 „ сдвига и информация с выхода каждого регистра подается на его вход, а также на суммирующий вход соответствующего реверсивного счетчика 7„ 7„. После прихода и -го тактового импульса на второй (нычитающий) вход реверсивного счетчика

22 он переходит к нулевое состояние, так как в исходном состоянии н него записано число ь, соответствующее максимальной размерности матрицы смежности. На выходе реверсивного счетчика 22 появляется напряжение логической единицы, которое, через элементы НЕ 23 запрещает дальнейшее прохождение тактовых импульсов через элемент И 24. За и тактов информация в регистрах переписывается полностью и соответствует исходной матрице смежности. И соответствующих ренерсивных счетчиках 71 — 7„ записывается число единиц, содержащихся н соответствующей строке матрицы смежности.

На этом заканчивается перный шаг итер ации. (h + 1) -й импульс с генератора 25 тактовых импульсов поступает через элемент И 15> на вычитающий вход реверсивного счетчика 7,, так как элемент И 15„ открыт единичным потенциалом с выхода реверсивного счетчика

22 и выхода дешифратора 12z через элемент НЕ 14 а счетчик 7„ находится в нулевом состоянии и на его выходе напряжение логического нуля.

Дешифраторы 1?„ - 12> и 13 „ - 13„ выдают на своем выходе напряжение ло" гической единицы, лишь в случае нулевого состояния соответствующего

11203 реверсивного счетчика. Тактовые импульсы, на:иная с (n + 1)-го, через элемент И 15„начинают поступать на вычитающий вход реверсивного счетчика 7„, а также на вторые входы эле— ментов И 3„ — 3„, соответствующих первым разрядам всех регистров

11 — 1 сдвига, на первые входы которых подаются сигналы с выходов пер— вых разрядов соответствующих регист" 10 ров сдвига. Поэтому если в первом разряде соответствующего регистра сдвига 11 — 1„ записана единица, соответствующий ему элемент И 31 -3„ открывается и тактовые импульсы че- 15 рез соответствующий элемент И 3, -3„, соответствующий элемент ИЛИ 51 — 5„, поступают на второй суммирующий вход соответствующего реверсивного счетчика 8> — 8„. После того, как, 20 на вычитающий вход реверсивного счетчика 7 поступает количество такто1 вых импульсов, соответствующее числу единиц в первой строке матрицы смежности, счетчик переходит в нулевое 25 состояние, на выходе дешифратора 1.", появляется напряжение логической единицы, которое через элемент

НЕ 14 запрещает прохождение такто1 вых импульсов через элемент И 5„.

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

И 15>, так как на первый вход этого элемента подается напряжение логической единицы с элемента НЕ 14>. Так в 40 товые импульсы через элемент И 15 с выхода тактового генератора поступают на вычитающий вход реверсивного счетчика ., а также на вторые входы всех элементов И 31 Зл, со 45 ответствующих вторым разрядам всех регистров сдвига 1„ — 1„, и если в них записана единица, то тактовые импульсы через соответствующий элемент ИЛИ 5„ — 5„ поступают на суммирующий вход соответствующего реверсивного счетчика 8- — 8

После прохождения тактовых импульсов, количество которых соответствует числу единиц во второй строке мат-55 рицы смежности, т.е. числу, записанному в реверсивном счетчике 7 . На выходе дешифратора 122 первой группы

41 8 появляется напряжение логической единицы, которое через элемент HF. 14 запрещает прохождение тактовых импульсов через элемент И 15 и разре-2 шает прохождение тактовых импульсов через следующий элемент И 15 . В даль3 нейшем работа устройства происходит аналогично до тех пор пока информация из последнего реверсивного счетчика 7„ не переписывается в соответствующие реверсивные счетчики 8„

8„. На этом заканчивается второй шаг итерации.

Единичные сигналы с выходов дешифраторов 12 — 12 поступают на вы-1 н ходы элемента И 18, напряжение с выхода которого открывает элемент И 17, для прохождения тактовых импульсов с выхода генератора 25 тактовых импульсов, так как на второй вход элемента И 17 поступает напряжение логической единицы с выхода элемента

НЕ 16, на вход которого подается напряжение логического нуля с выхода дешифратора 13„ . Тактовые импульсы с выхода генератора 25 тактовых импульсов поступают через элемент

И 17 на вычитающий вход реверсивно1

ro счетчика 81, а также на первые входы элементов И 4 „ — 4„, соответствующих первым разрядам регистров

1„ — 1„ сдвига, на вторые входы которых подключены выходы первых разрядов регистров 1 — 1 „ сдвига. Элементы И 4„ — 4„, которым соответствуют первые разряды соответствующих регистров 1 1 — 1 сдвига, в которых записана единица, открываются и тактовые импульсы через них и соответствующие элементы ИЛИ 6„ — 6 „ записываются в соответствующие счетчики

9 — 9 . При прохождении через эле1 n мент И 17„тактовых импульсов, количество которых соответствует числу, записанному в реверсивном счетчике 8„, счетчик 8 переходит в

1 нулевое состояние и на выходе дешифратора 13 появляется напряжение

1 логической единицы. Поэтому на выходе элемента НЕ 16„появляется напряжение логического нуля, которое запрещает дальнейшее прохождение тактовых импульсов через элемент И 17„ .

Одновременно напряжение логической единицы с выхода дешифратора

13, подается на первый вход и открывает элемент И 17, через который тактовые импульсы начинают поступать

9 11203 на вычитающий вход реверсивного счетчика 8 и первые входы элементов

И 4 - 4, соответствующих вторым разрядам регистров 1< — 1„ (второму столбцу матрицы смежйости), на вторые входы которых подключены выходы соответствующих вторых разрядов регистров 11 — 1„ сдвига. Напряжение логической единицы с тех разрядов, в которых записана единица, открыва" 10 ет соответствующие элементы И 4 -4. ъ и тактовые импульсы с их выхода через соответствующие элементы

ИПИ 6 — 6„ поступают на запись в соответствующие счетчики 9 — 9„.

Тактовые импульсы через элемент

И 17 проходят до тех пор, пока реверсивный счетчик 8 не переходит в нулевое состояние и не закрывает через дешифратор 13> и элемент 2О

НЕ 16 элемент И -17 . Напряжение ло2 гической единицы с выхода дешифратора 13 открывает следующий элемент

41 10

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

Устройство функционирует до тех пор, пока информация из последнего реверсивного счетчика 8 не nepenuF1 сывается в соответствующие счетчики

9> — 9„ (третий шаг итерации) . После этого прохождение тактовых импульсов на какие-либо элементы устройства запрещается элементами И 15> — 15»

17„- 17„и 24. Информация, записанная в каждом счетчике 9> - 9„,соответствует рангу соответствующей вершины исследуемого графа. Эта информация дешифрируется соответствующим дешифратором 10 — 10> и отображается на соответствующем блоке 11„ — 11,,„ индикации.

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

11? 0341

ВБИщщ Заказ 7744/37 тираж 698 Подписное

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