Bilinear Transformation via Synthetic Division: The Matrix Method

(Authors: Prof. Navdeep M. Singh, VJTI, University of Mumbai and Nalin Pithwa, 1992).

Abstract: The bilinear transformation can be achieved by using the method of synthetic division. A good deal of simplification is obtained when the process is implemented as a sequence of matrix operations. Besides, the matrices are found to have simple structures suitable for algorithmic implementation.

I) INTRODUCTION:

Davies [1] proposed a method for bilinear transformation using synthetic division. This method can be quite simplified when the synthetic division is carried out as a set of matrix operations because the operator matrices are found to have simple structures and so can be easily generated.

II) THE ALGORITHM:

Given a discrete time transfer function $H(z)$ , it is transformed to $G(s)$ in the s-plane under the transformation:

$z=\frac{s+1}{s-1}$

This can be sequentially achieved as :-

$H(z) \rightarrow H(s+1) \rightarrow H(\frac{1}{s}+1) \rightarrow H(\frac{2}{s}+1) \rightarrow H(\frac{2}{s-1}+1)=H(\frac{s+1}{s-1})=G(s)$

The first step is to represent the given characteristic polynomial in the standard companion form. Since the companion form represents a monic polynomial appropriate scaling is required in the course of the algorithm to ensure that the polynomial generated is monic after each step of transformation.

The method is developed for a third degree polynomial and then generalized.

Step 1:

$H(z) \rightarrow H_{1}(s+1) \rightarrow H(s+1)$ (decreasing of roots by one)

Given $H(z)=z^{3}+a_{2}z^{2}+a_{1}z+a_{0}$ (a_{3}=1) (monic)

Then, $H_{1}(s+1)=s^{3}+b_{2}s^{2}+b_{1}s+b_{0}$ where $b_{2}=a_{2}+1$ , $b_{1}=a_{1}+b_{2}$ , $b_{0}=a_{0}+b_{1}$

$H(s+1)=s^{3}+(a_{2}+3)s^{2}+(a_{1}+2a_{2}+3)s+(a_{0}+a_{1}+a_{2}+1)$ .

In the companion form, obviously the following transformation is sought:

$A = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -a_{0} & -a_{1} & -a_{2} \end{array}\right]$ and $B=\left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 &1 \\-b_{0} & -b_{1} & -b_{2} \end{array} \right]$ and $C = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -a_{0}-a_{1}-a_{2}-1 & -a_{1} - 2a_{2}-3 & -a_{2}-3 \end{array} \right]$

Performing elementary row and column transformations on A using matrix operators, the final row operator and column operator matrices, $P_{1}$ and $Q_{1}$ , respectively are found to be $P_{1} = \left[ \begin{array}{ccc} (a_{0}+a_{1})/a_{0} & a_{2}/a_{0} & 1/a_{0} \\ -1 & 1 & 0 \\ 0 & -1 & 1\end{array} \right]$ and $Q_{1} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array}\right]$ .

Thus, $P_{1}AQ_{1}=B$ .

In general, for a polynomial of degree n,

$P_{1} = \left[ \begin{array}{ccccc} (a_{0}+a_{1})/a_{0} & a_{2}/a_{0} & a_{3}/a_{0} & \ldots & 1\\ -1 & 1 & 0 & \ldots & a_{0}\\ 0 & -1 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & -1 & 1\end{array}\right]$ and $Q_{1} = \left[ \begin{array}{ccccc} 1 & 0 & 0 \ldots & 0 \\ 1 & 1 & 0 & \ldots & \ldots \\ 1 & 1 & 1 & \ldots & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & 1 & 1 & \ldots & 1\end{array}\right]$ , where both the matrices are $n \times n$ .

and $B = P_{1}AQ_{1} = \left[ \begin{array}{ccccc} 0 & 1 & 0 & \ldots & 0\\ 0 & 0 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ -b_{0} & -b_{1} & -b_{2} & \ldots & -b_{n-1} \end{array}\right]$ , and B is also $n \times n$ .

Where $b_{j} = \sum_{i=j}^{n-1}a_{i} + 1$ , where $i, j = 0, 1, 2, \ldots, (n-1)$ .

