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

 

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

„„SU„„1259281 А 1

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

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

РЕСПУБЛИК (5946 6 Р 15 20

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

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

H. АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2I) 3857442/24-24 (22) 20.02,85

,46) 23.09 ° 86 ° Бюл. 9 35 (72) Е. И. Бороденко, В. E. Назаренко и В. В, Рыбка (53) 681. 333(088. 8) (56) Авторское свидетельство СССР

И 943738, кл. G 06 F 15/20, 1982, Авторское свидетельство СССР

Ф 1174937> кл. G 06 F 15/20, 1984. но расчетных систем и т.д. Цель изобретения — расширение функциональных возможностей устройства за счет определения длины путей между вершинами ориентированного графа.

Устройство содержит группу из и элементов И, группу из и регистров, матрицу из п п элементов И, вход "Начальная установка, элемент ИЛИ-НЕ, дешифратор, генератор тактовых импульсов, счетчик. два,элемент И, вход "Запуск", наборное поле, коммутирующие элементы, вертикальные и горизонтальные шины наборного поля. Поставленная цель достигается введением генератора тактовых импульсов, и групп по и индикаторных счетчиков, группы элементов задержки. 4 ил. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ОРИЕНТИРОВАННЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для определения расстояний мекду вершинами ориентированных графов, являюшихся математическими моделями сетей связи, информационОПИСАНИЕ ИЗОБРЕТЕНИЯ / "

1259281

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

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

На фиг. 1 представлена функциональная схема устройства для исследования параметров ориентированных графов, на фиг. 2 — пример графа G(X,A); на фиг. 3 — матрица расстояний графа; на фиг. 4 — временные диаграммы, поясняющие принцип работы устройства, Устройство содержит группу элемен-, тов 1 - 1„задержки, группу H3 Il элементов И 2 (и -максимально возможное количество вершин графа), и групп по и индикаторных счетчиков 3, 3 4 -4 регистров 8,-8„:, матрицу из и х и элементов И 9 9н Щ 10ь !11, 11л

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

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

2„-2,„, выходы з.-го элемента И группы 2„ -2„ соединены с первыми входами элемента И 1-й строки .матрицы п.п элементов И 9„-9„, 10, -10„, ll l1 l2 l2 13 13 д

1 элементов И g-ro столбца соединены с одноименными информационными входами J-ro регистра 8, вход начальной установки счетчика 18 соединен с входами начальной установки регистров 8 и является входом "Начальная установка" 14 устройства, счетный вход счетчика. 18 подключен к. выходу первого элемента И 19, первый и

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

j-й ()=1,2,...,n) выход дешифратора 16 соединен с первыми входами элементов И J-ro столбца матрицы и и элементов И 9.„-9„, 10, -10„, 11„-11Ä 2 -12, 13, -13, выходы элементов 1, -1„ задержки соединены с горизонтальными шинами 25 наборного поля 23, а входы соединены с выходами соответствующих элементов И, группы 2„ -2„, вход запуска генератора 17 пакетов импульсов соединен с выходом второго элемента И

19, а выход соединен с информационными входами соответствукяцих индикаторных счетчиков 3 -3, 4„-4„, 5„.-5;, 6, -6>, 7 -7, входы сброса которых соединены с соответствующими выходами регистров 8„-8„.

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

ch2 П где,„ „ — период следования тактовых импульсов генератора 21, Элементы — 1„ задержки обеспечивают время. задержки, равное +

ch2

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

Предварительно на наборном поле 23.набирается структура исследуемого графа при помощи коммутирующих элементов 241 Если между вершинами х,; и х„" есть ребро, то между j.-й горизонтальной и g-й вертикальной пинами устанавливается элемент 24 в проводящем направлении. По входу 14

5 подается импульс, который устанавливает в нулевое состояние счетчик 18 регистры 8, -8„. Индикаторные счетчи125928! 4 торые находятся не в нулевом состоянии, сбрасываются в нулевое состояние при переходе соответствующего разряда регистров 8,-8„ из "1" в "О".

На вход элемента ИЛИ-НЕ 15 коммутируется (К+1)-й выход дешифратора, где К вЂ” количество вершин в исследуемом графе. Максимальное количество вершин равно числу и, После этого устройство готово к работе. 1О

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

9,, -96, 10! -10„, 11 -11„, !2 -12„, 13, -13 соответствующего регистра

8,,-8„, а также подается на вход соответствующей вертикальной шины наборного поля 23 ° Выходы вертикальных шин наборного поля 23 подключены к первым входам элементов И 2„ -2„, на вторые входы которых подается единичный потенциал с выхода инвер35 тора 15. Тактовые импульсы с выхода элемента И 19 поступают на управля-. ющий вход генератора 17 пакетов импульсов,и задним входом запускают генератэр после чего тот выдает паЭ

40 кет из и импульсов, задержанных относительно начала тактового импульI са на величину 1,,>1 =,;, (фиг. 4 г и д), Счетчики 3,-3„, 4, -4„, 5 -5,„, 6 -61„7 -7, рассчитаны на подсчет и 45 (n-1)-ro импульса, так как максимальиый путь в графе между двумя вершинами равен п-1, где n — количество вершин в графе. С приходом п-го импульса счетчики сбрасываютt 50 ся в нулевое состояние.

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

