On Thu, 10 May 2012 22:49:06 -0400, robert bristow-johnson wrote:> On 5/10/12 5:07 PM, Tim Wescott wrote: >> On Thu, 10 May 2012 16:20:59 -0400, robert bristow-johnson wrote: >> >>> On 5/10/12 4:11 PM, Tim Wescott wrote: >>>> On Thu, 10 May 2012 14:22:23 -0500, gretzteam wrote: >>>> >>>>> Thanks for the comment. My filter design method cannot generate 2nd >>>>> order section directly, but i'm only interested in 4th and 8th order >>>>> filters, and so far Robert's method works nicely - and I went down >>>>> from 23 lines of code + eyeballing to 4 simple lines! >>>> >>>> 8th order is a stretch, >>> >>> double-precision in MATLAB?? (it's gotta be something line MATLAB if >>> gretz can do this in 4 lines of code.) factoring an 8th-order >>> polynomial should not be a problem for floating-point with 53 bits of >>> mantissa. or even stretching it. bump that up to a "bazillionth >>> order" and any finite-precision arithmetic will fall short. >> >> Well, probably not. But even an 8th-order will have problems if the Q >> is too high or if the normalized center frequency is low. An 8-th >> order polynomials with all the root magnitudes on the order of |z|=1 >> means that the factorization is going to (roughly) good to an error >> magnitude of 0.01. That would work out to a 10% frequency change in a >> pole at 700Hz, or a change in 0.1 in the damping ratio, if you were >> sampling at 44000. >> >> > so you're saying (and you can well be right) that for an 8th-order > factorization problem, that even with 53 meaningful bits of in words of > any parameters and intermediate variables, that if the coefficients are > nasty enough that there are zeros real close to |z|=1 (do they have to > be close to each other for this to get pathological?), that you might > expect only 7 or 8 meaningful bits in the real and imaginary parts of > the roots? > > can't you precisely check the root by just plugging it into the original > polynomial? oh, i get it: 0.01^8 is about 2^(-53). > > i guess this is why there is an Add-With-Carry instruction. i dunno if > there is a MATLAB toolbox that does this, but i could imagine that there > is some programs out there that can factor nasty polynomials by making > really long fixed or floating-point words. but i don't know how you > would write the code in C, because you need Add-With-Carry.Even if your calculation is spot-on (and there are arbitrary-precision numerical packages for both C and C++), you still have the problem that the coefficients themselves must be accurate enough. And yes, the accuracy degradation is on the order of (coeff error)^(1/N) for an N-th order polynomial, so small errors get big quickly. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Online · Live + on demand
February 9-11, 2027
Price goes up Jan 1: register now to lock in today's rate
Register Now →
Factoring a high order allpass filter into cascade of 2nd order ALLPASS
Started by ●May 10, 2012
Reply by ●May 11, 20122012-05-11
Reply by ●May 12, 20122012-05-12
On May 11, 6:51�pm, Tim Wescott <t...@seemywebsite.com> wrote:> On Thu, 10 May 2012 22:49:06 -0400, robert bristow-johnson wrote: > > On 5/10/12 5:07 PM, Tim Wescott wrote: > >> On Thu, 10 May 2012 16:20:59 -0400, robert bristow-johnson wrote: > > >>> On 5/10/12 4:11 PM, Tim Wescott wrote: > >>>> On Thu, 10 May 2012 14:22:23 -0500, gretzteam wrote: > > >>>>> Thanks for the comment. My filter design method cannot generate 2nd > >>>>> order section directly, but i'm only interested in 4th and 8th order > >>>>> filters, and so far Robert's method works nicely - and I went down > >>>>> from 23 lines of code + eyeballing to 4 simple lines! > > >>>> 8th order is a stretch, > > >>> double-precision in MATLAB?? (it's gotta be something line MATLAB if > >>> gretz can do this in 4 lines of code.) �factoring an 8th-order > >>> polynomial should not be a problem for floating-point with 53 bits of > >>> mantissa. �or even stretching it. �bump that up to a "bazillionth > >>> order" and any finite-precision arithmetic will fall short. > > >> Well, probably not. �But even an 8th-order will have problems if the Q > >> is too high or if the normalized center frequency is low. �An 8-th > >> order polynomials with all the root magnitudes on the order of |z|=1 > >> means that the factorization is going to (roughly) good to an error > >> magnitude of 0.01. �That would work out to a 10% frequency change in a > >> pole at 700Hz, or a change in 0.1 in the damping ratio, if you were > >> sampling at 44000. > > > so you're saying (and you can well be right) that for an 8th-order > > factorization problem, that even with 53 meaningful bits of in words of > > any parameters and intermediate variables, that if the coefficients are > > nasty enough that there are zeros real close to |z|=1 (do they have to > > be close to each other for this to get pathological?), that you might > > expect only 7 or 8 meaningful bits in the real and imaginary parts of > > the roots? > > > can't you precisely check the root by just plugging it into the original > > polynomial? �oh, i get it: �0.01^8 is about 2^(-53). > > > i guess this is why there is an Add-With-Carry instruction. �i dunno if > > there is a MATLAB toolbox that does this, but i could imagine that there > > is some programs out there that can factor nasty polynomials by making > > really long fixed or floating-point words. �but i don't know how you > > would write the code in C, because you need Add-With-Carry. > > Even if your calculation is spot-on (and there are arbitrary-precision > numerical packages for both C and C++), you still have the problem that > the coefficients themselves must be accurate enough. > > And yes, the accuracy degradation is on the order of (coeff error)^(1/N) > for an N-th order polynomial, so small errors get big quickly. > > -- > My liberal friends think I'm a conservative kook. > My conservative friends think I'm a liberal kook. > Why am I not happy that they have found common ground? > > Tim Wescott, Communications, Control, Circuits & Softwarehttp://www.wescottdesign.comAt Rice University they have published methods and code for factoring very high order polynomials. Here's a link to their webpage: http://dsp.rice.edu/software/polynomial-root-finders Cheers, David
Reply by ●May 13, 20122012-05-13
On May 12, 10:52�am, Dave <dspg...@netscape.net> wrote:> On May 11, 6:51�pm, Tim Wescott <t...@seemywebsite.com> wrote: > > > > > On Thu, 10 May 2012 22:49:06 -0400, robert bristow-johnson wrote: > > > On 5/10/12 5:07 PM, Tim Wescott wrote: > > >> On Thu, 10 May 2012 16:20:59 -0400, robert bristow-johnson wrote: > > > >>> On 5/10/12 4:11 PM, Tim Wescott wrote: > > >>>> On Thu, 10 May 2012 14:22:23 -0500, gretzteam wrote: > > > >>>>> Thanks for the comment. My filter design method cannot generate 2nd > > >>>>> order section directly, but i'm only interested in 4th and 8th order > > >>>>> filters, and so far Robert's method works nicely - and I went down > > >>>>> from 23 lines of code + eyeballing to 4 simple lines! > > > >>>> 8th order is a stretch, > > > >>> double-precision in MATLAB?? (it's gotta be something line MATLAB if > > >>> gretz can do this in 4 lines of code.) �factoring an 8th-order > > >>> polynomial should not be a problem for floating-point with 53 bits of > > >>> mantissa. �or even stretching it. �bump that up to a "bazillionth > > >>> order" and any finite-precision arithmetic will fall short. > > > >> Well, probably not. �But even an 8th-order will have problems if the Q > > >> is too high or if the normalized center frequency is low. �An 8-th > > >> order polynomials with all the root magnitudes on the order of |z|=1 > > >> means that the factorization is going to (roughly) good to an error > > >> magnitude of 0.01. �That would work out to a 10% frequency change in a > > >> pole at 700Hz, or a change in 0.1 in the damping ratio, if you were > > >> sampling at 44000. > > > > so you're saying (and you can well be right) that for an 8th-order > > > factorization problem, that even with 53 meaningful bits of in words of > > > any parameters and intermediate variables, that if the coefficients are > > > nasty enough that there are zeros real close to |z|=1 (do they have to > > > be close to each other for this to get pathological?), that you might > > > expect only 7 or 8 meaningful bits in the real and imaginary parts of > > > the roots? > > > > can't you precisely check the root by just plugging it into the original > > > polynomial? �oh, i get it: �0.01^8 is about 2^(-53). > > > > i guess this is why there is an Add-With-Carry instruction. �i dunno if > > > there is a MATLAB toolbox that does this, but i could imagine that there > > > is some programs out there that can factor nasty polynomials by making > > > really long fixed or floating-point words. �but i don't know how you > > > would write the code in C, because you need Add-With-Carry. > > > Even if your calculation is spot-on (and there are arbitrary-precision > > numerical packages for both C and C++), you still have the problem that > > the coefficients themselves must be accurate enough. > > > And yes, the accuracy degradation is on the order of (coeff error)^(1/N) > > for an N-th order polynomial, so small errors get big quickly. > > > -- > > My liberal friends think I'm a conservative kook. > > My conservative friends think I'm a liberal kook. > > Why am I not happy that they have found common ground? > > > Tim Wescott, Communications, Control, Circuits & Softwarehttp://www.wescottdesign.com > > At Rice University they have published methods and code for factoring > very high order polynomials. Here's a link to their webpage:http://dsp.rice.edu/software/polynomial-root-finders >looks very cool, but i get the run-around when i click on the "here" link to see if i can download the code. r b-j
Reply by ●May 13, 20122012-05-13
>> there is a MATLAB toolbox that does thishave a look at tf2sos. An alternative might be to use a plain old FIR. It can give you an arbitrary amplitude response at the same time. I'm in the middle of writing a blog article on iterative reweighted least squares (aka IRLS) FIR design - if you have a good example problem, I could have a look.
Reply by ●May 13, 20122012-05-13
>> The usual 'split into SOS'.. looking back at the original question, I think you've tried that already. But then, I don't see the problem with "preserving the allpass property": For an allpass, poles and zeros should be reflections across the unit circle. Knowing either numerator (denominator) of a second-order section, you can get the other one easily.
Reply by ●May 13, 20122012-05-13
On Sun, 13 May 2012 12:05:52 -0500, mnentwig wrote:>>> there is a MATLAB toolbox that does this > have a look at tf2sos. > > An alternative might be to use a plain old FIR. It can give you an > arbitrary amplitude response at the same time.I'm not so sure -- I don't know that it's possible to make a finite impulse response, truly allpass filter, with a phase response that's anything other than a pure delay. Do you have examples of a FIR filter with arbitrary phase response and unity gain response from DC to Nyquist? Having said that, I won't even _try_ to claim that you can't do a perfectly adequate job of making an FIR "close to" allpass filter, and perhaps one that -- after all the other system effects are taken into account -- outperforms a theoretically perfect-in-amplitude IIR allpass. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by ●May 13, 20122012-05-13
On May 13, 12:10�am, robert bristow-johnson <r...@audioimagination.com> wrote:> On May 12, 10:52�am, Dave <dspg...@netscape.net> wrote: > > > > > > > > > > > On May 11, 6:51�pm, Tim Wescott <t...@seemywebsite.com> wrote: > > > > On Thu, 10 May 2012 22:49:06 -0400, robert bristow-johnson wrote: > > > > On 5/10/12 5:07 PM, Tim Wescott wrote: > > > >> On Thu, 10 May 2012 16:20:59 -0400, robert bristow-johnson wrote: > > > > >>> On 5/10/12 4:11 PM, Tim Wescott wrote: > > > >>>> On Thu, 10 May 2012 14:22:23 -0500, gretzteam wrote: > > > > >>>>> Thanks for the comment. My filter design method cannot generate 2nd > > > >>>>> order section directly, but i'm only interested in 4th and 8th order > > > >>>>> filters, and so far Robert's method works nicely - and I went down > > > >>>>> from 23 lines of code + eyeballing to 4 simple lines! > > > > >>>> 8th order is a stretch, > > > > >>> double-precision in MATLAB?? (it's gotta be something line MATLAB if > > > >>> gretz can do this in 4 lines of code.) �factoring an 8th-order > > > >>> polynomial should not be a problem for floating-point with 53 bits of > > > >>> mantissa. �or even stretching it. �bump that up to a "bazillionth > > > >>> order" and any finite-precision arithmetic will fall short. > > > > >> Well, probably not. �But even an 8th-order will have problems if the Q > > > >> is too high or if the normalized center frequency is low. �An 8-th > > > >> order polynomials with all the root magnitudes on the order of |z|=1 > > > >> means that the factorization is going to (roughly) good to an error > > > >> magnitude of 0.01. �That would work out to a 10% frequency change in a > > > >> pole at 700Hz, or a change in 0.1 in the damping ratio, if you were > > > >> sampling at 44000. > > > > > so you're saying (and you can well be right) that for an 8th-order > > > > factorization problem, that even with 53 meaningful bits of in words of > > > > any parameters and intermediate variables, that if the coefficients are > > > > nasty enough that there are zeros real close to |z|=1 (do they have to > > > > be close to each other for this to get pathological?), that you might > > > > expect only 7 or 8 meaningful bits in the real and imaginary parts of > > > > the roots? > > > > > can't you precisely check the root by just plugging it into the original > > > > polynomial? �oh, i get it: �0.01^8 is about 2^(-53). > > > > > i guess this is why there is an Add-With-Carry instruction. �i dunno if > > > > there is a MATLAB toolbox that does this, but i could imagine that there > > > > is some programs out there that can factor nasty polynomials by making > > > > really long fixed or floating-point words. �but i don't know how you > > > > would write the code in C, because you need Add-With-Carry. > > > > Even if your calculation is spot-on (and there are arbitrary-precision > > > numerical packages for both C and C++), you still have the problem that > > > the coefficients themselves must be accurate enough. > > > > And yes, the accuracy degradation is on the order of (coeff error)^(1/N) > > > for an N-th order polynomial, so small errors get big quickly. > > > > -- > > > My liberal friends think I'm a conservative kook. > > > My conservative friends think I'm a liberal kook. > > > Why am I not happy that they have found common ground? > > > > Tim Wescott, Communications, Control, Circuits & Softwarehttp://www.wescottdesign.com > > > At Rice University they have published methods and code for factoring > > very high order polynomials. Here's a link to their webpage:http://dsp.rice.edu/software/polynomial-root-finders > > looks very cool, but i get the run-around when i click on the "here" > link to see if i can download the code. > > r b-jYeah - I do too. There is a link near the bottom that says Files and drops down a list of files which I believe you can download. Try that and see if it works. Dave
Reply by ●May 14, 20122012-05-14
Hello,>> Do you have examples of a FIR filter with arbitrary phase response andunity gain response from DC to Nyquist? on a conceptual level, simply sample the impulse response of a "true" allpass and I can approximate it with arbitrary accuracy with a FIR. Now for a technical implementation, the first question would be, "what bandwidth do you really need"? Often, signals are oversampled. If so, a lowpass is not a "perfect" allpass, but then the "ideal" allpass phase response is usually not exactly what I want either, so I can probably tolerate some amplitude ripple as well. I'll try to put together a meaningful example. In the meantime, if anybody wants to try, here is an arbitrary nonlinear phase _lowpass_ FIR design, quickly hacked up: http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/mnFIR6.m It's under construction, so don't believe everything the comments say. It needs either Matlab, or free Octave (if functions are missing, install the "signal" package from OctaveForge and dependencies).
Reply by ●May 14, 20122012-05-14
>Hello, > >>> Do you have examples of a FIR filter with arbitrary phase response and>unity gain response from DC to Nyquist? > >on a conceptual level, simply sample the impulse response of a "true" >allpass and I can approximate it with arbitrary accuracy with a FIR. > >Now for a technical implementation, the first question would be, "what >bandwidth do you really need"? Often, signals are oversampled. >If so, a lowpass is not a "perfect" allpass, but then the "ideal" allpass >phase response is usually not exactly what I want either, so I canprobably>tolerate some amplitude ripple as well. > >I'll try to put together a meaningful example. >In the meantime, if anybody wants to try, here is an arbitrary nonlinear >phase _lowpass_ FIR design, quickly hacked up: > >http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/mnFIR6.m > >It's under construction, so don't believe everything the comments say. >It needs either Matlab, or free Octave (if functions are missing, install >the "signal" package from OctaveForge and dependencies). >Hi, Thanks for the tips, but the problem was quite easily solved by rbj's first reply. Given some allpass transfer function, simply doing (Matlab):> [sos,g] = tf2sos(b, a);will not yield 2nd order allpass transfer functions. However, using only the denominator:> [sos,g] = tf2sos(1, a);will give a bunch of second order transfer function, and I can then generate the numerator for each of them guaranteeing the allpass property. For the filters I was interested in, I didn't see that the poles/zeros of the SOS was any different than for the higher order transfer function, so it worked well.







