Zoom-FFT algorithm
CASTalk.com Forum Index CASTalk.com
Discussion of DSP, FPGA, storage and embedded system.
 
 FAQFAQ   MemberlistMemberlist     RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 
 
Google
 
Web castalk.com
Zoom-FFT algorithm

 
Post new topic   Reply to topic    CASTalk.com Forum Index -> DSP
Author Message
Michal Kvasnicka
Guest
Posted: Tue Jan 11, 2005 12:13 am    Post subject: Zoom-FFT algorithm Reply with quote
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
Back to top
Mark Borgerding
Guest
Posted: Tue Jan 11, 2005 3:20 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
Michal Kvasnicka wrote:
Quote:
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.
Back to top
Guest
Posted: Tue Jan 11, 2005 7:28 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
You could look up Chirp FFT.

Robert

"Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote:

Quote:
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
Back to top
Michal Kvasnicka
Guest
Posted: Tue Jan 11, 2005 8:06 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
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...
Quote:
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
Back to top
Michal Kvasnicka
Guest
Posted: Tue Jan 11, 2005 8:06 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
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...
Quote:
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.
Back to top
David Jones
Guest
Posted: Tue Jan 11, 2005 2:56 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
Michal Kvasnicka wrote:
Quote:
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
Back to top
Howard Long
Guest
Posted: Tue Jan 11, 2005 4:32 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
"Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote in message
news:crvq24$1shj$1@ns.felk.cvut.cz...
Quote:
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
Back to top
Michal Kvasnicka
Guest
Posted: Tue Jan 11, 2005 9:30 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
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...
Quote:
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

Back to top
Michal Kvasnicka
Guest
Posted: Tue Jan 11, 2005 10:40 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
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...
Quote:
"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

Back to top
rutiger
Guest
Posted: Wed Jan 12, 2005 3:23 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
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:
Quote:
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

Back to top
Rick Lyons
Guest
Posted: Wed Jan 12, 2005 4:07 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
On Mon, 10 Jan 2005 22:20:23 GMT, Mark Borgerding
<mark@borgerding.net> wrote:

Quote:
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-]
Back to top
Guest
Posted: Wed Jan 12, 2005 5:55 am    Post subject: Re: Zoom-FFT algorithm Reply with quote
"Michal Kvasnicka" <michal.kvasnicka@No_s_Pam.quick.cz> wrote:

Quote:
I am not sure that Chirp FFT is the same as Zomm FFT, see for example:
http://www.numerix-dsp.com/zoomfft.html

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
Back to top
Mark Borgerding
Guest
Posted: Wed Jan 12, 2005 6:16 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
Michal Kvasnicka wrote:
Quote:
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 ).
Back to top
Mark Borgerding
Guest
Posted: Wed Jan 12, 2005 6:20 pm    Post subject: Re: Zoom-FFT algorithm Reply with quote
Rick Lyons wrote:
Quote:
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]


Quote:
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.

Quote:

Ah but Mark, do I smell a "Borgerding magazine article"
here? Humm, ... :-)

No, that was just the beans I had at lunch. Sorry.
Back to top
 
Post new topic   Reply to topic    CASTalk.com Forum Index -> DSP All times are GMT
Page 1 of 1

 
 You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




VoIP Electronics Powered by phpBB