3
$\begingroup$

As detailed in this post Can I set a constraint on the first tap of an FIR filter such that its inverse is stable? I show how Cauchy's Argument Principle can be used to easily confirm if an FIR filter is minimum phase, meaning all zeros are inside or on the unit circle, or the converse, maximum phase, simply by plotting the frequency response on a complex plane.

However, the approach I use is completely graphical, in that I have to plot the frequency response and then manually count encirclements of the origin. Each encirclement of the origin indicates a zero that is outside the unit circle.

My question what would be a compact and efficient algorithmic approach (not graphical) based on the Cauchy Argument Principal that would be more efficient than solving for the roots and determining that $|z|>1$ for all roots, or any other approach to count the number of zeros outside the unit circle?

The graphical approach is as follows, using the example from the linked post above with a maximum-phase FIR filter with coefficients [1 -3 -3 2 5]. The frequency response (magnitude and phase versus frequency) is plotted below on a complex plane. The graphical way to count encirclements is to draw a vector from the origin out toward infinity at any angle and count how many crossings of the frequency response take place. Below you would count 4 encirlements indicating all four zeros are outside the unit circle. (A minimum phase filter would have no encirclements). The easy way to count encirclements is to note a direction on the frequency response with a forward direction consistent with increasing ω, 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. Note given the crossing locations it is not as simple as just counting crossings on the Real or Imaginary axis (here the Real can't work but the Imaginary could, but that is not a general solution).

enter image description here

Improve this question
$\endgroup$
9
  • $\begingroup$ hypothesis: when encircling the origin, you need to "touch" all four quadrants in sequence, which especially means you need to cut four "half-axes" in sequence, so solving for $\Im = 0, \Re>0$, $\Re=0, \Im>0$, $\Im = 0, \Re <0$ and $\Re=0, \Im <0$ should result in "sorted" phases. $\endgroup$ – Marcus Müller May 7 '20 at 21:04
  • 1
    $\begingroup$ ah wait, we need to remove double-crossings $\endgroup$ – Marcus Müller May 7 '20 at 21:04
  • $\begingroup$ Why do you say a minimum-phase filter would have no zeroes on the unit circle? Transforming a linear-phase FIR into a nonlinear-phase means reversing the zeroes outside the circle and keeping those on the circle, whether that is done by keeping the number of taps for the same reponse, or halving them for squared response. Also, pauvre Augustin $\endgroup$ – a concerned citizen May 8 '20 at 9:54
  • $\begingroup$ @aconcernedcitizen I updated it to be no zeros outside the unit circle; thanks. $\endgroup$ – Dan Boschen May 8 '20 at 10:34
  • $\begingroup$ As I'm re-reading my comment, it does seem a bit too belicose. That was the least of my intentions (actually none of it). If you can, read it in a sort of self-wondering way, as opposed to a confrontational tone. $\endgroup$ – a concerned citizen May 8 '20 at 11:48
1
$\begingroup$

Here is one answer, if someone can improve on this I will select it as the "right" answer (also comments very welcome on obvious flaws with this approach):

Given Cauchy's argument principle, the number of zeros outside the unit circle is given by the number of encirclements of the origin for the frequency response of the filter as plotted on a complex plane. Each encirclement causes the unwrapped phase to go further than $\pm \pi$ in any interval $\pi$ in normalized radian frequency.

Thus the algorithmic approach would be to unwrap the phase, remove the initial phase at $\omega=0$ and then count the number of crossings of the horizontal lines given by $\pm \pi$, using the Bentley-Ottman algorithm to efficiently count the crossings: https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm.

Further details on algorithmic phase unwrapping given here:

https://www.ljmu.ac.uk/~/media/files/ljmu/about-us/faculties-and-schools/fet/geri/onedimensionalphaseunwrapping_finalpdf.pdf

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Just a thought: for large N this is worth it, instead of root-finding, but for small N, wouldn't you have to do a phase calculation for more points than N in order to properly "catch" all the crossings? Would that bury the root-finding complexity of small N? $\endgroup$ – a concerned citizen May 8 '20 at 13:59
  • $\begingroup$ @aconcernedcitizen Good comment- And is the best algorithm to compute the roots known to be more complex than computing the minimum number of phases to find all the zero crossings even for large N? I don’t know this. $\endgroup$ – Dan Boschen May 8 '20 at 14:38
  • $\begingroup$ That's why I was cautious and said "just a thought". :-) $\endgroup$ – a concerned citizen May 8 '20 at 15:51

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.