Frequency Domain Convolution of Rational Transfer Functions

Ishan Kar

Prospect High School, Saratoga, USA.

DOI: 10.4236/jamp.2022.106144                

Abstract

The convolution of two rational transfer functions is also rational, but a formula for the convolution has never been derived. This paper introduces a formula for the convolution of two rational functions in the frequency domain by two new methods. The first method involves a partial fraction expansion of the rational transfer functions where the problem gets reduced to the sum of the convolution of the partial fractions of the two functions, each of which can be solved by a new formula. Since the calculation of the roots of a high-order polynomial can be very time-consuming, we also demonstrate new methods for performing the convolution without calculating these roots or undergoing partial fraction expansion. The convolution of two rational Laplace transform denominators can be calculated using their resultant, while that of the two rational Z-transform transfer functions can be found using Newton’s identities. The numerator can be easily found by multiplying the numerator with the initial values of the power series of the result.

Keywords

Z-Transform, Laplace Transform, Frequency Domain, Convolution

1. Introduction

1.1. Convolution of Rational Transfer Functions

Z-transform [1] or the frequency domain representation of a discrete-time signal $a\left[n\right]$ is the transfer function $A\left(z\right)$ defined as

$A\left(z\right)=\mathbb{Z}\left[a\left[n\right]\right]={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}a\left[n\right]z^{-n}$

where n is an integer and $z={\text{e}}^s$ is a complex variable. $A\left(z\right)$ exists if and only if the argument z is inside the region of convergence (ROC) in the z-plane, which is determined by $\left|z\right|=\left|{\text{e}}^s\right|={\text{e}}^{\sigma }>R$ (radius of a circle), the magnitude of variable z. The convolution [2] [3] [4] [5] in the frequency domain of two transfer functions

$A\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}a\left[n\right]z^{-n}\left(\left|z\right|>R_a\right)$

and

$B\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}b\left[n\right]z^{-n}\left(\left|z\right|>R_b\right)$

is the transfer function defined by

$\begin{array}{c}\mathbb{Z}\left[a\left[n\right]b\left[n\right]\right]=A\left(z\right)\ast B\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}a\left[n\right]b\left[n\right]z^{-n}\\ =\frac{1}{2\pi i}{\displaystyle {\oint }_C}A\left(s\right)B\left(\frac{z}{s}\right)\frac{\text{d}s}{s},\left|z\right|>R_a{R}_b\end{array}$

where C is a simple contour analytic at the origin with $R_a<\left|s\right|<\frac{\left|z\right|}{R_b}$. Convolution in the frequency domain is different from the product of $A\left(z\right)$ and $B\left(z\right)$, where the coefficient of $z^{-n}$ is the convolution of the sequences of $a\left[n\right]$ and $b\left[n\right]$ or convolution in time domain.

For example if $A\left(z\right)=\frac{1}{1-2z^{-}}=1+2z^{-}+2^2{z}^{-2}+\cdots$ and $B\left(z\right)=\frac{1}{1-3z^{-}}=1+3z^{-}+3^2{z}^{-2}+\cdots$ then

$A\left(z\right)\ast B\left(z\right)=1+2\cdot 3z^{-}+2^2\cdot 3^2{z}^{-2}\cdots ={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}{2}^n{3}^n{z}^{-n}=\frac{1}{1-6z^{-}}.$

The Z-transform is considered as a discrete-time equivalent of the Laplace transform, which is very useful for solving differential equations. Given a function $f\left(t\right)$, the Laplace transform gives us the transfer function $F\left(s\right)=\mathcal{L}\left\{f\left(t\right)\right\}={\displaystyle {\int }_0^{\infty }}{\text{e}}^{-st}f\left(t\right)\text{d}t$. Frequency domain convolution [4] of two transfer functions $F\left(s\right)$ and $G\left(s\right)$ is the Laplace transform of the product of their time domain signals $f\left(t\right)g\left(t\right)$ and

$F\left(s\right)\ast G\left(s\right)=\mathcal{L}\left\{f\left(t\right)g\left(t\right)\right\}=\frac{1}{2\pi i}{\displaystyle {\oint }_C}F\left(z\right)G\left(s-z\right)\text{d}z.$

The abscissa of convergence for the real value of s, $Re\left(s\right)>{\sigma }_f+{\sigma }_g$, where ${\sigma }_f$ and ${\sigma }_g$ are the axis of convergence for $f\left(t\right)$ and $g\left(t\right)$ respectively. For example

if $A\left(s\right)=\frac{1}{s-3}$ and $B\left(s\right)=\frac{1}{s-4}$, $a\left(t\right)={\text{e}}^{3t}u\left(t\right)$ and $b\left(t\right)={\text{e}}^{4t}u\left(t\right)$. $a\left(t\right)b\left(t\right)={\text{e}}^{7t}u\left(t\right)$ with $A\left(s\right)\ast B\left(s\right)=\frac{1}{s-7}$.

Convolution is commutative and distributive over addition. That is, for rational functions $A\left(z\right)\mathrm{,}B\left(z\right)$ and $C(\; z\; )$

$\text{Commutative}:A\left(z\right)\ast B\left(z\right)=B\left(z\right)\ast A(\; z\; )$

$\text{Distributive}:A\left(z\right)\ast \left\{B\left(z\right)+C\left(z\right)\right\}=A\left(z\right)\ast B\left(z\right)+A\left(z\right)\ast C\left(z\right)\mathrm{.}$

