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

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

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

История

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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) рисунка.

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

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

${\displaystyle {\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}}}$

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

Выбор переменных

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

Неединственность

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

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

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

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

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

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

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

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

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

Примечания

1. CE Shannon. The theory and design of linear differential equation machines (англ.) : journal. — Fire Control of the US National Defense Research Committee: Report 411, Section D-2, 1942. — January. Reprinted in Claude E. Shannon: Collected Papers / N. J. A. Sloane; Aaron D. Wyner. — Wiley IEEE Press, 1993. — С. 514. — ISBN 978-0-7803-0434-5.
2. S. J. Mason. Feedback Theory-Some Properties of Signal Flow Graphs // Proceedings of the IRE. — 1953-09. — Т. 41, вып. 9. — С. 1144–1156. — ISSN 2162-6634. — doi:10.1109/JRPROC.1953.274449. Архивировано 29 октября 2020 года.
3. S. J. Mason. Feedback Theory-Further Properties of Signal Flow Graphs // Proceedings of the IRE. — 1956-07. — Т. 44, вып. 7. — С. 920–926. — ISSN 2162-6634. — doi:10.1109/JRPROC.1956.275147. Архивировано 17 февраля 2022 года.
4. Chen, Wai-Kai, 1936-. Applied graph theory : graphs and electrical networks. — 2d rev. ed. — Amsterdam: North-Holland Pub. Co., 1976. — 1 online resource (xvi, 542 pages) с. — ISBN 978-0-7204-2371-6, 0-7204-2371-6, 978-1-4831-6415-1, 1-4831-6415-2.
5. Lorens, Charles Stanton, Vogel, Dan. Technical Report 317 - Theory and applications of flow graphs // Research Laboratory of Electronics, MIT. Архивировано 6 марта 2021 года.
6. Horace M. Trent. Isomorphisms between Oriented Linear Graphs and Lumped Physical Systems (англ.) // Acoustical Society of America Journal. — 1955. — Vol. 27, iss. 3. — P. 500. — ISSN 0001-4966. — doi:10.1121/1.1907949. Архивировано 24 октября 2019 года.
7. Louis PA Robichaud, Maurice Boisvert, Jean Robert. Signal Flow Graphs and Applications. — 1962.
8. Narsingh Deo. Graph Theory with Applications to Engineering and Computer Science. — 2004. — ISBN 9788120301450.
9. J. Choma. Signal flow analysis of feedback networks // IEEE Transactions on Circuits and Systems. — 1990-04. — Т. 37, вып. 4. — С. 455–463. — ISSN 1558-1276. — doi:10.1109/31.52748. Архивировано 30 октября 2020 года.
10. Wai-Kai Chen. Applied graph theory. — 1971. — ISBN 978-0444101051. Архивировано 27 октября 2020 года.

Литература

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