Noncommutative signal-flow graph

<h2 id="definition">Definition</h2>

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 <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> 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.

<h2 id="return-loop-method">Return Loop Method</h2>
There exist several<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> noncommutative generalizations of <a href="/facts/Mason%27s_rule/7GRvcxKG">Mason's rule</a>. 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,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> so it is sometimes called Riegle's rule.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
As with <a href="/facts/Mason%27s_rule/7GRvcxKG">Mason's rule</a>, these gain expressions combine terms in a <a href="/facts/Graph-theoretic/VVPCd4TX">graph-theoretic</a> manner (loop-gains, path products, etc.). They are known to hold over an arbitrary <a href="/facts/Noncommutative_ring/3jmll7q7">noncommutative ring</a> and over the <a href="/facts/Semiring/7cSvWXVQ">semiring</a> of regular expressions.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Formal Description</h3>
The method starts by enumerating all paths from input to output, indexed by j 
 
 
 
 ∈
 
 
 {\displaystyle \in }
 
 J. We use the following definitions:

<ul><li>The j-th path product is (by abuse of notation) a tuple of kj edge weights along it:</li></ul>

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)}).}

<ul><li>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).</li>
<li>The <a href="/facts/Loop_gain/h2E89W7B">loop gain</a> 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.</li>
<li>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.</li></ul>
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}.}

<h3>An Example</h3>

Consider the <a href="/facts/Signal-flow_graph/Tg5fNxgo">signal-flow graph</a> 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

T
          
            d
          
        
        =
        
          
            [
            
              1
              −
              f
              −
              e
              (
              1
              −
              b
              
                )
                
                  −
                  1
                
              
              c
            
            ]
          
          
            −
            1
          
        
        d
        .
      
    
    {\displaystyle T_{d}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d.}

Along path (e,a), FRL and BRL differ slightly, each having distinct splits of vertices y and z as shown in the following table.

Adding to Td, the alternating product of node factors and path weights, we obtain two gain expressions:

T
          
            (
            F
            R
            L
            )
          
        
        =
        
          
            [
            
              1
              −
              f
              −
              e
              (
              1
              −
              b
              
                )
                
                  −
                  1
                
              
              c
            
            ]
          
          
            −
            1
          
        
        d
        +
        
          
            [
            
              1
              −
              f
              −
              e
              (
              1
              −
              b
              
                )
                
                  −
                  1
                
              
              c
            
            ]
          
          
            −
            1
          
        
        e
        (
        1
        −
        b
        
          )
          
            −
            1
          
        
        a
        ,
      
    
    {\displaystyle T^{(FRL)}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d+\left[1-f-e(1-b)^{-1}c\right]^{-1}e(1-b)^{-1}a,}

and

T
          
            (
            B
            R
            L
            )
          
        
        =
        
          
            [
            
              1
              −
              f
              −
              e
              (
              1
              −
              b
              
                )
                
                  −
                  1
                
              
              c
            
            ]
          
          
            −
            1
          
        
        d
        +
        (
        1
        −
        f
        
          )
          
            −
            1
          
        
        e
        
          
            [
            
              1
              −
              b
              −
              c
              (
              1
              −
              f
              
                )
                
                  e
                
              
            
            ]
          
          
            −
            1
          
        
        a
        ,
      
    
    {\displaystyle T^{(BRL)}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d+(1-f)^{-1}e\left[1-b-c(1-f)^{e}\right]^{-1}a,}

These values are easily seen to be the same using identities (ab)−1 = b−1a−1 and a(1-ba)−1=(1-ab)−1a.

<h2 id="applications">Applications</h2>
<h3>Matrix Signal-Flow Graphs</h3>
Consider equations

y
          
            i
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            2
          
        
        
          a
          
            i
            j
          
        
        
          x
          
            j
          
        
        +
        
          ∑
          
            j
            =
            1
          
          
            2
          
        
        
          b
          
            i
            j
          
        
        
          y
          
            j
          
        
      
    
    {\displaystyle y_{i}=\sum _{j=1}^{2}a_{ij}x_{j}+\sum _{j=1}^{2}b_{ij}y_{j}}

