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

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

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

На фиг, 1 представлена функцио 3,- ,

выходы

нальная схема устройства для исследо- tS pa 16 соединен с первыми входами вания параметров ориентированных гра- элем ентов И J-ro столбца матрицы фов; на фиго 2 - пример графа G(X,A); .n«n элементов И 9.-9, 10 на фиг, 3 - матрица расстояний графа на фиг, 4 - времемные-диаграммы поясняющие принцип работы устройства, 20

Устройство содержит группу элемен- , тов задержки,группу из п элементов И 2 (п -максимально возможное коли - н. ,

элементов 1 -1 задержки соединен с горизонтальными шинами 25 набор

. ного ПОЛЯ 23, а входы соединены выходами соответствующих элементов И, группы 7.-1, вход запуск генератора ; 17 пакетов импульсов 25 динен с выходом второго элемента 19, а выход соединен с информаци ными входами соответствующих инд каторных счетчиков , .,

. чество вершин графа) , п групп по п индикаторных счетчиков 3, 3, -4, 1 h 6 -6h J « 7 -7j, , группу из п

Ц -Юн, , 13,-13,, вход Начальная

регистров 8,-8j,, матрицу из п х п элементов И , 12,-12,,

установка 14, элемент ИЛИ-НЕ 15, дешифратор 16,, генератор 1 пакетов импульсов, счетчик 18, элемент И 19, элемент Е 20, генератор 21 тактовых импульсов, вход Запуск 22, наборное полу 23 и коммутирующие элементы 24.

Наборное -поле содержит п вертикальных 25 и п горизонтальшзгх 26 шин, которые через коммутирующие элементы 24 соединены между собой в соответствии с топологией исследуемого графа, один вывод вертикальных шин. наборного поля 23 подключены к первым входам группы элементов И , выходы i-го элемента И группы 2 -2. соединены с первыми входами элемента И а-й строки .матрицы пяп элементов И , , , 12,-12, 13,-13, выходы элементов И j-ro столбца соединены с одноименными информационными входами J-ro регистра 8, вход начальной установки счетчика 18 соединен с входами начальной установки регистров 8 и является входом Начальная установка 14 устройства, счетный вход счетчика 18 подключен к. выходу первого элемента И 19, первый и

второй входы которого соединены соответственно с выходом второго элемента и 20 и выходом элемента ИЛИ-НЕ 15, который подключен также к вторым

входам элементов И 7.-2. , а вход элемента Р1ЛИ-НЕ 15 соединен с Сп+1)-м- выходом дешифратора 16, выход счетчика 18 подключен к входу дешифратора 16, первый вход первого элемента И 20 является входом Запуск 22 устройства, второй вход второго эле- мента И 20 подключен к выходу генератора 21 тактовых импульсов, а j-й (,2,.оо,п) выход дешифрато 3,- ,

выходы

pa 16 соединен с первыми входами элем ентов И J-ro столбца матрицы n«n элементов И 9.-9, 10

. ,

элементов 1 -1 задержки соединены с горизонтальными шинами 25 наборного ПОЛЯ 23, а входы соединены с выходами соответствующих элементов И, группы 7.-1, вход запуска генератора ; 17 пакетов импульсов сое- динен с выходом второго элемента И 19, а выход соединен с информационными входами соответствующих индикаторных счетчиков , .,

, п входы сброса которьгх соединены с соответствующими выходами регистров .

Генератор 17 пакетов импульсов вырабатывает пакеты из п импульсов и запускается задним фронтом такто- вого импульса с генератора 21 Период следования импульсов в пакете равен

-h .1 СЛ..2 п

где. - период следования тактовых импульсов генератора 21,

Элементы 1 -1 задержки обеспечивают время, задержки, равное t.

Устройство для определения парам метров ориентированных графов рабо- тает следующим образом.

Предварительно на наборном поле 23.набирается структура исследуемого графа при помощи коммутируклцих элементов 24 Если между вершинами .X ,: и Xj есть ребро, то между i-й горизонтальной и j-й вертикальной шинами устанавливается элемент 24 в проводящем направлении. По входу 14 подается импульс, который устанавливает в нулевое состояние счетчик 18, регистры 8, -8,, Индикаторные счетчики 3,-3.

