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

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для исследования параметров систем, описываемых графами. Целью изобретения является разработка устройства для исследования параметров графа, обеспечивающего более полный анализ функционирования систем, выполненных в форме графов, позволяющего учитывать и изменять временной интервал и выявлять неисправные дуги графа. Поставленная цель достигается тем, что устройство для исследования параметров графа содержит блок задания матрицы смежности 4, блок селекции дуг графа 2, блок определения конечных вершин 1, блок моделирования дуг графа 8, блок регистрации 10, блок формирователей временных интервалов 7, блок задания первоначальной вершины графа 3, блок разрешения 9, результирующий блок 6, блок имитации отказов дуг 11 и блок имитации воздействия помех 4. 27 ил.

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

Известны устройства определения путей распространения сигналов в системах, описываемых графами (например, авт. св. СССР N 223468, кл. G 06 G 7/122, 1967 и авт. св. СССР N 1522229, кл. G 06 F 15/20, 1988), состоящих из блока определения кратчайшего пути, времяимпульсного интегрирующего преобразователя, блока синхронизации и накапливающего блока логического сложения. Суть данных устройств заключается в исследовании распространения сигналов в системе, описываемой неполносвязанным графом, причем время распространения сигнала по разным дугам графа может быть различно, и определении времени появления сигнала в каждой вершине графа. Однако, известные способы-аналоги имеют недостатки: длительное время определения путей распространения сигнала от узла-источника до любой вершины графа (из-за отсутствия фиксации ребер дерева кратчайших путей); низкая вероятность выбора оптимального пути на графе (так как не обеспечивается достаточно оперативное изменение связности графа).

Наиболее близким по своей технической сущности к заявленному устройству является устройство, описанное в авт. св. СССР N 1603396, кл. G 06 F 15/20, от 30.10.90. Устройство-прототип содержит блок задания матрицы смежности, блок селекции дуг графа (удаления заходящих дуг), блок определения кратчайшего пути, блок регистрации и блок определения конечных вершин дуг, а кроме того, вход пуска устройства и выход признаков принадлежности ребер дереву кратчайших путей.

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

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

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

Поставленная цель достигается тем, что в известном устройстве для определения параметров графа, содержащем блок задания матрицы смежности, блок селекции дуг графа, блок определения конечных вершин, блок моделирования дуг графа, блок регистрации, дополнительно введены блок формирования временных интервалов, блок задания первоначальной вершины графа, результирующий блок, блок имитации отказов дуг и блок имитации воздействия помех, при этом K-й выход блока определения конечных вершин подключен к одноименному входу второй секции входов блока селекции дуг графа, (K,M)-й выход которого подключен к одноименному (K,M)-му входу первой секции входов блока моделирования дуг графа, где K - 1, 2, ..., B; M - 1, 2, ..., B; B - количество вершин в графе, а (K,M)-й выход блока моделирования дуг графа подключен к одноименному входу блока регистрации. (K,M)-й выход блока задания матрицы смежности подключен к одноименному входу первой секции входов блока селекции дуг графа и одноименно подключен к одноименному входу первой секции входов блока определения конечных вершин. Причем K-й выход блока задания первоначальной вершины графа подключен к одноименному входу третьей секции входов блока селекции дуг графа, (K, M)-й выход блока задания матрицы смежности дополнительно подключен к одноименному входу первой секции входов результирующего блока, (K, M)-й вход второй секции входов которого и (K,M)-й вход блока формирования временных интервалов подключены в параллель к одноименному выходу блока регистрации. (K,M)-й выход блока формирования временных интервалов подключен к одноименному входу второй секции входов блока определения конечных вершин, а (K,M)-й вход первой секции входов и второй секции входов блока разрешения подключен соответственно к одноименным выходам блока имитации воздействия помех и блока имитации отказов дуг. Также (K,M)-й выход блока разрешения подключен к одноименному входу второй секции входов блока моделирования дуг графа, кроме того, блок начальной установки устройства R параллельно подключен к соответствующим входам начальной установки блока задания первоначальной вершины графа, блока формирования временных интервалов, блока разрешения и блока регистрации, а вход запуска устройства S подключен к соответствующему входу блока задания первоначальной вершины графа. (K,M)-е входы результирующего блока являются выходами устройства, содержащими информацию о промоделированных или непромоделированных дугах графа.

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

