Signal-flow graph


A signal-flow graph or signal-flowgraph, invented by Claude Shannon, but often called a Mason graph after Samuel Jefferson Mason who coined the term, is a specialized flow graph, a directed graph in which nodes represent system variables, and branches represent functional connections between pairs of nodes. Thus, signal-flow graph theory builds on that of directed graphs, which includes as well that of oriented graphs. This mathematical theory of digraphs exists, of course, quite apart from its applications.
SFGs are most commonly used to represent signal flow in a physical system and its controller, 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
in dealing with analog computers. The greatest credit for the formulation of signal-flow graphs is normally extended to Mason , . 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."
Lorens wrote: "Previous to Mason's work, C. E. 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."
"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. "

Domain of application

Robichaud et al. identify the domain of application of SFGs as follows:
  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:
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 Fi. The flowgraph in represents a set of explicit relationships:
Node x1 is an isolated node because no arrow is incoming; the equations for x2 and x3 have the graphs shown in parts and 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."
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 x1 is unaffected while:
and now the functions fij can be associated with the signal-flow branches ij joining the pair of nodes xi, xj, rather than having general relationships associated with each node. A contribution by a node to itself like f33 for x3 is called a self-loop. Frequently these functions are simply multiplicative factors, for example, fij=cijxj, 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, and in this case the transmittance, c, often is called a transfer function.

Choosing the variables

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

Linear signal-flow graphs

Linear signal-flow graph 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. 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 linear active networks, Choma writes: "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:

Basic components

A linear signal flow graph is related to a system of linear equations of the following form:
The figure to the right depicts various elements and constructs of a signal flow graph.

Terms used in linear SFG theory also include:
A signal-flow graph may be simplified by graph transformation rules. These simplification rules are also referred to as signal-flow graph algebra.
The purpose of this reduction is to relate the dependent variables of interest to its independent variables.
The systematic reduction of a linear signal-flow graph is a graphical method equivalent to the Gauss-Jordan elimination method for solving linear equations.
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. Robichaud described this process of systematic flow-graph reduction:
For digitally reducing a flow graph using an algorithm, Robichaud extends the notion of a simple flow graph to a generalized flow graph:
The definition of an elementary transformation varies from author to author:
Parallel edges. Replace parallel edges with a single edge having a gain equal to the sum of original gains.
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.
The equations corresponding to the reduction between N and node I1 are:
Outflowing edges. Replace outflowing edges with edges directly flowing from the node's sources.
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.
The equations corresponding to the reduction directly relating N's input signals to its output signals are:
Zero-signal nodes.
Eliminate outflowing edges from a node determined to have a value of zero.
If the value of a node is zero, its outflowing edges can be eliminated.
Nodes without outflows.
Eliminate a node without outflows.
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.
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 .The equations corresponding to the reduction between N and all its input signals are:

Implementations

The above procedure for building the SFG from an acausal system of equations and for solving the SFG's gains have been implemented as an add-on to MATHLAB 68, an on-line 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. The set of equations must be consistent and all equations must be linearly independent.

Putting the equations in "standard form"

For M equations with N unknowns where each yj is a known value and each xj is an unknown value, there is equation for each known of the following form.
Although it is feasible, particularly for simple cases, to establish a signal flow graph using the equations in this form, some rearrangement allows a general procedure that works easily for any set of equations, as now is presented. To proceed, first the equations are rewritten as
and further rewritten as
and finally rewritten as
The signal-flow graph is now arranged by selecting one of these equations and addressing the node on the right-hand side. This is the node for which the node connects to itself with the branch of weight including a '+1', making a self-loop in the flow graph. The other terms in that equation connect this node first to the source in this equation and then to all the other branches incident on this node. Every equation is treated this way, and then each incident branch is joined to its respective emanating node. For example, the case of three variables is shown in the figure, and the first equation is:
where the right side of this equation is the sum of the weighted arrows incident on node x1.
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, 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.
Often the known values, yj are taken as the primary causes and the unknowns values, xj 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'].

Applying Mason's gain formula

In the most general case, the values for all the xk variables can be calculated by computing Mason's gain formula for the path from each yj to each xk and using superposition.
In general, there are N-1 paths from yj to variable xk so the computational effort to calculated Gkj is proportional to N-1.
Since there are M values of yj, Gkj must be computed M times for a single value of xk. The computational effort to calculate a single xk variable is proportional to. The effort to compute all the xk variables is proportional to. If there are N equations and N unknowns, then the computation effort is on the order of N3.

Relation to block diagrams

For some authors, a linear signal-flow graph is more constrained than a block diagram, 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.
A tabulation of the comparison between block diagrams and signal-flow graphs is provided by Bakshi & Bakshi, and another tabulation by Kumar. According to Barker et al.:
In the figure, a simple block diagram for a feedback system is shown with two possible interpretations as a signal-flow graph. The input R is the Laplace-transformed input signal; it is shown as a source node in the signal-flow graph. The output signal C is the Laplace-transformed output variable. It is represented as a sink node in the flow diagram. G and H are transfer functions, with H serving to feed back a modified version of the output to the input, B. The two flow graph representations are equivalent.

