Signal-flow graph: Difference between revisions

Revision as of 20:34, 17 November 2019

Latest revision as of 23:37, 25 July 2025

(35 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|Flow graph invented by Claude Shannon}}

{{Redirect|Mason graph|other flow graphs|Flow graph (mathematics)}}

[[File:Spectrum trigger function.png|A modern flow graph based teal time spectrum analyzer software]]

A '''signal-flow graph''' or '''signal-flowgraph''' ('''SFG'''), invented by [[Claude Shannon]],<ref name =Shannon/> but often called a '''Mason graph''' after [[Samuel Jefferson Mason]] who coined the term,<ref name=Mason/> is a specialized [[Flow graph (mathematics)|flow graph]], a [[directed graph]] in which nodes represent system variables, and branches (edges, arcs, or arrows) represent functional connections between pairs of nodes. Thus, signal-flow graph theory builds on that of [[directed graph]]s (also called [[Digraph (mathematics)|digraph]]s), which includes as well that of [[Orientation (graph theory)#Oriented graphs|oriented graph]]s. This mathematical theory of digraphs exists, of course, quite apart from its applications.<ref name=Gutin>

{{cite book |title=Digraphs |url=https://books.google.com/books?id=5GdXCWhE4-MC&printsec=frontcover |author1=Jørgen Bang-Jensen |author2=Gregory Z. Gutin |year=2008 |publisher=Springer |isbn=9781848009981}}

</ref><ref name=Bollobas>

{{cite book |title=Modern graph theory |url=https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA8 |page=8 |author=Bela Bollobas |publisher=Springer Science & Business Media |year=1998 |isbn= 9781461206194}}i

Line 11 ⟶ 12:

== History ==

Wai-Kai Chen wrote: "The concept of a signal-flow graph was originally worked out by [[Claude Shannon|Shannon]] [1942]<ref name=Shannon>

{{cite journalreport |author =CE Shannon |title=The theory and design of linear differential equation machines |date=January 1942 |publisher=Fire Control of the US National Defense Research Committee: Report 411, Section D-2}} Reprinted in {{cite book |title=Claude E. Shannon: Collected Papers |editor1=N. J. A. Sloane |editor2=Aaron D. Wyner |publisher=Wiley IEEE Press |year=1993 |page=514 |isbn=978-0-7803-0434-5 |url=https://books.google.com/books?id=wbLuAAAAMAAJ&dq=isbn%3A9780780304345&q=Theory+and+Design+of+Linear+Differential+Equation+Machines.}}

</ref>

in dealing with analog computers. The greatest credit for the formulation of signal-flow graphs is normally extended to [[Samuel Jefferson Mason|Mason]] [1953],<ref name=Mason>

{{cite journal|last=Mason|first=Samuel J. |date=September 1953|title=Feedback Theory - Some Properties of Signal Flow Graphs |journal=Proceedings of the IRE |date=September 1953 |pages=1144–1156 |doi=10.1109/jrproc.1953.274449 |url=http://ecee.colorado.edu/~ecen5014/Mason-IRE-1953.pdf |quote=The flow graph may be interpreted as a signal transmission system in which each node is a tiny repeater station. The station receives signals via the incoming branches, combines the information in some manner, and then transmits the results along each outgoing branch. |volume=41|issue=9 |s2cid=17565263 }}

</ref> [1956].<ref name=Mason2>

{{cite journal |title=Feedback Theory-Further Properties of Signal Flow Graphs |author=SJ Mason |doi=10.1109/JRPROC.1956.275147 |date=July 1956 |volume=44 |issue=7 |journal=Proceedings of the IRE |pages=920–926 |hdl=1721.1/4778 |s2cid=18184015 |hdl-access=free }} On-line version found at [http://dspace.mit.edu/bitstream/handle/1721.1/4778/RLE-TR-303-15342712.pdf?sequence=1 MIT Research Laboratory of Electronics].

</ref> He showed how to use the signal-flow graph technique to solve some difficult electronic problems in a relatively simple manner. The term '''signal flow graph''' was used because of its original application to electronic problems and the association with electronic signals and flowcharts of the systems under study."<ref>{{cite book|last=Chen|first=Wai-Kai|date=1976|title= Applied Graph Theory : Graphs and Electrical Networks |publisher=[[Elsevier]]|url=https://books.google.com/books?id=wYqjBQAAQBAJ&pg=PA167 |isbn=9781483164151}}{{Harv|WKCWai-Kai Chen|1976|p=167}}</ref>

Lorens wrote: "Previous to [[Samuel Jefferson Mason|Mason]]'s work, [[Claude Shannon|C. E. Shannon]]<ref name="Shannon"/> worked out a number of the properties of what are now known as flow graphs. Unfortunately, the paper originally had a restricted classification and very few people had access to the material."<ref>

Line 31 ⟶ 32:

}}</ref>

"The rules for the evaluation of the graph determinant of a Mason Graph were first given and proven by Shannon [1942] using mathematical induction. His work remained essentially unknown even after Mason published his classical work in 1953. Three years later, Mason [1956] rediscovered the rules and proved them by considering the value of a determinant and how it changes as variables are added to the graph. [...]"<ref>{{Harv|WKCWai-Kai Chen|1976|p=169}}</ref>

== Domain of application ==

Robichaud ''et al.'' identify the ___domain of application of SFGs as follows:<ref name=Robichaud>

{{cite book |title=Signal flow graphs and applications |author1=Louis PA Robichaud |author2=Maurice Boisvert |author3=Jean Robert |year=1962 |publisher=Prentice Hall |chapter-url=http://babel.hathitrust.org/cgi/pt?id=uc1.b4338380;view=1up;seq=8 |asin=B0000CLM1G |chapter = Preface |series=Prentice-Hall electrical engineering series |page=x}}

</ref>

:"All the physical systems analogous to these networks [constructed of ideal transformers, active elements and gyrators] constitute the ___domain of application of the techniques developed [here]. Trent<ref name=Trent>

Line 61 ⟶ 62:

:<math>x_3=f_{31}(x_1)+f_{32}(x_2)+f_{33}(x_3) \ ,</math>

and now the functions ''f_ij'' can be associated with the signal-flow branches ''ij'' joining the pair of nodes ''x_i, x_j'', rather than having general relationships associated with each node. A contribution by a node to itself like ''f₃₃'' for ''x₃'' is called a ''self-loop''. Frequently these functions are simply multiplicative factors (often called ''transmittances'' or ''gains''), for example, ''f_ij(x_j)=c_ijx_j'', where ''c'' is a scalar, but possibly a function of some parameter like the Laplace transform variable ''s''. Signal-flow graphs are very often used with Laplace-transformed signals, andbecause inthen they represent systems of [[Linear differential equation]]s. In this case the transmittance, ''c(s)'', often is called a [[transfer function]].

=== Choosing the variables ===

{{quoteblockquote|In general, there are several ways of choosing the variables in a complex system. Corresponding to each choice, a [[system of equations]] can be written and each system of equations can be represented in a graph. This formulation of the equations becomes direct and automatic if one has at his disposal techniques which permit the drawing of a graph directly from the [[schematic diagram]] of the system under study. The structure of the graphs thus obtained is related in a simple manner to the [[topology]] of the [[schematic diagram]], and it becomes unnecessary to consider the [[equations]], even implicitly, to obtain the graph. In some cases, one has simply to imagine the flow graph in the schematic diagram and the desired answers can be obtained without even drawing the flow graph.|Robichaud<ref>{{harv|Robichaud|Boisvert|Robert|1962|p=ix}}</ref>}}

=== Non-uniqueness ===

Robichaud et al. wrote: "The signal flow graph contains the same information as the equations from which it is derived; but there does not exist a one-to-one correspondence between the graph and the system of equations. One system will give different graphs according to the order in which the equations are used to define the variable written on the left-hand side."<ref name=Robichaud /> If all equations relate all dependent variables, then there are ''n!'' possible SFGs to choose from.<ref name=Deo2>{{cite book |title=Graph Theory with Applications to Engineering and Computer Science |author=Narsingh Deo |url=https://books.google.com/books?id=Yr2pJA950iAC&pg=PA418&dqq=%22set+of+n+equations+we+can+obtain%22#v=onepage&qpg=%22set%20of%20n%20equations%20we%20can%20obtain%22&f=falsePA418 |page=418 |isbn=9788120301450 |year=2004 |publisher=PHI Learning Pvt. Ltd}}</ref>

== Linear signal-flow graphs ==

Linear signal-flow graph (SFG) methods only apply to [[linear time-invariant system]]s, as studied by [[LTI system theory|their associated theory]]. When modeling a system of interest, the first step is often to determine the equations representing the system's operation without assigning causes and effects (this is called acausal modeling).<ref>{{Citation

|lastlast1 = Kofránek

|firstfirst1 = J

|last2 = Mateják

|first2 = M

Line 86 ⟶ 87:

|url = http://www2.humusoft.cz/kofranek/058_Kofranek.pdf

|url-status = dead

|archiveurlarchive-url = https://web.archive.org/web/20091229065507/http://www2.humusoft.cz/kofranek/058_Kofranek.pdf

|archivedatearchive-date = 2009-12-29

}}</ref> A SFG is then derived from this system of equations.

Line 95 ⟶ 96:

For linear active networks, Choma writes:<ref name=Choma>

{{cite journal |title=Signal flow analysis of feedback networks |author=J Choma, Jr |journal= IEEE Transactions on Circuits and Systems |volume=37 |issue=4 |date=April 1990 |pages=455–463 |url=http://wenku.baidu.com/view/e046d9d528ea81c758f578c7.html |doi=10.1109/31.52748|bibcode=1990ITCS...37..455C }}

</ref> "By a 'signal flow representation' [or 'graph', as it is commonly referred to] we mean a diagram that, by displaying the algebraic relationships among relevant branch variables of network, paints an unambiguous picture of the way an applied input signal ‘flows’ from input-to-output ... ports."

Line 114 ⟶ 115:

::where <math>t_{jk}</math> = transmittance (or gain) from <math>x_k</math> to <math>x_j</math>.

The figure to the right depicts various elements and constructs of a signal flow graph (SFG).<ref name="Kuo, 2nd ed, p 59">{{cite book|last=Kuo|first= Benjamin C. |year= 1967 |title=Automatic Control Systems |edition=2nd |publisher= Prentice-Hall |isbn= |doi= |pppages=59–60}}</ref>

:Exhibit (a) is a node. In this case, the node is labeled <math>x</math>. A node is a vertex representing a variable or signal.

Line 147 ⟶ 148:

** '''Residual node.''' In any contemplated process of graph reduction, the nodes to be retained in the new graph are called residual nodes.<ref name=Mason/>

* '''Splitting a node.''' Splitting a node corresponds to splitting a node into two half nodes, one being a sink and the other a source.<ref name=Robichaud2>

{{cite book |title=Signal flow graphs and applications |author1=Louis PA Robichaud |author2=Maurice Boisvert |author3=Jean Robert |year=1962 |publisher=Prentice Hall |chapter-url=http://babel.hathitrust.org/cgi/pt?id=uc1.b4338380;view=1up;seq=8 |asin=B0000CLM1G |chapter = §1-4: Definitions and terminology |series=Prentice-Hall electrical engineering series |page=8}}

</ref>

* '''Index''': The index of a graph is the minimum number of nodes which have to be split in order to remove all the loops in a graph.

Line 160 ⟶ 161:

The purpose of this reduction is to relate the dependent variables of interest (residual nodes, sinks) to its independent variables (sources).

The systematic reduction of a linear signal-flow graph is a graphical method equivalent to the [[Gaussian elimination|Gauss-Jordan elimination]] method for solving linear equations.<ref name="Henley 1973 12">{{harv|Henley|Williams|1973|p=12}}</ref>

The rules presented below may be applied over and over until the signal flow graph is reduced to its "minimal residual form". Further reduction can require loop elimination or the use of a "reduction formula" with the goal to directly connect sink nodes representing the dependent variables to the source nodes representing the independent variables. By these means, any signal-flow graph can be simplified by successively removing internal nodes until only the input and output and index nodes remain.<ref>{{harv|Phang|2001|p=37}}</ref><ref>Examples of the signal-flow graph reduction can be found in {{harv|Robichaud|Boisvert|Robert||1962|p=186, Sec. 7-3 Algebraic reduction of signal flow graphs}}</ref> Robichaud described this process of systematic flow-graph reduction:

{{QuotationBlockquote|The reduction of a graph proceeds by the elimination of certain nodes to obtain a residual graph showing only the variables of interest. This elimination of nodes is called "'''node absorption'''". This method is close to the familiar process of successive eliminations of undesired variables in a system of equations. One can eliminate a variable by removing the corresponding node in the graph. If one reduces the graph sufficiently, it is possible to obtain the solution for any variable and this is the objective which will be kept in mind in this description of the different methods of reduction of the graph. In practice, however, the techniques of reduction will be used solely to transform the graph to a residual graph expressing some fundamental relationships. Complete solutions will be more easily obtained by application of [[Mason's gain formula|Mason's rule]].<ref name="Robichaud 1962 9–10, Sec. 1–5: Reduction of the flow graph">{{harv|Robichaud|Boisvert|Robert||1962|pp=9–10, Sec. 1–5: Reduction of the flow graph}}</ref>

The graph itself programs the reduction process. Indeed a simple inspection of the graph readily suggests the different steps of the reduction which are carried out by elementary transformations, by loop elimination, or by the use of a reduction formula.<ref name="Robichaud 1962 9–10, Sec. 1–5: Reduction of the flow graph"/>|Robichaud|Boisvert|Robert||Signal flow graphs and applications, 1962}}

For digitally reducing a flow graph using an algorithm, Robichaud extends the notion of a simple flow graph to a ''generalized'' flow graph:

{{QuotationBlockquote|Before describing the process of reduction...the correspondence between the graph and a system of linear equations ... must be generalized...''The generalized graphs will represent some operational relationships between groups of variables''...To each branch of the generalized graph is associated a matrix giving the relationships between the variables represented by the nodes at the extremities of that branch...<ref>{{harv|Robichaud|Boisvert|Robert||1962|pp=182, 183 Sec. 7-1, 7-2 of Chapter 7: Algebraic reduction of signal flow graphs using a digital computer}}</ref>

The elementary transformations [defined by Robichaud in his Figure 7.2, p. 184] and the loop reduction permit the elimination of any node ''j'' of the graph by the ''reduction formula'':[described in Robichaud's Equation 7-1]. With the reduction formula, it is always possible to reduce a graph of any order... [After reduction] the final graph will be a cascade graph in which the variables of the sink nodes are explicitly expressed as functions of the sources. This is the only method for reducing the generalized graph since Mason's rule is obviously inapplicable.<ref>{{harv|Robichaud|Boisvert|Robert||1962|p=185, Sec. 7-2: Generalization of flow graphs}}</ref>|Robichaud|Signal flow graphs and applications, 1962}}

The definition of an '''elementary transformation''' varies from author to author:

* Some authors only consider as elementary transformations the summation of parallel-edge gains and the multiplication of series-edge gains, but not the elimination of self-loops<ref name="Henley 1973 12"/><ref>{{harv|Robichaud|Boisvert|Robert||1962|pp=9, Sec. 1–5 REDUCTION OF THE FLOW GRAPH}}</ref>

* Other authors consider the elimination of a self-loop as an elementary transformation<ref>{{Cite book|title = Design of Analog Circuits Through Symbolic Analysis|lastlast1 = Fakhfakh|firstfirst1 = Mourad|publisher = Bentham Science Publishers|year = 2012|isbn = 978-1-60805-425-1|___location = |pages = 418|chapter = Section 4.1.2 Signal flow graphs algebra|last2 = Tlelo-Cuautle|first2 = Esteban|last3 = V. Fernández|first3 = Francisco|editor-last = Fakhfakh}}</ref>

'''Parallel edges. '''Replace parallel edges with a single edge having a gain equal to the sum of original gains.{{brclear}}

[[File:Signal-Flow-Graph-Refactoring 01 parallel.svg|upright|Signal flow graph refactoring rule: replacing parallel edges with a single edge with a gain set to the sum of original gains.]]{{brclear}}

The graph on the left has parallel edges between nodes. On the right, these parallel edges have been replaced with a single edge having a gain equal to the sum of the gains on each original edge.{{brclear}}

The equations corresponding to the reduction between '''N''' and node '''I₁''' are:

:<math>\begin{align}

Line 186 ⟶ 187:

\end{align}</math>

'''Outflowing edges. '''Replace outflowing edges with edges directly flowing from the node's sources.{{brclear}}

[[File:Signal-Flow-Graph-Refactoring 03 outflowing.svg|upright|Signal flow graph refactoring rule: replacing outflowing edges with direct flows from inflowing sources.]]{{brclear}}

The graph on the left has an intermediate node '''N''' between nodes from which it has inflows, and nodes to which it flows out.

The graph on the right shows direct flows between these node sets, without transiting via '''N'''.

For the sake of simplicity, '''N''' and its inflows are not represented. The outflows from '''N''' are eliminated.{{brclear}}

The equations corresponding to the reduction directly relating '''N''''s input signals to its output signals are:

:<math>\begin{align}

Line 207 ⟶ 208:

'''Zero-signal nodes.'''

Eliminate outflowing edges from a node determined to have a value of zero.{{brclear}}

[[File:Signal-Flow-Graph-Refactoring 04 from zero-signal node.svg|upright|Signal flow graph refactoring rule: eliminating outflowing edges from a node known to have a value of zero.]]{{brclear}}

If the value of a node is zero, its outflowing edges can be eliminated.

'''Nodes without outflows.'''

Eliminate a node without outflows.{{brclear}}

[[File:Signal-Flow-Graph-Refactoring 05 don't care.svg|upright|Signal flow graph refactoring rule: a node that is not of interest can be eliminated provided that it has no outgoing edges.]]{{brclear}}

In this case, '''N''' is not a variable of interest, and it has no outgoing edges; therefore, '''N''', and its inflowing edges, can be eliminated.

'''Self-looping edge. '''Replace looping edges by adjusting the gains on the incoming edges.{{brclear}}

[[File:Signal-Flow-Graph-Refactoring 02 self-loop.svg|upright|Signal flow graph refactoring rule: a looping edge at node N is eliminated and inflow gains are multiplied by an adjustment factor.]]{{brclear}}The graph on the left has a looping edge at node '''N''', with a gain of '''g'''. On the right, the looping edge has been eliminated, and all inflowing edges have their gain divided by '''(1-g)'''.{{brclear}}The equations corresponding to the reduction between '''N''' and all its input signals are:

<div style="display: flex; overflow-x: auto;">

:<math>\begin{align}

N &= I_\mathrm{1} f_\mathrm{1} + I_\mathrm{2} f_\mathrm{2} + I_\mathrm{3} f_\mathrm{3} + N g \\

Line 225 ⟶ 228:

N &= I_\mathrm{1} f_\mathrm{1}\div (1-g) + I_\mathrm{2} f_\mathrm{2}\div (1-g) + I_\mathrm{3} f_\mathrm{3} \div (1-g) \\

\end{align}</math>

</div>

==== Implementations ====

The above procedure for building the SFG from an acausal system of equations and for solving the SFG's gains have been implemented<ref>Labrèche P., [https://www.researchgate.net/publication/266391592_1977_Labreche_-_LINEAR_ELECTRICAL_CIRCUITS_SYMBOLIC_NETWORK_ANALYSIS presentation: Linear Electrical Circuits:Symbolic Network Analysis], 1977.</ref> as an add-on to [[MATHLAB 68]],<ref>Carl{{cite Engelman,book '''| chapter-url=http://dl.acm.org/citation.cfm?id=806265 | doi=10.1145/800204.806265 | chapter=The legacy of MATHLAB 68''', published in Proceeding SYMSAC '71| title=Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, pages 29-41 SYMSAC [http://dl.acm.org/citation.cfm?id'71 | date=806265]1971 | last1=Engelman | first1=Carl | pages=29–41 | isbn=978-1-4503-7786-7 }}</ref> an on-line [[Computer algebra system|system providing machine aid for the mechanical symbolic processes encountered in analysis]].

=== Solving linear equations ===

Signal flow graphs can be used to solve sets of simultaneous linear equations.<ref name="Deo page 416">"... solving a set of simultaneous, linear algebraic equations. This problem, usually solved by matrix methods, can also be solved via graph theory. " {{cite book| last=Deo|first= Narsingh | year= 1974|title=Graph Theory with Applications to Engineering and Computer Science |edition= |publisher= Prentice-Hall of India |isbn= 978-81-203-0145-0 | ppage=416}} also on-line at [https://books.google.com/books?id=Yr2pJA950iAC&pg=PA417&dq=%22THe+signal-flow+graph+representing+Eqs.+%2815-2%29%22&hlpg=en&sa=X&ei=z1iwVNXZFs3WoASYj4D4DQ&ved=0CB8Q6AEwAA#v=onepage&q=%22THe%20signal-flow%20graph%20representing%20Eqs.%20(15-2)%22&f=falsePA417]</ref> The set of equations must be consistent and all equations must be linearly independent.

==== Putting the equations in "standard form" ====

Line 264 ⟶ 268:

where the right side of this equation is the sum of the weighted arrows incident on node ''x₁''.

As there is a basic symmetry in the treatment of every node, a simple starting point is an arrangement of nodes with each node at one vertex of a regular polygon. When expressed using the general coefficients {''c_in''}, the environment of each node is then just like all the rest apart from a permutation of indices. Such an implementation for a set of three simultaneous equations is seen in the figure.<ref name="Deo page 417">{{cite book| last=Deo|first= Narsingh | year= 1974|title=Graph Theory with Applications to Engineering and Computer Science |edition= |publisher= Prentice-Hall of India |isbn= 978-81-203-0145-0 | ppage=417}} also on-line at [https://books.google.com/books?id=Yr2pJA950iAC&pg=PA417&dq=%22THe+signal-flow+graph+representing+Eqs.+%2815-2%29%22&hlpg=en&sa=X&ei=z1iwVNXZFs3WoASYj4D4DQ&ved=0CB8Q6AEwAA#v=onepage&q=%22THe%20signal-flow%20graph%20representing%20Eqs.%20(15-2)%22&f=falsePA417]</ref>

Often the known values, y_j are taken as the primary causes and the unknowns values, x_j to be effects, but regardless of this interpretation, the last form for the set of equations can be represented as a signal-flow graph. This point is discussed further in the subsection [[#Interpreting 'causality'|Interpreting 'causality']].

==== Applying Mason's gain formula ====

{{detailsfurther|Mason's gain formula}}

In the most general case, the values for all the x_k variables can be calculated by computing Mason's gain formula for the path from each y_j to each x_k and using superposition.

:<math>\begin{align} x_\mathrm{k} &= \sum_{\mathrm{j}=1}^{\mathrm{M}} ( G_\mathrm{kj} ) y_\mathrm{j} \end{align} </math>

Line 282 ⟶ 286:

For some authors, a linear signal-flow graph is more constrained than a [[block diagram]],<ref name="Kuo, 6th ed, p77">

"A signal flow graph may be regarded as a simplified version of a block diagram. ... for cause and effect ... of linear systems ...we may regard the signal-flow graphs to be constrained by more rigid mathematical rules, whereas the usage of the block-diagram notation is less stringent." {{cite book |last= Kuo |first= Benjamin C. |year= 1991 |title= Automatic Control Systems |edition= 6th |publisher= Prentice-Hall |isbn= 978-0-13-051046-4 |ppage= [https://archive.org/details/automaticcontrol00kuob_0/page/77 77] |url-access= registration |url= https://archive.org/details/automaticcontrol00kuob_0/page/77 }}</ref> in that the SFG rigorously describes linear algebraic equations represented by a directed graph.

For other authors, linear block diagrams and linear signal-flow graphs are equivalent ways of depicting a system, and either can be used to solve the gain.<ref name=Franklin>

{{cite book |title=Feedback Control of Dynamic Systems|author= Gene F. Franklin|chapter= Appendix W.3 Block Diagram Reduction|page= |isbn= |date= Apr 29, 2014 |publisher= Prentice Hall|display-authors=etal}}

</ref>

Line 293 ⟶ 297:

{{cite book |title=Control Systems |author= A Anand Kumar |chapter-url=https://books.google.com/books?id=sJBeBAAAQBAJ&pg=PA165 |page=165 |chapter=Table: Comparison of block diagram and signal flow methods |isbn=9788120349391 |year=2014 |edition=2nd |publisher=PHI Learning Pvt. Ltd}}

</ref> According to Barker ''et al.'':<ref name=Barker>

{{cite book |chapter=Algorithms for transformations between block diagrams and digital flow graphs |author1=HA Barker |author2=M Chen |author3=P. Townsend |chapter-url=https://books.google.com/books?id=I9bSBQAAQBAJ&pg=PA281 |pages=281 ''ff'' |title= Computer Aided Design in Control Systems 1988: Selected Papers from the 4th IFAC Symposium, Beijing, PRC, 23-25, August 1988 |publisher=Elsevier |year=2014|isbn=9781483298795 }}

</ref>

:"The signal flow graph is the most convenient method for representing a dynamic system. The topology of the graph is compact and the rules for manipulating it are easier to program than the corresponding rules that apply to block diagrams."

Line 317 ⟶ 321:

There is no reference to "cause and effect" here, and as said by Barutsky:<ref name=Barutsky>

{{cite book |title=Bond Graph Methodology: Development and Analysis of Multidisciplinary Dynamic System Models |author=Wolfgang Borutzky |url=https://books.google.com/books?id=TUlPJ5M7jIUC&pg=PA10#v=onepage&q&f=false |isbn=9781848828827 |year=2009 |publisher=Springer Science & Business Media |page=10}}

</ref>

:"Like block diagrams, signal flow graphs represent the computational, not the physical structure of a system."

Line 323 ⟶ 327:

The term "cause and effect" may be misinterpreted as it applies to the SFG, and taken incorrectly to suggest a system view of causality,<ref name=Callahan>

{{cite book |title=The Geometry of Spacetime: An Introduction to Special and General Relativity |author=James J. Callahan |chapter-url=https://books.google.com/books?id=UMDurS6HSl4C&pg=PA76&dqq=%22The+causal+past+of+%22+%22The+causal+future+of+an+event+%22&hlpg=en&sa=X&ei=Lx7qVLOHHYufoQS2qoL4Dg&ved=0CB8Q6AEwAA#v=onepage&q=%22The%20causal%20past%20of%20%22%20%22The%20causal%20future%20of%20an%20event%20%22&f=falsePA76 |chapter=Causality: Definition 2.10 |isbn=9780387986418 |year=2000 |publisher= Springer Science & Business Media |page=76}}

</ref> rather than a ''computationally'' based meaning. To keep discussion clear, it may be advisable to use the term "computational causality", as is suggested for [[bond graphs]]:<ref name=Vichnevetsky>

{{cite book |title=IMACS '91, Proceedings of the 13th IMACS World Congress on Computation and Applied Mathematics: July 22-26, 1991, Trinity College, Dublin, Ireland |author1=John JH Miller |author2=Robert Vichnevetsky |editor1=John JH Miller |editor2=Robert Vichnevetsky |date=July 22–26, 1991 |publisher=International Association for Mathematics and Computers in Simulation |url=https://www.google.com/search?tbo=p&q=%22Bond-graph+literature+uses+the+term+computational+causality,+indicating+the+order+of+calculation+in+a+simulation,+in+order+to+avoid+any+interpretation+in+the+sense+of+intuitive+causality.+%22&num=10&gws_rd=ssl}}

</ref>

:"Bond-graph literature uses the term computational causality, indicating the order of calculation in a simulation, in order to avoid any interpretation in the sense of intuitive causality."

The term "computational causality" is explained using the example of current and voltage in a resistor:<ref name=Cellier>

{{cite book |title= Continuous System Simulation |author1=François E. Cellier |author2=Ernesto Kofman |url=https://www.google.com/search?tbo=p&q=%22physical+laws+can+therefor+not+be+predetermined%22&num=10&gws_rd=ssl#tbm=bks&q=%22physical+laws+can+therefore+not+be+predetermined%22 |year=2006 |page=15 |isbn=9780387261027 |publisher=Springer Science & Business Media}}

</ref>

:"The ''computational causality'' of physical laws can therefore not be predetermined, but depends upon the particular use of that law. We cannot conclude whether it is the current flowing through a resistor that causes a voltage drop, or whether it is the difference in potentials at the two ends of the resistor that cause current to flow. Physically these are simply two concurrent aspects of one and the same physical phenomenon. Computationally, we may have to assume at times one position, and at other times the other."

Line 337 ⟶ 341:

A computer program or algorithm can be arranged to solve a set of equations using various strategies. They differ in how they prioritize finding some of the variables in terms of the others, and these algorithmic decisions, which are simply about solution strategy, then set up the variables expressed as dependent variables earlier in the solution to be "effects", determined by the remaining variables that now are "causes", in the sense of "computational causality".

Using this terminology, it is ''computational'' causality, not ''system'' causality, that is relevant to the SFG. There exists a wide-ranging philosophical debate, not concerned specifically with the SFG, over connections between computational causality and system causality.<ref name= Lewandowsky>See, for example, {{cite book |title=Computational Modeling in Cognition: Principles and Practice |author1=Stephan Lewandowsky |author2=Simon Farrell |url=https://books.google.com/books?id=Jva6smQTUW4C&printsec=frontcover |isbn=9781452236193 |year=2010 |publisher=SAGE Publications}}

</ref>

Line 345 ⟶ 349:

=== Signal-flow graphs for dynamic systems analysis ===

When building a model of a dynamic system, a list of steps is provided by Dorf & Bishop:<ref>{{cite book|title = Modern Control Systems|lastlast1 = Dorf|firstfirst1 = Richard C.|publisher = Prentice Hall|year = 2001|isbn = 978-0-13-030660-9|___location = |chapter = Chap 2.-1: Introduction |page=2 |last2 = Bishop|first2 = Robert H.|chapter-url = https://www.site.uottawa.ca/~rhabash/ELG4152LN02.pdf}}</ref>

* Define the system and its components.

* Formulate the mathematical model and list the needed assumptions.

Line 356 ⟶ 360:

=== Signal-flow graphs for design synthesis ===

Signal-flow graphs have been used in [[Design Space Exploration|Design Space Exploration (DSE)]], as an intermediate representation towards a physical implementation. The DSE process seeks a suitable solution among different alternatives. In contrast with the typical analysis workflow, where a system of interest is first modeled with the physical equations of its components, the specification for synthesizing a design could be a desired transfer function. For example, different strategies would create different signal-flow graphs, from which implementations are derived.<ref>{{Cite journal|title = ARCHGEN: Automated synthesis of analog systems|lastlast1 = Antao|firstfirst1 = B. A. A.|date = June 1995|journal = IEEE Transactions on Very Large Scale Integration (VLSI) Systems |doi = 10.1109/92.386223|pmid = |volume = 3|issue = 2|pages = 231–244|last2 = Brodersen|first2 = A.J.}}</ref>

Another example uses an annotated SFG as an expression of the continuous-time behavior, as input to an architecture generator<ref>{{Cite book|chapter = A heuristic technique for system-level architecture generation from signal-flow graph representations of analog systems|lastlast1 = Doboli|firstfirst1 = A.|date = May 2000|doi = 10.1109/ISCAS.2000.856026|pmid = |access-date = |series = Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on|last2 = Dhanwada|first2 = N.|last3 = Vemuri|first3 = R. |title title= 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No.00CH36353) | chapter=A heuristic technique for system-level architecture generation from signal-flow graph representations of analog systems |volume = 3|pages = 181–184|isbn = 978-0-7803-5482-1|citeseerx = 10.1.1.59.304|s2cid = 13948702}}</ref>

== Shannon and Shannon-Happ formulas ==

Shannon's formula is an analytic expression for calculating the gain of an interconnected set of amplifiers in an analog computer. During World War II, while investigating the functional operation of an analog computer, Claude Shannon developed his formula. Because of wartime restrictions, Shannon's work was not published at that time, and, in 1952, [[Samuel Jefferson Mason|Mason]] rediscovered the same formula.

[[William W. Happ]] generalized the Shannon formula for topologically closed systems.<ref name=Happ66>{{Cite journal|title = Flowgraph Techniques for Closed Systems|last = Happ|first = William W.|date = 1966|journal = IEEE Transactions on Aerospace and Electronic Systems|doi = 10.1109/TAES.1966.4501761|pmid = |pages = 252–264|volume=AES-2|issue = 3|bibcode = 1966ITAES...2..252H|s2cid = 51651723}}</ref> The Shannon-Happ formula can be used for deriving transfer functions, sensitivities, and error functions.<ref name=Potash />

For a consistent set of linear unilateral relations, the Shannon-Happ formula expresses the solution using direct substitution (non-iterative).<ref name=Potash>{{cite journalbook |titlelast1 =ApplicationPotash|first1 of= unilateralHanan|first2 and= graphLawrence techniquesP.|last2 to= analysisMcNamee| title=Proceedings of linearthe circuits:1968 Solution23rd byACM non-iterativenational methods|lastconference =Potash|first chapter=Application Hanan|first2of =unilateral Lawrenceand P.|last2graph =techniques to analysis of linear circuits McNamee|year =1968 |journal=Proceedings, ACM National Conference|pages=367–378 |chapter-url =https://www.deepdyve.com/lp/association-for-computing-machinery/application-of-unilateral-and-graph-techniques-to-analysis-of-linear-b8r753Bq03 |doi=10.1145/800186.810601|s2cid =16623657|doi-access =free}}</ref><ref name=NASAP-70>{{Cite book|title = NASAP-70 User's and Programmer's manual|lastlast1 = Okrent|firstfirst1 = Howard|publisher = School of Engineering and Applied Science, University of California at Los Angeles|year = 1970|isbn = |___location = Los Angeles, California|pages = 3–9|first2 = Lawrence P.|last2 = McNamee|chapter-url = https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19710025849.pdf|chapter = 3. 3 Flowgraph Theory}}</ref>

NASA's electrical circuit software NASAP is based on the Shannon-Happ formula.<ref name=Potash /><ref name=NASAP-70 />

Line 382 ⟶ 386:

[[File:Control parameter.PNG|thumb|upright=1.0|Figure 4: A different signal-flow graph for the [[asymptotic gain model]] ]]

[[File:Signal flow graph for feedback amplifier.png|thumb|upright=1.0 |A signal flow graph for a nonideal [[negative feedback amplifier]] based upon a control variable ''P'' relating two internal variables: ''x_j=Px_i''. Patterned after D.Amico ''et al.''<ref name=Damico>

{{cite journal |title=Resistance of Feedback Amplifiers: A novel representation |author=Arnaldo D’Amico, Christian Falconi, Gianluca Giustolisi, Gaetano Palumbo |journal= IEEE Transactions on Circuits and Systems – II: Express Briefs |url=http://piezonanodevices.uniroma2.it/wp-content/uploads/2013/04/Rosenstark.pdf |date=April 2007 |volume=54 |issue=4 |pages=298–302 |doi=10.1109/tcsii.2006.889713|bibcode=2007ITCSE..54..298D |citeseerx=10.1.1.694.8450 |s2cid=10154732 }}

</ref>]]

A possible SFG for the [[asymptotic gain model]] for a [[negative feedback amplifier]] is shown in Figure 3, and leads to the equation for the gain of this amplifier as

Line 439 ⟶ 443:

== Terminology and classification of signal-flow graphs ==

There is some confusion in literature about what a signal-flow graph is; [[Henry Paynter]], inventor of [[bond graphs]], writes: "But much of the decline of signal-flow graphs [...] is due in part to the mistaken notion that the branches must be linear and the nodes must be summative. Neither assumption was embraced by Mason, himself !"<ref name=Paynter>{{cite journalweb|last=Paynter|first=Henry |date=1992|title=An Epistemic Prehistory of Bond Graphs|journal=|pages=10, 15 pages |url=https://www.me.utexas.edu/~longoria/paynter/hmp/BGprehistory.pdf |quote=}}</ref>

=== Standards covering signal-flow graphs ===

Line 447 ⟶ 451:

=== State transition signal-flow graph ===

[[File:State transition SFG.svg|thumb|upright=1|State transition signal-flow graph. Each initial condition is considered as a source (shown in blue).]]

A '''state transition SFG''' or '''state diagram''' is a simulation diagram for a system of equations, including the initial conditions of the states.<ref>{{Cite book|title = Linear Control System Analysis and Design with MATLAB®, Sixth Edition|lastlast1 = Houpis|firstfirst1 = Constantine H.|publisher = CRC press|year = 2013|isbn = 9781466504264|___location = Boca Raton, FL|pages = 171–172|last2 = Sheldon|first2 = Stuart N.|chapter = section 8.8}}</ref>

=== Closed flowgraph ===

Line 472 ⟶ 476:

=== Examples of nonlinear signal-flow graph models ===

* Although they generally can't be transformed between time ___domain and frequency ___domain representations for classical control theory analysis, nonlinear signal-flow graphs can be found in electrical engineering literature.<ref>For example: {{Citation

| firstfirst1 =Thomas A.

| lastlast1 =Baran

| author-link =

| first2 =Alan V.

| last2 =Oppenhiem

| id = | title =2011 Digital Signal Processing and Signal Processing Education Meeting (DSP/SPE)

| author2-link =

| chapter= INVERSION=Inversion OFof NONLINEARnonlinear ANDand TIMEtime-VARYINGvarying SYSTEMSsystems

| contribution-url =

| series =Digital Signal Processing Workshop and IEEE Signal Processing Education Workshop (DSP/SPE)

| year = 2011

| pages =283–288

| place =

| publisher =IEEE

| doi =10.1109/DSP-SPE.2011.5739226

| id = | title =2011 Digital Signal Processing and Signal Processing Education Meeting (DSP/SPE)

| isbn =978-1-61284-226-4

| citeseerx =10.1.1.695.7460

| s2cid =5758954

}}</ref><ref name=Guilherme/>

* Nonlinear signal-flow graphs can also be found in life sciences, for example, Dr [[Arthur Guyton]]'s model of the cardiovascular system.<ref>{{Cite journal|last=Hall|first=John E.|date=2004-11-01|title=The pioneering use of systems analysis to study cardiac output regulation|journal=American Journal of Physiology. Regulatory, Integrative and Comparative Physiology|volume=287|issue=5|pages=R1009–R1011|doi=10.1152/classicessays.00007.2004|pmid=15475497|issn=0363-6119|quote=Figure 2, Arthur Guyton's computer model of the cardiovascular system, [https://www.physiology.org/na101/home/literatum/publisher/physio/journals/content/ajpregu/2004/ajpregu.2004.287.issue-5/classicessays.00007.2004/production/images/large/zh60110424520002.jpeg download jpeg]}}</ref>

Line 494:

== Applications of SFG techniques in various fields of science ==

* [[Electronic circuits]]

** Characterizing sequential circuits of the [[Moore state machine|Moore]] and [[Mealy state machine|Mealy]] type, obtaining [[Regular Expressions|regular expressions]] from [[state diagram]]s.<ref>{{Cite book|title = Signal Flow Graph Techniques for Sequential Circuit State Diagrams|lastlast1 = BRZOZOWSKI|firstfirst1 = J.A.|publisher = IEEE|year = 1963|isbn = |___location = |pages = 97|last2 = McCLUSKEY|first2 = E. J.|series = IEEE Transactions on Electronic Computers}}</ref>

** Synthesis of non-linear data converters<ref name=Guilherme>{{Cite book|title = SYMBOLIC SYNTHESIS OF NON-LINEAR DATA CONVERTERS|lastlast1 = Guilherme|firstfirst1 = J.|year = 1999|isbn = |___location = |pages = |url = http://orion.ipt.pt/~jorge/Docs/Artigos/icecs.pdf|last2 = Horta|first2 = N. C.|last3 = Franca|first3 = J. E.}}</ref>

** Control and network theory

** Stochastic signal processing.<ref name=Barry>

Line 507:

|edition=Third

|isbn=978-0-7923-7548-7

|url=https://books.google.com/books?id=hPx70ozDJlwC&pg=PA86&dqq=signal+flow+graph#PPA86,M1&pg=PA86}}

</ref>

** Reliability of electronic systems<ref>{{Cite journalbook |urllast = Happ|titlefirst = ApplicationWilliam ofW.| flowgraphtitle=Second techniquesAnnual toSymposium on the solutionPhysics of reliabilityFailure problems|lastin =Electronics Happ|first chapter=Application Williamof Flowgraph Techniques to the Solution of Reliability Problems W.|date = 1964|doi = 10.1109/IRPS.1963.362257|pmid = |access-date = |journal = Physics of Failure in Electronics|editor-last = Goldberg|editor-first = M. F.|issue = AD434/329|pages = 375–423}}</ref>

* [[Physiology]] and [[biophysics]]

** Cardiac output regulation<ref>{{Cite journal|title = The pioneering use of systems analysis to study cardiac output regulation|last = Hall|first = John E.|date = August 23, 2004|journal = Am J Physiol Regul Integr Comp Physiol|doi = 10.1152/classicessays.00007.2004|pmid = 15475497|volume=287|issue = 5|pages=R1009–R1011}}</ref>

* [[Simulation]]

** Simulation on analog computers<ref>{{harv|Robichaud|Boisvert|Robert||1962|loc=chapter 5 Direct Simulation on Analog Computers Through Signal Flow Graphs}}</ref>

*[[Neuroscience]] and [[Combinatorics]]

** Study of Polychrony<ref>{{Cite journal | title = Polychronization: computation with spikes|last = Izhikevich |first = Eugene M |journal = Neural Computation | date = Feb 2006|doi= 10.1162/089976606775093882 | pmid = 16378515 | volume = 18 | issue = 2 |pages = 245–282 |s2cid = 14253998 }}</ref><ref>{{Cite journal | title = Polychrony as Chinampas

|author = Dolores-Cuenca, E.& Arciniega-Nevárez, J.A.& Nguyen, A.& Zou, A.Y.& Van Popering, L.& Crock, N.& Erlebacher, G.& Mendoza-Cortes, J.L.

|journal = Algorithms

| date = April 2023|doi= 10.3390/a16040193 | volume = 16|issue = 4 |page = 193

|doi-access = free

|arxiv = 2103.15265}}</ref>

==See also==

Line 531 ⟶ 538:

==References==

* {{cite book |ref=harv|author1first1=Ernest J. |last1=Henley |author2first2=R. A. |last2=Williams |lastauthorampname-list-style=yesamp |title=Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis|year=1973|publisher=Academic Press|isbn=978-0-08-095607-7}} Book almost entirely devoted to this topic.

*{{Citation |last=Kou|first= Benjamin C. |year= 1967 |title= Automatic Control Systems|publisher= Prentice Hall |isbn= |doi=}}

*{{cite book|ref=harv|last=RobichaudOgata|first=LouisKatsuhiko P.A. |author2= Maurice Boisvert|author3= Jean Robert|year= 1962 2002|title=Signal flowModern graphsControl andEngineering applications |pages=xiv, 214 p4th Edition|publisher= Prentice-Hal Hall|___locationchapter=EnglewoodSection Cliffs,3-9 N.J.Signal Flow Graphs|isbn= |doi=|url=http://babel.hathitrust.org/cgi/pt?id=uc1.b4338380978-0-13-043245-2}}

* {{Cite thesis |last= Phang |first= Khoman |title= CMOS Optical Preamplifier Design Using Graphical Circuit Analysis|type= |chapter= ''2.5 An overview of Signal-flow graphs'' |chapter-url= http://www.eecg.toronto.edu/~kphang/papers/PhDthesis.pdf|date= 2000-12-14 |year= 2001 |publisher= Department of Electrical and Computer Engineering, University of Toronto|access-date= |docket= |oclc= }} © Copyright by Khoman Phang 2001

*{{Citation |last=Deo|first=Narsingh |year= 1974|title= Graph Theory with Applications to Engineering and Computer Science|pages= 418|publisher= PHI Learning Pvt. Ltd.|___location=|isbn= 978-81-203-0145-0|doi=|url=https://books.google.com/?id=Yr2pJA950iAC&printsec=frontcover#v=onepage&q&f=false}}

*{{cite book|last1=Robichaud |first1=Louis P.A. |first2= Maurice |last2=Boisvert |first3=Jean |last3=Robert |year= 1962 |title=Signal flow graphs and applications |series=Prentice-Hall electrical engineering series |pages=xiv, 214 p |publisher= Prentice Hall|___location=Englewood Cliffs, N.J.|url=http://babel.hathitrust.org/cgi/pt?id=uc1.b4338380}}

*{{cite book |title=Graphs: Theory and algorithms |author1=K Thulasiramen |author2=MNS Swarmy |chapter=§6.11 The Coates and Mason graphs |pages=163 ''ff'' |chapter-url=https://books.google.com/books?id=rFH7eQffQNkC&pg=PA163 |publisher=John Wiley & Sons |year=2011 |isbn=9781118030257}}

* {{cite book|author=Wai-Kai Chen|title=Applied Graph Theory|publisher=North Holland Publishing Company|year=1976|isbn=978-0720423624}} Chapter 3 for the essentials, but applications are scattered throughout the book.

*{{cite book|ref=harv|last=Ogata|first=Katsuhiko |year= 2002|title= Modern Control Engineering 4th Edition|publisher= Prentice-Hal |chapter=Section 3-9 Signal Flow Graphs|isbn=978-0-13-043245-2|doi=}}

* {{Cite thesis |last= Phang |first= Khoman |title= CMOS Optical Preamplifier Design Using Graphical Circuit Analysis|type= |chapter= ''2.5 An overview of Signal-flow graphs'' |chapter-url= http://www.eecg.toronto.edu/~kphang/papers/PhDthesis.pdf|date= 2000-12-14 |year= 2001 |publisher= Department of Electrical and Computer Engineering, University of Toronto|access-date= |docket= |oclc= }} © Copyright by Khoman Phang 2001

==Further reading==

*{{Citation |last=Deo|first=Narsingh |year= 1974|title= Graph Theory with Applications to Engineering and Computer Science|pages= 418|publisher= PHI Learning Pvt. Ltd.|___location=|isbn= 978-81-203-0145-0|doi=|url=https://books.google.com/books?id=Yr2pJA950iAC&printsec=frontcover#v=onepage&q&f=false}}

* {{cite book|author=Wai-Kai Chen|title=Applied Graph Theory|publisher=North Holland Publishing Company|year=1976|isbn=978-0720423624}} Chapter 3 for the essentials, but applications are scattered throughout the book.

*{{cite book |title=Graphs: Theory and algorithms |author1=K Thulasiramen |author2=MNS Swarmy |chapter=§6.11 The Coates and Mason graphs |pages=163 ''ff'' |chapter-url=https://books.google.com/books?id=rFH7eQffQNkC&pg=PA163 |publisher=John Wiley & Sons |year=2011 |isbn=9781118030257}}

* {{cite web |author=Wai-Kai Chen |title=Some applications of linear graphs |url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0601623 |archive-url=https://web.archive.org/web/20150110010404/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0601623 |url-status=dead |archive-date=January 10, 2015 |publisher=Coordinated Science Laboratory, University of Illinois, Urbana |date=May 1964 |work=Contract DA-28-043-AMC-00073 (E)}}

* {{cite book|author1=K. Thulasiraman |author2=M. N. S. Swamy |lastauthorampname-list-style=yesamp |title= Graphs: Theory and Algorithms|year=1992|publisher=John Wiley & Sons |isbn=978-0-471-51356-8|at=6.10-6.11 for the essential mathematical idea}}

* {{cite book|editor=Richard C. Dorf|title=Circuits, Signals, and Speech and Image Processing|year=2006|publisher=CRC Press|isbn=978-1-4200-0308-6|author=Shu-Park Chan|chapter=Graph theory|at=§ 3.6|edition=3rd}} Compares Mason and Coates graph approaches with Maxwell's k-tree approach.

* {{cite book |author=RF Hoskins |chapter=Flow-graph and signal flow-graph analysis of linear systems |chapter-url=https://books.google.com/books?id=6DeoBQAAQBAJ&pg=PA156 |editor=SR Deards |title=Recent Developments in Network Theory: Proceedings of the Symposium Held at the College of Aeronautics, Cranfield, September 1961 |year=2014 |publisher=Elsevier |isbn=9781483223568}} A comparison of the utility of the [[Coates graph|Coates flow graph]] and the Mason flow graph.

Line 551 ⟶ 558:

* [https://web.archive.org/web/20040325002849/http://www.apl.jhu.edu/Classes/Notes/Penn/EE774/Chap_03r.pdf M. L. Edwards: ''S-parameters, signal flow graphs, and other matrix representations'' ] All Rights Reserved

* [https://tube.switch.ch/channels/d206c96c H Schmid: ''Signal-Flow Graphs in 12 Short Lessons'' ]

* {{wikibooks- inline|Control Systems/Signal Flow Diagrams}}

* {{commons category-inline|Signal flow graphs}}