5,-5н,

6, -6 , 7, -7 , ко3

торые находятся не в нулевом состоянии, сбрасываются в нулевое состоя- ние при переходе соответствующего разряда регистров 8 , из 1 в O На вход элемента ИПИ-НЕ 15 коммутируется (К+1)-и.выход дешифратора, где К - количество вершин в исследуемом графе. Максимальное количество вершин равно числу п. После этог устройство готово к работе.

При.подаче на вход 22 единичного потенциала через второй элемент И 2 начинают проходить тактовые импульс с-генератора 21, Тактовые импульсы с выхода элемента И 20 поступают на один вход элемента И 19, на другой вход которого подается единичный потенциал с выхода элемента ИЛИ-НЕ Тактовые импульсы с выхода элемента И 19 поступан)Т на счетный вход счетчика 18о В зависимости от состояния счетчика 18 на соответствующем выходе дешифратора появляется единичный потенциал, который открывает элементы И соответствующего столбца матрицы nVn элементов И

9,.-9м . 2.- 2,. соответствующего регистра

, а также подается на вход соответствующей вертикальной шины наборного поля 23, Выходы вертикальных шин наборного поля 23 подключены к первым входам элементов И 2-2 на вторые входы которых подаётся единичный потенциал с выхода инвертора 15. Тактовые импульсы с выхода элемента И 19 поступают на управля- ющий вход генератора I7 пакетов импульсов и задним входом запускают генератор, после чего тот выдает пакет из п импульсов, задержанных относительно начала тактового импуль- ; величину Yjpa.i (фиг. 4 г и д). Счетчики 3,-3, 4,-4 , 5,-5,, рассчитаны на подсчет

6|-6h.

,, ,- -7и.

(n-l)-ro импульса, так как максимальный путь в графе между двумя вершинами равен п-1, где п - количество вершин в графе, С приходом п-го импульса, счетчики сбрасываются в нулевое состояние,

Пример работы устройства, Иссле-. дуеь|ый граф изображен на фиг, 2, временные диаграммы работы устройства - на фиг, 4,

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

25928 4

единицы {т})иг, 46), Генератор пакетов импульсов запускаетск и выдает,пакет из п импульсов (фиг, 4r)t Напряжение логической 1 с первого выхода де- 5 шифратора 16 поступает на первые входы элементов И 9, -9ц и открывает их. Кроме того5;это же напряжение поступает на один вьгеод первой вертикальной шины наборного поля 23, 10 на котором набрана топология исследуемого графа (фиг, 1), С другого вывода шины 25 это напряжение пос15

20

тупает на элемент И 2,, который открыт напряжением логической 1 с выхода элемента ИЛИ-НЕ 15, С выхода элемента И 2| (фиг, 4д) напряжение логической 1 поступает на схему И 9, и записывает в первый ;- разряд регистра 8 1, Кроме того, это напряжение поступает на линию 1./ задержки и через нее задержанное

25

0

5

0

5

5

время bcA. z горизонтальную шину Наборного поля 23, Напряжение логической 1 с инверсного выхода первого разряда регистра 8., при его переходе в; единичное состояние пропадает (фиг, 4е), запрещая тем самым запись в индикаторный счетчик 3., импульсов с генератора 17, так как первый импуш с пакета задержки на величину Т цз. 1 (фиг, 4д и а). Первый импульс пакета записывается во все счетчики , , 1-5,, 6,-6, 7, -7 , кроме счетчи- .ка 3i ,

Напряжение логической 1 с горизонтальной шины наборного поля 23 через элемент 24, попадает-на вертикальную шину 25, через элементы И 2 и 9j записывает 1 в третий разряд регистра 8. и запрещает дальнейшую запись импульсов в счетчик 3j (4иг, 4з ) о Поэтому второй импульс запишется только в счетчике

Зи.-,.,

1 6, -6,

