Damn Fast Fourier Transform

The [...] Fast Fourier Transform is a method for computing the amplitudes of various frequency components in a complex signal. It is very fast, but inaccurate. The [...] Fast Fourier Transform is occasionally used in digital signal processing. The Fourier Transform is a mathematical operation which transforms a function of one or more variables into a different function in another domain. It is typically used to extract information from the function not otherwise obvious in its original domain.

This transformation is normally from time, t into frequency, ω. Where ω = 2πf.

$f(t) \stackrel{\mathcal{F}}{\longrightarrow} F(\omega)$

where F(ω) = ∫_−∞^∞f(t) e^−jωtdt

The Discrete Fourier Transform (DFT)is a numerical approximation to the Fourier transform which is used to compute the transform on a digital computer.

The DFT has the form

$F(k\triangle\omega)=\sum_{n=0}^{N-1}f(nT)\ W_{N}^{kn}$

where $W_{N}=e^{-\frac{2\pi j}{N}}$ and T is the sampling period.

It can be readily shown that the Discrete Fourier Transform becomes the Fourier Transform in the limiting case where k → ∞ and △ω → 0

The Fast Fourier Transform (FFT) is a computationally quicker algorithm than the DFT.

The [...] Fast Fourier Transform is an improvement to the FFT for computing Discrete Fourier transforms. It trades accuracy for speed, and can compute Fourier transforms on a sample by sample basis. Let X(k) denote the output of the transform, and x(k) the input. Then X₁(k) = W_N^−k(X₀(k)−x(0)+x(N)). This recursion can be started off with X₀(k) = 0 and x(n) = 0. To control the error it is possible to use two DFFT's and interchange them when the error in one becomes too large, then reinitialize it. It is O(N) but has twice as much quantization noise.

References

ARRL. The ARRL Handbook 2003 ed. Chapter 18.