Now, the transformation $B \rightarrow C$ is sought respectively. The row and column operator matrices $P_{c1}$ and $Q_{c1}$ respectively are : $P_{c1} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 1 & -2 & 1 \end{array}\right]$ and $Q_{c1} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array}\right]$ .

$P_{c1}$ and $Q_{c1}$ are found to have the following general structures:

$P_{c1} = \left[ \begin{array}{ccccc}1 & 0 & \ldots & \ldots & 0 \\ -1 & 1 & \ldots & \ldots & 0 \\ 1 & -2 & 1 & \ldots & 0 \\ -1 & 3 & -3 & 1 & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \ldots & \ldots & \ldots & \ldots & 1\end{array}\right]$ and $Q_{c1} = \left[ \begin{array}{ccccc} 1 & 0 & \ldots & \ldots & 0 \\ 0 & 1 & 0 & \ldots & 0 \\ 0 & 1 & 1 & \ldots & 0 \\ 0 & 1 & 2 & 1 &\ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \ldots & \ldots & \ldots & \ldots & 1\end{array}\right]$ , both general matrices $P_{c1}$ and $Q_{c1}$ , being of dimensions $n \times n$ .

$P_{c1}$ is lower triangular and can be generated as : $P_{c1}(i,j) = [|P_{c1(i-j)}|+|P_{c1}(i-1,j-1)|] \times (-1)^{(i+j)}$ , where $i=2, 3, 4, \ldots, n$ and so we get

$P_{c1}(i,1)=(-1)^{(i-1)}$ , where $i=1, 2, 3, \ldots, n$ , and $P_{c1}(i,i)=1$ .

Similarly, $Q_{c1}$ is lower triangular and can be generated as :

$Q_{c1}(i,1)=0$ , where $i=2,3,4, \ldots, n$

$Q_{c1}(i,j) = Q_{c1}(i-1,j) + Q_{c1}(i-1,j-1)$ .

Thus, when A is the companion form of a polynomial of any degree n, then $P_{c1}(P_{1}AQ_{1})Q_{c1}$ gives $H(s+1)$ in the companion form.

Step 2:

$H(s+1) \rightarrow (\frac{s^{3}}{b_{0}}).H(1/s + 1)$ (scaled inversion).

Let $H(s+1) = s^{3} + b_{2}s^{2}+b_{1}s+b_{0}$ where $b_{0}=a_{0} + a_{1} + a_{2} +1$ , $b_{1} = a_{1} + 2a_{2}+3$ , $b_{2}=a_{2}+3$ .

The scaling of the entire polynomial by $b_{0}$ ensures that the polynomial generated is monic and hence, can be represented in the companion form.

The following transformation is sought: $C = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -b_{0} & -b_{1} & -b_{2} \end{array}\right] \rightarrow D = \left[\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1 \\ -1/b_{0} & (-b_{2}/b_{0}) & (-b_{1}/b_{0})\end{array}\right]$

The row and column operator matrices $P_{2}$ and $Q_{2}$ respectively are:

$P_{2}=\left[\begin{array}{ccc} b_{1}/b_{2} & 0 & 0 \\ 0 & b_{2}/b_{1} & 0 \\ 0 & 0 & 1/b_{0}\end{array}\right]$ and $Q_{2} = \left[ \begin{array} {ccc}1/b_{0} & 0 & 0 \\ 0 & b_{2}/b_{1} & 0 \\ 0 & 0 & b_{1}/b_{2}\end{array}\right]$

In general, $P_{2} = \left[ \begin{array}{ccccc} b_{1}/b_{n-1} & 0 & 0 & 0 & \ldots \\ 0 & 0 & 0 & \ldots & \ldots \\ 0 & 0 & \ldots & \ldots & \ldots \\ 0 & \ldots & \ldots & b_{n-1}/b_{1} \\ \ldots & \ldots & \ldots & \ldots & 1/b_{0}\end{array}\right]$ and $Q_{2} = \left[ \begin{array}{ccccc} 1/b_{0} & 0 & 0 & \ldots & 0\\ 0 & b_{n-1}/b_{0} & \ldots & \ldots & 0 \\ 0 & 0 & 0 & \ldots & 0 \\ 0 & \ldots & \ldots & \ldots & 0 \\ 0 & 0 & \ldots & \ldots & b_{1}/b_{n-1}\end{array}\right]$ , where both the general matrices $P_{2}$ and $Q_{2}$ are of dimensions $n \times n$ .

