# Algorithm to Count Zeros Outside Unit Circle for FIR Filter

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).

• 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. May 7, 2020 at 21:04
• ah wait, we need to remove double-crossings May 7, 2020 at 21:04
• 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 May 8, 2020 at 9:54
• @aconcernedcitizen I updated it to be no zeros outside the unit circle; thanks. May 8, 2020 at 10:34
• 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. May 8, 2020 at 11:48

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: