In automata theory and control theory, branches of mathematics, theoretical computer science and systems engineering, a noncommutative signal-flow graph is a tool for modeling interconnected systems and state machines by mapping the edges of a directed graph to a ring or semiring. A single edge weight might represent an array of impulse responses of a complex system (see figure to the right), or a character from an alphabet picked off the input tape of a finite automaton, while the graph might represent the flow of information or state transitions. As diverse as these applications are, they share much of the same underlying theory.
Definition
Consider n equations involving n+1 variables {x0, x1,...,xn}.
x i = ∑ j = 0 n a i j x j , 1 ≤ i ≤ n , {\displaystyle x_{i}=\sum _{j=0}^{n}a_{ij}x_{j},\;\;\;1\leq i\leq n,}
with aij elements in a ring or semiring R. The free variable x0 corresponds to a source vertex v0, thus having no defining equation. Each equation corresponds to a fragment of a directed graph G=(V,E) as show in the figure. The edge weights define a function f from E to R. Finally fix an output vertex vm. A signal-flow graph is the collection of this data S = (G=(V,E), v0,vm ∈ {\displaystyle \in } V, f : E → R). The equations may not have a solution, but when they do,
x m = T x 0 , {\displaystyle x_{m}=Tx_{0},}
with T an element of R called the gain.
Return Loop Method There exist several noncommutative generalizations of Mason's rule. The most common is the return loop method (sometimes called the forward return loop method (FRL), having a dual backward return loop method (BRL)). The first rigorous proof is attributed to Riegle, so it is sometimes called Riegle's rule. As with Mason's rule, these gain expressions combine terms in a graph-theoretic manner (loop-gains, path products, etc.). They are known to hold over an arbitrary noncommutative ring and over the semiring of regular expressions.
Formal Description The method starts by enumerating all paths from input to output, indexed by j ∈ {\displaystyle \in } J. We use the following definitions:
The j-th path product is (by abuse of notation) a tuple of kj edge weights along it:
p j = ( w k j ( j ) , … , w 2 ( j ) , w 1 ( j ) ) . {\displaystyle p_{j}=(w_{k_{j}}^{(j)},\ldots ,w_{2}^{(j)},w_{1}^{(j)}).}
To split a vertex v is to replace it with a source and sink respecting the original incidence and weights (this is the inverse of the graph morphism taking source and sink to v). The loop gain of a vertex v w.r.t. a subgraph H is the gain from source to sink of the signal-flow graph split at v after removing all vertices not in H. Each path defines an ordering of vertices along it. The along path j, the i-th FRL (BRL) node factor is (1-Si(j))−1 where Si(j) is the loop gain of the i-th vertex along the j-th w.r.t. the subgraph obtained by removing v0 and all vertices ahead of (behind) it. The contribution of the j-th path to the gain is the product along the path, alternating between the path product weights and the node factors:
T j = ∏ i = k j 1 ( 1 − S i ( j ) ) − 1 w i ( j ) , {\displaystyle T_{j}=\prod _{i=k_{j}}^{1}(1-S_{i}^{(j)})^{-1}w_{i}^{(j)},}
so the total gain is
T = ∑ j ∈ J T j . {\displaystyle T=\sum _{j\in J}T_{j}.}
An Example
Consider the signal-flow graph shown. From x to z, there are two path products: (d) and (e,a). Along (d), the FRL and BRL contributions coincide as both share same loop gain (whose split reappears in the upper right of the table below):
f + e ( 1 − b ) − 1 c , {\displaystyle f+e(1-b)^{-1}c,}
Multiplying its node factor and path weight, its gain contribution is
… excerpt ends here. Continue reading the full article.
