2
$\begingroup$

Let's say I have the following FIR filter $h[n]$, so the output $y[n]$ for an input $x[n]$ is $$ y[n] = \sum_{k=0}^{m-1}x[n-k]h[k] $$

The inverse of this filter is given by the IIR difference equation

$$ y[n] = \frac{1}{h[0]}\bigg(x[n] - \sum_{k=1}^{m-1}y[n-k]h[k]\bigg) $$

Is there some constraint I can put on the filter taps such that the inverse is stable?

I know that if I keep the zeros of the FIR filter inside the unit circle, then the poles of the inverse filter will also be inside the unit circle implying stability. However, are there more simple constraints I can make on $h[n]$ to ensure the stability of the inverse? I was thinking something like $h[0] > \sum_{k\neq0} h[k]$, but I can't prove stability of that.

$\endgroup$
  • $\begingroup$ Yes. There is some minimum value for the first tap relative to the other taps (probably the sum of their absolute values) that would make your inverse stable. I base this on the Evans root locus of a feedback system $k H(z) / (1 + k H(z))$ where $H(z) = \sum_{k=0}^{n-1} a_k z^{-k}$. That will have a root of multiplicity $n$ at $z = 0$, so for sufficiently high $k$ the system will be guaranteed stable -- and the value of $k$ is related to the weight of the first tap of the filter relative to the weights of the rest. But I can't chase the proof now (and the filter would probably be useless). $\endgroup$ – TimWescott May 5 at 22:48
  • $\begingroup$ Sufficently low $k$? Argh -- it's out there, in Mathmagic land. I can hear its mating cry, and I've found droppings, but I just can't see it yet. $\endgroup$ – TimWescott May 5 at 22:49
  • $\begingroup$ Just a thought: what do you do in the case of a half-band filter, with that $h_0$? $\endgroup$ – a concerned citizen May 8 at 9:49
4
$\begingroup$

The Invertible FIR Filter

A constraint based on the first coefficient alone is developed as follows:

From Cauchy's argument principle any FIR filter that meets the following constraint will be invertible (including marginal invertibility, change $\le$ to $<$ otherwise):

$$\max\left(\arg \left( H(e^{j\omega}) \right)\right)-\min\left(\arg \left( H(e^{j\omega}) \right)\right) \le \pi\tag{1}\label{1}, \space\space \omega \in [\omega_o, \omega_o+\pi) $$

Where:

$H(e^{j\omega}) = \sum_{n=0}^{N-1}h_ne^{-j\omega n}$: Frequency response of FIR filter

$\arg()$ : unwrapped phase of $H(\omega)$

Note: In an earlier version of this post, I had a simpler subset of the above that constrained the absolute value of the phase to not exceed $\pi$, but consider given any such solution that we can rotate the filter response by a fixed angle without effecting invertibility. Thus it is more generally constrained to be that for a FIR with real coefficients, the difference of the unwrapped phase for $\omega \in [0, \pi)$ cannot exceed $\pi$. Extending this to an FIR with complex coefficients, and given that we rotate the filter response (which shifts the frequency response by a fixed amount), results in the generalized constraint above applicable to any interval over $\pi$ in frequency.

Thus to constrain the first coefficient $h_o$ we can derive from $\ref{1}$:

$$\arg( h_0) + \max\left(\arg\left(\sum_{n=1}^{N-1}h_ne^{-j\omega n} \right)\right)- \min\left(\arg\left(\sum_{n=1}^{N-1}h_ne^{-j\omega n} \right)\right) \le \pi\tag{2}\label{2}$$

Which shows the complexity of a constraint based on the first coefficient alone but that it can exist. It is equivalent from this and simpler to state that if all the zeros are inside the unit circle (an invertible FIR filter), then the plot of the frequency response on a complex plane as we sweep $\omega$ from $0$ to $2\pi$) cannot encircle the origin.

Further details below:


An invertible FIR filter is a minimum phase filter, since all zeros must be inside the unit circle (or on the unit circle for marginal stability). However a subset of all possible minimum phase filters given a first tap would be the set of decreasing coefficients as the OP has hypothesized as the would meet the constraint given below under “by inspection”. However other minimum phase filters also exist where subsequent taps are larger than the first.