and

z
          
            i
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            2
          
        
        
          c
          
            i
            j
          
        
        
          y
          
            j
          
        
        ,
      
    
    {\displaystyle z_{i}=\sum _{j=1}^{2}c_{ij}y_{j},}

This system could be modeled as scalar signal-flow graph with multiple inputs and outputs. But, the variables naturally fall into layers, which can be collected into vectors 
x=(x1,x2)t
y=(y1,y2)t and
z=(z1,z2)t.
This results in much simpler matrix signal-flow graph as shown in the figure at the top of the article.
Applying the forward return loop method is trivial as there's a single path product (C,A) with a single loop-gain B at y. Thus as a matrix, this system has a very compact representation of its input-output map:

T
        =
        C
        (
        1
        −
        B
        
          )
          
            −
            1
          
        
        A
        .
      
    
    {\displaystyle T=C(1-B)^{-1}A.}

<h3>Finite Automata</h3>

An important kind of noncommutative signal-flow graph is a <a href="/facts/Finite-state_machine/GMusWd0a">finite state</a> <a href="/facts/Automaton/SXtErQr2">automaton</a> over an alphabet 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Serial connections correspond to the concatenation of words, which can be extended to subsets of the <a href="/facts/Free_monoid/h3nPVjqr">free monoid</a> 
 
 
 
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle \Sigma ^{*}}
 
. For A, B 
 
 
 
 ⊆
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle \subseteq \Sigma ^{*}}

A
        ⋅
        B
        =
        {
        a
        b
        ∣
        a
        ∈
        A
        ,
        b
        ∈
        B
        }
        .
      
    
    {\displaystyle A\cdot B=\{ab\mid a\in A,b\in B\}.}

Parallel connections correspond to <a href="/facts/Set_union/KVVXKfWl">set union</a>, which in this context is often written A+B.
Finally, self-loops naturally correspond to the <a href="/facts/Kleene_closure/I6SX0f2Y">Kleene closure</a>

A
          
            ∗
          
        
        =
        {
        λ
        }
        +
        A
        +
        A
        A
        +
        A
        A
        A
        +
        ⋯
        ,
      
    
    {\displaystyle A^{*}=\{\lambda \}+A+AA+AAA+\cdots ,}

where 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 is the <a href="/facts/Empty_word/T7udJlmQ">empty word</a>. The similarity to the infinite geometric series

(
        1
        −
        x
        
          )
          
            −
            1
          
        
        =
        1
        +
        x
        +
        
          x
          
            2
          
        
        +
        
          x
          
            3
          
        
        ⋯
        ,
      
    
    {\displaystyle (1-x)^{-1}=1+x+x^{2}+x^{3}\cdots ,}

is more than superficial, as expressions of this form serve as 'inversion' in this <a href="/facts/Semiring/7cSvWXVQ">semiring</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
In this way, the subsets of 
 
 
 
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle \Sigma ^{*}}
 
 built of from finitely many of these three operations can be identified with the <a href="/facts/Semiring/7cSvWXVQ">semiring</a> of <a href="/facts/Regular_expressions/KFL3veHX">regular expressions</a>. Similarly, finite graphs whose edges are weighted by subsets of 
 
 
 
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle \Sigma ^{*}}
 
 can be identified with finite automata, though generally that theory starts with <a href="/facts/Singleton_(mathematics)/LtNVfujT">singleton</a> sets as in the figure.
This automaton is deterministic so we can unambiguously enumerate paths via words. Using the return loop method, path contributions are:

<ul><li>path ab, has node factors (c*, 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
), yielding gain contribution</li></ul>

a
        
          c
          
            ∗
          
        
        b
        ,
      
    
    {\displaystyle ac^{*}b,}

<ul><li>path ada, has node factors (c*, c*, 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
), yielding gain contribution</li></ul>

