Signal-flow graph: Difference between revisions

Revision as of 12:53, 6 June 2025

Latest revision as of 23:37, 25 July 2025

(6 intermediate revisions by 3 users not shown)

Line 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&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 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 ==

Line 65:

=== Choosing the variables ===

{{blockquote|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 ===

Line 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 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:

{{Blockquote|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:

{{Blockquote|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|last1 = Fakhfakh|first1 = Mourad|publisher = Bentham Science Publishers|year = 2012|isbn = 978-1-60805-425-1|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>

Line 231:

==== 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 ===

Line 361:

=== 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|last1 = Antao|first1 = B. A. A.|date = June 1995|journal = IEEE Transactions on Very Large Scale Integration (VLSI) Systems |doi = 10.1109/92.386223|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 |last1 = Doboli|first1 = A.|date = May 2000|doi = 10.1109/ISCAS.2000.856026 |last2 = Dhanwada|first2 = N.|last3 = Vemuri|first3 = R. | 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 ==

Line 368:

[[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|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 |last1 =Potash|first1 = Hanan|first2 = Lawrence P.|last2 = McNamee| title=Proceedings of the 1968 23rd ACM national conference | chapter=Application of unilateral and graph techniques to analysis of linear circuits |year =1968 |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|last1 = Okrent|first1 = Howard|publisher = School of Engineering and Applied Science, University of California at Los Angeles|year = 1970|___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 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 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|pages=10, 15 pages |url=https://www.me.utexas.edu/~longoria/paynter/hmp/BGprehistory.pdf }}</ref>

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

Line 480:

| first2 =Alan V.

| last2 =Oppenhiem

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

| chapter =Inversion of nonlinear and time-varying systems

| year = 2011

| pages =283–288

Line 507 ⟶ 509:

|url=https://books.google.com/books?id=hPx70ozDJlwC&q=signal+flow+graph&pg=PA86}}

</ref>

** Reliability of electronic systems<ref>{{Cite journalbook |titlelast = ApplicationHapp|first of= flowgraphWilliam techniquesW.| totitle=Second Annual Symposium 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|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

Line 536 ⟶ 538:

==References==

* {{cite book |author1first1=Ernest J. |last1=Henley |author2first2=R. A. |last2=Williams |name-list-style=amp |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 }}

*{{cite book|last=Robichaud|first=Louis P.A. |author2= Maurice Boisvert|author3= Jean 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}}

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

*{{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|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}}

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

*{{cite book|lastlast1=Robichaud |firstfirst1=Louis P.A. |author2first2= Maurice Boisvert|author3last2=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|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.

==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.|isbn= 978-81-203-0145-0|url=https://books.google.com/books?id=Yr2pJA950iAC}}

* {{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 |name-list-style=amp |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}}