Zooming FFT

Zooming FFT

Post by Craig M. Wals » Thu, 05 Jan 1995 10:50:24



Dear comp.dsp members:

I recall having read a few years back (when I used to actually
read such things at bedtime) about zooming FFTs.  As I recollect,
it is possible to re-compute an FFT so as to "zoom" in on a
particular segment of the spectrum to get more detailed information
about that part of the spectrum.  Can anyone describe this method
or provide a reference for this?  Or, was I already asleep and
dreaming when I read this <g>?

Thanks for the help,

Craig Walsh

 
 
 

Zooming FFT

Post by John W. Herm » Fri, 06 Jan 1995 04:17:28


The correct reference was pointed out in another thread in this group.

--


Newsgroups: comp.dsp
Subject: Re: FFT algorithm for padded data wanted
Date: 4 Jan 1995 01:39:11 GMT
Organization: NASA Goddard Space Flight Center -- Greenbelt, Maryland USA
Lines: 42

Dear Greg:

Also try the following reference:

Sorenson, H. V. and Burrus, S.

Efficient Computation of the DFT with only a subset of input or output points

IEEE Transactions of Signal Processing, V. 41, N0. 3, March, 1993,
pp. 1184-1200.

This method is guaranteed to be better than any DFT-pruning algorithm
in existence.

I have used it to implement a parallel FFT using a message passing
paradigm.

Good luck.

Samir

 
 
 

Zooming FFT

Post by Jens Joergen Niels » Sat, 07 Jan 1995 09:07:54


Hi



Quote:>I recall having read a few years back (when I used to actually
>read such things at bedtime) about zooming FFTs.


I think you might be looking for what I know as a zoom FFT, an algorithm
used in some commercially available FFT based spectrum analyzers. Here
is a (rough) outline of the algorithm :

(1) The (real) input signal, x(n), is multiplied by the complex signal:
    y(n) = x(n) * (cos(2*pi*fc/fs*n) - i*sin(2*pi*fc/fs*n)). fs is the
    sample frequency and fc is the center frequency of the frequency
    band of interest. (The multiplication with exp(-i*2pi*fc/fs)
    corresponds to a convolution with a deltafunction located at fc in
    the frequency domain and the result is a frequency shift).

(2) The sample rate of the frequency shifted complex signal, y(n), is
    reduced by a factor M. Be sure to lowpass filter y(n) appropriately
    before decimation in order to avoid aliasing. The real and the
    imaginary part of y(n) can be handled as two separate signals.

(3) The decimated complex signal, z(m), is window weighted, complex
    FFT'ed (and perhaps averaged). If an FFT of length N is used the
    index, n, of a spectrum value (bin) is related to the frequency :

       freq(n) = fc + n * fs / (M * N)      for  n < N/2
                 fc + (n-N) * fs / (M * N)  for  N/2 <= n < N

This method effectively focuses the FFT effort in the frequency band
of interest (near fc). The obtained resolution is equivalent to that
of an FFT of length (N*M).

In a follow-up Mark Fowler gave the following reference:
   I think you'll find the following paper of interest:
   J. W. Cooley and S. Winograd, "A Limited range Discrete Fourier
   Transform Algorithm," ICASSP 1980, pp. 213-217.

(which I haven't read)

Best regards
Jens Joergen

*---------------------*---------------------------------------------------*
: Jens Jorgen Nielsen : Ever watched galaxies clash ?                     :

*---------------------*---------------------------------------------------*

 
 
 

Zooming FFT

Post by Sunil Narasimh » Tue, 10 Jan 1995 04:45:48


For a given length of data, a ZOOMING effect may be introduced
by using Chirp-Z transform (see Digital Signal Processing by Rabiner
and Gold). The Chirp-Z transform generates the samples on any arc in
the Z-domain. If one chooses points on a portion of the unit circle that
corresponds to the required part of the spectrum to be zoomed -- that is
probably what you have in mind.

Chirp-Z transform actually interpolates the FFT, and does not provide any
increase in resolution. The resolution is limited by the length of the
data signal.

Sunil Narasimhan

 
 
 

Zooming FFT

Post by Akinori NISHIHA » Wed, 11 Jan 1995 12:28:57



 >Also try the following reference:
 >
 >Sorenson, H. V. and Burrus, S.
 >Efficient Computation of the DFT with only a subset of input or output points
 >IEEE Transactions of Signal Processing, V. 41, N0. 3, March, 1993,
 >pp. 1184-1200.

Also try the following reference:

T.Cooklev and A.Nishihara
Generalized and Partial FFT
IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences
vol.E77-A, No.9, pp.1466-1474, September 1994
--
Akinori Nishihara                                         "To je pravda."
Tokyo Institute of Technology,    Phone:    +81 3 5734 2560
2-12-1, Ookayama, Meguro-ku,      Fax:      +81 3 5734 2909

 
 
 

Zooming FFT

Post by Steven Webst » Sat, 14 Jan 1995 23:38:06


I've missed all of this thread, as I've not been at University over Xmas.  

I am however *extremely* interested in more reading on Zooming FFT's.  If
anyone has saved this thread, or if the original poster could forward me any
replied (s)he received I would be extremely grateful.

Thanks very much in advance,

        Steven

___________________________________________________________________________
                    |
 Steven Webster     | 4th Year Computer Science and Electronic Engineering

____________________|_____________________________________________________

 
 
 

1. ZOOM FFT

I have done a search through the old comp.dsp threads at
sbibtemp.rice.edu for references to the Zoom FFT. All the information
I can find is what I already know. No one in the previous threads
appeared to have implemented one, but have just read a bit about one
(sound familiar?).

I wonder if anyone has actually implemented a zoom FFT with success,
and if so, is there any source code anywhere because my searches came
up blank.

Thanks

Andy Callow

2. PC controller?

3. Zoom FFT (Bruel & Kjaer)

4. Young Lady needs file conversion help

5. Zoom-FFT

6. language setting

7. Zoom-FFT in MATLAB

8. Q: ShowWindow() vs UpdateWindow()

9. Zoom-FFT/MATLAB

10. Mutlirate filters and the zoom FFT

11. zoom FFT

12. Zoom FFT?

13. Zoom-FFT source code?