So, we get $D=P_{2}A_{1}Q_{2} = \left[ \begin{array}{ccccc} 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1/b_{0} & (-b_{n-1}/b_{0}) & (-b_{n-2}/b_{0}) & \ldots & (-b_{1}/b_{0})\end{array}\right]$ , which is also a matrix of dimension $n \times n$ .

Step 3:

$(s^{3}/b_{0})H(1/s + 1) \rightarrow (s^{3}/b_{0})H(1 + k/s)$ , with $k=2$ (scaling of roots)

If $F(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \ldots + s_{0}$ , then $F(x/k) = a_{n}x^{n} + ka_{n-1}x^{n-1} + k^{2}a_{n-2}x^{n-2}+ \ldots + a_{0}k^{n}$ .

The following transformation is sought:

$D = \left[\begin{array}{ccc}0 & 1 & 0 \\ 0 & 0 & 1 \\ -1/b_{0} & (-b_{2}/b_{0}) & (-b_{1}/b_{0}) \end{array}\right]$ and $E = \left[ \begin{array}{ccc}0 & 1 & 0 \\ 0 & 0 & 1 \\ -k^{3}/b_{0} & (-k^{2}b_{2}/b_{0}) & (-kb_{1}/b_{0})\end{array}\right]$ .

The row and column operators, $P_{3}$ and $Q_{3}$ , respectively are:

$P_{3}= \left[ \begin{array}{ccc} 1/k^{2} & 0 & 0 \\ 0 & 1/k & 0 \\ 0 & 0 &\ 1\end{array}\right]$ , and $Q_{3}=\left[ \begin{array}{ccc} k^{3} & 0 & 0 \\ 0 & k^{2} & 0 \\ 0 & 0 & k \end{array}\right]$

In general, $P_{3} = \left[ \begin{array}{ccccc}1/k^{n-1} & 0 & 0 & \ldots & 0 \\ 0 & 1/k^{n-2} & 0 & \ldots & 0 \\ 0 & \ldots & \ldots & \ldots & 0 \\ 0 & \vdots & \vdots & \vdots & 1/k \\ 0 & \ldots & \ldots & \ldots & 1\end{array}\right]$ , and $Q_{3} = \left[ \begin{array}{ccccc}k^{n} & 0 & 0 & \ldots & 0 \\ 0 & k^{n-1} & 0 & \ldots & 0 \\ 0 & 0 & \ldots & \ldots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \ldots & k\end{array}\right]$ , where the general matrices $P_{3}$ and $Q_{3}$ are both of dimensions $n \times n$

and $E=P_{3}A_{2}Q_{3} = \left[ \begin{array}{ccccc}0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0 \\ 0 & \ldots & \ldots & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ (-k^{n}/b_{0}) & (-b_{n-1}k^{n-1}/b_{0}) & \ldots & \ldots & (-kb_{1}/b_{0})\end{array}\right]$

Step 4:

$(s^{3}/b_{0})H(1+k/s) \rightarrow (s^{3}/b_{0})H(1+k/(s-1))$ (increasing of roots by one)

For the third degree case, the following transformation is sought:

$E = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -A_{0} & -A_{1} & -A_{2}\end{array}\right]$ and $F = \left[ \begin{array}{ccc}0 & 1 & 0 \\ 0 & 0 & 1 \\ -B_{0} & -B_{1} & -B_{2}\end{array}\right]$ and $G = \left[ \begin{array}{ccc}0 & 1 & 0\\ 0 & 0 & 1 \\ (-A_{0}+A_{1}-A_{2}+1) & (-A_{1}+2A_{2}-3) & (3-A_{2}) \end{array}\right]$ ,

where $B_{2}=A_{2}-1$ , $B_{1}=A_{1}-B_{2}$ , $B_{0}=A_{0}-B_{1}$ .

