next up previous contents
Next: Practical application of the Up: Short-Term Fourier Analysis  Previous: Zero padding

Fast Fourier transforms

A simple interpretation requires tex2html_wrap_inline2931 operations. The FFT requires tex2html_wrap_inline2933 if N is a factor of two. In general, FFT style techniques can be used for any N - firstly N is decomposed into prime factors and then a recursive ``butterfly'' operation is performed for each factor.

The ``Decimation in Time'' algorithm (Cooley and Turkey, 1965):

Start with the top level Fourier transform described by:

Now write tex2html_wrap_inline2941 as a summation of odd terms and even terms:


That is, the original Fourier transform has been written in terms of two Fourier transforms operating on the odd and even portions of the data.

This recursion can be continued until the trivial case of one point is reached.

Speech Vision Robotics group/Tony Robinson