1.2. Prior Methods

The analytic solution of convolution in frequency domain is complex involving Cauchy’s residue theorem [4] [6] [7]. For the Z-transform:

$\frac{1}{2\pi i}{\displaystyle {\oint }_C}A\left(s\right)B\left(\frac{z}{s}\right)\frac{\text{d}s}{s}={\displaystyle \underset{i=1}{\overset{k}{\sum }}}re{s}_{s=s_i}\left\{\frac{A\left(s\right)B\left(x/s\right)}{s}\right\}\mathrm{,}$

and for the Laplace transform:

$\frac{1}{2\pi i}{\displaystyle {\oint }_C}F\left(z\right)G\left(s-z\right)\text{d}z={\displaystyle \underset{i=1}{\overset{k}{\sum }}}re{s}_{z=z_i}\left\{F\left(z\right)G\left(s-z\right)\right\}\mathrm{.}$

The integral can be evaluated in terms of residues where k is the number of different poles $s_i$ of $A\left(s\right)B\left(z/s\right)/s$ and $z_i$ of $F\left(z\right)G\left(s-z\right)$ within C. Residue computation is complex for pole $s_i$ of multiplicity $m>1$.

$re{s}_{s=s_i}\left\{\frac{A\left(s\right)B\left(z/s\right)}{s}\right\}=\frac{1}{\left(m-1\right)!}\underset{s\to s_i}{lim}\frac{{\text{d}}^{m-1}}{\text{d}{s}^{m-1}}\left[{\left(s-s_i\right)}^m\frac{A\left(s\right)B\left(z/s\right)}{s}\right].$ (1)

Salvy and Zimmerman [8] describe a Maple implementation of a method for computing the differential equations satisfied by convolution of the holonomic power series (series that satisfy a linear differential equation with polynomial coefficients). Shapiro [9] and Kim [10] [11] gave a combinatorial proof using tilings of the convolution of generating functions for Chebyshev polynomials.

Although it has been proven by partial fraction expansion [5] [12] that the convolution of two rational transfer functions is also rational, an explicit formula for the product of two rational transfer functions has not been derived. In the next section, we present a new method for convolution in the frequency domain of two rational transfer functions. Partial fraction expansion is used to break down a rational function to its partial fractions. This simplifies the problem into the convolution of the partial fractions of the rational transfer functions by the distributive property. As the computations needed are in the order of the product of the number of partial fractions, it can be heavy for a large number of partial fractions. In Section 3, I have found a new method for convolution in the frequency domain of Laplace transform by using the resultant of two polynomials without performing partial fraction expansion. The same is done in Section 3 for Z-transform by using Newton’s identities.

2. The New Method with Partial Fraction Expansion

2.1. Partial Fraction Expansion of the Rational Functions

A transfer function is a way of encoding an infinite sequence of numbers by treating them as the coefficients of a power series. A rational Z-transform transfer function $A\left(z\right)$, where the degree of the numerator is less than the degree of the denominator, has a unique partial fraction expansion [13] to represent $A\left(z\right)$ as a linear combination of

$A\left(z\right)={\displaystyle \underset{i=1}{\overset{M}{\sum }}}\left[\frac{A_{i,0}}{1-a_i{z}^{-}}+\frac{A_{i,1}}{{\left(1-a_i{z}^{-}\right)}^2}+\cdots +\frac{A_{i,m}}{{\left(1-a_i{z}^{-}\right)}^{m+1}}\right],$

where $1/a_i$ are the roots of $A\left(z\right)$ and $A_{i\mathrm{,}m}$ is a constant. The convolution after the partial fraction expansion of two rational functions $A\left(z\right)\mathrm{,}B\left(z\right)$ is given as

$A\left(z\right)\ast B\left(z\right)$ (2)

$={\displaystyle \underset{i=1}{\overset{M}{\sum }}}{\displaystyle \underset{m=0}{\overset{m_i}{\sum }}}\frac{A_{i,m}}{{\left(1-a_i{z}^{-}\right)}^{m+1}}\ast {\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \underset{n=0}{\overset{n_j}{\sum }}}\frac{B_{j,n}}{{\left(1-b_j{z}^{-}\right)}^{n+1}}$ (3)

$={\displaystyle \underset{i=1}{\overset{M}{\sum }}}{\displaystyle \underset{m=0}{\overset{m_i}{\sum }}}{\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \underset{n=0}{\overset{n_j}{\sum }}}\frac{A_{i,m}}{{\left(1-a_i{z}^{-}\right)}^{m+1}}\ast \frac{B_{j,n}}{{\left(1-b_j{z}^{-}\right)}^{n+1}}.$ (4)

where $1/a_i$ are the roots of $A\left(z\right)$ with multiplicity $m+1$, $1/b_j$ are the roots of $B\left(z\right)$ with multiplicity n, $A_{i\mathrm{,}m}$ and $B_{j\mathrm{,}n}$ are constants. Since the convolution of two rational transfer functions $A\left(z\right)$ and $B\left(z\right)$ is the sum of the convolution of the terms in their partial fraction expansion, it is sufficient to find a formula for $\frac{1}{{\left(1-a{z}^{-}\right)}^{m+1}}\ast \frac{1}{{\left(1-b{z}^{-}\right)}^{n+1}}$ to find the solution for $A\left(z\right)\ast B\left(z\right)$.

The new method can also be used to find the convolution of two rational Laplace transform transfer functions $F\left(s\right)$ and $G\left(s\right)$. The convolution after the partial fraction expansion of two rational function $F\left(s\right)$ and $G\left(s\right)$ with roots $f_i$ with multiplicity $m+1$ and $g_j$ with multiplicity $n+1$ respectively and constants $F_{i\mathrm{,}m}$, $G_{j\mathrm{,}n}$ is:

$F\left(s\right)\ast G\left(s\right)={\displaystyle \underset{i,m}{\sum }}\frac{F_{i,m}}{{\left(s-f_i\right)}^{m+1}}\ast {\displaystyle \underset{j,n}{\sum }}\frac{G_{j,n}}{{\left(s-g_j\right)}^{n+1}}$ (5)

$={\displaystyle \underset{i,j,n,m}{\sum }}\frac{F_{i,m}}{{\left(s-f_i\right)}^{m+1}}\ast \frac{G_{j,n}}{{\left(s-g_j\right)}^{n+1}}.$ (6)

Again, it is sufficient to find a formula for $\frac{1}{{\left(s-f\right)}^{m+1}}\ast \frac{1}{{\left(s-g\right)}^{n+1}}$ to find the solution for $F\left(s\right)\ast G\left(s\right)$.

2.2. Convolution of the Partial Fractions of Laplace Transform

The last equation $\frac{1}{{\left(s-f\right)}^{m+1}}\ast \frac{1}{{\left(s-g\right)}^{n+1}}$ can be derived by observing that

$\frac{1}{{\left(s-f\right)}^{m+1}}\ast \frac{1}{{\left(s-g\right)}^{n+1}}=\mathcal{L}\left\{{\text{e}}^{ft}\frac{t^m}{m!}\right\}\ast \mathcal{L}\left\{{\text{e}}^{gt}\frac{t^n}{n!}\right\}$ (7)

$=\mathcal{L}\left\{{\text{e}}^{\left(f+g\right)t}\frac{t^{n+m}}{n!m!}\right\}=\frac{\left(\begin{array}{c}n+m\\ m\end{array}\right)}{{\left(s-f-g\right)}^{n+m+1}}$ (8)

From this equation:

$F\left(s\right)\ast G\left(s\right)={\displaystyle \underset{i,j,n,m}{\sum }}\frac{F_{i,m}}{{\left(s-f_i\right)}^{m+1}}\ast \frac{G_{j,n}}{{\left(s-g_j\right)}^{n+1}}={\displaystyle \underset{i,j,n,m}{\sum }}\frac{F_{i,m}{G}_{j,n}}{{\left(s-f_i-g_j\right)}^{m+n+1}}.$ (9)

Example of Convolution of Laplace Transfer Functions

In my new method using partial fraction expansion, given two rational transfer functions, we can find their convolution by following three simple algebraic steps. The two rational functions at first undergo a partial fraction expansion. The problem gets reduced to the sum of the convolution of the partial fractions of the two functions. Convolution of each partial fraction is obtained by using the formula derived in Equations (8) and (12).

From a simple example of Laplace transfer functions, we do a partial fraction expansion of

$F\left(s\right)=\frac{s}{s^2-3s+2}=\frac{s}{\left(s-1\right)\left(s-2\right)}=\frac{2}{s-2}-\frac{1}{s-1}$

and

$G\left(s\right)=\frac{1}{s-3}.$

Convolution of the partial fraction using the fact $\frac{1}{s-a}\ast G\left(s\right)=G\left(s-a\right)$, we get

$\frac{2}{s-2}\ast \frac{1}{s-3}=\frac{2}{s-5}$

and

$\frac{1}{s-1}\ast \frac{1}{s-3}=\frac{1}{s-4}.$

Constructing the transfer function by the sum of each convolution of the partial fractions we get

$F\left(s\right)\ast G\left(s\right)=\frac{2}{s-5}-\frac{1}{s-4}=\frac{s-3}{s^2-9s+20}.$

Note that the partial fractions obtained as a result of convolution can be used to find the time domain function by inverse Laplace transform. The fact that they already exist as partial fractions makes finding the inverse transform easy.

2.3. Convolution of the Partial Fractions of Z-Transform

The convolution of the partial fractions of the Z-transform can be proved by combinatorics. For simple convolution ( $m=n=0$ ) it is easy to observe

$\frac{1}{1-a{z}^{-}}\ast \frac{1}{1-b{z}^{-}}={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}{\left(ab{z}^{-}\right)}^n=\frac{1}{1-ab{z}^{-}}.$ (10)

Also, note that $\frac{1}{1-a{z}^{-}}\ast F\left(z\right)=F\left(az\right)$.

For $m,n>0$, the binomial theorem gives us

$\frac{1}{{\left(1-a{z}^{-}\right)}^{m+1}}={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\left(\begin{array}{c}m+k\\ m\end{array}\right)a^k{z}^{-k}$

and

$\frac{1}{{\left(1-b{z}^{-}\right)}^{n+1}}={\displaystyle \underset{j=0}{\overset{\infty }{\sum }}}\left(\begin{array}{c}n+j\\ n\end{array}\right)b^j{z}^{-j}$

where $n\mathrm{,}m\in {\mathbb{Z}}_{\ge 0}$. Using the binomial [14] identity

$\left(\begin{array}{c}n+k\\ n\end{array}\right)\left(\begin{array}{c}m+k\\ m\end{array}\right)={\displaystyle \underset{j=0}{\overset{\min \left(m,n\right)}{\sum }}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}m\\ j\end{array}\right)\left(\begin{array}{c}n+m+k-j\\ n+m\end{array}\right)$

where $\min \left(m,n\right)$ is the minimum of m and n.

$\begin{array}{l}\frac{1}{{\left(1-a{z}^{-}\right)}^{n+1}}\ast \frac{1}{{\left(1-b{z}^{-}\right)}^{m+1}}={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\left(\begin{array}{c}n+k\\ n\end{array}\right)\left(\begin{array}{c}m+k\\ m\end{array}\right)a^k{b}^k{z}^{-k}\\ ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\displaystyle \underset{j=0}{\overset{m}{\sum }}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}m\\ j\end{array}\right)\left(\begin{array}{c}n+m+k-j\\ n+m\end{array}\right)a^k{b}^k{z}^{-k}\\ ={\displaystyle \underset{j=0}{\overset{\min \left(m,n\right)}{\sum }}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}m\\ j\end{array}\right){\left(ab{z}^{-}\right)}^j{\displaystyle \underset{r}{\sum }}\left(\begin{array}{c}n+m+r\\ n+m\end{array}\right){\left(ab{z}^{-}\right)}^r\\ =\frac{{\displaystyle {\sum }_{j=0}^m}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}m\\ j\end{array}\right){\left(ab{z}^{-}\right)}^j}{{\left(1-ab{z}^{-}\right)}^{n+m+1}}=\frac{{\left(1+a{z}^{-}\right)}^m\ast {\left(1+b{z}^{-}\right)}^n}{{\left(1-ab{z}^{-}\right)}^{m+n+1}}\end{array}$ (11)

Putting this equation back into Equation (4) we will get the formula for the convolution of two rational functions.

$A\left(z\right)\ast B\left(z\right)={\displaystyle \underset{i,j,m,n}{\sum }}\frac{A_{i,n+1}{B}_{j,m+1}{\left(1+a_i{z}^{-}\right)}^n\ast {\left(1+b_j{z}^{-}\right)}^m}{{\left(1-a_i{b}_j{z}^{-}\right)}^{n+m+1}}$ (12)

Example of Convolution of Z-Transform Transfer Functions

An example of the convolution of two Z-transform transfer functions is shown in three simple steps.

Step 1: Partial Fraction Expansion

$A\left(z\right)=\frac{9z^{-2}-8z^{-1}+3}{-9z^{-3}+15z^{-2}-7z^{-1}+1}=\frac{1}{1-z^{-1}}+\frac{2}{{\left(1-3z^{-1}\right)}^2}$

$B\left(z\right)=\frac{4z^{-1}-1}{-8z^{-3}+12z^{-2}-6z^{-1}+1}=\frac{-2}{{\left(1-2z^{-1}\right)}^2}+\frac{1}{{\left(1-2z^{-1}\right)}^3}$

Step 2: Convolution of the Partials using Equation (11).

$\frac{1}{1-z^{-1}}\ast \frac{-2}{{\left(1-2z^{-1}\right)}^2}=\frac{-2}{{\left(1-2z^{-1}\right)}^2},$

$\frac{2}{{\left(1-3z^{-1}\right)}^2}\ast \frac{-2}{{\left(1-2z^{-1}\right)}^2}=\frac{-4\left(1+6z^{-1}\right)}{{\left(1-6z^{-1}\right)}^3}$

$\frac{1}{1-z^{-1}}\ast \frac{1}{{\left(1-2z^{-1}\right)}^3}=\frac{1}{{\left(1-2z^{-1}\right)}^3},$

$\frac{1}{{\left(1-2z^{-1}\right)}^3}\ast \frac{2}{{\left(1-3z^{-1}\right)}^2}=\frac{2\left(1+12z^{-1}\right)}{{\left(1-6z^{-1}\right)}^4}$

Step 3: Sum of the Hadamard Product of the Partials

$\begin{array}{l}A\left(z\right)\ast B\left(z\right)\\ =\frac{-2}{{\left(1-2z^{-1}\right)}^2}+\frac{-4\left(1+6z^{-1}\right)}{{\left(1-6z^{-1}\right)}^3}+\frac{1}{{\left(1-2z^{-1}\right)}^3}+\frac{2\left(1+12z^{-1}\right)}{{\left(1-6z^{-1}\right)}^4}\\ =\frac{4032z^{-5}-3216z^{-4}+1168z^{-3}-336z^{-2}+64z^{-1}-3}{{\left(1-6z^{-1}\right)}^4{\left(1-2z^{-1}\right)}^3}\end{array}$

As the degree of the transfer functions increase, this method can get very compute intensive. In the next section, we introduce new methods without undergoing partial fraction expansion. The denominator of the convolution of two Laplace transfer function can be found by the Resultant of polynomials while for the Z transfer functions, Newton’s identities will be used. The numerator can then be found easily from the initial values.

3. A New Method for Convolution of Laplace Transfer Functions Using the Resultant

If we assume that $F\left(s\right)=\frac{F_n\left(s\right)}{F_d\left(s\right)}$ and $G\left(s\right)=\frac{G_n\left(s\right)}{G_d\left(s\right)}$ are rational functions, then we can factor the denominator as

$F_d\left(s\right)={\displaystyle \underset{i=0}{\overset{m}{\sum }}}{\alpha }_i{s}^i={\alpha }_m{\displaystyle \underset{i=1}{\overset{m}{\prod }}}\left(s-a_i\right)$

and

$G_d\left(s\right)={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\beta }_j{s}^j={\beta }_n{\displaystyle \underset{j=1}{\overset{n}{\prod }}}\left(s-b_j\right)$

respectively. Here ${\alpha }_i\mathrm{,}{\beta }_j$ are the coefficients and $a_i\mathrm{,}{b}_j$ are the roots of $A\left(s\right)$ and $B\left(s\right)$ respectively. By using $\frac{1}{s-a_i}\ast \frac{1}{s-b_j}=\frac{1}{s-a_i-b_j}$ from Equation (8), their convolution is given by

$\frac{F_n\left(s\right)}{{\alpha }_m{\displaystyle {\prod }_{i=1}^m\left(s-a_i\right)}}\ast \frac{G_n\left(s\right)}{{\beta }_n{\displaystyle {\prod }_{j=1}^n\left(s-b_j\right)}}=\frac{N\left(s\right)}{{\alpha }_m^n{\beta }_n^m{\displaystyle {\prod }_{i=1}^m{\displaystyle {\prod }_{j=1}^n\left(s-a_i-b_j\right)}}}$

where $N\left(s\right)$ is the numerator of the result. The objective is to find the denominator of ${\alpha }_m^n{\beta }_n^m{\displaystyle {\prod }_{i=1}^m{\displaystyle {\prod }_{j=1}^n\left(s-a_i-b_j\right)}}$ without finding the roots, i.e., only with the coefficients ${\alpha }_i$ and ${\beta }_j$.

Given two polynomials $F_d\left(s\right)$ and $G_d\left(s\right)$, their resultant relative to the variable s is a polynomial over the field of coefficients of $F_d\left(s\right)$ and $G_d\left(s\right)$ defined as

$\text{Res}\left(F_d,G_d,s\right)={\alpha }_m^n{\beta }_n^m{\displaystyle \underset{i,j}{\prod }}\left(a_i-b_j\right).$

The resultant of two polynomials is computed by the determinant of the corresponding Sylvester matrix [15] of size $\left(n+m\right)\times \left(n+m\right)$

$\text{Syl}\left(F_d,G_d\right)=\underset{m+n}{\underset{︸}{\left[\begin{array}{cccc}{\alpha }_m& \cdots & {\alpha }_0& \\ \ddots & & \ddots & \\ & {\alpha }_m& \cdots & {\alpha }_0\\ {\beta }_n& \cdots & {\beta }_0& \\ \ddots & & \ddots & \\ & {\beta }_n& \cdots & {\beta }_0\end{array}\right]}}\begin{array}{c}\begin{array}{c}\\ \\ \end{array}\}n\\ \begin{array}{c}\\ \\ \end{array}\}m\end{array}$

If we replace s by $-s+u$ in $F_d\left(s\right)$ we get

$F_d\left(u-s\right)={\left(-1\right)}^m{\alpha }_m{\displaystyle \underset{i=1}{\overset{m}{\prod }}}\left(s-u+a_i\right)={\displaystyle \underset{i=0}{\overset{m}{\sum }}}{\alpha }_i{\left(-s+u\right)}^i$ (13)

$G_d\left(s\right)={\beta }_n{\displaystyle \underset{j=1}{\overset{m}{\prod }}}\left(s-b_j\right)={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\beta }_j{s}^j$ (14)

$\text{Res}\left(F_d\left(u-s\right),G_d\left(s\right),s\right)={\alpha }_m^n{\beta }_n^m{\displaystyle \underset{i=1}{\overset{m}{\prod }}}{\displaystyle \underset{j=1}{\overset{n}{\prod }}}\left(u-a_i-b_j\right)=H_d\left(u\right).$ (15)

Replacing u with s in $H_d\left(u\right)$, we get the denominator of $F\left(s\right)\ast G\left(s\right)$. Now that we know the denominator, we can find the numerator by computing enough terms of the series expansion of $F\left(s\right)\ast G\left(s\right)$ and multiplying them with the denominator obtained from the resultant. For Laplace transforms, it’s better to expand the functions using negative powers of s. By using

$\frac{1}{s-\zeta }={\displaystyle {\sum }_k}\frac{{\zeta }^k}{s^{k+1}}$, the series expansion of

$F\left(s\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{f_k}{s^{k+1}}$

and

$G\left(s\right)={\displaystyle \underset{l=0}{\overset{\infty }{\sum }}}\frac{g_l}{s^{l+1}}$

then

$F\left(s\right)\ast G\left(s\right)={\displaystyle \underset{k,l}{\sum }}\frac{f_k}{s^{k+1}}\ast \frac{g_l}{s^{l+1}}.$

Using the fact that the convolution of two Laplace transfer functions is equal to the Laplace transform of product of two functions and $\mathcal{L}\left\{t^k\right\}=\frac{k!}{s^{k+1}}$ we have

$\frac{1}{s^{k+1}}\ast \frac{1}{s^{l+1}}=\mathcal{L}\left\{\frac{t^k}{k!}\frac{t^l}{l!}\right\}=\left(\begin{array}{c}k+l\\ l\end{array}\right)\frac{1}{s^{k+l+1}}.$

So,

$F\left(s\right)\ast G\left(s\right)={\displaystyle \underset{k,l}{\sum }}\left(\begin{array}{c}k+l\\ l\end{array}\right)\frac{f_k{g}_l}{s^{k+l+1}}={\displaystyle \underset{j=0}{\overset{\infty }{\sum }}}{\displaystyle \underset{n=0}{\overset{j}{\sum }}}\left(\begin{array}{c}n\\ l\end{array}\right)f_{n-l}{g}_l{s}^{-\left(n+1\right)}.$ (16)

Multiplying the denominator of $F\left(s\right)\ast D\left(s\right)$, which is

$H_d\left(s\right)={\alpha }_m^n{\beta }_n^m{\displaystyle \underset{i=1}{\overset{m}{\prod }}}{\displaystyle \underset{j=1}{\overset{n}{\prod }}}\left(s-a_i-b_j\right)={\displaystyle \underset{k=0}{\overset{nm}{\sum }}}{ℌ}_k{s}^k$

with the first $nm$ terms of the series expansion of $F\left(s\right)\ast D\left(s\right)$ gives us the numerator with the result

$F\left(s\right)\ast G\left(s\right)=H\left(s\right)=\frac{{\displaystyle {\sum }_{k=0}^{nm}{\displaystyle {\sum }_{j=0}^{k-1}{\displaystyle {\sum }_{l=0}^j\left(\begin{array}{c}j\\ l\end{array}\right){ℌ}_k{f}_{j-l}{g}_l{s}^k}}}}{{\displaystyle {\sum }_{k=0}^{nm}{ℌ}_k{s}^k}}$ (17)

As a simple example, we have

$F\left(s\right)=\frac{s}{s^2-3s+2}=\frac{s}{\left(s-1\right)\left(s-2\right)}$

and

$G\left(s\right)=\frac{1}{s-3}.$

Computing the determinant of the Sylvester matrix of modified $F_d\left(u-s\right)=s^2+\left(3-2u\right)s+\left(u^2-3u+2\right)$ and $G_d\left(s\right)=s-3$, we find

$\left|\begin{array}{ccc}1& 3-2u& u^2-3u+2\\ 1& -3& 0\\ 0& 1& -3\end{array}\right|=u^2-9u+20.$

So the denominator is $s^2-9s+20$. The series expansion of $F\left(s\right)$ and $G\left(s\right)$ in negative powers of s are

$F\left(s\right)=\frac{1}{s}+\frac{3}{s^2}+\frac{7}{s^3}+\frac{15}{s^4}+O\left(s^{-5}\right)$

$G\left(s\right)=\frac{1}{s}+\frac{3}{s^2}+\frac{9}{s^3}+\frac{27}{s^4}+O\left(s^{-5}\right)$

Then using Equation (16) we find that

$F\left(s\right)\ast G\left(s\right)=\frac{1}{s}+\frac{6}{s^2}+\frac{34}{s^3}+\frac{186}{s^4}+O\left(s^{-5}\right)\mathrm{.}$

Multiplying this with the denominator $s^2-9s+20$ by using Equation (17), we get the result

$F\left(s\right)\ast G\left(s\right)=H\left(s\right)=\frac{s-3}{s^2-9s+20}.$

4. A New Method for Z-Transform Using Newton’s Identity

Just like the Laplace transform, the convolution of two rational Z-transform transfer functions (Equation (4))

$A\left(z\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}a\left[k\right]z^{-k}=\frac{A_n\left(z\right)}{{\displaystyle {\prod }_{i=1}^m\left(1-a_i{z}^{-}\right)}}=\frac{A_n\left(z\right)}{{\displaystyle {\sum }_{s=0}^m{\alpha }_s{z}^{-s}}},$

$B\left(z\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}b\left[k\right]z^{-k}=\frac{B_n\left(z\right)}{{\displaystyle {\prod }_{j=1}^n\left(1-b_j{z}^{-}\right)}}=\frac{B_n\left(z\right)}{{\displaystyle {\sum }_{t=0}^n{\beta }_t{z}^{-t}}}$

$A\left(z\right)\ast B\left(z\right)=\frac{A_n\left(z\right)}{{\displaystyle {\prod }_{i=1}^m\left(1-a_i{z}^{-}\right)}}\ast \frac{B_n\left(z\right)}{{\displaystyle {\prod }_{j=1}^n\left(1-b_j{z}^{-}\right)}}$

By using $\frac{1}{1-a_i{z}^{-}}\ast \frac{1}{1-b_j{z}^{-}}=\frac{1}{1-a_i{b}_j{z}^{-}}$ we get ( $N\left(z\right)$ is the numerator)

$A\left(z\right)\ast B\left(z\right)=\frac{N\left(z\right)}{{\displaystyle {\prod }_{i=1}^m{\displaystyle {\prod }_{j=1}^n\left(1-a_i{b}_j{z}^{-}\right)}}}=\frac{N\left(z\right)}{{\displaystyle {\sum }_{k=0}^{nm}{\left(-1\right)}^{-k}{e}_k{z}^{-k}}}$

The denominator ${\displaystyle {\sum }_{k=0}^{nm}}{\left(-1\right)}^{-k}{e}_k{z}^{-k}$ can be found by Newton’s identity [16] [17]. Newtons identity can be stated as

$k{e}_k={\displaystyle \underset{r=1}{\overset{k}{\sum }}}{\left(-1\right)}^{r-1}{e}_{k-r}{p}_r\left\{a_1{b}_1,\cdots ,a_i{b}_j,\cdots ,a_m{b}_n\right\}$

$p_r\left\{a_1{b}_1,\cdots ,a_i{b}_j,\cdots ,a_m{b}_n\right\}={\displaystyle \underset{i,j}{\sum }}{\left(a_i{b}_j\right)}^r={\displaystyle \underset{i}{\sum }}{a}_i^r{\displaystyle \underset{j}{\sum }}{b}_j^r=p_r\left\{a_1,\cdots ,a_m\right\}{p}_r\left\{b_1,\cdots ,b_n\right\}$

Here, $p_r\left\{a_1{b}_1,\cdots ,a_i{b}_j,\cdots ,a_m{b}_n\right\}$ is the r-th power sum of $a_i{b}_j$ and can be expressed as the product of $p_r\left\{a_1,\cdots ,a_m\right\}$ and $p_r\left\{b_1,\cdots ,b_n\right\}$, which are the r-th power sum of $a_i$ and $b_j$ respectively. The values of $p_r\left\{a_1,\cdots ,a_m\right\}$ can be found from the coefficients of the denominators ${\displaystyle {\sum }_{s=0}^m}{\alpha }_s{z}^{-s}$ from the equation

$a_m{p}_r\left\{a_1\mathrm{,}\cdots ,a_m\right\}=(\begin{array}{ll}{\left(-1\right)}^{r-1}r{a}_r+{\displaystyle \underset{i=1}{\overset{r-1}{\sum }}}{\left(-1\right)}^{r-1+i}{a}_{r-i}{p}_i\left\{a_1,\cdots ,a_m\right\}\hfill & \text{for}n\ge r\ge 1\hfill \\ {\displaystyle \underset{i=r-m}{\overset{r-1}{\sum }}}{\left(-1\right)}^{r-1+i}{a}_{r-i}{p}_i\left\{a_1,\cdots ,a_m\right\}\hfill & \text{for}r>n\ge 1\hfill \end{array}$

A similar equation will give us the value of $p_r\left\{b_1,\cdots ,b_n\right\}$ from ${\displaystyle {\sum }_{t=0}^n}{\beta }_t{z}^{-t}$. The numerator $N\left(z\right)$ can be found by multiplying the denominator with the first $nm$ terms of the product of the first $nm$ terms of the series expansion of $A\left(z\right)\ast B\left(z\right)$ gives us the numerator with the result

$A\left(z\right)\ast B\left(z\right)=\frac{{\displaystyle {\sum }_{k=0}^{nm}{\left(-1\right)}^{-k}{e}_k{z}^{-k}}{\displaystyle {\sum }_{k=0}^{nm}a\left[k\right]b\left[k\right]z^{-k}}}{{\displaystyle {\sum }_{k=0}^{nm}{\left(-1\right)}^{-k}{e}_k{z}^{-k}}}.$

An example of the convolution of two Z-transform transfer functions is given below.

$A\left(z\right)=\frac{1}{1-a{z}^{-}-z^{-2}},B\left(z\right)=\frac{1}{1-b{z}^{-}-z^{-2}}$

For the denominators, $1-a{z}^{-}-z^{-2}=\left(1-a_1{z}^{-}\right)\left(1-a_2{z}^{-}\right)$ and $1-b{z}^{-}-z^{-2}=\left(1-b_1{z}^{-}\right)\left(1-b_2{z}^{-}\right)$, where $a_1\mathrm{,}{a}_2$ and $b_1\mathrm{,}{b}_2$ are the corresponding roots of the polynomials.

$p_1\left\{a_1{b}_1,a_1{b}_2,a_2{b}_1,a_2{b}_2\right\}=p_1\left\{a_1,a_2\right\}{p}_1\left\{b_1,b_2\right\}=ab$

$p_2\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=p_2\left\{a_1,a_2\right\}{p}_2\left\{b_1,b_2\right\}=\left(a^2+2\right)\left(b^2+2\right)$

$p_3\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=p_3\left\{a_1,a_2\right\}{p}_3\left\{b_1,b_2\right\}=\left(a^3+3a\right)\left(b^3+3b\right)$

$p_4\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=p_4\left\{a_1,a_2\right\}{p}_4\left\{b_1,b_2\right\}=\left(a^4+4a^2+2\right)\left(b^4+4b^2+2\right)$

Calculating the values of $e_k$ from the $p_1\mathrm{,}{p}_2\mathrm{,}{p}_3$ and $p_4$ from above

$e_0=1,e_1=p_1\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=ab$,

$2e_2=e_1{p}_1\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}-p_2\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=-a^2-b^2-2$,

$3e_3=e_2{p}_1\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}-e_1{p}_2\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}+p_3\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}=3ab$,

$\begin{array}{c}4e_4=e_3{p}_1\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}-e_2{p}_2\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}\\ +e_1{p}_3\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}-p_4\left\{a_1{b}_1,\cdots ,a_2{b}_2\right\}\\ =4.\end{array}$

The denominator is $1-ab{z}^{-}-\left(2+a^2+b^2\right)z^{-2}-ab{z}^{-3}+z^{-4}$. Multiplying this with the initial terms of

$\begin{array}{c}A\left(z\right)\ast B\left(z\right)=1+ab{z}^{-}+\left(a^2+1\right)\left(b^2+1\right)z^{-2}+\left(a^3+2a\right)\left(b^3+2b\right)z^{-3}\\ +\left(a^4+3a^2+1\right)\left(b^4+3b^2+1\right)z^{-4}+\cdots \end{array}$ we get

$A\left(z\right)\ast B\left(z\right)=\frac{1-z^{-2}}{1-ab{z}^{-}-\left(2+a^2+b^2\right)z^{-2}-ab{z}^{-3}+z^{-4}}$

5. Conclusion and Future Work

This novel method provides a three-step process to replace the complex computation of the convolution of two rational transfer functions. If the denominator of the rational function has many roots, then the number of convolution of the partials and the sum of products can grow exponentially. To significantly improve computation speed, we have come up with new methods, where the rational functions do not need to undergo a partial fraction expansion. The denominator of the convolution of two Laplace transfer functions can be found by the resultant of polynomials while for the Z-transform transfer functions, Newton’s identities were used. The numerator can then be found easily from the product of the denominator and the initial terms of the power series expansion of the convolution of the transfer functions. The applications of this method in the field of signal processing are enormous [18]. Novel filters can be designed by the convolution of different transfer functions. Another application is Parseval’s theorem, widely used to find the power spectrum of a signal. The power spectrum can be found by the convolution of two rational transfer functions followed by substituting $z=1$. In recent research, Prodinger [19], Ekhad and Zeilberger [20] have derived convolution identities for Fibonacci, Tribonacci, and k-bonacci numbers using methods that are complicated. My future research will investigate using our methods to simplify the computing for those identities.

Acknowledgements

I would like to thank my advisor Dr. Ira M. Gessel, Professor Emeritus, at Brandeis University for his encouragement and guidance on this research.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Oppenheim, A.V., Willsky, A.S. and Nawab, S.H. (1996) Signals and Systems.2nd Edition, Prentice-Hall, Inc., Upper Saddle River.
[2]	Allouche, J.-P. and France, M.M. (2011) Hadamard Grade of Power Series.Journal of Number Theory, 131, 2013-2022 https://doi.org/10.1016/j.jnt.2011.04.011
[3]	Kliger, I. and Lipinski, W. (1964) The Z Transform of a Product of Two Functions.IEEE Transactions on Automatic Control, 9, 582-583. https://doi.org/10.1109/TAC.1964.1105738
[4]	Poularikas, A.D. (2010) Transforms and Applications Handbook. CRC Press, Boca Raton.
[5]	Stanley, R.P. (2011) Enumerative Combinatorics: Volume 1. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9781139058520
[6]	Hautus, M.L.J. and Klarner, D.A. (1971) The Diagonal of a Double Power Series.Duke Mathematical Journal, 38, 229-235. https://doi.org/10.1215/S0012-7094-71-03829-4
[7]	Pohlen, T. and Müller, J. (2009) The Hadamard Product and Universal Power Series. Universität Trier, Trier.
[8]	Salvy, B. and Zimmermann, P. (1994) GFUN: A Maple Package for the Manipulation of Generating and Holonomic Functions in One Variable.ACM Transactions on Mathematical Software, 20, 163-177. https://doi.org/10.1145/178365.178368
[9]	Shapiro, L.W. (1981) A Combinatorial Proof of a Chebyshev Polynomial Identity.Discrete Mathematics, 34, 203-206. https://doi.org/10.1016/0096-3003(81)90146-6
[10]	Kim, J.H. (2009) Hadamard Products and Tilings. Journal of Integer Sequences, Vol. 12.
[11]	Kim, J.H. (2011) Hadamard Products, Lattice Paths, and Skew Tableaux. Brandeis Univ. https://people.brandeis.edu/gessel/homepage/students/kimthesis.pdf
[12]	Van der Poorten, A.J. (1982) Hadamard Operations on Rational Functions. Secrétariat Mathématique, 10, 1-11. http://www.numdam.org/item/GAU_1982-1983__10_1_A3_0
[13]	Lando, S.K. (2003) Lectures on Generating Functions. American Mathematical Society, Providence. https://doi.org/10.1090/stml/023
[14]	Gessel, I. and Stanton, D. (1985) Short Proofs of Saalschütz’s and Dixon’s Theorems. Journal of Combinatorial Theory, Series A, 87-90. https://doi.org/10.1016/0097-3165(85)90026-3
[15]	Gelfand, I.M., Kapranov, M.M. and Zelevinsky, A.V.M (1994) Discriminants, Resultants, and Multidimensional Determinants. Birkhäuser, Boston. https://doi.org/10.1007/978-0-8176-4771-1
[16]	Tignol, J.P. (2001) Galois’ Theory of Algebraic Equations. World Scientific, Singapore. https://doi.org/10.1142/4628
[17]	Gessel, I. (2019) Algorithm for Computing Hadamard Product of Two Rational Generating Functions, Mathematics Stack Exchange.
[18]	Kar, I. (2020) A New Method to Compute the Z-Transform of a Product of Two Functions. 2020 IEEE 5th International Conference on Signal and Image Processing (ICSIP), Nanjing, 23-25 October 2020, 670-674. https://doi.org/10.1109/ICSIP49896.2020.9339352
[19]	Prodinger, H. (2021) Convolution Identities for Tribonacci Numbers via the Diagonal of a Bivariate Generating Function. Palestine Journal of Mathematics, 10, 440-442.
[20]	Ekhad, S.B. and Zeilberger, D. (2021) Automatic Generation of Convolution Identities for C-Finite Sequences. https://doi.org/10.48550/arXiv.2108.02918