Content deleted Content added
Citation bot (talk | contribs) Alter: url, chapter-url. URLs might have been internationalized/anonymized. Add: isbn, page, pages, s2cid, author pars. 1-1. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Suggested by Abductive | All pages linked from cached copy of User:Abductive/sandbox | via #UCB_webform_linked 782/988 |
|||
Line 2:
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
</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:
== 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 journal |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
</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 |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|WKC|1976|p=167}}</ref>
Line 67:
=== 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&
== 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
|
|
|last2 = Mateják
|first2 = M
Line 114:
::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= |
: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 175:
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|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|
'''Parallel edges. '''Replace parallel edges with a single edge having a gain equal to the sum of original gains.{{br}}
Line 231:
=== 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 |
==== Putting the equations in "standard form" ====
Line 264:
where the right side of this equation is the sum of the weighted arrows incident on node ''x<sub>1</sub>''.
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<sub>in</sub>''}, 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 |
Often the known values, y<sub>j</sub> are taken as the primary causes and the unknowns values, x<sub>j</sub> 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']].
Line 282:
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 |
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>
Line 293:
{{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:
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
</ref>
:"Like block diagrams, signal flow graphs represent the computational, not the physical structure of a system."
Line 323:
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&
</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?
</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?
</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:
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
</ref>
Line 345:
=== 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|
* Define the system and its components.
* Formulate the mathematical model and list the needed assumptions.
Line 356:
=== 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|
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|
== 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.
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 journal |title =Application of unilateral and graph techniques to analysis of linear circuits: Solution by non-iterative methods|
NASA's electrical circuit software NASAP is based on the Shannon-Happ formula.<ref name=Potash /><ref name=NASAP-70 />
Line 382:
[[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<sub>j</sub>=Px<sub>i</sub>''. 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|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 447:
=== 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|
=== Closed flowgraph ===
Line 472:
=== 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
|
|
| author-link =
| first2 =Alan V.
Line 489:
| 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 ⟶ 495:
== 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|
** Synthesis of non-linear data converters<ref name=Guilherme>{{Cite book|title = SYMBOLIC SYNTHESIS OF NON-LINEAR DATA CONVERTERS|
** Control and network theory
** Stochastic signal processing.<ref name=Barry>
Line 507 ⟶ 508:
|edition=Third
|isbn=978-0-7923-7548-7
|url=https://books.google.com/books?id=hPx70ozDJlwC&
</ref>
** Reliability of electronic systems<ref>{{Cite journal|url = |title = Application of flowgraph techniques to the solution of reliability problems|last = Happ|first = William 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>
Line 533 ⟶ 534:
*{{Citation |last=Kou|first= Benjamin C. |year= 1967 |title= Automatic Control Systems|publisher= Prentice Hall |isbn= |doi=}}
*{{cite book|ref=harv|last=Robichaud|first=Louis P.A. |author2= Maurice Boisvert|author3= Jean Robert|year= 1962 |title=Signal flow graphs and applications |pages=xiv, 214 p |publisher= Prentice Hall|___location=Englewood Cliffs, N.J.|isbn= |doi=|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.|___location=|isbn= 978-81-203-0145-0|doi=|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|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=}}
| |||