A signal-flow graph or signal-flowgraph (SFG), invented by Claude Shannon,^[1] but often called a Mason graph after Samuel Jefferson Mason who coined the term,^[2] is a specialized 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 graphs (also called digraphs), which includes as well that of oriented graphs. This mathematical theory of digraphs exists, of course, quite apart from its applications.^[3][4]

SFGs are most commonly used to represent signal flow in a physical system and its controller(s), forming a cyber-physical system. Among their other uses are the representation of signal flow in various electronic networks and amplifiers, digital filters, state-variable filters and some other types of analog filters. In nearly all literature, a signal-flow graph is associated with a set of linear equations.

History

Wai-Kai Chen wrote: "The concept of a signal-flow graph was originally worked out by Shannon ^[1] in dealing with analog computers. The greatest credit for the formulation of signal-flow graphs is normally extended to Mason ,^[2] .^[5] 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."^[6]

Lorens wrote: "Previous to Mason's work, C. E. Shannon^[1] 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."^[7]

"The rules for the evaluation of the graph determinant of a Mason Graph were first given and proven by Shannon using mathematical induction. His work remained essentially unknown even after Mason published his classical work in 1953. Three years later, Mason rediscovered the rules and proved them by considering the value of a determinant and how it changes as variables are added to the graph. "^[8]

Domain of application

Robichaud et al. identify the domain of application of SFGs as follows:^[9]

"All the physical systems analogous to these networks constitute the domain of application of the techniques developed . Trent^[10] has shown that all the physical systems which satisfy the following conditions fall into this category.

1. The finite lumped system is composed of a number of simple parts, each of which has known dynamical properties which can be defined by equations using two types of scalar variables and parameters of the system. Variables of the first type represent quantities which can be measured, at least conceptually, by attaching an indicating instrument to two connection points of the element. Variables of the second type characterize quantities which can be measured by connecting a meter in series with the element. Relative velocities and positions, pressure differentials and voltages are typical quantities of the first class, whereas electric currents, forces, rates of heat flow, are variables of the second type. Firestone has been the first to distinguish these two types of variables with the names across variables and through variables.
2. Variables of the first type must obey a mesh law, analogous to Kirchhoff's voltage law, whereas variables of the second type must satisfy an incidence law analogous to Kirchhoff's current law.
3. Physical dimensions of appropriate products of the variables of the two types must be consistent. For the systems in which these conditions are satisfied, it is possible to draw a linear graph isomorphic with the dynamical properties of the system as described by the chosen variables. The techniques can be applied directly to these linear graphs as well as to electrical networks, to obtain a signal flow graph of the system."

Basic flow graph concepts

The following illustration and its meaning were introduced by Mason to illustrate basic concepts:^[2]

In the simple flow graphs of the figure, a functional dependence of a node is indicated by an incoming arrow, the node originating this influence is the beginning of this arrow, and in its most general form the signal flow graph indicates by incoming arrows only those nodes that influence the processing at the receiving node, and at each node, i, the incoming variables are processed according to a function associated with that node, say F_i. The flowgraph in (a) represents a set of explicit relationships:

${\displaystyle {\begin{aligned}x_{\mathrm {1} }&={\text{an independent variable}}\\x_{\mathrm {2} }&=F_{2}(x_{\mathrm {1} },x_{\mathrm {3} })\\x_{\mathrm {3} }&=F_{3}(x_{\mathrm {1} },x_{\mathrm {2} },x_{\mathrm {3} })\\\end{aligned}}}$

Node x₁ is an isolated node because no arrow is incoming; the equations for x₂ and x₃ have the graphs shown in parts (b) and (c) of the figure.

These relationships define for every node a function that processes the input signals it receives. Each non-source node combines the input signals in some manner, and broadcasts a resulting signal along each outgoing branch. "A flow graph, as defined originally by Mason, implies a set of functional relations, linear or not."^[9]