The row and column operators $P_{4}$ and $Q_{4}$ are :

$P_{4}= \left[ \begin{array}{ccc} (A_{0}-A_{1})/A_{0} & (-A_{2}/A _{0}) & (-1/A_{0}) \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{array}\right]$ and $Q_{4}=\left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 1 & -1 & 1\end{array}\right]$

In general, $P_{4} = \left[ \begin{array}{ccccc} (C_{0}-C_{1})/C_{0} & (-C_{2}/C_{0}) & (-C_{3}/C_{0}) & \ldots & (1/C_{0}) \\ 1 & 1 & \ldots & \ldots & 0\\ 0 & 1 & 1 & \ldots & 0\\0 & \ldots & \ldots & 1 & 1 \\\vdots & \vdots & \vdots & \vdots & 1 \end{array}\right]$ , and $Q_{4}=\left[ \begin{array}{ccccc} 1 & 0 & \ldots & \ldots & 0 \\ -1 & 1 & 0 & \ldots & 0 \\ 1 & -1 & 1 & 0 & \ldots\\ \ldots & \ldots & \ldots & \ldots & 1 \\ \vdots & \vdots & \vdots & \vdots & 1\end{array}\right]$ , both the general matrices $P_{4}$ and $Q_{4}$ being of dimensions $n \times n$ .

Where $C_{0}=k^{n}/b_{0}$ and $C_{j}=k^{n-j}b_{n-j}/b_{0}$ , where $j=1, 2, 3, \ldots, (n-1)$ and $Q_{4}$ is a lower triangular matrix where $q_{4}(i,j) = (-1)^{i+j}$ .

In general, we have $F = P_{4}A_{3}Q_{4} = \left[ \begin{array}{ccccc} 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ -\hat{C_{0}} & -\hat{C_{1}} & -\hat{C_{2}} & \ldots & -\hat{C_{n-1}}\end{array}\right]$

where $-\hat{C_{0}} = -C_{0} + C_{1} - C_{2} + \ldots + (-1)^{n-1}$

where $-\hat{C_{1}} = -C_{1} + C_{2} - C_{3} + \ldots - (-1)^{n-1}$

where $-\hat{C_{2}} = -C_{2} + C_{3} - C_{4} + \ldots + (-1)^{n-1}$

and so on $\vdots$

Now, the transformation $F \rightarrow G$ is to be achieved. The row and column operators, $P_{c4}$ and $Q_{c4}$ , respectively are: $P_{c4}=\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0\\ 1 & 2 & 1\end{array}\right]$ and $Q_{c4}=\left[ \begin{array}{ccc}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1\end{array}\right]$

In general, $P_{c4}=\left[ \begin{array}{ccccc} 1 & 0 & 0 & \ldots & 0\\ 1 & 1 & 0 & \ldots & 0 \\ 1 & 2 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \ldots & \ldots & \ldots & 1\end{array}\right]$ and $Q_{c4}= \left[ \begin{array} {ccccc} 1 & 0 & \ldots & \ldots & 0 \\ 0 & 1 & 0 & \ldots & 0 \\ 0 & -1 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \ldots & \ldots & \ldots & \ldots & 1\end{array}\right]$ , where both the general matrices $P_{c4}$ and $Q_{c4}$ are of dimensions $n \times n$ .

$P_{c4}$ , a lower triangular matrix can be easily generated as:

$p_{c4}(i,i)=1$ ; $p_{c4}(i,j) = p_{c4}(i-1,j) + p_{c4}(i-1,j-1)$ .

and $Q_{c4}$ , also a lower triangular matrix can be easily generated as:

$q_{c4}(i,i)=1$ ; and $q_{c4}(i,1)=0$ when $i \neq 1$ ; and

$q_{c4}(i,j) = [|| Q_{c4}(i-1,j)+ |Q_{c4}(i-1,j-1)|] \times (-1)^{i+j}$ .

Thus, $P_{c4}(P_{4}EQ_{4})Q_{c4}$ finishes the process of bilinear transformation. Steps 2 and 3 can be combined so that the algorithm reduces to three steps only.

