Coeff test

Given an FIR filter of length N, I need to test if all the zeros are on the unit circle or not, without factoring. Any ideas?

Bob

>Given an FIR filter of length N, I need to test if all the zeros are on
the unit circle or not, without factoring. Any ideas?
>
>Bob
>

if you let Matlab do it for you (assuming Vlad is not irritated) then

h = fir1(40,.1); -- example filter
h = round(h*2^15);
zplane(h,1);
	 

_____________________________		
Posted through www.DSPRelated.com

I was looking for a math solution that is more fundamental. For example, symmettry is necessary but not sufficient to say that all zeros are on the unit circle (for N odd ). I was hoping some other way of looking at the coefficients could be found. 

Bob

>I was looking for a math solution that is more fundamental. For example,
symmettry is necessary but not sufficient to say that all zeros are on the
unit circle (for N odd ). I was hoping some other way of looking at the
coefficients could be found. 
>
>Bob
>

well you experiment with zplane but I don't expect all zeros to be on unit
circle.	 

_____________________________		
Posted through www.DSPRelated.com

radams2000@gmail.com writes:

> Given an FIR filter of length N, I need to test if all the zeros are
> on the unit circle or not, without factoring. Any ideas?

Hi Bob,

Analyticially, if you did an inverse bilinear transformation (from z to
s), then unit circle roots would be transformed to phi axis roots. If
all the roots of a polynomial are on the phi axis, then the polynomial
is real. Unfortunately this is not an iff. Maybe it helps you in the
right direction?
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Randy

Thanks for the suggestion. I will think about this and see if life is better over there in S land. 

Bob

On Wed, 02 Jul 2014 03:37:25 -0700, radams2000 wrote:

> Given an FIR filter of length N, I need to test if all the zeros are on
> the unit circle or not, without factoring. Any ideas?

Off hand I don't see how to do it other than numerically.  If you're 
constraining it to an is/is not test on the unit circle then you can go 
looking for zeros there.

But it's starting to sound an awful lot like slightly constrained 
factoring to me, so I'm not sure about the utility of it all.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Wed, 02 Jul 2014 17:43:56 -0500, Tim Wescott wrote:

> On Wed, 02 Jul 2014 03:37:25 -0700, radams2000 wrote:
> 
>> Given an FIR filter of length N, I need to test if all the zeros are on
>> the unit circle or not, without factoring. Any ideas?
> 
> Off hand I don't see how to do it other than numerically.  If you're
> constraining it to an is/is not test on the unit circle then you can go
> looking for zeros there.
> 
> But it's starting to sound an awful lot like slightly constrained
> factoring to me, so I'm not sure about the utility of it all.

But -- why are you against factoring?  If it's the whole coefficient 
sensitivity issue, you're going to have that no matter what.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On 07/02/14 19:15, Tim Wescott wrote:
> On Wed, 02 Jul 2014 17:43:56 -0500, Tim Wescott wrote:
>
>> On Wed, 02 Jul 2014 03:37:25 -0700, radams2000 wrote:
>>
>>> Given an FIR filter of length N, I need to test if all the zeros are on
>>> the unit circle or not, without factoring. Any ideas?
>>
>> Off hand I don't see how to do it other than numerically.  If you're
>> constraining it to an is/is not test on the unit circle then you can go
>> looking for zeros there.
>>
>> But it's starting to sound an awful lot like slightly constrained
>> factoring to me, so I'm not sure about the utility of it all.
>
> But -- why are you against factoring?  If it's the whole coefficient
> sensitivity issue, you're going to have that no matter what.
>

Lots of interesting facts on

http://en.wikipedia.org/wiki/Properties_of_polynomial_roots

which you might want to look at.  In principle you might be able to use 
some of the bounds mentioned there to show that a given polynomial has 
roots not on the unit circle.  In practice I'm not sure you'll find 
anything better than factoring.

One more random fact that might help:  for every monic (i.e. leading 
coefficient equal to one) polynomial p there is an associated "companion 
matrix" (check wikipedia again for details) whose entries are ones, 
zeros, and the coefficients of the polynomial (and so no factoring is 
required to form it) and whose characteristic polynomial is p.  Since 
the determinant of a matrix is the product of its eigenvalues if the 
determinant of the companion matrix to p is not on the unit circle then 
some root of p is not on the unit circle.  But possibly for some p with 
roots off the unit circle the product of all the roots may still have 
modulus one.

Robert Beaudoin

Tim Wescott <tim@seemywebsite.really> wrote:
> On Wed, 02 Jul 2014 03:37:25 -0700, radams2000 wrote:
 
>> Given an FIR filter of length N, I need to test if all the zeros 
>> are on the unit circle or not, without factoring. Any ideas?
 
> Off hand I don't see how to do it other than numerically.  If you're 
> constraining it to an is/is not test on the unit circle then you 
> can go looking for zeros there.

I hadn't thought too much about this before, but now it reminds
me of another problem. How about a numeric contour integral?
 
> But it's starting to sound an awful lot like slightly constrained 
> factoring to me, so I'm not sure about the utility of it all.

Thinking about this backwards, there are tests for convergence
of infinite series that give the radius of convergence, which 
tells you the position of poles in the complex plane.

OK, the other problem: there was a question on how to find the
number of possible ways to make change for a given amount,
and given set of coins. There is a solution that involves
a numeric contour integral around the unit circle that, within
roundoff error, will answer the question.

-- glen