Способы формального описания коммутационных схем
Диаграмма коммутационной схемы - одна из основных составляющих исходной информации системы автоматического проектирования. Гиперграф - обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые их подмножества.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 12.06.2016 |
| Размер файла | 267,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Введение
Речь идет об описании принципиальных электрических схем. В литературе по САПР принципиальные электрические схемы называют коммутационными. Связи в схеме соответствуют передаче электрических сигналов.
Принципиальную электрическую схему рассматриваем, как состоящую из множества элементов E=e1,e2,…,en, соединенных между собой электрическими цепями из множества V=v1,v2,…,vm). Назовем такое представление коммутационной схемой (рис. 1).
Каждый i-ый элемент имеет множество выводов С=сi1,сi2,…,cik. Внешние выводы схемы, служащие для связи с другими схемами (например, через электросоединитель), удобно представить фиктивным элементом e0.
1. Граф коммутационной схемы
Рис. 1
гиперграф коммутационный подмножество
Среди различных вариантов описания коммутационных схем наибольшей общностью и наглядностью обладает описание схемы в виде графа. Оно позволяет в целом ряде случаев найти адекватные задачи в теории графов и воспользоваться при разработке алгоритмов решения задач конструирования известными математическими методами.
Наиболее общим способом описания схем графами является граф коммутационной схемы (ГКС) G = (E,V,C,F,W).
Он несколько отличается от обычного линейного графа. Он содержит три типа вершин соответствующих:
- E - элементам;
- C - выводам элементов;
- V - цепям (комплексам).
Рёбра делятся на:
- элементные F;
- cигнальные W.
Элементные рёбра F определяют принадлежность выводов из множества C элементам из множества E и задаются парами вершин (ei,ck).
Сигнальные ребра W определяют вхождение выводов из С в отдельные цепи и описываются парами вершин (ck,vi).
Для схемы, приведенной на рис. 1, (ГКС) приведен на рис. 2.
Рис. 2
2. Описание ГКС матрицами
Т.к. ГКС содержит вершины и рёбра разных типов, его удобно описать двумя матрицами A и B.
Матрица A представляет цепи схемы и определяется следующим образом:
А=¦aij¦mxk,
где m - число цепей, k - число выводов в схеме. Строки матрицы соответствуют цепям, а столбцы - выводам элементов.
Для графа, приведенного на рис. 2, матрица А имеет вид:
Табл. 1
|
A= |
c01 |
c02 |
c03 |
c04 |
c11 |
c12 |
c13 |
c21 |
c22 |
c23 |
c31 |
c32 |
c33 |
c41 |
c42 |
||
|
v1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
v2 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
||
|
v3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
||
|
v4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
||
|
v5 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
||
|
v6 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Каждый столбец матрицы A содержит одну единицу, поскольку любой вывод может входить лишь в одну цепь. Число единиц в любой строке матрицы равно размеру соответствующей цепи.
Матрица:
B=¦bij¦nxk,
выделяет подмножества выводов, принадлежащих отдельным элементам. Строки матрицы соответствуют элементам, а столбцы - выводам.
Для графа, приведенного на рис. 2, матрица B имеет вид:
Табл. 2
|
B= |
c01 |
c02 |
c03 |
c04 |
c11 |
c12 |
c13 |
c21 |
c22 |
c23 |
c31 |
c32 |
c33 |
c41 |
c42 |
||
|
e0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
e1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
e2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
||
|
e3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
||
|
e4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
В каждом столбце матрицы В одна единица, т.к. вывод может принадлежать только одному элементу. Число единиц в строке равно числу выводов на соответствующем элементе.
Структуру ГКС можно задать одной матрицей
T=¦tij¦nxk1,
строки которой соответствуют элементам, а столбцы выводам элемента, причём к1 = max ki, i=1,n.
Элемент матрицы tij представляет номер цепи, связанной с выводом cj элемента ei. Т.е. t23 - номер цепи, связанной с выводом c3 элемента e2. Для нашей схемы:
Табл. 3
|
T= |
c1 |
c2 |
c3 |
c4 |
||
|
e0 |
1 |
2 |
5 |
6 |
||
|
e1 |
1 |
2 |
3 |
- |
||
|
e2 |
3 |
4 |
5 |
- |
||
|
e3 |
3 |
2 |
4 |
- |
||
|
e4 |
4 |
6 |
- |
- |
Матрица T называется матрицей цепей. Для построения матрицы цепей необходимо каждой цепи присвоить номер.
Существуют упрощенные модели схем. Так, при компоновке элементов в конструктивные узлы можно не рассматривать выводы элементов, а рассматривать только сами элементы. Тогда элементные рёбра можно устранить, т.е. вершины - как бы «стянуть» в элементы (убираем выводы элементов, а цепи обозначаем точками). Тогда можно построить граф элементных комплексов (ГЭК) G1= (E,V1,W) Здесь множества вершин соответствуют:
- Е - элементам;
- V1 - элементным комплексам;
- W - сигнальным рёбрам.
Элементный комплекс V'j - подмножество элементов из E=e1,e2,…,en, соединенных цепью j, j=1,M. Элементные комплексы могут содержать общие элементы, то есть V'jV'j0, ij. Число элементов в комплексе V'j назовем размером элементного комплекса p'j.
ГЭК для схемы рис. 2 имеет вид:
Рис. 3
Описать множества цепей (комплексов) этого графа:
V1=e0,e1; V2= ; V3= ; V4= ; V5= ; V6=
Для описания ГЭК удобно воспользоваться матрицей:
Q=¦qij¦nxm,
строки которой соответствуют элементам, а столбцы элементным комплексам.
В нашем случае:
Табл. 4
|
Q= |
V11 |
V21 |
V31 |
V41 |
V51 |
V61 |
||
|
e0 |
1 |
1 |
0 |
0 |
1 |
1 |
||
|
e1 |
1 |
1 |
1 |
0 |
0 |
0 |
||
|
e2 |
0 |
0 |
1 |
1 |
1 |
0 |
||
|
e3 |
0 |
1 |
1 |
1 |
0 |
0 |
||
|
e4 |
0 |
0 |
0 |
1 |
0 |
1 |
3. Описание ГКС гиперграфами
Коммутационную схему можно также упрощенно описать с помощью гиперграфов.
Гиперграф -- обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.
С математической точки зрения, гиперграф представляет собой пару H = (E,V), где E - непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а V - семейство непустых (необязательно различных) подмножеств множества E, называемых рёбрами гиперграфа.
Гиперграфы применяются, в частности, при моделировании электрических схем.
Пример гиперграфа приведен на рис. 4.
Рис. 4
E=e1,e2,e3,e4,e5,e6,e7
V=v1,v2,v3,v4=e1,e2,e3,e2,e3,e3,e5,e6,e4
Граф H = (E,V) называется гиперграфом, если он состоит из множества вершин Е={е1,е2,…,еn} и множества рёбер V={v1,v2,…,vm}. Причём каждое ребро viV представляет собой некоторое подмножество множества вершин, т.е. viE, viпусто,
В гиперграфе H=(E,V) две вершины считаются смежными, если существует ребро V, содержащее эти вершины. Два ребра смежные, если их пересечение - непустое множество.
4. Применение ГКС, ГЭК, ВГС
ГКС - является наиболее полным и точным описанием и входит в исходную информацию САПР. Непосредственно используется при решении задачи трассировки. ГКС применяется для решения задачи размещения, когда надо учитывать размеры элементов и положения их выводов. Можно для размещения сначала использовать модели ГЭК и ВГС, а для получения окончательного решения ГЭК и ГКС. Для решения задач компоновки информация о точном расположении выводов на элементах не требуется. Поэтому наиболее часто используется ВГС и ГЭК. Причём ГЭК более соответствует физическому содержанию, а ВГС при описании его матрицей смежности наиболее легко реализуется на компьютере.
5. Графы монтажных соединений
Помимо графов для описания принципиальных схем используют графы монтажных соединений. О них будем говорить в разделе разводки цепей. Сейчас отметим их свойства:
1. Графы соединений всегда связны.
2. Графы соединений чаще всего не содержат циклов, т.е. являются деревьями. Это связано с тем, что удаление любого ребра в цикле не нарушает электрического соединения. Правда, в монтаже электрокоробок применяются и замкнутые цепочки.
3. При печатном монтаже помимо выводов элементов используют дополнительные точки ветвления. Так образуются связи «вывод - проводник», «проводник - вывод».
Такие деревья называются деревьями Штейнера.
Размещено на Allbest.ru
...Подобные документы
Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Задача о кенигсбергских мостах, четырех красках, выходе из лабиринта. Матрица инцидентности для неориентированного и (ориентированного) графа. Степень вершины графа. Ориентированное дерево. Линейные диаграммы или графики Ганта. Метод критического пути.
презентация [258,0 K], добавлен 23.06.2013История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Примеры решения задач по заданию графов. Определение основных характеристик графа: диаметра, радиуса, эксцентриситета каждой вершины. Вычисление вершинного и реберного хроматического числа. Упорядоченность матричным способом и построение функции.
контрольная работа [224,6 K], добавлен 05.07.2014Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
контрольная работа [227,5 K], добавлен 20.04.2015Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Построение сигнального графа и структурной схемы системы управления. Расчет передаточной функции системы по формуле Мейсона. Анализ устойчивости по критерию Ляпунова. Синтез формирующего фильтра. Оценка качества эквивалентной схемы по переходной функции.
курсовая работа [462,5 K], добавлен 20.10.2013Общее понятие теоремы Эйлера, этапы ее доказательства. Необходимые и достаточные условия существования эйлерова цикла. Сущность задачи о построении каркаса куба. Алгоритм Флери построения эйлерова цикла. Обход полуэйлерова графа с нечетной вершины.
презентация [27,1 K], добавлен 12.04.2014Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Разработка логико-формальной модели описания методики изготовления винных изделий. Разделение ингредиентов и продукции на множества. Исследование на рефлексивность, транзитивность, симметричность. Построение графа, матрицы смежности и инцидентности.
контрольная работа [165,2 K], добавлен 07.06.2010Побудова графічної схеми алгоритму та розмітка станів автомата, графа та кодування, структурної таблиці. Синтез комбінаційних схем для функцій збудження тригерів і вихідних сигналів. Представлення функції в канонічних формах алгебр Буля, їх мінімізація.
курсовая работа [902,8 K], добавлен 27.08.2014Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
курсовая работа [584,3 K], добавлен 26.04.2011Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Построение статистического ряда исходной информации. Определение среднего значения показателя надежности и среднеквадратического отклонения. Проверка информации на выпадающие точки. Определение доверительных границ при законе распределения Вейбулла.
контрольная работа [65,7 K], добавлен 31.01.2014Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
учебное пособие [1,5 M], добавлен 27.10.2013Особенности нормальной формы линейного преобразования. Изучение собственных и присоединенных векторов линейного преобразования. Выделение подпространства, в котором преобразование А имеет только одно собственное значение. Анализ инвариантных множителей.
курсовая работа [37,6 K], добавлен 21.02.2010Проверка справедливости тождеств или включений с использованием алгебры множеств и диаграмм Эйлера-Венна. Изображение графа и матрицы отношения, обладающего свойствами рефлексивности, транзитивности и антисиммеричности. Изучение неориентированного графа.
контрольная работа [1,3 M], добавлен 05.05.2013Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.
курсовая работа [200,4 K], добавлен 27.04.2011Основные правила решения системы заданных уравнений методом Гаусса с минимизацией невязки и методом простых итераций. Понятие исходной матрицы; нахождение определителя для матрицы коэффициентов. Пример составления блок-схемы метода минимизации невязок.
лабораторная работа [264,1 K], добавлен 24.09.2014
