Using Mason's Rule to Analyze DSP Networks
There have been times when I wanted to determine the z-domain transfer function of some discrete network, but my algebra skills failed me. Some time ago I learned Mason's Rule, which helped me solve my problems. If you're willing to learn the steps in using Mason's Rule, it has the power of George Foreman's right hand in solving network analysis problems.
This blog discusses a valuable analysis method (well known to our analog control system engineering brethren) to obtain the z-domain transfer function equations of digital signal processing (DSP) networks. That method, called "Mason's Rule" (sometimes called "Mason's Gain Formula"), was developed by Samuel Mason in the early 1950s to analyze interconnected analog systems[1-3]. Here we describe Mason's Rule and present several examples showing the utility of this network analysis technique.
Mason's Rule enables us to determine the H(z) = Y(z)/X(z) transfer function of complicated networks, such as the multi-feedback loop network in Figure 1.
Figure 1: A discrete network with multiple feedback loops.
Mason's Rule is also particularly useful for deriving the z-domain transfer function of, say, a discrete network that has inner feedback loops embedded within outer feedback loops (nested loops). Here's the good news: if we are able to draw the block diagram of some discrete network, then the application of Mason's Rule will give us that network's z-domain H(z) transfer function. Once we have H(z) we can then use all the algebraic and software tools at our command to determine the frequency-domain behavior, and stability, of the network. Here we describe Mason's Rule, accompanied by several examples, in the hope this robust analysis technique is of use to the reader in their future DSP network analysis efforts.
For our purposes, Mason's Rule is a method to derive a discrete network's z-domain transfer function by identifying various forward paths from the input node to the output node of a discrete network, and the various feedback paths that may, or may not, share common signal nodes with those feedforward paths. This sounds mysterious, but it's not really too complicated. Let's define our Mason's Rule terminology and then demonstrate this analysis technique by way of examples.
I. A Few Definitions
Mason's Rule is based on converting a network's block diagram to a signal flow diagram like that shown in Figure 2, and identifying crucial signal paths and loops.
Figure 2: Example signal flow diagram.
Using Figure 2 as an example, we establish the following definitions:
- A gain symbol is an arrowhead with its associated z-domain function (indicated by an uppercase letter), such as a sample delay (z-1) or a constant multiplier. The direction of the arrowhead shows the direction of signal flow.
- A signal node is a single point in the flow diagram. In Figure 2, signal nodes are indicated by an italicized lowercase letter.
- A path is a sequence of signal flow branches from one node to another node.
- A forward path is a path that travels from the x(n) input to the y(n) output, without going through the same node twice. In Figure 2, the path from node a to node g, [a,b,c,d,e,f,g], is a forward path. The gain of that forward path is the product ACDFGI.
- A loop is a path that starts and ends at the same node, with no node encountered more than once. That is, a loop is a feedback path. In Figure 2, the path from node b to node c and back to node b is a loop. A signal flow diagram, of course, can have multiple forward paths and multiple loops.
- Nontouching loops are two loops that do not share a common signal node. In Figure 2, the loops [b,c,b] and [d,e,d], for example, are nontouching loops. The loops [b,c,b] and [b,c,d,e,f,g,b] are touching loops because they share the signal nodes b and c.
- The loop gain of a loop is the product of all the branch gain symbols within a loop. In Figure 2, the loop gain of the [d,e,d] loop is the product FE. The loop gain of the [b,c,d,e,f,g,b] loop is the product CDFGIJ.
With those simple definitions established (here comes the exciting part), we define the Δ(z) determinant of a signal flow diagram as:
Δ(z) = 1 – the sum of all loop gains
+ the sum of products of nontouching loop gains taken two at a time
– the sum of products of nontouching loop gains taken three at a time
+ ... etc. (1)
The "nontouching loop gains taken two at a time" are the combinations of pairs of loop gains. The pairs of nontouching loop gains in Figure 2 are the loop gain combinations: CB,FE; CB,IH; and FE,IH. The "nontouching loop gains taken three at a time" are the combinations of triplets of loop gains. The only triplet of nontouching loop gains in Figure 2 is the loop gain combination: CB,FE,IH.
The Δ(z) determinant for the diagram in Figure 2 is
Δ(z) = 1 – (CB + FE + IH + CDFGIJ)
+ (CBFE + CBIH + FEIH) – CBFEIH. (2)
For each forward path in a signal flow diagram there is an associated determinant represented by Δi(z). If a diagram has P = 3 forward paths (designated as paths P1(z), P2(z), and P3(z)), then there will be a Δ1(z), a Δ2(z), and a Δ3(z) determinant. Subscript variable i is merely the index identifying the individual forward paths and their associated determinants. Determinant Δi(z) is the determinant of the signal flow diagram that does not touch the ith forward path. To ascertain Δ1(z), for example, we delete the P1(z) forward path in a signal flow diagram (and any branches that touch the P1(z) forward path) and use the above Eq. (1) for whatever signal flow paths that remain. If no loops remain after deleting the P1(z) forward path, then Δ1(z) = 1.
To recap, a signal flow diagram has a Δ(z) determinant, and each Pi(z) forward path has a gain as well as its own Δi(z)(z) determinant. All determinants are defined by Eq. (1) once a diagram's loops have been determined. With all this said, we can now (finally) define Mason's Rule.
II. Mason's Rule, How To Use It
Mason's Rule states that the H(z) = Y(z)/X(z) transfer function of a linear network is:
where P is the number of forward paths in the network. To determine the transfer function of a discrete network, we implement Mason's Rule as the following series of steps:
Step 1: Convert the discrete-time network block diagram to a signal flow diagram; replacing multipliers and function blocks with directional gain symbols, and replacing branching nodes and adders with signal nodes. The minus sign associated with subtraction is represented by a gain symbol of –1.
Step 2: Identify the number, P, of forward paths and their individual P5(z) path gains.
Step 3: Identify the total number of loops and their individual loop gains, as well as the number of nontouching loop pairs and nontouching loop triplets.
Step 4: Delete each of the diagram's P forward paths (along with any branches touching those forward paths), in turn, and define the individual Δi(z) determinants.
Step 5: Define the original network's overall Δ(z) determinant using Eq. (1).
Step 6: Apply the P5(z) gains and the Δi(z) and Δ(z) determinants to Eq. (3) to find the desired H(z) transfer function.
Step 7: The final step is to sit back and enjoy a job well done.
III. Some Encouragement
If you're still with me so far, don't worry if the above definitions and steps appear to be gibberish. I can assure you they are not. For my money, Mason's Rule is the single most powerful network analysis tool at our disposal, and I now attempt to prove that by way of examples. Don't touch that dial.
IV. Examples of Mason's Rule
Again, the Mason's rule procedure seems a bit complicated but we can show how straightforward the process really is. What follows are a few examples, ranging in complexity, illustrating the execution and utility of Mason's Rule in analyzing discrete networks.
Our first Mason's Rule example will be to determine the H(z) transfer function of our old friend, the biquad infinite impulse response (IIR) filter shown in Figure 3(a).
Figure 3: Biquad IIR filter: (a) discrete network diagram;
(b) signal flow diagram; (c) forward paths shown with bold lines; (d) signal flow diagram with forward path P1 deleted.
Starting with the discrete network diagram in Figure 3(a), we draw the signal flow diagram shown in Figure 3(b). Examination of that flow diagram tells us that there are three forward paths, P = 3 (shown by the bold lines in Figure 3(c)), and two loops. So the three forward path gains and the two loop gains are:
P1(z) = b0, P2(z) = b1z-1, P3(z) = z-1z-1b2 = b2z-2,
Loop1 gain = a1z-1, and Loop2 gain = z-1z-1a2 = a2z-2.
Implementing Step 4, when forward path P1(z) is deleted, along with any branches touching P1(z), the remaining paths are shown in Figure 3(d), and those paths define forward path P1(z)'s determinant Δ1(z). In Figure 3(d) we see no remaining loops, so Δ1(z) = 1. Similarly, when forward paths P2(z) and P3(z) are deleted, along with any paths touching P2(z) and P3(z), no loops remain so our removed-path determinants are:
Δ1(z) = Δ2(z) = Δ3(z) = 1.
Realizing there are no nontouching loops in our original signal flow diagram, we now use Eq. (1) to define the network's primary Δ(z) determinant to be:
Δ(z) = 1 –(Loop1 gain + Loop2 gain) = 1 –(a1z-1 + a2z-2).
We have all the information we need to use Eq. (3) to obtain the network's transfer function as
Our Hbiquad(z) result is the well-known transfer function of a 2nd-order IIR filter. Next, let's analyze a discrete network having nested loops as given in the following example.
This example applies Mason's Rule to a DC bias removal network containing nested loops. Beginning with the network in Figure 4(a), we convert it to the signal flow diagram in Figure 4(b). Notice how the subtraction in Figure 4(a) is replaced with a gain symbol of minus one in the signal flow diagram.
Figure 4: DC bias removal: (a) discrete network diagram;
(b) signal flow diagram; (c) signal flow diagram with forward path P1 deleted.
Examination of that flow diagram tells us that there is one forward path (P = 1), and two loops. As such, the single forward path gain and the two loop gains are:
P1(z) = 1,
Loop1 gain = (1–α)z-1(–1) = –(1–α)z-1 = αz-1 –z-1
Loop2 gain = z-1.
When forward path P1(z) is deleted, the remaining paths are shown in Figure 4(c). There we see one remaining loop, so the determinant associated with forward path P1(z) is:
Δ1(z) = 1–z-1.
Because there are no nontouching loops in our original signal flow diagram, using Eq. (1) to define the network's primary Δ(z) determinant, we state:
Δ(z) = 1 –(Loop1 gain + Loop2 gain)
= 1 –[αz-1 –z-1 + z-1] = 1 –αz-1.
Given what we know so far, we use Eq. (3) to obtain the network's transfer function as
Next I present a final Mason's Rule example that brings to bear all the concepts we've covered so far.
Let's analyze that intricate network in Figure 1 by first converting it to the signal flow diagram in Figure 5(a).
Figure 5: Signal flow diagrams for Figure 1: (a) complete signal flow
diagram; (b) signal flow diagram with forward path P1 deleted;
(c) signal flow diagram with forward path P2 deleted.
Upon first glance at the flow diagram in Figure 5(a), we might guess this network has two forward paths and two loops. Watch out! The network actually has four forward paths, three loops, and a pair of nontouching loops. (Careful scrutiny is needed when evaluating a signal flow diagram in preparation for Mason's Rule. Stated in different words, using Mason's Rule is like pinning a cloth diaper on a baby—the process requires caution because a small mistake can cause big problems.)
Examination of the Figure 5(a) flow diagram tells us we have P = 4 forward paths, and three loops. The forward path gains (with the path nodes indicated in brackets) and loop gains are:
P1(z) = 8z-1, [a,b,c,d]
P2(z) = 15z-1, [a,f,e,d]
P3(z) = 30z-2, [a,b,c,f,e,d]
P4(z) = 24z-2. [a,f,e,b,c,d]
Loop1 gain = z-1/2, [b,c,b]
Loop2 gain = z-1/3, [f,e,f]
Loop3 gain = 6z-2. [b,c,f,e,b]
When forward path P1(z) is deleted, the remaining paths are shown in Figure 5(b), with one remaining loop, so Δ1(z) = 1–z-1/3. Similarly, when forward path P2(z) is deleted, the remaining paths are shown in Figure 5(c), with one remaining loop, thus Δ2(z) = 1–z-1/2. Now when forward paths P3(z) and P4(z) are deleted we have no paths remaining. Thus our removed-path determinants are:
Δ1(z) = 1–z-1/3,
Δ2(z) = 1–z-1/2,
Δ3(z) = 1,
Δ4(z) = 1.
In this example there are two nontouching loops, [b,c,b] and [f,e,f], so the sum of products nontouching loop gains taken two at a time is z-1/2 times z-1/3 = z-2/6. So we now use Eq. (1) to define the network's primary Δ(z) determinant to be:
Δ(z) = 1 –(Loop1 gain + Loop2 gain + Loop3 gain)
+ (product of Loop1 gain and Loop2 gain)
= 1 –(z-1/2 + z-1/3 + 6z-2) + z-2/6
= 1 –(5/6)z-1 –(35/6)z-2.
Using Eq. (3) to obtain the network's transfer function, we have
After plowing through this last example, Step 7 at the end of Section II is well-deserved.
V. MATLAB Code
For those readers having access of MATLAB software, there is a Mason's Rule MATLAB function, written by Rob Walton, available at: http://www.mathworks.com/matlabcentral/fileexchange/22 . (I tried to contact Rob, using E-mails and phone calls to Canada, to thank him for his MATLAB routine. I was unable to reach him. Perhaps Walton won the Canadian Lottery and is now living on a yacht off the coast of a Greek island.)
Walton's slick routine requires the user to create a ".txt" file describing a network's signal paths. The ".txt" file for our above Example# 3 contains the following 10 lines of text (parameters are separated by tabs).
1 1 2 2
2 3 2 (1/2)
3 2 3 z^(-1)
4 5 2 2
5 3 4 4
6 5 4 5
7 3 6 3
8 6 5 z^(-1)
9 5 6 (1/3)
10 1 6 3
Mason's Rule is an analog system analysis technique formulated in the early 1950s (around the time the young truck driver Elvis Presley arrived on the pop music scene) by Samuel Mason. Here we described how to use Mason's Rule to aid in modern-day discrete (DSP) network analysis. Although a bit tedious for complicated networks, Mason's Rule provides a super-effective method for determining the z-domain transfer function of even the most complicated discrete networks. Happily, public domain Mason's Rule MATLAB code is available.
 S. Mason, "Feedback Theory: Some Properties of Signal Flow Graphs," Proc. of IRE, Vol. 41, pp. 1144-1156, Sept. 1953.
 S. Mason, "Feedback Theory: Further Properties of Signal Flow Graphs," Proc. of IRE, Vol. 44, pp. 1920-926, Sept. 1956.
 S. Mason and H. Zimmerman, Electronic Circuits, Signals, and Systems, John Wiley & Sons, New York, 1960.
Previous post by Rick Lyons:
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Next post by Rick Lyons:
Some Thoughts on a German Mathematician
Keep it up. Thanks a lot
Thank you for explaining this technique.
BTW, I think equation 4 for "Hbiquad(z)" is missing - it's not showing in my browser.
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.