Reply by Mark Borgerding●January 12, 20052005-01-12
Rick Lyons wrote:
> On Mon, 10 Jan 2005 22:20:23 GMT, Mark Borgerding
> <mark@borgerding.net> wrote:
>
>
>>Michal Kvasnicka wrote:
>>
>>>Dear colleagues,
>>>
>>>I am looking for detailed description of the "zoom-fft" algorithm
[snip]
>>>Michal
>>Rick Lyons' book "Understanding DSP" has a good description.
>>
>>My only beef (maybe 3rd edition, Rick?) is that he leaves the details of
>>the low-pass/band-pass filter as an exercise to the reader.
[snip]
> Hi Mark, (hope all is well)
>
> You are correct. I'm "guilty as charged".
> When I was preparing that Zoom FFT description,
> I realized 4-5 possibilites for implementing the
> lowpass filter with each possibility having their own
> computational workload. Combine with those
> possibilities the fact that each filter type's
> workload would be a function of the desired
> passband flatness, transition regon width, and
> stopband attenuation. The problem of characterizing
> all the possible scenarios seemed a bit overwhelming
> to me at the time.
Not to mention the differences between various platforms. The
performance tradeoffs involved would be very different for a Pentium4
compared to a TI-54x DSP.
>
> Ah but Mark, do I smell a "Borgerding magazine article"
> here? Humm, ... :-)
No, that was just the beans I had at lunch. Sorry.
Reply by Mark Borgerding●January 12, 20052005-01-12
Michal Kvasnicka wrote:
> Could you recommend me some good starting point for "multirate decimation"?
Most of my understanding comes from Crochiere & Rabiner's Multirate book
( which I no longer have, so I cannot quote chapter & verse ).
I hear that Fredric Harris' new book is good too ( I just ordered it
myself ).
This is more than one way to zoom in an FFT, and they can all be
called "Zoom-FFT" ... even if this guy thinks that the method he has
using is the only one for that name. But I think he is mainly just
explaining correctly that the method he is using and the Chirp FFT are
not the same.
I also wanted to be able to focus the transform in on a subset of the
standard Fs/2 range given by a standard FFT ( i.e. Zoom ). I
originally took the approach that this guy did, but the mix down to
baseband was done using multiplication by sinusoids, and I was never
able to get enough resolution in these sinusoid terms. So I went
looking for a different approach, and found the Chirp-FFT.
I do not believe that you will find free code for that entire
"Zoom-FFT". But you can see all the pieces, as he shows on the
pictures ( with maybe some additional research needed ). Some of
these pieces you may find code for, like the FFT or possibly filters.
But the other parts you can probably code yourself. That is the most
fun part of DSP!
Regards,
Robert
( modify address for return mail )
www.numbersusa.com
www.americanpatrol.com
Reply by Rick Lyons●January 11, 20052005-01-11
On Mon, 10 Jan 2005 22:20:23 GMT, Mark Borgerding
<mark@borgerding.net> wrote:
>Michal Kvasnicka wrote:
>> Dear colleagues,
>>
>> I am looking for detailed description of the "zoom-fft" algorithm and its
>> effective implementation in C/C++, Fortran or Matlab.
>> Thanks in advance,
>>
>> Michal
>>
>>
>
>Rick Lyons' book "Understanding DSP" has a good description.
>
>My only beef (maybe 3rd edition, Rick?) is that he leaves the details of
>the low-pass/band-pass filter as an exercise to the reader. Without
>care, the cost of the filtering could outweigh the gains from the
>smaller FFT.
>
>I'd suggest multirate decimation
>
>-- Mark Borgerding.
Hi Mark, (hope all is well)
You are correct. I'm "guilty as charged".
When I was preparing that Zoom FFT description,
I realized 4-5 possibilites for implementing the
lowpass filter with each possibility having their own
computational workload. Combine with those
possibilities the fact that each filter type's
workload would be a function of the desired
passband flatness, transition regon width, and
stopband attenuation. The problem of characterizing
all the possible scenarios seemed a bit overwhelming
to me at the time.
Ah but Mark, do I smell a "Borgerding magazine article"
here? Humm, ... :-)
[-Rick-]
Reply by rutiger●January 11, 20052005-01-11
I could be mistaken, but it looks like all the freeware you need is the
FFTW. The decimation and filtering is easliy implemented in a dozen or
so lines of c-code. As for the filter coefficients, just use matlab to
find them and then incorporate them into your code. I am guessing that
the whole thing, driver and all, should come in at less than 200 lines
of code.
Michal Kvasnicka wrote:
> I am still can not believe to fact, that is not possible to find any
> freeware code (matlab, fortran, C) which implemented zoom-fft
algorithm.
>
> Who knows any freeware code or detailed description of the zoom-fft
> algorithm???
>
> Michal
>
> "David Jones" <dajxxx@ceh.ac.uk> p=ED=B9e v diskusn=EDm p=F8=EDsp=ECvku
> news:41e3a2b1$1@news.nwl.ac.uk...
> > Michal Kvasnicka wrote:
> > > I am not sure that Chirp FFT is the same as Zomm FFT, see for
> > example:
> > > http://www.numerix-dsp.com/zoomfft.html
> > >
> > > Michal
> > > <r_obert@REMOVE_THIS.hotmail.com> p=EDse v diskusn=EDm pr=EDspevku
> > > news:rde6u0t4pfpgjla9t1ogkftnskplcnn2ug@4ax.com...
> > >> You could look up Chirp FFT.
> > >>
> > >> Robert
> > >>
> > >> "Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote:
> > >>
> > >>> Dear colleagues,
> > >>>
> > >>> I am looking for detailed description of the "zoom-fft"
algorithm
> > >>> and its effective implementation in C/C++, Fortran or Matlab.
> > >>> Thanks in advance,
> > >>>
> > >>> Michal
> > >>>
> > >>
> > >>
> > >> ( modify address for return mail )
> > >>
> > >> www.numbersusa.com
> > >> www.americanpatrol.com
> >
> > From this description it seems closely related to what used (?) to
be
> > called "complex demodulation". The only ref I have to hand relates
to
> > its use in estimating bispectra:
> >
> > MG Godfrey (1965) An exploratory study of the bi-spectrum of
ecomomic
> > time-series, Applied Statistics, 14 (1), 48-69.
> >
> > This does give a first-principles outline of the approach.
> >
> > David Jones
> >
> >
Reply by Michal Kvasnicka●January 11, 20052005-01-11
Yes, NumerixDSP is really good solution, but in this time I am looking for
any freeware code before I buy something better.
So, do you know any freeware code for the zoom-fft???
Michal
"Howard Long" <howard@howardlongxxx.com> p��e v diskusn�m p��sp�vku
news:cs0v2e$95e$1@hercules.btinternet.com...
> "Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote in message
> news:crvq24$1shj$1@ns.felk.cvut.cz...
> > I am not sure that Chirp FFT is the same as Zomm FFT, see for example:
> > http://www.numerix-dsp.com/zoomfft.html
>
> My understanding of the NumerixDSP ZoomFFT function is that it does uses
> quadrature frequency mixing to downconvert the area of interest to
> 'baseband' I/Q and then performs the FFT on that baseband.
>
> Although I haven't used that particular function within the NumerixDSP
> library, I have used several other parts of the library and it takes the
> donkey work out of re-inventing the wheel, especially if you develop
> cross-platform: it's convenient to be able to write and test stuff on the
> laptop first, and then implement it on the target platform later.
>
> Cheers, Howard
>
>
Reply by Howard Long●January 11, 20052005-01-11
"Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote in message
news:crvq24$1shj$1@ns.felk.cvut.cz...
My understanding of the NumerixDSP ZoomFFT function is that it does uses
quadrature frequency mixing to downconvert the area of interest to
'baseband' I/Q and then performs the FFT on that baseband.
Although I haven't used that particular function within the NumerixDSP
library, I have used several other parts of the library and it takes the
donkey work out of re-inventing the wheel, especially if you develop
cross-platform: it's convenient to be able to write and test stuff on the
laptop first, and then implement it on the target platform later.
Cheers, Howard
Reply by Michal Kvasnicka●January 11, 20052005-01-11
I am still can not believe to fact, that is not possible to find any
freeware code (matlab, fortran, C) which implemented zoom-fft algorithm.
Who knows any freeware code or detailed description of the zoom-fft
algorithm???
Michal
"David Jones" <dajxxx@ceh.ac.uk> p��e v diskusn�m p��sp�vku
news:41e3a2b1$1@news.nwl.ac.uk...
> Michal Kvasnicka wrote:
> > I am not sure that Chirp FFT is the same as Zomm FFT, see for
> example:
> > http://www.numerix-dsp.com/zoomfft.html
> >
> > Michal
> > <r_obert@REMOVE_THIS.hotmail.com> p�se v diskusn�m pr�spevku
> > news:rde6u0t4pfpgjla9t1ogkftnskplcnn2ug@4ax.com...
> >> You could look up Chirp FFT.
> >>
> >> Robert
> >>
> >> "Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote:
> >>
> >>> Dear colleagues,
> >>>
> >>> I am looking for detailed description of the "zoom-fft" algorithm
> >>> and its effective implementation in C/C++, Fortran or Matlab.
> >>> Thanks in advance,
> >>>
> >>> Michal
> >>>
> >>
> >>
> >> ( modify address for return mail )
> >>
> >> www.numbersusa.com
> >> www.americanpatrol.com
>
> From this description it seems closely related to what used (?) to be
> called "complex demodulation". The only ref I have to hand relates to
> its use in estimating bispectra:
>
> MG Godfrey (1965) An exploratory study of the bi-spectrum of ecomomic
> time-series, Applied Statistics, 14 (1), 48-69.
>
> This does give a first-principles outline of the approach.
>
> David Jones
>
>
Reply by David Jones●January 11, 20052005-01-11
Michal Kvasnicka wrote:
> I am not sure that Chirp FFT is the same as Zomm FFT, see for
example:
> http://www.numerix-dsp.com/zoomfft.html
>
> Michal
> <r_obert@REMOVE_THIS.hotmail.com> p�se v diskusn�m pr�spevku
> news:rde6u0t4pfpgjla9t1ogkftnskplcnn2ug@4ax.com...
>> You could look up Chirp FFT.
>>
>> Robert
>>
>> "Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote:
>>
>>> Dear colleagues,
>>>
>>> I am looking for detailed description of the "zoom-fft" algorithm
>>> and its effective implementation in C/C++, Fortran or Matlab.
>>> Thanks in advance,
>>>
>>> Michal
>>>
>>
>>
>> ( modify address for return mail )
>>
>> www.numbersusa.com
>> www.americanpatrol.com
From this description it seems closely related to what used (?) to be
called "complex demodulation". The only ref I have to hand relates to
its use in estimating bispectra:
MG Godfrey (1965) An exploratory study of the bi-spectrum of ecomomic
time-series, Applied Statistics, 14 (1), 48-69.
This does give a first-principles outline of the approach.
David Jones
Reply by Michal Kvasnicka●January 11, 20052005-01-11
Could you recommend me some good starting point for "multirate decimation"?
The basic question is:
Is Zoom FFT generally faster than standard FFT if I am looking only for
narrow band part of spectrum?
Michal
"Mark Borgerding" <mark@borgerding.net> p�se v diskusn�m pr�spevku
news:HcDEd.82573$mA3.259@fe2.columbus.rr.com...
> Michal Kvasnicka wrote:
> > Dear colleagues,
> >
> > I am looking for detailed description of the "zoom-fft" algorithm and
its
> > effective implementation in C/C++, Fortran or Matlab.
> > Thanks in advance,
> >
> > Michal
> >
> >
>
> Rick Lyons' book "Understanding DSP" has a good description.
>
> My only beef (maybe 3rd edition, Rick?) is that he leaves the details of
> the low-pass/band-pass filter as an exercise to the reader. Without
> care, the cost of the filtering could outweigh the gains from the
> smaller FFT.
>
> I'd suggest multirate decimation
>
> -- Mark Borgerding.