На фиг. 1 приведена общая структурная схема устройства для исследования параметров графа; на фиг. 2 - блок определения конечных вершин 1; на фиг. 3 - элемент И блока определения конечных вершин 1.1; на фиг. 4 - элемент выходной матрицы блока определения конечных вершин 1.2; на фиг. 5 - блок селекции дуг графа 2; на фиг. 6 - элемент матрицы селекции блока селекции дуг графа 2.1; на фиг. 7 - блок задания первоначальной вершины графа 3; на фиг. 8 - элемент НЕ блока задания первоначальной вершины графа 3.1; на фиг. 9 - одновибратор блока задания первоначальной вершины графа 3.2; на фиг. 10 - блок задания матрицы смежности 4; на фиг. 11 - блок имитации воздействия помех 5; на фиг. 12 - имитатор помех блока имитации воздействия помех 5.1; на фиг. 13 - четырехвходовый элемент И блока имитации воздействия помех 5.2; на фиг. 14 - трехвходовый элемент И блока имитации воздействия помех 5.3; на фиг. 15 - результирующий блок 6; на фиг. 16 - элемент матрицы выходов результирующего блока 6.1; на фиг. 17 - блок формирования временных интервалов 7; на фиг. 18 - элемент матрицы формирования временных интервалов 7.1; на фиг. 19 - блок моделирования дуг графа 8; на фиг. 20 - задающий генератор блока моделирования дуг графа 8.1; на фиг. 21 - элемент матрицы моделирования дуг графа блока моделирования дуг графа 8.2; на фиг. 22 - блок разрешения 9; на фиг. 23 - элемент НЕ блока разрешения 9.1; на фиг. 24 - трехвходовый элемент ИЛИ-НЕ блока разрешения 9.2; на фиг. 25 - блок регистрации 10; на фиг. 26 - регистрирующий элемент блока регистрации 10.1; на фиг. 27 - блок имитации отказов дуг 11.

Заявленное устройство, представленное на фиг. 1, состоит из блока определения конечных вершин 1, блока селекции дуг графа 2, блока задания первоначальной вершины графа 3, блока задания матрицы смежности 4, блока имитации воздействия помех 5, результирующего блока 6, блока формирования временных интервалов 7, блока моделирования дуг графа 8, блока разрешения 9, блока регистрации 10 и блока имитации отказов дуг 11. При этом K-й выход блока определения конечных вершин 1 подключен к одноименному входу второй секции входов блока селекции дуг графа 2, где K - 1, 2, ..., B; M - 1, 2, ..., B; B - количество вершин в графе, (K,M)-й выход которого подключен к одноименному (K, M)-му входу первой секции входов блока моделирования дуг графа 8, а (K, M)-й выход блока моделирования дуг графа 8 подключен к одноименному входу блока регистрации 10. (K, M)-й выход блока задания матрицы смежности 4 подключен к одноименному входу первой секции входов блока селекции входов блока селекции дуг графа 2 и одновременно подключен к одноименному входу первой секции входов блока определения конечных вершин 1. K-й выход блока задания первоначальной вершины графа 3 подключен к одноименному входу третьей секции входов блока селекции дуг графа 2, (K,M)-й выход блока задания матрицы смежности 4 дополнительно подключен к одноименному входу первой секции входов результирующего блока 6, (K,M)-й вход второй секции входов которого и (K, M)-й вход блока формирования временных интервалов 7 подключены в параллель к одноименному выходу блока регистрации 10. (K,M)-й выход блока формирования временных интервалов 7 подключен к одноименному входу второй секции входов блока определения конечных вершин 1, а (K,M)-й вход первой секции входов и второй секции входов блока разрешения 9 подключены соответственно к одноименным входам блока имитации воздействия помех 5 и блока имитации отказов дуг 11. (K,M)-й выход блока разрешения 9 подключен к одноименному входу второй секции входов блока моделирования дуг графа 2, кроме того, вход начальной установки устройства R параллельно подключен к соответствующим входам начальной установки блока задания первоначальной вершины графа 3, блока формирования временных интервалов 7, блока разрешения 9 и блока регистрации 10, а вход запуска устройства S подключен к соответствующему входу блока задания первоначальной вершины графа 3. (K,M)-е выходы результирующего блока 6 являются выходами устройства.