При.поступлении первого тактового импульса на первом выходе дешифрато- . ра появляется напряжение логической единицы ("фиг. 4б). Генератор пакетов импульсов запускается и выдает. пакет из и импульсов (фиг, 4г}. Напряжение логической "1" с первого выхода дешифратора 16 поступает на первые входы элементов И 9, -91, и открывает их. Кроме того,;это же напряжение поступает на один вывод первой вертикальной шины 25, наборного поля 23, на котором набрана топология исследуемого графа (фиг. 1). С другого вывода шины 25, это напряжение поступает на элемент И 2,„, который открыт напряжением логической "1" с выхода элемента ИЛИ-НЕ 15, С выхода элемента И 2 (фиг. 4д) напряжение логической " 1" поступает на схему И 9 и записывает в первый

1 разряд регистра 8 "1". Кроме того, это напряжение поступает на линию 1„» задержки и через нее задержанное время -t, „ — на горизонтальную шину 26, наборного поля 23. Напряжение логической "1" с инверсного выхода первого разряда регистра 8, при его переходе в единичное состояние пропадает (фиг. 4е), запрещая тем самым запись в индикаторный счетчик 3, импульсов с генератора 17 так как первый импульс пакета saдержки на величину Т 3 1 =t (фиг. 4д и а). Первый импульс пакета записыается ao ace счетчики 3,-3, 4 -4

5,-5„, 6, -6„, 7, -7„, кроме счетчика 3i.

Напряжение логической "1" с горизонтальной шины 26 наборного по"

1 ля 23 через элемент 24,, попадает на вертикальную шину 25, через элемен" ты И 2 и 9 записывает "1". в третий разряд регистра 81 и запрещает дальнейшую запись импульсов в счетчик 33 (фиг. 4з). Поэтому второй импульс запишется только в счетчике 3,3„

Напряжение логической "1" с выхода элемента И 23 поступает на вход линии 1 задержки и через нее — на

3 горизонтальную шину 26 наборного поля 23, а затем через коммутирующий элемент 24>, элемент И 2, записывает в четвертый разряд регистра 8„

"1", запрещая тем самым дальнейшую запись импульсов в счетчик 34 (фиг. 4к). После этого во все счетчики, кроме счетчиков Зу, 3 и 34,, запишутся и-1 импульсов, а затем и-й импульс, сбросив их содержимое в "0"

S 1

Таким образом, в первой строке матрицы расстояний после первого такта. работы (счетчики 3, -3 ) будет

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

В первых четырех разрядов регистров

8,, 82, 8 . и 8„ записывается матрица достижимостей графа (фиг. 2), а в индикаторных счетчиках 3, -3„, 4,-4,, 5,-5, б, -6,записывается

Ф . матрица расстояний (фиг, 3) исследуемого графа (фиг, 2). Во всех остальнь х разрядах регистров и счетчиках будут записаны нули.

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

Устройство для исследования параметров ориентированных графов, содержащее генератор тактовых импульсов, группу из и элементов И (rpe n — максимально возможное количество исследуемого графа), два эле-. мента И, матрицу пвп элементов И, элемент ИЛИ-НЕ, дешифратор, счетчик, п регистров, коммутирующие элементы, наборное поле, содержащее вертикальные и горизонтальные шины, горизонтальные шины. наборного поля через коммутирующие элементы соединены с соответствующими вертикальными шинами в соответствии с монологией графа, один выход каждой вертикальной шины наборного поля подключен к первому входу одноименного элемента И группы, выход которого подключен к первым входам элемента И одноименной строки матрицы из ns n элементов И, вторые входы всех элемен259281 Ь тов И группы объединены и подключены к выходу элемента ИЛИ-HE выхщт каждого i-ro элемента И каждого дго столбца матрицы из п п элемен5 тов И подключен к i-му информационному входу группы входов 1-го регистра (где i, J=-1, 2, 3,...; п) входы начальной установки всех регистров и счетчика объединенй и являются

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

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

20 запуска устройства, а второй вход подключен к выходу генератора тактовых импульсов, вторые входы всех элементов И каждого )-ro столбца матрицы из n"n элементов И объединен ны и подключены к j-му выходу дешифратора, другой выход каждой вертикальной шины наборного поля подключен к одноименному выходу дешифратора, о т л и ч а ю щ е е с я тем, ЗО что, с целью расширения функциональных воэможностей за счет определения длины пути между вершинами, в него введены генератор пакетов импульсов, и групп индикаторных счетчиков по и счетчиков в каждой, группа из п эле35 ментов задержки, выходы которых соединены с горизонтальными шинами наборного поля, а.вход каждого эле мента задержки группы подключен к

4О выходу одноименного элемента И группы, вход запуска генератора запуска пакетов импульсов подключен к выходу первого элемента И, а выход подключен к счетным входам всех индикатор4S ных счетчиков группы, вход сброса каждого i-го индикаторного счетчика

Ф каждой i-й группы подключен к --му выходу группы выходов j-го регистра.!

259281

1259281

1 2

Составитель Т. Сапунова

Редактор Н, Яцола Техред И.Попович Корректор И. Муска

Заказ 5123/47 Тираж 671 Подписно е

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, R-35, Раушская наб,, д, 4/5

Производственно- полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

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

 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта

 

Наверх