Zoom-FFT algorithm

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-]
 

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

>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

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 ).

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.