На фиг. 2 показана структурная схема блока определения конечных вершин 1, который служит для определения существования исходящих дуг от моделируемой в данный момент вершины-приемника. Данный блок имеет две секции входов на KM входов каждая и секцию на K выходов. Кроме того, блок содержит матрицу KM элементов И 1.1 и K элементов выходной матрицы блока определения конечных вершин 1.2, причем первый вход каждого элемента 1.1 подключен к соответствующему контакту первой секции входов, а второй вход - к соответствующему контакту второй секции входов. Выходы M элементов 1.1 K-го столбца матрицы подключены к соответствующим M входам K-го элемента 1.2, а K выходов элементов 1.2 составляют секцию выходов данного блока. Элемент 1.1, представленный на фиг. 3, представляет собой логический двухвходовый элемент И и, в частности может быть реализован на ИМС К555ЛИ1. Элемент выходной матрицы блока определения конечных вершин 1.2, приведенный на фиг. 14, представляет собой элемент ИЛИ на B входов, выполненный по известной схеме [1], и может быть, в частности реализован на ИМС К155ЛА8 и К555ЛН1.

На фиг. 5 показана структурная схема блока селекции дуг графа 2, который используется для подключения исходящих дуг графа. В своем составе блок имеет секцию выходов и три секции входов, причем первая секция имеет KM входов, а вторая и третья - по K входов каждая. Кроме того, блок имеет KM матрицу селекции, состоящую из элементов 2.1. Структурная схема элементов матрицы селекции представлена на фиг. 6. Каждый элемент данной матрицы имеет три входа. Первый вход каждого элемента подключен к соответствующему контакту первой секции входов, вторые входы элементов K-го столбца объединены и подключены к соответствующему контакту второй секции входов, а третьи входы элементов K-го столбца объединены и подключены к соответствующему контакту третьей секции входов. Выходы элементов матрицы селекции 2.1 составляют секцию выходов блока селекции дуг графа 2. Элемент матрицы селекции 2.1 содержит двухвходовый элемент ИЛИ и двухвходовый элемент И, причем выход двухвходового элемента ИЛИ подключен к второму входу двухвходового элемента И. Элемент матрицы селекции 2.1 может быть, в частности реализован на ИМС К555ЛЛ1 и К555ЛИ1.

На фиг. 7 показана общая структурная схема блока задания первоначальной вершины графа 3. Вышеназванный блок служит для установки начальной вершины графа и содержит элементы 3.1, одновибратор 3.2, переключатель B1. Блок имеет вход начальной установки R, вход запуска устройства S и секцию на K выходов. Вход S подключен к входу элемента 3.1, его выход подключен к первому входу элемента 3.2. Второй вход этого же элемента подключен к входу R. Выход элемента 3.2 подключен к общему выходу переключателя B1. Выходы переключателя образуют секцию выходов блока. Элемент 3.1, показанный на фиг. 8, представляет собой элемент "НЕ" и может быть, в частности реализован на ИМС К555ЛН1. Элемент 3.2, приведенный на фиг. 9, представляет собой одновибратор DD1 с соответствующими времязадающими цепями, выполненный по рекомендациям [2] . Элемент может быть, в частности реализован на ИМС К555АГ3, VD1 - КД522В. Номиналы R и C зависят от требуемой длительности выходного импульса.

На фиг. 10 представлен блок задания матрицы смежности 4, служащий для задания конфигурации графа. Блок имеет секцию на KM выходов, каждый из которых подключен к соответствующему переключателю B из матрицы KM переключателей. Уровень логической "1" на выходе соответствует наличию дуги между соответствующими вершинами графа, уровень "0" - ее отсутствию.

На фиг. 11 показан блок имитации воздействия помех 5. Его функцией является моделирование сигналов помехи. В рассматриваемом варианте блок имеет секцию KM выходов, матрицу KM трехвходовых элементов И 5.3, показанного на фиг. 14, два имитатора помех 5.1, показанного на фиг. 12, и четырехвходовый элемент И 5.2, показанный на фиг. 13. Каждый из имитаторов помех 5.1 имеет K+2 выхода, причем к первым K выходам первого имитатора помех подключены первые входы K-й строки матрицы трехвходовых элементов И 5.3, выходы K+1 и K+2 этого же элемента подключены к первому и второму входам четырехвходового элемента И 5.2. Первые K выходов второго имитатора помех 5.1 подключены к третьим входам K-го столбца матрицы трехвходовых элементов И 5.3. K+1 и K+2 выходы этого же элемента подключены к третьему и четвертому входам четырехвходового элемента И 5.2, выход которого подключен к вторым входам всех трехвходовых элементов И 5.3, выходы которых образуют секцию выходов. Имитатор помех 5.1 представляет собой цифровую схему, содержащую тактовый генератор на трех элементах НЕ - DD1.1 ... DD1.3 и генератор псевдослучайных чисел на двух логических элементах НЕ - DD1.4 и DD1.5, трехвходовом элементе ИСКЛЮЧАЮЩЕЕ ИЛИ = DD2 и регистрах - DD3 ... DD(2+K/8). Имитатор помех может быть, в частности реализован на ИМС К555ЛН1, К1553ЛП3, К555ИР8. Номиналы R и C зависят от требуемой частоты. Трехвходовый элемент И 5.3 может быть, в частности реализован на ИМС К555ЛИ3. Четырехвходовый элемент И 5.2 может быть реализован, в частности на ИМС К555ЛИ6.

На фиг. 15 показан результирующий блок 6. Функциями данного блока являются конечная обработка результатов моделирования и выдача их устройству индикации. Данный блок имеет две секции входов по KM входов каждая, секцию на KM выходов, переключатель B1, резистор R и матрицу KM выходов результирующего блока, состоящую из элементов данной матрицы 6.1, представленном на фиг. 16, причем первый вход каждого элемента матрицы выходов результирующего блока 6.1 подключен к соответствующему контакту первой секции входов, третий вход - к соответствующему контакту второй секции входов, вторые входы всех элементов объединены и подключены к переключателю B1. Выходы элементов матрицы выходов результирующего блока 6.1 образуют секцию выходов. Элемент матрицы выходов результирующего блока 6.1 представляет собой логическую схему, состоящую из двух элементов НЕ, двухвходового элемента ИЛИ и трех двухвходовых элементов И, которая, в частности может быть реализована на ИМС К555ЛИ1, К555ЛН1, К555ЛЛ1.

На фиг. 17 представлена структурная схема блока формирования временных интервалов 7, служащий для определения допустимого времени передачи сигнала от моделируемой вершины-приемника. Блок состоит из матрицы KM элементов формирования временных интервалов 7.1. Входы элементов матрицы 7.1 объединены в секцию входов KM, а выходы этих же элементов объединены в секцию выходов KM. Один из элементов данной матрицы 7.1 показан на фиг. 18. Первый вход каждого элемента матрицы 7.1 подключен к соответствующему контакту секции входов, вторые входы объединены и на них подается сигнал начальной установки блока R. Элемент матрицы формирования временных интервалов 7.1 представляет собой одновибратор DD1 с соответствующими времязадающими цепями, выполненный по рекомендациям [2]. Номиналы R и C зависят от длительности импульса на выходе 2 элемента матрицы, который, в частности может быть реализован на ИМС К555АГ3, VD1 - КД522В.

