I was looking an algorithm to calculate fourier coefficents and update them at every new input sample, the Sliding Goertzel algorithm. This one seems to give both an estimate of the amplitude AND phase. I am not sure if any of you guys are familar with it. http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf My thoughts are that if i can generate a number lets say N coefficients with each complex resonator at every time sample then i should be able to use the coefficents and resenthesize the signal. The problem is i dont know how many coefficents i would need to synthesize the signal. With the FFT that number is known to be the length of the input data. However in this case the input data is not constrained in length, it can be a infinate input stream, where the 'state' of the filter along with the present input determines the fourier coefficent. (hopefully i am describing the question correctly)
How many Fourier Coefficents are Needed to Synthesize a signal?
Started by ●March 26, 2012
Reply by ●March 26, 20122012-03-26
On 3/26/12 12:11 PM, westocl wrote:> I was looking an algorithm to calculate fourier coefficents and update them > at every new input sample, the Sliding Goertzel algorithm. This one seems > to give both an estimate of the amplitude AND phase. I am not sure if any > of you guys are familar with it. > > http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf > > My thoughts are that if i can generate a number lets say N coefficients > with each complex resonator at every time sample then i should be able to > use the coefficents and resenthesize the signal. > > The problem is i dont know how many coefficents i would need to synthesize > the signal. > > With the FFT that number is known to be the length of the input data. > However in this case the input data is not constrained in length, it can be > a infinate input stream, where the 'state' of the filter along with the > present input determines the fourier coefficent. > > (hopefully i am describing the question correctly)dunno about "correctly", but it ain't clear to me. neither is the paper you cited. the Goertzel FT algorithm is an algorithm to compute a single DFT bin value X[k] with a simple recursive (and critically or marginally stable) filter that has impulse response h_k[n] = e^(-j*2*pi*n*k/N) * u[n] where u[n] is the unit step, and then you have to "sample" the output at time n=N to get X[k] for the x[n] data for 0 <= n < N. so it looks like, since n=N not N-1, that there would be one zero-valued x[n] going into this thing for the final clock tick. now the filter depicted in Fig 1 of your paper is a filter to do that. just like in the text books. to make it a *sliding* Goertzel, you must turn that impulse response into h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) this is an FIR filter but could be implemented with something that has been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or moving-average is the simplest non-trivial example of such. this requires a delay line, and i did not see that in the paper you supplied (but i didn't read through it super carefully). i've done TIIR filters before that had a "ringing" component like Goertzel, and unlike a fixed-point moving sum, where you can exactly subtract what you added previously, because of multiplication (that makes the words wider) and truncation, you *cannot* exactly subtract a previous sample out, and since this is critically stable (some, like me, would call this "unstable" or at least "not stable"), if a numerical turd gets stuck in your accumulator, it will never come out nor die off. you can make it die off by changing the impulse response slightly: h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) for 0 < alpha <<< 1 . i would look at this problem solely from the POV of TIIR. if you want, i can send you a quickie .pdf that i had made a couple years ago that might help you set up a truncated IIR that will do what you want it to do. i think you *could* do this without that alpha stuff, if you explicitly multiply your input with e^(-j*2*pi*n*k/N) and put the product x[n] * e^(-j*2*pi*n*k/N) into your delay line and use a simple moving-sum TIIR. n y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } m=n-N+1 and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to n=N-1 . i guess that's just a simple sliding DFT. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 13:34:43 -0400, robert bristow-johnson wrote:> On 3/26/12 12:11 PM, westocl wrote: >> I was looking an algorithm to calculate fourier coefficents and update >> them at every new input sample, the Sliding Goertzel algorithm. This >> one seems to give both an estimate of the amplitude AND phase. I am not >> sure if any of you guys are familar with it. >> >> http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf>> >> My thoughts are that if i can generate a number lets say N coefficients >> with each complex resonator at every time sample then i should be able >> to use the coefficents and resenthesize the signal. >> >> The problem is i dont know how many coefficents i would need to >> synthesize the signal. >> >> With the FFT that number is known to be the length of the input data. >> However in this case the input data is not constrained in length, it >> can be a infinate input stream, where the 'state' of the filter along >> with the present input determines the fourier coefficent. >> >> (hopefully i am describing the question correctly) > > dunno about "correctly", but it ain't clear to me. > > neither is the paper you cited. > > the Goertzel FT algorithm is an algorithm to compute a single DFT bin > value X[k] with a simple recursive (and critically or marginally stable) > filter that has impulse response > > h_k[n] = e^(-j*2*pi*n*k/N) * u[n] > > where u[n] is the unit step, and then you have to "sample" the output > at time n=N to get X[k] for the x[n] data for 0 <= n < N. so it looks > like, since n=N not N-1, that there would be one zero-valued x[n] going > into this thing for the final clock tick. > > now the filter depicted in Fig 1 of your paper is a filter to do that. > just like in the text books. > > to make it a *sliding* Goertzel, you must turn that impulse response > into > > h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) > > this is an FIR filter but could be implemented with something that has > been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or > moving-average is the simplest non-trivial example of such. this > requires a delay line, and i did not see that in the paper you supplied > (but i didn't read through it super carefully). > > i've done TIIR filters before that had a "ringing" component like > Goertzel, and unlike a fixed-point moving sum, where you can exactly > subtract what you added previously, because of multiplication (that > makes the words wider) and truncation, you *cannot* exactly subtract a > previous sample out, and since this is critically stable (some, like me, > would call this "unstable" or at least "not stable"), if a numerical > turd gets stuck in your accumulator, it will never come out nor die off. > you can make it die off by changing the impulse response slightly: > > h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) > > for 0 < alpha <<< 1 . > > i would look at this problem solely from the POV of TIIR. if you want, > i can send you a quickie .pdf that i had made a couple years ago that > might help you set up a truncated IIR that will do what you want it to > do. > > i think you *could* do this without that alpha stuff, if you explicitly > multiply your input with e^(-j*2*pi*n*k/N) and put the product > > x[n] * e^(-j*2*pi*n*k/N) > > into your delay line and use a simple moving-sum TIIR. > > n > y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } > m=n-N+1 > > and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to > n=N-1 . i guess that's just a simple sliding DFT.Totally non-apropos to the original question, you _could_ make a sliding DFT with a TIIR: * multiply by exp(i * w * t) * run the result through a CIC (which is a TIIR) * multiply by exp(-i * w * t) It might even make sense, in some situations. -- 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
Reply by ●March 26, 20122012-03-26
>On 3/26/12 12:11 PM, westocl wrote: >> I was looking an algorithm to calculate fourier coefficents and updatethem>> at every new input sample, the Sliding Goertzel algorithm. This oneseems>> to give both an estimate of the amplitude AND phase. I am not sure ifany>> of you guys are familar with it. >> >>http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf>> >> My thoughts are that if i can generate a number lets say N coefficients >> with each complex resonator at every time sample then i should be ableto>> use the coefficents and resenthesize the signal. >> >> The problem is i dont know how many coefficents i would need tosynthesize>> the signal. >> >> With the FFT that number is known to be the length of the input data. >> However in this case the input data is not constrained in length, it canbe>> a infinate input stream, where the 'state' of the filter along with the >> present input determines the fourier coefficent. >> >> (hopefully i am describing the question correctly) > >dunno about "correctly", but it ain't clear to me. > >neither is the paper you cited. > >the Goertzel FT algorithm is an algorithm to compute a single DFT bin >value X[k] with a simple recursive (and critically or marginally stable) >filter that has impulse response > > h_k[n] = e^(-j*2*pi*n*k/N) * u[n] > >where u[n] is the unit step, and then you have to "sample" the output >at time n=N to get X[k] for the x[n] data for 0 <= n < N. so it looks >like, since n=N not N-1, that there would be one zero-valued x[n] going >into this thing for the final clock tick. > >now the filter depicted in Fig 1 of your paper is a filter to do that. >just like in the text books. > >to make it a *sliding* Goertzel, you must turn that impulse response into > > h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) > >this is an FIR filter but could be implemented with something that has >been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >moving-average is the simplest non-trivial example of such. this >requires a delay line, and i did not see that in the paper you supplied >(but i didn't read through it super carefully). > >i've done TIIR filters before that had a "ringing" component like >Goertzel, and unlike a fixed-point moving sum, where you can exactly >subtract what you added previously, because of multiplication (that >makes the words wider) and truncation, you *cannot* exactly subtract a >previous sample out, and since this is critically stable (some, like me, >would call this "unstable" or at least "not stable"), if a numerical >turd gets stuck in your accumulator, it will never come out nor die off. > you can make it die off by changing the impulse response slightly: > > h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) > >for 0 < alpha <<< 1 . > >i would look at this problem solely from the POV of TIIR. if you want, >i can send you a quickie .pdf that i had made a couple years ago that >might help you set up a truncated IIR that will do what you want it todo.> >i think you *could* do this without that alpha stuff, if you explicitly >multiply your input with e^(-j*2*pi*n*k/N) and put the product > > x[n] * e^(-j*2*pi*n*k/N) > >into your delay line and use a simple moving-sum TIIR. > > n > y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } > m=n-N+1 > >and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to >n=N-1 . i guess that's just a simple sliding DFT. > > >-- > >r b-j rbj@audioimagination.com > >"Imagination is more important than knowledge." > > >>i would look at this problem solely from the POV of TIIR. if you want, >i can send you a quickie .pdf that i had made a couple years ago that >might help you set up a truncated IIR that will do what you want it todo. Yes, I would like the pdf on how to create such a thing. I dont like the alpha. either. I do need it to give the phase information, not just the magnitude. The other question is, could i use the coefficents from the filter to resynthesize the input signal to the filter? kinda like an 'inverse sliding goertzel'. if so, how many resionators would one need? westocl@yahoo.com
Reply by ●March 26, 20122012-03-26
On 3/26/12 1:45 PM, Tim Wescott wrote:> On Mon, 26 Mar 2012 13:34:43 -0400, robert bristow-johnson wrote: > >> On 3/26/12 12:11 PM, westocl wrote: >>> I was looking an algorithm to calculate fourier coefficents and update >>> them at every new input sample, the Sliding Goertzel algorithm. This >>> one seems to give both an estimate of the amplitude AND phase. I am not >>> sure if any of you guys are familar with it. >>> >>> http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ > ASlidingGoertzelAlgorithm.pdf >>> >>> My thoughts are that if i can generate a number lets say N coefficients >>> with each complex resonator at every time sample then i should be able >>> to use the coefficents and resenthesize the signal. >>> >>> The problem is i dont know how many coefficents i would need to >>> synthesize the signal. >>> >>> With the FFT that number is known to be the length of the input data. >>> However in this case the input data is not constrained in length, it >>> can be a infinate input stream, where the 'state' of the filter along >>> with the present input determines the fourier coefficent. >>> >>> (hopefully i am describing the question correctly) >> >> dunno about "correctly", but it ain't clear to me. >> >> neither is the paper you cited. >> >> the Goertzel FT algorithm is an algorithm to compute a single DFT bin >> value X[k] with a simple recursive (and critically or marginally stable) >> filter that has impulse response >> >> h_k[n] = e^(-j*2*pi*n*k/N) * u[n] >> >> where u[n] is the unit step, and then you have to "sample" the output >> at time n=N to get X[k] for the x[n] data for 0<= n< N. so it looks >> like, since n=N not N-1, that there would be one zero-valued x[n] going >> into this thing for the final clock tick. >> >> now the filter depicted in Fig 1 of your paper is a filter to do that. >> just like in the text books. >> >> to make it a *sliding* Goertzel, you must turn that impulse response >> into >> >> h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >> >> this is an FIR filter but could be implemented with something that has >> been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >> moving-average is the simplest non-trivial example of such. this >> requires a delay line, and i did not see that in the paper you supplied >> (but i didn't read through it super carefully). >> >> i've done TIIR filters before that had a "ringing" component like >> Goertzel, and unlike a fixed-point moving sum, where you can exactly >> subtract what you added previously, because of multiplication (that >> makes the words wider) and truncation, you *cannot* exactly subtract a >> previous sample out, and since this is critically stable (some, like me, >> would call this "unstable" or at least "not stable"), if a numerical >> turd gets stuck in your accumulator, it will never come out nor die off. >> you can make it die off by changing the impulse response slightly: >> >> h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >> >> for 0< alpha<<< 1 . >> >> i would look at this problem solely from the POV of TIIR. if you want, >> i can send you a quickie .pdf that i had made a couple years ago that >> might help you set up a truncated IIR that will do what you want it to >> do. >> >> i think you *could* do this without that alpha stuff, if you explicitly >> multiply your input with e^(-j*2*pi*n*k/N) and put the product >> >> x[n] * e^(-j*2*pi*n*k/N) >> >> into your delay line and use a simple moving-sum TIIR. >> >> n >> y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } >> m=n-N+1 >> >> and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to >> n=N-1 . i guess that's just a simple sliding DFT. > > Totally non-apropos to the original question, you _could_ make a sliding > DFT with a TIIR: > > * multiply by exp(i * w * t) > * run the result through a CIC (which is a TIIR) > * multiply by exp(-i * w * t) > > It might even make sense, in some situations.that's sorta what i suggested in the last part, except for your last step. i would rather not see the phase changing each output sample, so i would leave your last step off. but if you want to compute that exp(i*w*t) as the output of a ringing, critically stable IIR, then that will eventually lead you to Goertzel, i think. but if you want to trim off the samples older than N samples ago, it has to be a Goertzel modified as a TIIR (instead of IIR). but *then*, because it ain't a simple CIC, numerical turds will get in there and will not come out, that's why i would dampen the ringing, just a teeny-weeny bit. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 14:12:54 -0400, robert bristow-johnson wrote:> On 3/26/12 1:45 PM, Tim Wescott wrote: >> On Mon, 26 Mar 2012 13:34:43 -0400, robert bristow-johnson wrote: >> >>> On 3/26/12 12:11 PM, westocl wrote: >>>> I was looking an algorithm to calculate fourier coefficents and >>>> update them at every new input sample, the Sliding Goertzel >>>> algorithm. This one seems to give both an estimate of the amplitude >>>> AND phase. I am not sure if any of you guys are familar with it. >>>> >>>> http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ >> ASlidingGoertzelAlgorithm.pdf >>>> >>>> My thoughts are that if i can generate a number lets say N >>>> coefficients with each complex resonator at every time sample then i >>>> should be able to use the coefficents and resenthesize the signal. >>>> >>>> The problem is i dont know how many coefficents i would need to >>>> synthesize the signal. >>>> >>>> With the FFT that number is known to be the length of the input data. >>>> However in this case the input data is not constrained in length, it >>>> can be a infinate input stream, where the 'state' of the filter along >>>> with the present input determines the fourier coefficent. >>>> >>>> (hopefully i am describing the question correctly) >>> >>> dunno about "correctly", but it ain't clear to me. >>> >>> neither is the paper you cited. >>> >>> the Goertzel FT algorithm is an algorithm to compute a single DFT bin >>> value X[k] with a simple recursive (and critically or marginally >>> stable) filter that has impulse response >>> >>> h_k[n] = e^(-j*2*pi*n*k/N) * u[n] >>> >>> where u[n] is the unit step, and then you have to "sample" the output >>> at time n=N to get X[k] for the x[n] data for 0<= n< N. so it looks >>> like, since n=N not N-1, that there would be one zero-valued x[n] >>> going into this thing for the final clock tick. >>> >>> now the filter depicted in Fig 1 of your paper is a filter to do that. >>> just like in the text books. >>> >>> to make it a *sliding* Goertzel, you must turn that impulse response >>> into >>> >>> h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>> >>> this is an FIR filter but could be implemented with something that has >>> been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >>> moving-average is the simplest non-trivial example of such. this >>> requires a delay line, and i did not see that in the paper you >>> supplied (but i didn't read through it super carefully). >>> >>> i've done TIIR filters before that had a "ringing" component like >>> Goertzel, and unlike a fixed-point moving sum, where you can exactly >>> subtract what you added previously, because of multiplication (that >>> makes the words wider) and truncation, you *cannot* exactly subtract a >>> previous sample out, and since this is critically stable (some, like >>> me, would call this "unstable" or at least "not stable"), if a >>> numerical turd gets stuck in your accumulator, it will never come out >>> nor die off. >>> you can make it die off by changing the impulse response slightly: >>> >>> h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>> >>> for 0< alpha<<< 1 . >>> >>> i would look at this problem solely from the POV of TIIR. if you >>> want, i can send you a quickie .pdf that i had made a couple years ago >>> that might help you set up a truncated IIR that will do what you want >>> it to do. >>> >>> i think you *could* do this without that alpha stuff, if you >>> explicitly multiply your input with e^(-j*2*pi*n*k/N) and put the >>> product >>> >>> x[n] * e^(-j*2*pi*n*k/N) >>> >>> into your delay line and use a simple moving-sum TIIR. >>> >>> n >>> y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } >>> m=n-N+1 >>> >>> and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to >>> n=N-1 . i guess that's just a simple sliding DFT. >> >> Totally non-apropos to the original question, you _could_ make a >> sliding DFT with a TIIR: >> >> * multiply by exp(i * w * t) >> * run the result through a CIC (which is a TIIR) * multiply by exp(-i * >> w * t) >> >> It might even make sense, in some situations. > > that's sorta what i suggested in the last part, except for your last > step. i would rather not see the phase changing each output sample, so > i would leave your last step off. > > but if you want to compute that exp(i*w*t) as the output of a ringing, > critically stable IIR, then that will eventually lead you to Goertzel, i > think. but if you want to trim off the samples older than N samples > ago, it has to be a Goertzel modified as a TIIR (instead of IIR). but > *then*, because it ain't a simple CIC, numerical turds will get in there > and will not come out, that's why i would dampen the ringing, just a > teeny-weeny bit.The mix -> CIC -> mix architecture I was proposing was specifically intended to eliminate those turds naturally. Think of it as fiber vs. stronger laxatives. -- 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
Reply by ●March 26, 20122012-03-26
On 3/26/2012 2:04 PM, westocl wrote:>> On 3/26/12 12:11 PM, westocl wrote: >>> I was looking an algorithm to calculate fourier coefficents and update > them >>> at every new input sample, the Sliding Goertzel algorithm. This one > seems >>> to give both an estimate of the amplitude AND phase. I am not sure if > any >>> of you guys are familar with it. >>> >>> > http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf >>> >>> My thoughts are that if i can generate a number lets say N coefficients >>> with each complex resonator at every time sample then i should be able > to >>> use the coefficents and resenthesize the signal. >>> >>> The problem is i dont know how many coefficents i would need to > synthesize >>> the signal. >>> >>> With the FFT that number is known to be the length of the input data. >>> However in this case the input data is not constrained in length, it can > be >>> a infinate input stream, where the 'state' of the filter along with the >>> present input determines the fourier coefficent. >>> >>> (hopefully i am describing the question correctly) >> >> dunno about "correctly", but it ain't clear to me. >> >> neither is the paper you cited. >> >> the Goertzel FT algorithm is an algorithm to compute a single DFT bin >> value X[k] with a simple recursive (and critically or marginally stable) >> filter that has impulse response >> >> h_k[n] = e^(-j*2*pi*n*k/N) * u[n] >> >> where u[n] is the unit step, and then you have to "sample" the output >> at time n=N to get X[k] for the x[n] data for 0<= n< N. so it looks >> like, since n=N not N-1, that there would be one zero-valued x[n] going >> into this thing for the final clock tick. >> >> now the filter depicted in Fig 1 of your paper is a filter to do that. >> just like in the text books. >> >> to make it a *sliding* Goertzel, you must turn that impulse response into >> >> h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >> >> this is an FIR filter but could be implemented with something that has >> been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >> moving-average is the simplest non-trivial example of such. this >> requires a delay line, and i did not see that in the paper you supplied >> (but i didn't read through it super carefully). >> >> i've done TIIR filters before that had a "ringing" component like >> Goertzel, and unlike a fixed-point moving sum, where you can exactly >> subtract what you added previously, because of multiplication (that >> makes the words wider) and truncation, you *cannot* exactly subtract a >> previous sample out, and since this is critically stable (some, like me, >> would call this "unstable" or at least "not stable"), if a numerical >> turd gets stuck in your accumulator, it will never come out nor die off. >> you can make it die off by changing the impulse response slightly: >> >> h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >> >> for 0< alpha<<< 1 . >> >> i would look at this problem solely from the POV of TIIR. if you want, >> i can send you a quickie .pdf that i had made a couple years ago that >> might help you set up a truncated IIR that will do what you want it to > do. >> >> i think you *could* do this without that alpha stuff, if you explicitly >> multiply your input with e^(-j*2*pi*n*k/N) and put the product >> >> x[n] * e^(-j*2*pi*n*k/N) >> >> into your delay line and use a simple moving-sum TIIR. >> >> n >> y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } >> m=n-N+1 >> >> and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to >> n=N-1 . i guess that's just a simple sliding DFT. >> >> >> -- >> >> r b-j rbj@audioimagination.com >> >> "Imagination is more important than knowledge." >> >> >> > > >> i would look at this problem solely from the POV of TIIR. if you want, >> i can send you a quickie .pdf that i had made a couple years ago that >> might help you set up a truncated IIR that will do what you want it to > do. > > Yes, I would like the pdf on how to create such a thing. I dont like the > alpha. either. I do need it to give the phase information, not just the > magnitude. > > The other question is, could i use the coefficents from the filter to > resynthesize the input signal to the filter? kinda like an 'inverse sliding > goertzel'. if so, how many resionators would one need?Please straighten me out here. Two points leave me wondering. 1. A Goertzel computes one (or maybe a few) bin(s) of a more complete DFT, not the entire spectrum. What do you want to reproduce? 2. A sliding DFT, however many bins it encompasses, gives a changing picture of a changing spectrum. What particular time is the instant of interest? How can one represent THEN using coefficients that represent NOW? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 26, 20122012-03-26
On 3/26/2012 2:12 PM, Jerry Avins wrote:> On 3/26/2012 2:04 PM, westocl wrote: >>> On 3/26/12 12:11 PM, westocl wrote: >>>> I was looking an algorithm to calculate fourier coefficents and update >> them >>>> at every new input sample, the Sliding Goertzel algorithm. This one >> seems >>>> to give both an estimate of the amplitude AND phase. I am not sure if >> any >>>> of you guys are familar with it. >>>> >>>> >> http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf >> >>>> >>>> My thoughts are that if i can generate a number lets say N coefficients >>>> with each complex resonator at every time sample then i should be able >> to >>>> use the coefficents and resenthesize the signal. >>>> >>>> The problem is i dont know how many coefficents i would need to >> synthesize >>>> the signal. >>>> >>>> With the FFT that number is known to be the length of the input data. >>>> However in this case the input data is not constrained in length, it >>>> can >> be >>>> a infinate input stream, where the 'state' of the filter along with the >>>> present input determines the fourier coefficent. >>>> >>>> (hopefully i am describing the question correctly) >>> >>> dunno about "correctly", but it ain't clear to me. >>> >>> neither is the paper you cited. >>> >>> the Goertzel FT algorithm is an algorithm to compute a single DFT bin >>> value X[k] with a simple recursive (and critically or marginally stable) >>> filter that has impulse response >>> >>> h_k[n] = e^(-j*2*pi*n*k/N) * u[n] >>> >>> where u[n] is the unit step, and then you have to "sample" the output >>> at time n=N to get X[k] for the x[n] data for 0<= n< N. so it looks >>> like, since n=N not N-1, that there would be one zero-valued x[n] going >>> into this thing for the final clock tick. >>> >>> now the filter depicted in Fig 1 of your paper is a filter to do that. >>> just like in the text books. >>> >>> to make it a *sliding* Goertzel, you must turn that impulse response >>> into >>> >>> h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>> >>> this is an FIR filter but could be implemented with something that has >>> been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >>> moving-average is the simplest non-trivial example of such. this >>> requires a delay line, and i did not see that in the paper you supplied >>> (but i didn't read through it super carefully). >>> >>> i've done TIIR filters before that had a "ringing" component like >>> Goertzel, and unlike a fixed-point moving sum, where you can exactly >>> subtract what you added previously, because of multiplication (that >>> makes the words wider) and truncation, you *cannot* exactly subtract a >>> previous sample out, and since this is critically stable (some, like me, >>> would call this "unstable" or at least "not stable"), if a numerical >>> turd gets stuck in your accumulator, it will never come out nor die off. >>> you can make it die off by changing the impulse response slightly: >>> >>> h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>> >>> for 0< alpha<<< 1 . >>> >>> i would look at this problem solely from the POV of TIIR. if you want, >>> i can send you a quickie .pdf that i had made a couple years ago that >>> might help you set up a truncated IIR that will do what you want it to >> do. >>> >>> i think you *could* do this without that alpha stuff, if you explicitly >>> multiply your input with e^(-j*2*pi*n*k/N) and put the product >>> >>> x[n] * e^(-j*2*pi*n*k/N) >>> >>> into your delay line and use a simple moving-sum TIIR. >>> >>> n >>> y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } >>> m=n-N+1 >>> >>> and the output y_k[N-1] would be the correct X[k] for x[n] from n=0 to >>> n=N-1 . i guess that's just a simple sliding DFT. >>> >>> >>> -- >>> >>> r b-j rbj@audioimagination.com >>> >>> "Imagination is more important than knowledge." >>> >>> >>> >> >> >>> i would look at this problem solely from the POV of TIIR. if you want, >>> i can send you a quickie .pdf that i had made a couple years ago that >>> might help you set up a truncated IIR that will do what you want it to >> do. >> >> Yes, I would like the pdf on how to create such a thing. I dont like the >> alpha. either. I do need it to give the phase information, not just the >> magnitude. >> >> The other question is, could i use the coefficents from the filter to >> resynthesize the input signal to the filter? kinda like an 'inverse >> sliding >> goertzel'. if so, how many resionators would one need? > > Please straighten me out here. Two points leave me wondering. > > 1. A Goertzel computes one (or maybe a few) bin(s) of a more complete > DFT, not the entire spectrum. What do you want to reproduce? > > 2. A sliding DFT, however many bins it encompasses, gives a changing > picture of a changing spectrum. What particular time is the instant > of interest? How can one represent THEN using coefficients that > represent NOW? > > JerryI am very concerned about the idea of updating every time sample. Now, if you mean you are going to update the FFT, or whatever equivalent, I do understand that all right. But then you mention "synthesis". This implies that each sinusoidal basis function changes amplitude and phase at each time sample for the "synthesis". So, are you planning to do "synthesis" at each time sample for one sample? Yet the IFFT has N output samples..... Fred
Reply by ●March 27, 20122012-03-27
>On 3/26/2012 2:12 PM, Jerry Avins wrote: >> On 3/26/2012 2:04 PM, westocl wrote: >>>> On 3/26/12 12:11 PM, westocl wrote: >>>>> I was looking an algorithm to calculate fourier coefficents andupdate>>> them >>>>> at every new input sample, the Sliding Goertzel algorithm. This one >>> seems >>>>> to give both an estimate of the amplitude AND phase. I am not sureif>>> any >>>>> of you guys are familar with it. >>>>> >>>>> >>>http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/ASlidingGoertzelAlgorithm.pdf>>> >>>>> >>>>> My thoughts are that if i can generate a number lets say Ncoefficients>>>>> with each complex resonator at every time sample then i should beable>>> to >>>>> use the coefficents and resenthesize the signal. >>>>> >>>>> The problem is i dont know how many coefficents i would need to >>> synthesize >>>>> the signal. >>>>> >>>>> With the FFT that number is known to be the length of the inputdata.>>>>> However in this case the input data is not constrained in length, it >>>>> can >>> be >>>>> a infinate input stream, where the 'state' of the filter along withthe>>>>> present input determines the fourier coefficent. >>>>> >>>>> (hopefully i am describing the question correctly) >>>> >>>> dunno about "correctly", but it ain't clear to me. >>>> >>>> neither is the paper you cited. >>>> >>>> the Goertzel FT algorithm is an algorithm to compute a single DFT bin >>>> value X[k] with a simple recursive (and critically or marginallystable)>>>> filter that has impulse response >>>> >>>> h_k[n] = e^(-j*2*pi*n*k/N) * u[n] >>>> >>>> where u[n] is the unit step, and then you have to "sample" the output >>>> at time n=N to get X[k] for the x[n] data for 0<= n< N. so it looks >>>> like, since n=N not N-1, that there would be one zero-valued x[n]going>>>> into this thing for the final clock tick. >>>> >>>> now the filter depicted in Fig 1 of your paper is a filter to dothat.>>>> just like in the text books. >>>> >>>> to make it a *sliding* Goertzel, you must turn that impulse response >>>> into >>>> >>>> h_k[n] = e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>>> >>>> this is an FIR filter but could be implemented with something thathas>>>> been dubbed "Truncated IIR" filters (TIIR) of which a moving-sum or >>>> moving-average is the simplest non-trivial example of such. this >>>> requires a delay line, and i did not see that in the paper yousupplied>>>> (but i didn't read through it super carefully). >>>> >>>> i've done TIIR filters before that had a "ringing" component like >>>> Goertzel, and unlike a fixed-point moving sum, where you can exactly >>>> subtract what you added previously, because of multiplication (that >>>> makes the words wider) and truncation, you *cannot* exactly subtracta>>>> previous sample out, and since this is critically stable (some, likeme,>>>> would call this "unstable" or at least "not stable"), if a numerical >>>> turd gets stuck in your accumulator, it will never come out nor dieoff.>>>> you can make it die off by changing the impulse response slightly: >>>> >>>> h_k[n] = e^(-alpha*n) * e^(-j*2*pi*n*k/N) * (u[n] - u[N-1-n]) >>>> >>>> for 0< alpha<<< 1 . >>>> >>>> i would look at this problem solely from the POV of TIIR. if youwant,>>>> i can send you a quickie .pdf that i had made a couple years ago that >>>> might help you set up a truncated IIR that will do what you want itto>>> do. >>>> >>>> i think you *could* do this without that alpha stuff, if youexplicitly>>>> multiply your input with e^(-j*2*pi*n*k/N) and put the product >>>> >>>> x[n] * e^(-j*2*pi*n*k/N) >>>> >>>> into your delay line and use a simple moving-sum TIIR. >>>> >>>> n >>>> y_k[n] = SUM{ x[m] * e^(-j*2*pi*m*k/N) } >>>> m=n-N+1 >>>> >>>> and the output y_k[N-1] would be the correct X[k] for x[n] from n=0to>>>> n=N-1 . i guess that's just a simple sliding DFT. >>>> >>>> >>>> -- >>>> >>>> r b-j rbj@audioimagination.com >>>> >>>> "Imagination is more important than knowledge." >>>> >>>> >>>> >>> >>> >>>> i would look at this problem solely from the POV of TIIR. if youwant,>>>> i can send you a quickie .pdf that i had made a couple years ago that >>>> might help you set up a truncated IIR that will do what you want itto>>> do. >>> >>> Yes, I would like the pdf on how to create such a thing. I dont likethe>>> alpha. either. I do need it to give the phase information, not justthe>>> magnitude. >>> >>> The other question is, could i use the coefficents from the filter to >>> resynthesize the input signal to the filter? kinda like an 'inverse >>> sliding >>> goertzel'. if so, how many resionators would one need? >> >> Please straighten me out here. Two points leave me wondering. >> >> 1. A Goertzel computes one (or maybe a few) bin(s) of a more complete >> DFT, not the entire spectrum. What do you want to reproduce? >> >> 2. A sliding DFT, however many bins it encompasses, gives a changing >> picture of a changing spectrum. What particular time is the instant >> of interest? How can one represent THEN using coefficients that >> represent NOW? >> >> Jerry > >I am very concerned about the idea of updating every time sample. >Now, if you mean you are going to update the FFT, or whatever >equivalent, I do understand that all right. >But then you mention "synthesis". >This implies that each sinusoidal basis function changes amplitude and >phase at each time sample for the "synthesis". >So, are you planning to do "synthesis" at each time sample for one >sample? Yet the IFFT has N output samples..... > >Fred---------------------------------------------------- 1. A Goertzel computes one (or maybe a few) bin(s) of a more complete DFT, not the entire spectrum. What do you want to reproduce? ----------------------------------------------------------------- Lets say we were trying to do a perfect notch filter, one should be able to take a signal into a Goertzel 'bank', and zero one of the coefficents,a and do the inverse process to get the sample domain signal. This would be very interesting, beccause the Goertzel would be very different than setting a single bin to zero in a DFT and could be done in real time, no sine(x)/x artifacts. The question is how many bins would one need. The DFT is defined to have as many basis functions as input samples... And the DFT maps N points of data in to N points of data. The Goertzel is IIR. Clearly one shoulnt need an infinite amount of resonators to only produce one sample. i only want to map one point of data into one point of data. x[n] -> GOERTZEL BANK -> multiply a coefficnt -> INVERSE BANK -> y[n]>So, are you planning to do "synthesis" at each time sample for one >sample?Yes, i want synthesis at each time sample.>Yet the IFFT has N output samples.....Correct. So i dont want to do the IFFT. I want an iverse type process that only produces the last sample. The Sliding Goerzel was interesting because it approaches an infinie length! i looked at it is kindal like what Kalman did vs what Weiener did if one could make it work.
Reply by ●March 27, 20122012-03-27
On 3/27/12 12:01 PM, westocl wrote:> > x[n] -> GOERTZEL BANK -> multiply a coefficnt -> INVERSE BANK -> y[n] >do you want to do this whole operation for *every* sample? what are you doing for the INVERSE BANK? and how do you add up the results of that to get y[n]? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