Interpreting 'causality'

The term "cause and effect" was applied by Mason to SFGs:
and has been repeated by many later authors:
However, Mason's paper is concerned to show in great detail how a set of equations is connected to an SFG, an emphasis unrelated to intuitive notions of "cause and effect". Intuitions can be helpful for arriving at an SFG or for gaining insight from an SFG, but are inessential to the SFG. The essential connection of the SFG is to its own set of equations, as described, for example, by Ogata:
There is no reference to "cause and effect" here, and as said by Barutsky:
The term "cause and effect" may be misinterpreted as it applies to the SFG, and taken incorrectly to suggest a system view of causality, 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:
The term "computational causality" is explained using the example of current and voltage in a resistor:
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.

Signal-flow graphs for analysis and design

Signal-flow graphs can be used for analysis, that is for understanding a model of an existing system, or for synthesis, that is for determining the properties of a design alternative.

Signal-flow graphs for dynamic systems analysis

When building a model of a dynamic system, a list of steps is provided by Dorf & Bishop:
In this workflow, equations of the physical system's mathematical model are used to derive the signal-flow graph equations.

Signal-flow graphs for design synthesis

Signal-flow graphs have been used in Design Space Exploration, 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.
Another example uses an annotated SFG as an expression of the continuous-time behavior, as input to an architecture generator

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, Mason rediscovered the same formula.
Happ generalized the Shannon formula for topologically closed systems. The Shannon-Happ formula can be used for deriving transfer functions, sensitivities, and error functions.
For a consistent set of linear unilateral relations, the Shannon-Happ formula expresses the solution using direct substitution.
NASA's electrical circuit software NASAP is based on the Shannon-Happ formula.

Linear signal-flow graph examples

Simple voltage amplifier

The amplification of a signal V1 by an amplifier with gain a12 is described mathematically by
This relationship represented by the signal-flow graph of Figure 1. is that V2 is dependent on V1 but it implies no dependency of V1 on V2. See Kou page 57.

Ideal negative feedback amplifier

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
The interpretation of the parameters is as follows: T = return ratio, G∞ = direct amplifier gain, G0 = feedforward. Figure 3 has the interesting aspect that it resembles Figure 2 for the two-port network with the addition of the extra feedback relation x2 = T y1.
From this gain expression an interpretation of the parameters G0 and G∞ is evident, namely:
There are many possible SFG's associated with any particular gain relation. Figure 4 shows another SFG for the asymptotic gain model that can be easier to interpret in terms of a circuit. In this graph, parameter β is interpreted as a feedback factor and A as a "control parameter", possibly related to a dependent source in the circuit. Using this graph, the gain is
To connect to the asymptotic gain model, parameters A and β cannot be arbitrary circuit parameters, but must relate to the return ratio T by:
and to the asymptotic gain as:
Substituting these results into the gain expression,
which is the formula of the asymptotic gain model.

Electrical circuit containing a two-port network

The figure to the right depicts a circuit that contains a y-parameter two-port network. Vin is the input of the circuit and V2 is the output. The two-port equations impose a set of linear constraints between its port voltages and currents. The terminal equations impose other constraints. All these constraints are represented in the SFG below the circuit. There is only one path from input to output which is shown in a different color and has a gain of -RLy21. There are also three loops: -Riny11, -RLy22, Riny21RLy12. Sometimes a loop indicates intentional feedback but it can also indicate a constraint on the relationship of two variables. For example, the equation that describes a resistor says that the ratio of the voltage across the resistor to the current through the resistor is a constant which is called the resistance. This can be interpreted as the voltage is the input and the current is the output, or the current is the input and the voltage is the output, or merely that the voltage and current have a linear relationship. Virtually all passive two terminal devices in a circuit will show up in the SFG as a loop.
The SFG and the schematic depict the same circuit, but the schematic also suggests the circuit's purpose. Compared to the schematic, the SFG is awkward but it does have the advantage that the input to output gain can be written down by inspection using Mason's rule.

Mechatronics : Position servo with multi-loop feedback

This example is representative of a SFG used to represent a servo control system and illustrates several features of SFGs. Some of the loops are extrinsic intentionally designed feedback loops. These are shown with dotted lines. There are also intrinsic loops that are not intentional feedback loops, although they can be analyzed as though they were. These loops are shown with solid lines. Loop 3 and loop 4 are also known as minor loops because they are inside a larger loop.
See Mason's rule for development of Mason's Gain Formula for this example.

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 !"

Standards covering signal-flow graphs

A state transition SFG or state diagram is a simulation diagram for a system of equations, including the initial conditions of the states.

Closed flowgraph

Closed flowgraphs describe closed systems and have been utilized to provide a rigorous theoretical basis for topological techniques of circuit analysis.
Mason introduced both nonlinear and linear flow graphs. To clarify this point, Mason wrote : "A linear flow graph is one whose associated equations are linear."

Examples of nonlinear branch functions

It we denote by xj the signal at node j, the following are examples of node functions that do not pertain to a linear time-invariant system:

Examples of nonlinear signal-flow graph models