1

л

7г-7ь. с выхода

Напряжение логической элемента И 2. поступает на вход линии Ц задержки и через нее - на горизонтальную шину 263 наборного поля 23, а затем через коммутирующий элемент 24, элемент И 2,. запи- сыв1ает в четвертый разряд регистра 8., 1, запрещая тем самым дальнейшую запись импульсов в счетчик 3 (фиг. 4к), После этого во все счет- Ч1ЖИ, кроме счетчиков 3, Зз и ,, запишутся п-1 импульсов, а затем п-й импульс,сбросив их содержимое

Таким образом, в первой строке матрицы расстояний после первого такта, работы {счетчики , ) будет записано 0012 (фиг. З), а во всех остальных счетчиках будут записаны нули. Аналогично будет работать устройство и во втором, третьем и четвертом тактах, С приходом пятого тактового импульса на пятом выходе дешифратора 16, который скоммутиро- ван на вход элемента ИЛИ-НЕ 15, по- ,является напряжение логической 1, которое через элемент ИЛИ-НЕ 15 запрещает дальнейшую работу устройства В первых четырех разрядов регистров 8,, 8,j, 8,,и 8 записывается матрица достижимостей графа (фиг, 2), а в индикаторных счетчиках З.-З, , , 6j-6 .записывается матрица расстояний (фиг. З) исследуемого гра фа (фиг. 2). Во всех остальных разрядах регистров и счетчиках будут.записаны нули.

Формула изобретени

Устройство для исследования параметров ориентированных графов, содержащее генератор тактовых импульсов, группу из п элементов И (где п - максимально возможное количество исследуемого графа), два эле мента И, матрицу пуп элементов И, элемент ИЛИ-НЕ, дешифратор, счетчик п регистров, коммутирующие элементы наборное поле, содержащее вертикальные, и горизонтальные щины,,горизонтальные шины-наборного поля через коммутирующие элементы соединены с соответствующими вертикальными шинами в соответствии с монологией графа, один, выход каждой вертикальной щины наборного поля подключен к первому входу одноименного элемента И группы, выход которого подключен к первым входам элемента И одноименной строки матрицы из элементов И, аторые входы всех элементов И группы объединены и подкщоЧе- ны к выходу элемента ИЛИ-НЕ, выход каждого i-ro элемента И каждого j- го столбца матриць из nvn элементов И подключен к 1-му информационному входу группы.входов j-ro регистра (где i, j l , 2, 3,,..-, п) входы начальной устанйвки всех регистров и счетчика объединейьГ и являются

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

0 запуска устройства, а второй вход подключен к выходу генератора, тактовых импульсов, вторые входы всех элементов И каждого J-ro столбца матрицы из элементов И объедине5 ны и подключены к j-му выходу дешифратора, другой выход каждой верти- : кальнои шины наборного поля подключен к одноименному выходу дешифратора, отличающееся тем,

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

Q выходу одноименного элемента И группы, вход запуска генератора запуска пакетов импульсов подключен к выходу первого .элемента И, а выход подключен к счетным входам всех индиАаторс ных счетчиков группы, вход сброса каждого i-ro индикаторного счетчика каждой i-й группы подключен к 1-му выходу группы выходов j-ro регистра.

5

Изобретение относится к вычислительной технике и может быть использовано для определения расстояний между вершинами ориентированных графов, являютдихся математическими моделями сетей связи, информационно расчетных систем и т,д. Цель изобретения - расширение функцио нальных возможностей устройства за счет определения длины путей между вершинами ориентированного графа, Устройство содержит группу из п элементов И, группу из п регистров, матрицу из пхп элементов И, вход Начальная установка, элемент ИЛИ-НЕ, дешифратор, генератор тактовых импульсов, счетчик, два,элемент И, вход Запуск, наборное поле, коммутирующие элементы, вертикальные и горизонтальные шины наборного поля. Поставленная цель достигается введением генератора тактовых импульсов, п групп по п индикаторных счетчиков, группы элементов задержки. 4 ил. i IS9 СП со to 00