However, the commonly used Mason graph is more restricted, assuming that each node simply sums its incoming arrows, and that each branch involves only the initiating node involved. Thus, in this more restrictive approach, the node x₁ is unaffected while:

${\displaystyle x_{2}=f_{21}(x_{1})+f_{23}(x_{3})}$

${\displaystyle x_{3}=f_{31}(x_{1})+f_{32}(x_{2})+f_{33}(x_{3})\ ,}$

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, because then they represent systems of Linear differential equations. In this case the transmittance, c(s), often is called a transfer function.

Choosing the variables

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^[11]

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."^[9] If all equations relate all dependent variables, then there are n! possible SFGs to choose from.^[12]

Linear signal-flow graphs

Linear signal-flow graph (SFG) methods only apply to linear time-invariant systems, as studied by 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).^[13] A SFG is then derived from this system of equations.

A linear SFG consists of nodes indicated by dots and weighted directional branches indicated by arrows. The nodes are the variables of the equations and the branch weights are the coefficients. Signals may only traverse a branch in the direction indicated by its arrow. The elements of a SFG can only represent the operations of multiplication by a coefficient and addition, which are sufficient to represent the constrained equations. When a signal traverses a branch in its indicated direction, the signal is multiplied the weight of the branch. When two or more branches direct into the same node, their outputs are added.

For systems described by linear algebraic or differential equations, the signal-flow graph is mathematically equivalent to the system of equations describing the system, and the equations governing the nodes are discovered for each node by summing incoming branches to that node. These incoming branches convey the contributions of the other nodes, expressed as the connected node value multiplied by the weight of the connecting branch, usually a real number or function of some parameter (for example a Laplace transform variable s).

For linear active networks, Choma writes:^[14] "By a 'signal flow representation' 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."

A motivation for a SFG analysis is described by Chen:^[15]

"The analysis of a linear system reduces ultimately to the solution of a system of linear algebraic equations. As an alternative to conventional algebraic methods of solving the system, it is possible to obtain a solution by considering the properties of certain directed graphs associated with the system." "The unknowns of the equations correspond to the nodes of the graph, while the linear relations between them appear in the form of directed edges connecting the nodes. ...The associated directed graphs in many cases can be set up directly by inspection of the physical system without the necessity of first formulating the →associated equations..."

Basic components

A linear signal flow graph is related to a system of linear equations^[16] of the following form:

${\displaystyle {\begin{aligned}x_{\mathrm {j} }&=\sum _{\mathrm {k} =1}^{\mathrm {N} }t_{\mathrm {jk} }x_{\mathrm {k} }\end{aligned}}}$

where ${\displaystyle t_{jk}}$ = transmittance (or gain) from ${\displaystyle x_{k}}$ to ${\displaystyle x_{j}}$.

The figure to the right depicts various elements and constructs of a signal flow graph (SFG).^[17]

Exhibit (a) is a node. In this case, the node is labeled ${\displaystyle x}$. A node is a vertex representing a variable or signal.

A source node has only outgoing branches (represents an independent variable). As a special case, an input node is characterized by having one or more attached arrows pointing away from the node and no arrows pointing into the node. Any open, complete SFG will have at least one input node.

An output or sink node has only incoming branches (represents a dependent variable). Although any node can be an output, explicit output nodes are often used to provide clarity. Explicit output nodes are characterized by having one or more attached arrows pointing into the node and no arrows pointing away from the node. Explicit output nodes are not required.

A mixed node has both incoming and outgoing branches.

Exhibit (b) is a branch with a multiplicative gain of ${\displaystyle m}$. The meaning is that the output, at the tip of the arrow, is ${\displaystyle m}$ times the input at the tail of the arrow. The gain can be a simple constant or a function (for example: a function of some transform variable such as ${\displaystyle s}$, ${\displaystyle \omega }$Zdroj:https://en.wikipedia.org?pojem=Signal-flow_graph
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---