The easiest constraint I can think of that would be on all coefficients specifically beyond solving for the roots is given by Cauchy's argument principle: The frequency response as given by the coefficients cannot encircle the origin for an invertible FIR filter. With the frequency response given as:

$$H(z) \bigg|_{z=j\omega} = \sum_{n=0}^{N-1}h_n e^{-j\omega n}$$


Further details below:

The invertible filter must have all zeros inside the unit circle, since zeros become poles once the filter is inverted, and any poles outside the unit circle means instability for causal systems. (For marginal stability consideration; meaning a system that neither grows nor decays, the zero can be on the unit circle.)

An FIR filter with all zeros inside the unit circle is a minimum phase filter Any other FIR filters would not be invertible. This includes maximum phase filters, which have all zero's outside the unit circle, and mixed phased filters with both minimum and maximum phase components (linear phase filters are mixed phase).

So the constraint is the filter must be a minimum phase filter to be invertible. Below I list 4 tests for detecting a minimum phase filter, with the Cauchy's argument principle the closest to providing a simple coefficient constraint rule.

By Inspection: A tell-tale sign of a minimum phase filter is the concentration of coefficients toward the start of the filter. Given this, you can rule out many filters by simple inspection if the coefficients are either concentrated in the center or end of the filter. Specifically when considering all filters with the same magnitude response, the coefficients for the minimum phase filter (which is the filter's impulse response), will decay the fastest in time. A detailed proof of this property specific to minimum phase polynomials is given in Oppenheim and Shafer's Digital Signal Processing book and is summarized as:

$$\sum_{n=0}^N|h[n]|^2\ge \sum_{n=0}^N|g[n]|^2$$

Where $h[n]$ is a minimum phase filter and $g[n]$ is any other filter with the same magnitude response and $N$ can be any positive integer. This does not mean all coefficients are in decreasing order, for example [5 6 3 2 1] is linear phase, while [5 8 3 2 1] is not, so this is not necessarily a simple constraint that can be applied but can certainly identify obvious non-linear phase solutions.

Cauchy's Argument Principle: A very simple approach to test for this condition applicable to FIR filters is to use Cauchy's argument principle (see Nyquist's Stability Criterion and Cauchy's Argument Principle) by plotting the frequency response on a complex plane. For a causal FIR filter, the number of clock-wise encirclements of the origin will be equal to the number of zeros outside the unit circle. If all the zeros are inside the unit circle, there will be no encirclements of the origin (I show an example below). For an FIR filter, there cannot be any counter-clockwise encirclements (as all poles are at the origin), so if any encirclements do happen, they will be clock-wise only.

Solving for the Roots: Confirm the magnitude of all roots of the polynomial given by the coefficients of the filter are all $|z|\le 1$

Hilbert Transform: Compare the magnitude and phase response for the filter. Since there is a unique relationship between the magnitude response and phase response for minimum phase filters, the two can be compared to determine if the filter in question is indeed the minimum phase solution for that magnitude response. This is detailed further by PeterK in this post: Derive minimum phase from magnitude with relationship copied below:

$$ \theta(\omega) = - {\scr H}\left[ \ln(G(\omega)) \right] $$ where ${\scr H}$ is the Hilbert transform.

Every magnitude response has a minimum phase solution, therefore every FIR filter can be decomposed into a minimum phase filter (invertible) cascaded with a all-pass filter (constant magnitude response with phase change only over frequency and not invertible).


These concepts are demonstrated with a simple example of a 2 tap FIR filter with coefficients [1 0.5] and it's reverse [0.5 1]. In the first case the filter is minimum phase with a transfer function $1+0.5z^{-1}$ and the second filter is the reverse, which is a maximum phase filter with the transfer function $0.5+z^{-1}$. The magnitude response of both filters is identical but the phase response is very different, as given by the vector diagram showing phase versus frequency for both filters. (This diagram is created by simply replacing $z^{-1}$ with the phasor $e^{-j\omega}$ which is exactly how to get the frequency response from the z-transform).

It is a bit of an optical illusion but the resulting phasor given by the sum $\sum_n h[n]e^{-jn \omega}$ does have the exact same magnitude for all frequencies as we sweep the frequency $\omega$ from $0$ to $2\pi$. However notice how constrained the angle will be in the diagram on the left, compared to the one on the right! Minimum phase versus Maximum phase. This plot also demonstrates Cauchy's argument principle showing how the frequency response of a minimum phase filter when plotted on the complex plane will not encircle the origin.

min and max phase

Below is a plot of the magnitude and phase response for the two example filters above (with the same magnitude response for either). Since group delay is $d\phi/d\omega$ the minimum phase filter will have the lowest delay while the maximum phase filter will have the largest delay, which makes sense when you consider the placement of the largest tap in the FIR filter which is a series of summed and weighted delays (the energy will emerge from the minimum phase filter sooner).

freq response

Another example demonstrating the Cauchy argument principle is below, with a plot of the frequency response on the complex plane for filters [5 6 3 2 1] and [5 8 3 2 1]. The filter [5 8 3 2 1] is proven to not be minimum phase since the frequency response encircles the origin:

Cauchy 2

And here is another example for a maximum phase filter, which is also confirmed using Cauchy's Argument Principle. This is for the fourth order filter with coefficients [1 -3 -3 2 5] where we see all four zeros are outside the unit circle as we have four encirclements of the origin. (The easy way to count encirclements is to note a direction on the frequency response with a forward direction consistent with increasing $\omega$, and then draw a vector from the origin out toward infinity at any angle and count how many crossings of the frequency response take place: if the cross is of a forward direction the count increases, and if of a negative direction the count decreases).

Cauchy maximum phase

And here is another simple example with the FIR filter given by coefficients [1, 1,5, 0.6] showing how the frequency response of an FIR with a real positive first coefficient can enter the LHP and still be a minimum phase filter. Specifically, it is the origin that is not encircled consistent with Cauchy's Argument Principle. With that constraint the phase response can never exceed $\pm \pi$. Below the plot is the standard magnitude and phase frequency response as two separate plots.

Nyquist Plot

Frequency Response

| improve this answer | |
$\endgroup$
  • $\begingroup$ Argh! You said "minimum phase", I read "constant delay". I'm just going to delete my off-base comment. My apologies. $\endgroup$ – TimWescott May 5 at 23:53
  • $\begingroup$ @Tim Ha no worries! I was totally open to being wrong---especially if my thought's on using Cauchey's Argument would universally apply to detection of minimum phase filters. I haven't put that one to practice for this purpose but seems to make sense. If so it is very easy. $\endgroup$ – Dan Boschen May 5 at 23:58
  • 1
    $\begingroup$ I was trying to figure out how to apply Cauchey's Argument (it's what I was thinking of when I mentioned in my comment to the OP that I knew my prey was out there in Mathemagic Land) -- I believe your use of it is entirely correct. $\endgroup$ – TimWescott May 6 at 0:28
  • 1
    $\begingroup$ @Tim yeah and makes sense then you were also pulling that from the control loop world which was my exposure to it. $\endgroup$ – Dan Boschen May 6 at 0:36
  • $\begingroup$ @DanBoschen excellent response, it was very helpful in my work! I am having a hard time interpreting Cauchy's arg principal in (1). I don't understand what you mean by $\arg$ in $\arg(H(\omega))$. $\endgroup$ – Condensation May 21 at 23:14
0
$\begingroup$

In general, an $n$-th order IIR filter will have $n$ poles which should all be inside the unit circle for stability.

Those poles are equivalently represented as the roots of the characteristic polynomial of the LCCDE that represents the IIR filter. Incidentally, they are also the roots of the forward FIR filter polynomial (which are the zeros of the FIR filter).

The constraint on the roots (poles) should be reflected on the coefficients of the polynomial (which are the taps of the FIR filter) and a single coefficient is not sufficient to guarantee that all roots of the polynomial wil be less than unity. Hence the answer is no.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.