next up previous contents index CD CD Algorithms
Next: Combinatorial Problems Up: Numerical Problems Previous: Knapsack Problem

Discrete Fourier Transform



Input description: A sequence of n real or complex values tex2html_wrap_inline27722 , tex2html_wrap_inline27724 , sampled at uniform intervals from a function h.

Problem description: The discrete Fourier transform H of h, tex2html_wrap_inline27726 , for tex2html_wrap_inline27728 .

Discussion: Although computer scientists tend to be relatively unfamiliar with Fourier transforms, electrical engineers and signal processors eat them for breakfast. Functionally, Fourier transforms provide a way to convert samples of a standard time-series into the ``frequency domain''. This provides a ``dual'' representation of the function, in which certain operations become easier than in the time domain. Applications of Fourier transforms include:         

The discrete Fourier transform takes as input n   complex numbers tex2html_wrap_inline27746 , tex2html_wrap_inline27748 , corresponding to equally spaced points in a time series, and outputs n complex numbers tex2html_wrap_inline27750 , tex2html_wrap_inline27752 , each describing a sine function of given frequency. The discrete Fourier transform is defined by


and the inverse Fourier transform is defined by


which enables us move easily between h and H.

Since the output of the discrete Fourier transform consists of n numbers, each of which can be computed using a formula on n numbers, they can be computed in tex2html_wrap_inline27754 time. The fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform in tex2html_wrap_inline27756 . This is arguably the most important algorithm known, as measured by practical impact, for it opened the door to modern image processing. There are several different algorithms that call themselves FFTs, all of which are based on a divide-and-conquer approach. Essentially, the problem of computing the discrete Fourier transform on n points is reduced to computing two transforms on n/2 points each and is then applied recursively     

The FFT usually assumes that n is a power of two. If this is not the case for your data, you are usually better off padding your data with zeros to create tex2html_wrap_inline27760 elements rather than hunting for a more general code.

Since many image processing systems have strong real-time constraints, FFTs are often implemented in hardware, or at least in assembly language tuned to the particular machine. Be aware of this possibility if the codes below prove too slow.    

Implementations: FFTPACK is a package of Fortran subprograms for the fast Fourier transform of periodic and other     symmetric sequences, written by P. Swartzrauber. It includes complex, real, sine, cosine, and quarter-wave transforms. A C language translation of the main routines is also provided.   FFTPACK resides on Netlib (see Section gif) at  

Algorithm 545 [Fra79] of the Collected Algorithms of the ACM is an implementation of the fast Fourier transform optimizing virtual memory performance and written in Fortran.     See Section gif for further information.

XTango (see Section gif) is an algorithm animation system for UNIX and X-windows, which includes an interesting animation of the fast Fourier transform.  

A Pascal implementation of the fast Fourier transform for tex2html_wrap_inline27762 points appears in [MS91].   For more details, see Section gif. Sedgewick [Sed92] provides a bare bones implementation of the fast Fourier transform in C++.   See Section gif for details.

Notes: Brigham [Bri74] is an excellent introduction to Fourier transforms and the FFT and is strongly recommended, as is the exposition in [PFTV86]. Expositions in algorithms texts on the fast Fourier transform include [AHU74, Baa88, CLR90, Man89].

Credit for inventing the fast Fourier transform is usually given to Cooley and Tukey [CT65], although it is not completely deserved. See [Bri74] for a complete history.

An interesting divide-and-conquer algorithm for polynomial multiplication [KO63] does the job in tex2html_wrap_inline27764 time and is discussed in [AHU74, Man89]. An FFT-based algorithm that multiplies two n-bit numbers in tex2html_wrap_inline27766 time is due to Schönhage and Strassen [SS71] and is presented in [AHU74].

In recent years, wavelets have been proposed to replace Fourier transforms in filtering.   See [Dau92] for an introduction to wavelets.

Related Problems: Data compression (see page gif), high-precision arithmetic (see page gif).    

next up previous contents index CD CD Algorithms
Next: Combinatorial Problems Up: Numerical Problems Previous: Knapsack Problem

Mon Jun 2 23:33:50 EDT 1997