a
        
          c
          
            ∗
          
        
        d
        
          c
          
            ∗
          
        
        a
        ,
      
    
    {\displaystyle ac^{*}dc^{*}a,}

<ul><li>path ba, has node factors (c*, 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
), yielding gain contribution</li></ul>

b
        
          c
          
            ∗
          
        
        a
        .
      
    
    {\displaystyle bc^{*}a.}

Thus the <a href="/facts/Formal_language/crDTyP8q">language</a> accepted by this automaton (the gain of its signal-flow graph) is the sum of these terms

L
        =
        a
        
          c
          
            ∗
          
        
        b
        +
        a
        
          c
          
            ∗
          
        
        d
        
          c
          
            ∗
          
        
        a
        +
        b
        
          c
          
            ∗
          
        
        a
        .
      
    
    {\displaystyle L=ac^{*}b+ac^{*}dc^{*}a+bc^{*}a.}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Signal-flow_graph/Tg5fNxgo">Signal-flow graph</a></li>
<li><a href="/facts/Mason%27s_rule/7GRvcxKG">Mason's rule</a></li>
<li><a href="/facts/Finite_automata/GMusWd0a">Finite automata</a></li>
<li><a href="/facts/Regular_expressions/KFL3veHX">Regular expressions</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Andaloussi, C.; Chalh, Z.; Sueur, C. (2006). "Infinite zero of linear time varying bond-graph models: Graphical rules". Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications. pp. 2962–2967. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FCACSD-CCA-ISIC.2006.4777109">10.1109/CACSD-CCA-ISIC.2006.4777109</a>.</li>
<li>Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene (1971). <a href="http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf">"Ambiguity in graphs and expressions"</a> (PDF). IEEE Transactions on Computers. 100 (2). IEEE: 149–153. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2Ft-c.1971.223204">10.1109/t-c.1971.223204</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:20676251">20676251</a>.</li>
<li>Brzozowski, J. A.; McCluskey, E. J. Jr. (1963). "Signal flow graph techniques for sequential circuit state diagrams". IEEE Transactions on Electronic Computers (2). IEEE: 67–76. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FPGEC.1963.263416">10.1109/PGEC.1963.263416</a>.</li>
<li>Greibach, Sheila (1965). <a href="https://doi.org/10.1145%2F321250.321254">"A new normal-form theorem for context-free phrase structure grammars"</a>. Journal of the ACM. 12 (1). ACM: 42–52. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321250.321254">10.1145/321250.321254</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12991430">12991430</a>.</li>
<li>Kuich, Werner; Salomaa, Arto (1985). Semirings, automata and languages. Springer-Verlag.</li>
<li>Lorens, Charles S. (1964). Flowgraphs: For the Modeling and Analysis of Linear Systems. McGraw-Hill.</li>
<li>Pliam, John; Lee, E. Bruce (1995). <a href="http://www.atbash.com/node/8">"On the global properties of interconnected systems"</a>. IEEE Transactions on Circuits and Systems I: Fund. Theory and Apps. 42 (12). IEEE: 1013–1017. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2F81.481196">10.1109/81.481196</a>.</li>
<li>Riegle, Daryle; Lin, P.M. (1972). "Matrix signal flow graphs and an optimum topological method for evaluating their gains". IEEE Transactions on Circuit Theory. 19 (5). IEEE: 427–435. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2Ftct.1972.1083542">10.1109/tct.1972.1083542</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Lorens 1964. - Lorens, Charles S. (1964). Flowgraphs: For the Modeling and Analysis of Linear Systems. McGraw-Hill. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Riegle & Lin 1972. - Riegle, Daryle; Lin, P.M. (1972). "Matrix signal flow graphs and an optimum topological method for evaluating their gains". IEEE Transactions on Circuit Theory. 19 (5). IEEE: 427–435. doi:10.1109/tct.1972.1083542. <a href="https://doi.org/10.1109%2Ftct.1972.1083542" target="_blank">https://doi.org/10.1109%2Ftct.1972.1083542</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Brzozowski & McCluskey 1963. - Brzozowski, J. A.; McCluskey, E. J. Jr. (1963). "Signal flow graph techniques for sequential circuit state diagrams". IEEE Transactions on Electronic Computers (2). IEEE: 67–76. doi:10.1109/PGEC.1963.263416. <a href="https://doi.org/10.1109%2FPGEC.1963.263416" target="_blank">https://doi.org/10.1109%2FPGEC.1963.263416</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Book et al. 1971. - Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene (1971). "Ambiguity in graphs and expressions" (PDF). IEEE Transactions on Computers. 100 (2). IEEE: 149–153. doi:10.1109/t-c.1971.223204. S2CID 20676251. <a href="http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf" target="_blank">http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Pliam & Lee 1995. - Pliam, John; Lee, E. Bruce (1995). "On the global properties of interconnected systems". IEEE Transactions on Circuits and Systems I: Fund. Theory and Apps. 42 (12). IEEE: 1013–1017. doi:10.1109/81.481196. <a href="http://www.atbash.com/node/8" target="_blank">http://www.atbash.com/node/8</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Riegle & Lin 1972. - Riegle, Daryle; Lin, P.M. (1972). "Matrix signal flow graphs and an optimum topological method for evaluating their gains". IEEE Transactions on Circuit Theory. 19 (5). IEEE: 427–435. doi:10.1109/tct.1972.1083542. <a href="https://doi.org/10.1109%2Ftct.1972.1083542" target="_blank">https://doi.org/10.1109%2Ftct.1972.1083542</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Riegle & Lin 1972. - Riegle, Daryle; Lin, P.M. (1972). "Matrix signal flow graphs and an optimum topological method for evaluating their gains". IEEE Transactions on Circuit Theory. 19 (5). IEEE: 427–435. doi:10.1109/tct.1972.1083542. <a href="https://doi.org/10.1109%2Ftct.1972.1083542" target="_blank">https://doi.org/10.1109%2Ftct.1972.1083542</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Andaloussi, Chalh & Sueur 2006, pp. 2962. - Andaloussi, C.; Chalh, Z.; Sueur, C. (2006). "Infinite zero of linear time varying bond-graph models: Graphical rules". Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications. pp. 2962–2967. doi:10.1109/CACSD-CCA-ISIC.2006.4777109. <a href="https://doi.org/10.1109%2FCACSD-CCA-ISIC.2006.4777109" target="_blank">https://doi.org/10.1109%2FCACSD-CCA-ISIC.2006.4777109</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Pliam & Lee 1995. - Pliam, John; Lee, E. Bruce (1995). "On the global properties of interconnected systems". IEEE Transactions on Circuits and Systems I: Fund. Theory and Apps. 42 (12). IEEE: 1013–1017. doi:10.1109/81.481196. <a href="http://www.atbash.com/node/8" target="_blank">http://www.atbash.com/node/8</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Brzozowski & McCluskey 1963. - Brzozowski, J. A.; McCluskey, E. J. Jr. (1963). "Signal flow graph techniques for sequential circuit state diagrams". IEEE Transactions on Electronic Computers (2). IEEE: 67–76. doi:10.1109/PGEC.1963.263416. <a href="https://doi.org/10.1109%2FPGEC.1963.263416" target="_blank">https://doi.org/10.1109%2FPGEC.1963.263416</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Book et al. 1971. - Book, Ronald; Even, Shimon; Greibach, Sheila; Ott, Gene (1971). "Ambiguity in graphs and expressions" (PDF). IEEE Transactions on Computers. 100 (2). IEEE: 149–153. doi:10.1109/t-c.1971.223204. S2CID 20676251. <a href="http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf" target="_blank">http://www.diku.dk/hjemmesider/ansatte/henglein/papers/book1971.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Kuich & Salomaa 1985. - Kuich, Werner; Salomaa, Arto (1985). Semirings, automata and languages. Springer-Verlag. <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

Noncommutative signal-flow graph open-in-new

Noncommutative signal-flow graph