Forums

Sliding window FFT

Started by Tanriover August 22, 2005
Hi,

I am trying to understand the difference between the sliding window FFT
algorithm and the windowed FFT (i.e. the conventional method).

Say we have a 6000 sample time domain data that we wish analyze in
frequency. We can take two approaches:

1- Pad the data stream with 2192 zeros and apply a 8192 point FFT.

2- Choose a short window size (e.g 256 points) and slide this window
across the 6000 data samples while taking the 256 point FFT and shifting
the window by one sample after doing so. Continue this operation until the
end of the 6000th sample.

I realize that method 2 gives a short term frequency response of the data
sample. However, I wonder if either of the above two methods are preferred
over the other in certain cases.

Also, in 2, after each FFT operation does one discard half of the spectrum
and scale the amplitudes by the FFT window length as in conventional FFT?
Are there any other issues that I should be aware of while applying the
sliding window FFT algorithm?


Regards,
Cagri 






 
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com
Tanriover skrev:
> Hi, > > I am trying to understand the difference between the sliding window FFT > algorithm and the windowed FFT (i.e. the conventional method). > > Say we have a 6000 sample time domain data that we wish analyze in > frequency. We can take two approaches: > > 1- Pad the data stream with 2192 zeros and apply a 8192 point FFT.
If you have an elaborate FFT algorithm, you don't need to zero pad.
> 2- Choose a short window size (e.g 256 points) and slide this window > across the 6000 data samples while taking the 256 point FFT and shifting > the window by one sample after doing so. Continue this operation until the > end of the 6000th sample. > > I realize that method 2 gives a short term frequency response of the data > sample. However, I wonder if either of the above two methods are preferred > over the other in certain cases.
The answer is yes. The methods you describe are two different tools that are used for different things. The 8192pt FFT provides one spectrum, represented as a 1D vector, that describes the whole data segment. The result from applying the sliding window FFT you describe, is a 2D image of dimension frequency vs time, that sketches the spectrum for different time intervals. This image is known as a spectrogram.
> Also, in 2, after each FFT operation does one discard half of the spectrum
If one uses the spectrogram to analyze real-valued data, it is usually convenient to skip half the image in order to save storage space. If one works with complex-valued data, one can in general not skip half the spectrum.
> and scale the amplitudes by the FFT window length as in conventional FFT?
Formally, yes, but not always in practice. Some implementations of the FFT skips a normalization step to save some floating point operations. The normalization step is not crucial in many applications. If you work with calibrated data sensors and want properly quantified spectra, you need the proper scaling. You as user are responsible for implementing the scaling when appropriate.
> Are there any other issues that I should be aware of while applying the > sliding window FFT algorithm?
It is always useful to be aware of the Heisenberg uncertainty principle. It states that you trade frequency resolution for time localization, and vice versa. Apart from that, just get yourself some simple data set (use your computers microphone and sound card to record some sound) and start analyzing. Getting experience with the tools is quite useful. Rune
On Mon, 22 Aug 2005 19:16:11 -0500, "Tanriover" <c.tanriover@ieee.org>
wrote:

>I am trying to understand the difference between the sliding window FFT >algorithm and the windowed FFT (i.e. the conventional method). > >Say we have a 6000 sample time domain data that we wish analyze in >frequency. We can take two approaches: > >1- Pad the data stream with 2192 zeros and apply a 8192 point FFT. > >2- Choose a short window size (e.g 256 points) and slide this window >across the 6000 data samples while taking the 256 point FFT and shifting >the window by one sample after doing so. Continue this operation until the >end of the 6000th sample. > >I realize that method 2 gives a short term frequency response of the data >sample. However, I wonder if either of the above two methods are preferred >over the other in certain cases. > >Also, in 2, after each FFT operation does one discard half of the spectrum >and scale the amplitudes by the FFT window length as in conventional FFT? >Are there any other issues that I should be aware of while applying the >sliding window FFT algorithm?
Rune covered the major bases, so I'll just add a little bit. The main application for the sliding DFT is when a spectrogram or spectrogram-like output is desired, i.e., successive computations of the DFT of the input in a sliding-window sense. In this case the sliding-window-DFT provides a substantial reduction in the required computational load by making the process recursive and re-using the previous output. Recomputing the full DFT or FFT conventionally would provide the exact same result, it would just require more computation. In the cases where the DFTof the previous window isn't available, then there isn't much use for the sliding window algorithm. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org