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

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

0341

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

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

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

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

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

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

И, третий вход которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, вьЕХод, которого соединен с входом дешифратора, -й ( i 1, 2, ...,п) выход которого подключен через элемент задержки к управляющему входу элемента И первой группы i-го столбца, к управляющему входу элемента И i-ro столбца и к первым входам элементов И дуг строки, выход каждого триггера формирования дуги соединен с вторым ВХОДО1. элемента И дуги, выход каждого из которых подключен к входу элемента ИЛИ одноименного i-ro столбца, выход элемента ИЛИ соединен с управляющим входом элемента И второй группы t-го столбца, выход которого подключен к соответствующему входу узла выбора максимума, выход последнего соединен с пер,вым входом многовходового сумматора, выход которого подключен к информационным входам элементов И первой группы, выход элемента И первой группы i-ro столбца соединен с входом регистра i-ro столбца, выход которого лодключен к информационному входу элемента И второй группы i-ro столбца и к информационному,входу элемента И третьей группы -l-ro столбца, выходы элементов И третьей rpyn-j

jTibi соединены соответственно с входаМИ элементов ИЛИ группы, выходы кото рых подключены к второму входу много входового сумматора 2. Недостатком известных устройств является невозможность вычисления рангов вершин графа. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения вычисления рангов вершин графа. Поставленная цель достигается тем, что в устройство для исследования параметров графа,, содержащее генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом элемента НЕ, вход которого подключен к выходу переполнения реверсивного счетчика, вычитающий вход которого соединен с выходом .первого элемента И, введены второй элемент И, элемент задержки и п вычислительных блоков, каждый из которых состоит из регистра сдвига, блока ключей, первой и второй групп элементов И, первого и второго.элементов ИЛИ, первого, второго и третьего дешифраторов, первого, второго реверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов И, блока информации, причем в каждом вычислительном блоке выходы блока ключей соединены с установочными вхо дами разрядов регистра сдвига, выходы разрядов регистра сдвига подключе ны к первым входам элементов И первой и второй групп, выходы элементов И первой группы соединены с входом первого элемента ИЛИ, выход которого соединен с суммирующим входом первого реверсивного счетчика, выход которого через первый дешифратор сое динен с входом первого элемента НЕ, выход которого подключен к первому входу первого элемента И вычислитель ного блока, выход которого соединен с вычитающим входом первого реверсив ного счетчика и с вторым входом соответствующего элемента И второй группы, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход которого подключен к информационному входу счетчика выход которого через второй дешифратор соединен с входом блока индикации, выход последнего разряда регист ра сдвига соединен с установочным входом его первого разряда и подключен к cyммиpyющe fy входу второго реверсивного счетчика, вычитающий вход которого соединен с выходом второго элемента И вычислительного блока, первый вход которого соединен с выходом второго элемента НЕ, вход которого подключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивного счетчика, входы сдвига регистров сдвига всех вычислительных блоков подключены к выходу первого элемента И, выход третьего дешифратора каждого вычислительного блока соединен с соответствующим входом второго элемента И, выход которого соединен с вторым входом первого элемента И первого вычислительного блока, выход первого дешифратора каждого вычислительного блока, кроме последнего, подключен к второму входу первого элемента И последующего вычислительного блока, третий вход первого элемента И каждого вычислительного блока соединен с выходом генератора тактовых импульсов, выход третьего дешифратора каждого вычислительного блока, кроме последнего, соединен с вторым входом второго элемента И последующего вычислительного блока, второй вход второго элемента И первого вьмислительного блока подключен к выходу реверсивного счетчика, третий вход второго элемента И каждого вычислительного блока соединен с выходом генератора тактовых импульсов, выход второго элемента И i-ro вычислительного бло.ка соединен с вторыми входами i-х элементов И первой группы ц вычислительных блоков, выход первого элемента И i-ro вычислительного блока соединен с вторыми входами -х элементов И второй группы h вычислительных блоков (где 1 1, .. ., h .), установочные входы регистров сдвига, счетчиков, первого и второго реверсивных счетчиков всех вычислительных блоков объединены и соединены с входом блока задержки, выход которого соединен с входами блока ключей вычислительных блоков. Предлагаемое устройство осуществляет вычисление ранга вершин графа в соответствии с функцией (ч1+р;(кк...р (1с), i 1 где P (Ic) - количество путей длины Я 3, идущих от элемен та (вершины) i в п . На чертеже представлено предлагае мое устройство. Устройство для исследования параметров графа содержит регистры 1 1 сдвига, блоки ключей, первая группа элементов И 3 - Зп, вторая группа элементов И 4 - Afj, первые элементы И.ПИ 5 - , вторые элементы ИЛИ 6-j - 6,, второй 7 и первый 8 - 8 реверсивные счетчи ки, счетчики 9 - 9, вторые дешифраторы 10 - Ю, блоки 11 - llj, индикации, первые дешифраторы 12, 12j, третьи дешифраторы 13-, - 13,,, первые элементы НЕ 14 - 14,, первые элементы И 15 - 15, вторые элементы НЕ 16 - 16, вторые элеме ты И 17 - 17 , второй элемент И 18 элемент 19 задержки, входная шина 20 Сброс, шина 21, записи числа п реверсивный счетчик 22, элемент НЕ 23, элемент И 24, генератор 25 тактовых импульсов, входная шина 26 Пуск, вычислительные блоки 27. Устройство работает следуюпщм об разом. Предварительно в реверсивный счетчик 22 по входной шине 21 записывается число, соответствующее количеству разрядов в регистрах Ц -1 сдвига. Количество этих разрядов также соответствует числу регистров т.е. п , где и - максимальная разме ность матрицы смежности. Затем при помощи блока 2 - 2, ключей (например, перемычка, переключатель и т.д.) на вход разрядов регистров коммутируется выход элемента 19 задержки, причем коммутируются лишь те разряды регистров, которые соответствуют единичным элементам матри пы смежности исследуемого графа. Каждый регистр сдвига соответствует одной соответствующей строке матрицы смежности, а i-й разряд всех регистров соответствует -му столбцу этой матрицы. После коммута ции соответствующих разрядов к выхо ду элемента 19 задержки по входной шине 20 подается импульс сброса на еоответствуюпще входы сброса регист ров 1 - 1j сдвига, реверсивных сче чиков 7 - 7, реверсивных счетчико 8 - 8 J счетчиков 9-j - 9 для приве дения их в нулевое состояние. Задержанный элементом 19 задержки импульс сброса записывает через скоммутированные ключи блока 2 - 2 ключей в регистры матрицу смежности исследуемого графа. После окончания этой операции устройство готово к работе. При подаче разрешающего потенциала Пуск по входной шине 26 на первьш вход элемента И 24, на его выходе появляются тактовые импульсы с генератора 25 тактовых импульсов, так как на тратьем входе элемента И 24 находится единичный потени(иал с выхода элемента НЕ 23, который пропадает лишь при нулевом состоянии счетчика 22, т.е. после п -го тактового импульса,. Тактовые импульсы поступают на управляющие входы регистров 11 1 f, сдвига и информация .с выхода каждого регистра подается на его вход, а также на суммирующий вход соответствующего реверсивного счетчика 7-, - 7. После прихода п --го тактового импульса на второй (вычитающий) вход реверсивного счетчика 22 он переходит к нулевое состояние, так как в исходном состоянии в него записано число п , соответствующее максимальной размерности матрицы смежности. На выходе реверсивного счетчика 22 появляется напряжение логической единицы, которое .через элементы НЕ 23 запрещает дальнейшее прохождение тактовых импульсов через элемент И 24. За t тактов информация в регистрах переписывается полностью и соответствует матрице смежности. В соответствующих реверсивных счетчиках з аписывается число единиц, содержащихся в соответствующей строке матрицы смежности. На этом-заканчивается первый щаг итерации. (h+ 1)-й импульс с генератора 25 тактовых импульсов поступает через элемент И вычитающий вход реверсивного счетчика 7, так как элемент И 15 открыт единичным потенциалом с выхода реверсивного счетчика 22 и выхода дешифратора 12 через элемент НЕ 14, а счетчик 7 находится в нулевом состоянии и на его выходе напряжение логического нуля. Дешифраторы и 13 - 13, вьщают на своем выходе напряжение логической единицы лишь в случае нулевого состояния соответствующего реверсивного счетчика. Тактовые импульсы, начиная с (г + 1)-го, через элемент И 15 начинают поступать на вычитающий вход реверсивного счетчи ка 7 , а также на вторые входы элементов И 3 п соответствующих первым разрядам всех регистров Ц - 1 сдвига, на первые входы кот рых подаются сигналы с выходов первых разрядов соответствующих регист ров сдвига. Поэтому если в первом разряде соответствующего регистра сдвига 11 - 1 f, записана единица, соответствующий ему элемент И 3 -З открывается и тактовые импульсы через соответствующий элемент И 3 соответствующий элемент РШИ 5- - 5, поступают на второй суммирующий вход соответствующего реверсивного счетчика 8., - 8. После того, как на вычитающий вход реверсивного сче чика 7 поступает количество тактовых импульсов, соответствующее числу единиц в первой строке матрицы смежности, счетчик переходит в нулевое состояние, на выходе дeIШ фpaтopa . появляется напряжение логической единицы, которое через элемент НЕ 14 запрещает прохождение тактовых импульсов через элемент И 15. Б соответствующих реверсивных счетчиках записывается число, равное количеству единиц в первой строке матрицы смежности анализируемого графа. Напряжение логической единицы с выхода дешифратора 1л первой группы открывает элемент И 15-, так как на первый вход этого элемента подается напряжение логиче кой единицы с элемента НЕ 142. Тактовые импульсы через элемент И 15 с выхода тактового генератора поступают на вычитающий вход реверсивного счетчика 7 , а также на вторые входы всех элементов И 3 - 3, соответствующих вторым разрядам всех регистров сдвига 1 ri если в них записана единица, то тактовые импульсы через соответствующий элемент ИЛИ 5 - 5 поступают на сумми рующий вход соответствующего реверсивного счетчика . , т п После прохождения тактовых импул сов, количество которых соответству ет числу единиц во второй строке ма рицы, смежности, т.е. числу, записан ному в реверсивном счетчике 7. На выходе дешифратора 12, первой групп 18 появляется напряжение логической единицы, которое через элемент НЕ 14„ запрещает прохождение тактовых импульсов через элемент И 5„ и разрешает прохождение тактовых импульсов через следующий элемент И 15,. В дальнейшем работа устройства происходит аналогично до тех пор пока информация из последнего реверсивного счетчика 7„ не переписывается в соответствутощие реверсивные счетчики 8 8р|. На этом заканчивается второй шаг итерации. Единичные сигналы с выходов дешифраторов 12 - 12 поступают на выходы элемента И 18, напряжение с выхода которого открывает элемент И 17 для прохождения тактовых импульсов с выхода генератора 25 тактовых импульсов, так как на второй вход элемента И 17 поступает напряжение логической .единицы с выхода элемента НЕ 16, на вход которого подается напряжение логического нуля с выхода дешифратора 13. Тактовые импульсы с выхода генератора 25 тактовых импульсов поступают через элемент И 17 на вычитающий вход реверсивного счетчика 8, а также на первые входы элементов И 4 - 4, соответствующих первым разрядам регистров 1 - 1 j сдвига, на вторые входы которых подключены выходы первых разрядов регистров 1 - 1 f сдвига. Элементы И 4 - 4р, которым соответствуют первые разряды соответствуюпщх регистров 1 - 1 сдвига, в которых записана единица, открываются и тактовые импульсы через них и соответствующие элементы ИЛИ 6-, - 6, записываются в соответствующие счетчики 9 - 9. При прохождении через элемент И 17 тактовых импульсов, количество которых соответствует чис- лу, записанному в реверсивном счетчике 8, счетчик 8 переходит в нулевое состояние и на выходе дешифратора 13 появляется напряжение логической единицы. Поэтому на выходе элемента НЕ 16 появляется напряжение логического нуля, которое запрещает дальнейшее прохождение тактовых импульсов через элемент И 17,. Одновременно напряжение логической единицы с выхода дешифратора 13 подается на первый вход и открывает элемент И 17, через который тактовые импульсы начинают поступать 9 на вычитаюпщй вход реверсивного сче чика 8„ и первые входы элементов И 4 - 4, соответствующих вторым разрядам регистров 1 - 1 (второму столбцу матрицы смежности), на вторые входы которых подключены выходы соответствующих вторых разрядов регистров 1 - 1j сдвига. Напряжение логической единицы с тех разрядов, в которых записана единица, открьгеа ет соответствующие элементы И 4.,-4 и тактовые импульсы с их выхода через соответствующие элементы ИЛИ поступают на запись в соответствующие счетчики 9 - 9,. Тактовые импульсы через элемент И 172 проходят до тех пор, пока реверсивный счетчик Sg не переходит в нулевое состояние и не закрывает через дешифратор 13, и элемент НЕ 16 элемент И 17 . Напряжение ло гической единицы с выхода дешифрато ра 13j открывает следующий элемент 1 И 17, для прохождения тактовых импульсов и цикл работы протекает аналогично. Устройство функционирует до тех пор, пока информация из последнего реверсивного счетчика 8 не переписывается в соответствующие счетчики 9 - 9 (третий шаг итерации) . После этого прохождение тактовых импульсов на какие-либо элементы устройства запрещается элементами И 15, - 15,, 17 - 17 и 24. Информация, записанная в каждом счетчике 9., - 9,,соответствует рангу соответствующей вершины исследуемого графа. Эта информация дешифрируется соответствующим дешифратором lOj - 1, и отображается на соответствующем блоке ll. - 11|. индикации. Предлагаемое устройство благодаря наличию Новых блоков и связей между ними позволяет осуществлять вычисление ранга вершин графов.