На фиг. 19 показана структурная схема блока моделирования дуг графа 8. Блок задает задержки распространения сигналов на дугах графа, в том числе и при имитации воздействия помех. Данный блок имеет две секции по KM входов каждая, секцию на KM выходов, задающий генератор 8.1 (структурная схема которого представлена на фиг. 20), матрицу KM трехвходовых элементов матрицы моделирования дуг графа 8.2 (структурная схема которого представлена на фиг. 21), причем первый вход каждого элемента матрицы 8.2 подключен к соответствующему контакту первой секции входов, вторые входы всех элементов объединены и подключены к выходу задающего генератора 8.1, третий вход каждого элемента матрицы 8.2 подключен к соответствующему контакту второй секции входов. Выходы элементов матрицы 8.2 образует секцию выходов блока. Задающий генератор 8.1 собран по типовой схеме на трех элементах НЕ - DD1.1 ... DD1.3. Номиналы R и C зависят от требуемой частоты, Задающий генератор 8.1, в частности может быть реализован на ИМС К555ЛН1. Элемент матрицы моделирования дуг графа 8.2 содержит регистр DD1, двухвходовый элемент И и переключатель B1, причем выход трехвходового элемента И подключен к счетному входу регистра, а его выходы - к переключателю B1. Подвижный контакт переключателя является выходом элемента матрицы 8.2. В целом элемент данной матрицы 8.2, в частности может быть реализован на ИМС К555ИР8 и К555ЛИ1.

На фиг. 22 показана структурная схема блока разрешения 9, который осуществляет обработку информации о воздействии помех и отказах дуг. Блок имеет две секции по KM входов каждая, секцию на KM выходов, вход начальной установки R, матрицу KM трехвходовых элементов ИЛИ-НЕ 9.2, представленного на фиг. 24, и элемент НЕ 9.1, показанный на фиг. 23, причем первый вход каждого трехвходового элемента ИЛИ-НЕ 9.2 подключен к соответствующему контакту первой секции входов, вторые входы всех трехвходовых элементов ИЛИ-НЕ 9.2 объединены и подключены к выходу элемента НЕ 9.1, на вход которого подается сигнал начальной установки R. Третий вход каждого трехвходового элемента ИЛИ-НЕ 9.2 подключен к соответствующему контакту второй секции входов. Выходы элементов ИЛИ-НЕ 9.2 образуют секцию выходов. Логический элемент НЕ, в частности может быть реализован на ИМС К555ЛН1. Логический трехвходовый элемент ИЛИ-НЕ 9.2 может быть, в частности реализован на ИМС К555ЛЕ1.

На фиг. 25 представлена структурная схема блока регистрации 10, который фиксирует промоделированные дуги графа. Он имеет одну секцию на KM входов, секцию на KM выходов, вход начальной установки R и матрицу KM двухвходовых регистрирующих элементов 10.1, представленного на фиг. 26, причем первый вход каждого регистрирующего элемента 10.1 подключен к соответствующему контакту секции входов, вторые входы всех регистрирующих элементов 10.1 объединены и на них подается сигнал начальной установки R, а выходы регистрирующих элементов 10.1 образуют секцию выходов. Регистрирующий элемент 10.1 представляет собой RS-триггер, который может быть, в частности реализован на ИМС К555ТР2.

На фиг. 27 показана структурная схема блока имитации отказов дуг 11. Данный блок предназначен для моделирования отказавших дуг. В предлагаемом варианте блок имеет секцию на KM выходов и матрицу KM переключателей B, причем каждый переключатель соединен с соответствующим контактом секции выходов. Наличие логического "0" на выходе соответствует исправной дуге, логической "1" - неисправной.

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