If the original polynomial is non-monic (that is, $a_{n} \neq 1$ ), then multiplying the final tranformed polynomial by $b_{0}a_{n}$ restores it to the standard form.

III. Stability considerations:

In the $\omega$ plane, the Schwarz canonical approach can be applied as an algorithm directly to the canonical form of bilinear transformation of the polynomial obtained previously because a companion form is a non-derogatory matrix.

IV. An Example:

$F_{0}(z) = 2z^{4} + 4z^{3} + 6z^{2} + 5z +1$

$F(z) = z^{4} + 2z^{3} + 3z^{2} + 2.5z + (0.5)z$

$b_{0} = a_{0} + a_{1} + a_{2} + 1 =9$

$b_{1} = a_{1} + a_{2} + a_{3} + 1 = 8.5$

Similarly, $b_{2}=6$ and $b_{3}=3$

$B=P_{1}AQ_{1}= \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ -9 & -8.5 & -6 & -3\end{array}\right]$

$C = \left[ \begin{array}{cccc}1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1\end{array}\right] \times \left[ \begin{array}{cccc}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ -9 & -8.5 & -6 & -3\end{array}\right] \times \left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1\end{array}\right]$

Hence, $C = \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ -9 & -18.5 & -15 & -6\end{array}\right]$

$H(s+1)=s^{4}+6s^{3} + 15s^{2}+18.5s+9$

Steps 2 and 3:

$E=\left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ -2^{4}/9 & -2^{3}(6)/9 & -2^{2}(15)/9 & (-2)(18.5)/9\end{array}\right] = \left[ \begin{array}{cccc}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ (-16/9) & (-48/9) & (-60/9) & (-37/9)\end{array}\right]$

Step 4:

$C_{0}=16/9$ , $C_{1}=48/9$ , $60/9$ , $37/9$ .

$-\hat{C_{0}}=0$ , $-\hat{C_{1}}=-16/9$ , $-\hat{C_{2}}=-32/9$ , $-\hat{C_{3}}=-28/9$

$P_{c4}(P_{4}EQ_{4})Q_{c4}= \left[ \begin{array}{cccc}1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1\end{array}\right] \times \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & -16/9 & -32/9 & -28/9\end{array}\right] \times \left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 1 & -2 & 1\end{array}\right]$ , so we get

$P_{c4}(P_{4}EQ_{4})Q_{c4}=\left[ \begin{array}{cccc}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & -3/9 & -3/9 & -1/9\end{array}\right]$

The final monic polynomial is $s^{4} + (1/9)s^{3}+(3/9)s^{2} + (3/9)s$ , and multiplying it by $b_{0}a_{n}$ , that is, $9 \times 2 =18$ , restores it to the non-monic form:

$18s^{4}+2s^{3}+6s^{2}+6s$

V. Conclusion:

Since the operator matrices have lesser non-zero elements, storage requirements are lesser. The computational complexity should reduce for higher-order systems because the non-zero elements lesser manipulations are also lesser, besides lesser storage requirements. Additionally, the second and third steps can be combined giving a three step method only. Thus, the algorithm easily achieves bilinear transformation, especially, for higher systems compared to other available methods hitherto.

VI. References:

Davies, A.C., “Bilinear Transformation of Polynomials”, IEEE Automatic Control, Nov. 1974.
Barnett and Storey, “Matrix Methods in Stability Theory”, Thomas Nelson and Sons Ltd.
Datta, B. N., “A Solution of the Unit Circle Problem via the Schwarz Canonical Form”, IEEE Automatic Control, Volume AC 27, No. 3, June 1982.
Parthsarthy R., and Jaysimha, K. N., “Bilinear Transformation by Synthetic Division”, IEEE Automatic Control, Volume AC 29, No. 6, June 1986.
Jury, E.I., “Theory and Applications of the z-Transform Method”, John Wiley and Sons Inc., 1984.

Concepts and Problems of DSP & Applied Math

Discussion about concepts, algorithms and problems of DSP, Digital Control, Digital Communications, Error Control Coding and Applied Mathematics.

Bilinear Transformation via Synthetic Division: The Matrix Method

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply