0.13 Least squares design of iir filters  (Page 4/9)

Prony-based equation error linearization

A number of algorithms that consider the approximation of functions in a least-squared sense using rational functions relate to Prony's method. This section summarizes these methods especially in the context of filter design.

Prony's method

The first method considered in this section is due to Gaspard Riche Baron de Prony, a Lyonnais mathematician and physicist which, in 1795, proposed to model the expansion properties of different gases by sums of damped exponentials. His method [link] approximates a sampled function $f\left(n\right)$ (where $f\left(n\right)=0$ for $n<0$ ) with a sum of $N$ exponentials,

where ${\lambda }_k=e^{s_k}$ . The objective is to determine the $N$ parameters $c_k$ and the $N$ parameters $s_k$ in [link] given $2N$ samples of $f\left(n\right)$ .

It is possible to express [link] in matrix form as follows,

System [link] has a Vandermonde structure with $N$ equations, but $2N$ unknowns (both $c_k$ and ${\lambda }_k$ are unknown) and thus it cannot be solved directly. Yet the major contribution of Prony's work is to recognize that $f\left(n\right)$ as given in [link] is indeed the solution of a homogeneous order- $N$ Linear Constant Coefficient Difference Equation (LCCDE) [link] given by

with $a_0=1$ . Since $f\left(n\right)$ is known for $0\le n\le 2N-1$ , we can extend [link] into an ( $N\times N$ ) system of the form

which we can solve for the coefficients $a_p$ . Such coefficients are then used in the characteristic equation [link] of [link] ,

The $N$ roots ${\lambda }_k$ of [link] are called the characteristic roots of [link] . From the ${\lambda }_k$ we can find the parameters $s_k$ using $s_k=ln{\lambda }_k$ . Finally, it is now possible to solve [link] for the parameters $c_k$ .

The method described above is an adequate representation of Prony's original method [link] . More detailed analysis is presented in [link] , [link] , [link] , [link] and [link] . Prony's method is an adequate algorithm for interpolating $2N$ data samples with $N$ exponentials. Yet it is not a filter design algorithm as it stands. Its connection with IIR filter design, however, exists and will be discussed in the following sections.

Padé's method

The work by Prony served as inspiration to Henry Padé, a French mathematician which in 1892 published a work [link] discussing the problem of rational approximation. His objective was to approximate a function that could be represented by a power series expansion using a rational function of two polynomials.

Assume that a function $f\left(x\right)$ can be represented with a power series expansion of the form

Padé's idea was to approximate $f\left(x\right)$ using the function

where

and

The objective is to determine the coefficients $a_k$ and $b_k$ so that the first $M+N+1$ terms of the residual

dissappear (i.e. the first $N+M$ derivatives of $f\left(x\right)$ and $\widehat{f}\left(x\right)$ are equal [link] ). That is, [link] ,

To do this, consider $A\left(x\right)f\left(x\right)=B\left(x\right)$ [link]

By equating the terms with same exponent up to order $M+N+1$ , we obtain two sets of equations,