Перед началом работы в блок 4 вводят данные о связности графа. При этом ребра графа задают двумя противоположно направленными углами K-M и M-K. Логической "1" соответствует наличие дуги между вершинами, номера которых определяются номером строки и столбца матрицы смежности, логическому "0" - ее отсутствие. Подачей отрицательного импульса на вход R устройства обнуляют блоки задания первоначальной вершины графа 3, формирования временных интервалов 7, регистрации 10, моделирования дуг графа 8, причем элементы матрицы моделирования дуг графа 8.2 обнуляют через соответствующие элементы ИЛИ-НЕ 9.2 блока разрешения 9. Переключателем B1 блока задания первоначальной вершины графа 3 устанавливают номер вершины-источника, с которой начинается распространение сигнала в графе. Переключателями B1, входящими в состав элементов матрицы моделирования дуг графа 8.2, выставляются временные задержки распространения сигнала по дугам графа в зависимости от моделируемой скорости передачи информации по каналам связи. Подачей на вход S отрицательного импульса запускают устройство. При этом из блока задания первоначальной вершины графа 3 в течение времени, определяемого одновибратором 3.2, в блок селекции дуг графа 2 по одному из входов третьей секции входов подается сигнал, разрешающий начало моделирования дуг, исходящих от вершины источника к сопряженным с ней вершинам. Информация о наличии связей между ними поступает в блок селекции дуг графа 2 из блока задания матрицы смежности 4 через первую секцию входов. Наличие логических "1" на выходах блока селекции дуг графа 2 разрешает начало моделирования соответствующих дуг в блоке моделирования дуг графа 8. Через некоторое время, определяемое задержкой распространения сигнала в элементах матрицы моделирования дуг графа 8.2, на соответствующих выходах блока моделирования дуг графа 8 появятся сигналы логических "0", которые будут зарегистрированы в блоке регистрации 10 триггерами, входящими в состав регистрирующих элементов 10.1. На соответствующих выходах блока регистрации 10 появятся сигналы логических "1", означающие то, что дуга графа промоделирована и сигнал достиг вершины-приемника. Эти сигналы поступят в блок формирования временных интервалов 7 и запустят соответствующие одновибраторы в элементах матрицы формирования временных интервалов 7.1, которые определяют время, разрешенное для передачи сигнала далее по графу от вершин-приемников. Импульсы логических "1" поступают из блока формирования временных интервалов 7 в блок определения конечных вершин 1 через вторую секцию входов, где они складываются с соответствующими сигналами из блока задания матрицы смежности 4, поступающими через первую секцию входов, и в случае, если существуют дуги из вершины-приемника к другим вершинам, на выходе соответствующих элементов выходной матрицы блока определения конечных вершин 1.2 формируются сигналы логических "1". Эти сигналы разрешат прохождение информации из блока задания матрицы смежности 4 в блок моделирования дуг графа 8 для начала моделирования новых дуг графа. Далее цикл повторяется, Описанный процесс будет повторяться до тех пор, пока у вершин, из которых разрешена передача сигнала на данный момент времени, существуют непромоделированные дуги. Для моделирования процесса распространения сигнала в графе при воздействии помех и проявления отказов дуг предназначены блоки имитации воздействия помех 5, разрешения 9, имитации отказов дуг 11. Блок имитации воздействия помех 5 вырабатывает сигналы воздействия помех. Он может быть построен по нескольким схемам, реализующим тот или иной закон воздействия помех на дуги графа. В предлагаемом варианте блок обеспечивает псевдослучайное воздействие помех. Блок имитации отказов дуг 11 также может быть реализован в различных вариантах. В данном случае он построен по схеме с ручным вводом отказа дуги. Сигналы логических "1" из этих двух блоков через соответствующие входы поступают в блок разрешения 9, где они инвертируются и поступают на соответствующие входы блока моделирования дуг графа 8, вызывая сброс регистров в элементах матрицы моделирования дуг графа 8.2, что при моделировании в этот момент времени соответствующих дуг обеспечивает дополнительную задержку при распространении сигнала. Задержка может оказаться столь большой, что истечет время, отведенное для передачи сигнала из данной вершины. В таком случае дуга останется непромоделированной, что будет выявлено результирующим блоком 6 после прекращения распространения сигнала по графу. Результирующий блок 6 в зависимости от положения переключателя B1 определяет промоделированные и непромоделированные дуги в графе. При наличии на выходе B1 логической "1" элементы матрицы выходов результирующего блока 6.1 выдают сигналы логических "1" при наличии промоделированных дуг. При наличии на выходе B1 логического "0" на выходах соответствующих элементов матрицы выходов результирующего блока 6.1 появятся логические "1" в случае непромоделированных дуг. Выходы элементов матрицы выходов результирующего блока 6.1 могут быть подключены к блоку индикации (в предложении не рассматривается). Таким образом устройство позволяет моделировать процессы распространения сигнала в графе с учетом воздействия помех на дуги графа и появления отказов в них, а также с учетом времени, отведенного для передачи сигнала из каждой вершины выявлять промоделированные и непромоделированные дуги в графе.

