Signal-flow graph: Difference between revisions

Revision as of 06:23, 12 November 2020

Revision as of 18:23, 26 November 2020

Line 86:

|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 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= |pages=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 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|last1 = Fakhfakh|first1 = 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.{{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 | page=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&hl=en&sa=X&ei=z1iwVNXZFs3WoASYj4D4DQ&ved=0CB8Q6AEwAA#v=onepage&q=%22THe%20signal-flow%20graph%20representing%20Eqs.%20(15-2)%22&f=false]</ref> The set of equations must be consistent and all equations must be linearly independent.

==== 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₁''.

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 | page=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&hl=en&sa=X&ei=z1iwVNXZFs3WoASYj4D4DQ&ved=0CB8Q6AEwAA#v=onepage&q=%22THe%20signal-flow%20graph%20representing%20Eqs.%20(15-2)%22&f=false]</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']].

Line 285:

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 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|last1 = Dorf|first1 = 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:

=== 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|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|last1 = Doboli|first1 = 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 = 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No.00CH36353)|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.

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|last1 =Potash|first1 = Hanan|first2 = Lawrence P.|last2 = McNamee|year =1968 |journal=Proceedings, ACM National Conference|pages=367–378 |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}}</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|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 439:

== 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 journal|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 474:

| first1 =Thomas A.

| last1 =Baran

| author-link =

| first2 =Alan V.

| last2 =Oppenhiem

| author2-link =

| chapter= INVERSION OF NONLINEAR AND TIME-VARYING SYSTEMS

| 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

Line 495 ⟶ 491:

== 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|last1 = BRZOZOWSKI|first1 = 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|last1 = Guilherme|first1 = 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 510 ⟶ 506:

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

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

* [[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>

Line 531 ⟶ 527:

==References==

* {{cite book|ref=harv|author1=Ernest J. Henley |author2=R. A. 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 |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=}}

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