Переходный граф сигналов

Перехо́дный граф сигна́лов (линейный переходный граф, линейный граф сигналов; англ. signal-flow graph, SFG), предложенный Клодом Шенноном, но часто называющийся графом Мейсона из-за его работ, посвящённых данному термину — специализированный потоковый граф^[en], в котором вершинам соответствуют некоторые переменные, а рёбра связывают инцидентные вершины какими-либо функциями. Более формально: ориентированный граф, каждой вершине $i$$i$ которого соответствует сигнал (весовая функция) $a_i$$a_{i}$, зависящий некоторым образом от сигналов (весовых функций) на других вершинах.

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

ИсторияПравить

Вай-Кай Чен писал: «Концепция переходного графа сигналов была разработана Шенноном при работе с аналоговыми компьютерами. Наибольший вклад в разработку переходного графа сигналов принадлежит Мейсону. Он показал, как использовать переходный граф сигналов для решения некоторых сложных электронных задач относительно простым способом. Термин переходный граф сигналов был использован из-за его первоначального применения к электронике и сходством с электронными сигналами и блок-схемами исследуемых систем».

Лоренс писал: «До работы Мейсона Шеннон выделил ряд свойств того, что сейчас известно как потоковые графы. К сожалению, документ изначально был очень ограничен в своей классификации, и очень немногие люди имели доступ к материалам».

«Правила вычисления определителя графа графа Мейсона были впервые даны и доказаны Шенноном с использованием математической индукции. Его работа оставалась практически неизвестной даже после того, как Мейсон опубликовал свой классический труд в 1953 году. Три года спустя Мейсон заново открыл правила и доказал их, рассматривая значение определителя и то, как оно изменяется при добавлении переменных в граф. [...]»

Область примененияПравить

Робишо и др. определяют область применения переходного графа сигналов следующим образом:

«Область применения разработанных методов составляют все физические системы, аналогичные этим сетям [построенным из идеальных трансформаторов, активных элементов и гираторов]. Трент показал, что в эту категорию попадают все физические системы, удовлетворяющие следующим условиям.

1. Конечная сосредоточенная система состоит из ряда простых частей, каждая из которых имеет известные динамические свойства, которые могут быть определены уравнениями с использованием двух типов скалярных переменных и параметров системы. Переменные первого типа представляют собой величины, которые могут быть измерены, по крайней мере, теоретически, путем присоединения измерительного прибора к двум точкам соединения элемента. Переменные второго типа характеризуют величины, которые можно измерить, последовательно подключив измеритель к элементу. Относительные скорости и положения, перепады давления и напряжения являются типичными величинами первого типа, тогда как электрические токи, силы, скорости теплового потока - величинами второго типа. [...]
2. Переменные первого типа должны подчиняться закону, аналогичному правилу напряжений Кирхгофа, тогда как переменные второго типа должны подчиняться закону, аналогичному правилу узлов Кирхгофа.
3. Физические размерности соответствующих результатов вычислений переменных обоих типов должны быть согласованы. Для систем, в которых выполняются эти условия, можно построить линейный граф, изоморфный динамическим свойствам системы, описываемым выбранными переменными. Эти методы [...] могут быть применены непосредственно к этим линейным графам, ровно как и к электрическим сетям, чтобы получить переходный граф сигналов системы.»

Основы теории потоковых графовПравить

 

(a) потоковый граф, (b) рёбра, входящий в узел 2 (c) рёбра, входящий в узел 3

В графе на рисунке функциональная зависимость узла обозначена входящей в него стрелкой, узел же, вызывающий эту зависимость, является началом этой стрелки, и в самом общем виде граф потока сигналов указывает входящими стрелками только те узлы, которые влияют на обработку в принимающем узле, и на каждом i-ом узле входящие переменные обрабатываются в соответствии с функцией, связанной с этим узлом, например F_i. Таким образом, (а) представляет набор явных отношений:

${\begin{aligned}x_{1}&={\text{независимая переменная}}\\x_{2}&=F_{2}(x_{1},x_{3})\\x_{3}&=F_{3}(x_{1},x_{2},x_{3})\\\end{aligned}}$ 

Узел x₁ является изолированным узлом, поскольку ни одна стрелка в него не входит; уравнения для x₂ и x₃ соответствуют графикам, показанным в пунктах (b) и (c) рисунка.

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

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

${\begin{aligned}x_{1}&={\text{независимая переменная}}\\x_{2}&=f_{21}(x_{1})+f_{23}(x_{3})\\x_{3}&=f_{31}(x_{1})+f_{32}(x_{2})+f_{33}(x_{3})\\\end{aligned}}$ 

Теперь функции $f_{ij}$$f_{ij}$  можно сопоставить $ij$$ij$  ребро графа сигналов, соединяющими пару узлов $x_i$$x_{i}$ , $x_j$$x_{j}$ , вместо того, чтобы для каждого узла задавать общие функции. Вклад узла в себя, например $f_{33}$$f_{33}$  для $x_3$$x_{3}$ , называется петлей. Часто эти функции являются просто мультипликативными коэффициентами (часто называемыми коэффициентами пропускания или коэффициентами усиления), например, $f_{ij}(x_j)=c_{ij}{x}_j$$f_{ij}(x_{j})=c_{ij}x_{j}$ , где $c$$c$  - может являться не только скаляром, но и функцией некоторого параметра, такого как переменная преобразования Лапласа $s$$s$ . Графики потока сигналов очень часто используются с сигналами, преобразованными по Лапласу, поскольку они представляют собой системы линейных дифференциальных уравнений. В этом случае коэффициент пропускания $c(s)$$c(s)$  часто называют передаточной функцией.

Выбор переменныхПравить

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

НеединственностьПравить

График потока сигналов содержит то же количество информации, что и уравнения, из которых он получен; но не существует взаимно однозначного соответствия между графиком и системой уравнений. Одна система будет давать различные графики в зависимости от порядка, в котором уравнения используются для нахождения переменной, записанной в левой части. Например, если каждое уравнение связывает все $n$$n$  зависимых переменных, то существует $n!$$n!$  возможных графов.

Линейный переходный граф сигналовПравить

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

Линейный переходный граф сигналов состоит из узлов и взвешенных направленных ветвей. Узлы — это переменные уравнений, а веса ветвей — это коэффициенты. Сигналы способны протекать по ветви лишь в направлении, указанном стрелкой. Граф может представлять только операции умножения на коэффициент и сложения, которых достаточно для представления уравнений связи. Когда сигнал пересекает ветвь в указанном направлении, сигнал умножается на вес ветви. Когда две или более ветви направляются в один и тот же узел, их выходы суммируются.

Для систем, описываемых линейными алгебраическими или дифференциальными уравнениями, граф потока сигналов математически эквивалентен системе уравнений, описывающей систему. В таком случае уравнения, задающие граф, могут быть найдены для каждого узла путем суммирования входящих в этот узел ветвей. Сами ветви передают вклады других узлов, выраженные как значение узла-истока, умноженное на вес соединительной ветви, обычно являющийся действительным числом или функцией некоторого параметра (например, переменной $s$$s$  преобразования Лапласа).

Чома, член IEEE, писал касательно линейных активных сетей следующее:

«Под представлением в виде потока сигналов (или «графа», как его обычно называют) мы подразумеваем диаграмму, которая, отображая алгебраические отношения между соответствующими переменными и ветвлениями сети, однозначно представляет то, как приложенный входной сигнал «течет» от портов ввода до портов вывода [...]».

Польза анализа потоковых графов сигналов была также описана информатиком Ченом:

«Анализ линейной системы в конечном итоге сводится к решению системы линейных алгебраических уравнений. В качестве альтернативы обычным алгебраическим методам решения системы можно получать решение, рассматривая свойства определенных ориентированных графов, связанных с системой. [...] Неизвестные уравнения соответствуют узлам графа, в то время как линейные отношения между ними проявляются в виде ориентированных ребер, соединяющих узлы. [...] Связанные ориентированные графы во многих случаях могут быть составлены непосредственно путем осмотра физической системы без необходимости сначала формулировать соответствующие уравнения».

ЛитератураПравить

• Карелин В. П., Курейчик В. М. Основные понятия теории линейных переходных графов // Ориентированные графы и конечные автоматы / А. Н. Мелихов. — М.: Наука, 1971. — С. 196—211. — 416 с. — (Теоретические основы технической кибернетики). (с. 196—211 написаны Карелиным В. П. и Курейчиком В. М. по просьбе автора книги Мелихова А. Н., см. с. 196 книги)