Наиболее сложным по своей технической реализации является блок имитации воздействия помех 5, обеспечивающий воздействие на дуги графа помех по псевдослучайному закону. Для этого в состав блока введены два генератора псевдослучайных чисел 5.1, построенные по рекомендациям [2]. С целью уменьшения интенсивности воздействия помех в состав блока имитации воздействия помех 5 введен четырехвходовый элемент И 5.2.

Поскольку скорости обмена информацией по каналам связи кратны 1200 бит/с, то целесообразно частоту задающего генератора 8.1 блока моделирования дуг графа 8 выбрать 9600 Гц, что позволит обеспечить на элементе матрицы моделирования дуг графа 8.2 задержку распространения сигнала, соответствующую скоростям передачи 9600, 4800, 2400, 1200 бит/с.

В предлагаемом варианте устройство реализовано на ИМС ТТЛ.

Справочные данные на примененные ИМС, узлы и схемы: 1. Шило В.Л. Популярные цифровые микросхемы: Справочник 2-е изд., исправленное. - М.: Радио и связь, 1989, 352 с.

2. Шевкопляс В. В. Микропроцессорные структуры. Инженерные решения. Справочник. 2-е изд., перераб. и доп. - М.: Радио и связь, 1990, 512 с.

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

Устройство для исследования параметров графа, содержащее блок задания матрицы смежности, блок селекции дуг графа, блок определения конечных вершин, блок моделирования дуг графа, блок регистрации, при этом К-й выход блока определения конечных вершин подключен к одноименному входу второй секции входов блока селекции дуг графа, К,М-й выход которого подключен к одноименному К,М-му входу первой секции входов блока моделирования дуг графа, где К - 1, 2 ... В; М - 1, 2 ... В; В - количество вершин в графе, а К,М-й выход блока моделирования дуг графа подключен к одноименному входу блока регистрации, К,М-й выход блока задания матрицы смежности подключен к одноименному входу первой секции входов блока селекции дуг графа и одновременно подключен к одноименному входу первой секции входов блока определения конечных вершин, отличающееся тем, что в него дополнительно введены блок формирования временных интервалов, блок задания первоначальной вершины графа, блок разрешения, результирующий блок, блок имитации отказов дуг и блок имитации воздействия помех, причем К-й выход блока задания первоначальной вершины графа подключен к одноименному входу третьей секции входов блока селекции дуг графа, К,М-й выход блока задания матрицы смежности дополнительно подключен к одноименному входу первой секции входов результирующего блока, К,М-й вход второй секции входов которого и К,М-й вход блока формирования временных интервалов подключены в параллель к одноименному выходу блока регистрации, К,М-й выход блока формирования временных интервалов подключен к одноименному входу второй секции входов блока определения конечных вершин, а К,М-й вход первой секции входов и второй секции входов блока разрешения подключен соответственно к одноименным выходам блока имитации воздействия помех и блока имитации отказов дуг, К,М-й выход блока разрешения подключен к одноименному входу второй секции входов блока моделирования дуг графа, кроме того, R-вход начальной установки устройства параллельно подключен к соответствующим входам начальной установки блока задания первоначальной вершины графа, блока формирования временных интервалов, блока разрешения и блока регистрации, а S-вход запуска устройства подключен к соответствующему входу блока задания первоначальной вершины графа, К,М-е выходы результирующего блока являются выходами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16, Рисунок 17, Рисунок 18, Рисунок 19, Рисунок 20, Рисунок 21, Рисунок 22, Рисунок 23, Рисунок 24, Рисунок 25, Рисунок 26, Рисунок 27