The Discrete Fourier Transform and Fast Fourier Transform

Before jumping into the details, let us examine the four different things that we attach Fourier's name to (see 2). The first one you probably learned about in your classes was the Fourier series. This takes a periodic signal with a continuous time input and gives an infinite number of frequency terms (technically, a countable infinity). And then you learned about the Fourier transform, which takes an non-periodic (i.e. infinite extent ³) signal with continuous time input and gives an infinite number of frequency terms (technically, an uncountable infinity). But neither of these is very useful for digital signal processing. We never have a continuous time input, all we have is a discretely sampled time input. So, we might wish to do the Discrete Time-Fourier transform, which takes a non-periodic signal with discrete time to an infinite number of frequency terms (a countable infinity). But that is no good either, since we never have an infinite length data sample. The best DSP money can buy only has a finite length buffer. So we must resort to the Discrete Fourier Transform (DFT). One can think of the DFT as sampling the DTFT. The DTFT computes an infinite number of frequency bins, and the DFT picks out a finite number of those. Understanding this concept will make a lot of the other concepts in this section easier to grasp.

To further illustrate this, let me give some example of each of these (and look these topics up on wikipedia for many more examples).

• Fourier Transform: if f (t) = e^{-a| t|}, then $\hat{{f}}$($\omega$) = $\sqrt{{1/2\pi}}$$\int_{{-\infty}}^{{\infty}}$f (t)e^-it$\omega$dt = $\sqrt{{\frac{2}{\pi}}}$${\frac{{a}}{{a^{2}+\omega^{2}}}}$, where $\omega$ is in rad/s.
• Fourier Series: if s(t) is a sawtooth wave s(t) = t/$\pi$, for  - $\pi$ < t < $\pi$, s(t + 2$\pi$k) = s(t) where k is an integer, then the Fourier coefficients are a_n = 0, b_n = 2(- 1)ⁿ⁺¹/$\pi$n.
• Discrete Time Fourier Transform: if f_n = sinc(a + n) for integer n and real a, with the sampling period given by t = n$\tau$ then $\hat{{f}}$($\omega$) = $\sum_{{n=-\infty}}^{{n=\infty}}$f_ne^{-i($\tau$n)$\omega$} = e^ia$\omega$.
• Discrete Fourier Transform: if f = [1, 2, 3, 4, 3, 2], then $\hat{{f}}$ = [15, - 4, 0, - 1, 0, - 4].

Of course, all of these different transforms are inter-related. And we can use the Discrete Fourier Transform to make some reasonable approximations to the Fourier Transform. The main point here is just that these are different things, and if we treat them as the same thing, we will not get the answer we want.

Table 2: A comparison of the various time to frequency transforms that we associate with Mr. Fourier.

	Continuous time input	Discretely sampled time input
Periodic input signal (i.e. finite duration in time)	Fourier Series	Discrete Fourier Transform (DFT), of which the FFT is a special case
Non-periodic signal (i.e. infinite duration in time)	Fourier Transform	Discrete time-Fourier Transform (DTFT)

The Fast Fourier Transform (FFT) is simply an efficient method for computing the DFT. The two terms are often used interchangeably, and often the terminology is abused (which is par for the course). The FFT is a recursive algorithm - it uses the divide-and-conquer strategy. For a problem of size N, the FFT splits the problem into several smaller problems, solves the smaller problems (recursively), and then assembles the results into the solution of the original problem. For this reason, the FFT is efficient only for problems where N is a power of 2 (or, at least, the product of several small factors such as 3 or 5). The FFT is not fast for problems where N is a large prime number, since that cannot be split up into smaller problems. For example, in Matlab version 6.5, an FFT of length 121,000 (having factors 2,5,11) is 2 to 3 times faster than an FFT of length 121,001 (prime). Note: many older FFT algorithms could only handle powers of 2, but modern implementations like Matlab do not have that limitation. I will not go into the details of FFT algorithms here. See [12] for a Computer Science oriented discussion or [11] for an engineering oriented discussion, or one of the many other fine books.

I frequently see people trying to use matlab fft() function to compare to Fourier Transforms of continuous functions. For example, you might have the function f (t) = e^-$\alpha$t, and you want to compute the Fourier Transform of it. Remember that this is a continous time function that extends out to infinite time. If you use matlab's fft(), you can only ever do a discretely sampled function that is periodic in time. Therefore, you may be disappointed with the results. To do a proper Fourier Transform, you will want to use a Computer Algebra System such as Maple or Mathematica. Or you could venture into matlab's symbolic toolbox.

Footnotes

...³

the Laplace transform is similar to the Fourier transform, but takes an input with semi-infinite extent (i.e. f(t) is non-zero only for t > 0)

" . $row['Name'] . " Posted on " . $row['DateTime']; echo "
"; echo $row['Comment']; echo "

"; } echo ""; ?> Leave a comment on this page:

Name: (optional)
To prove you are not a robot, what is 2+3?

This work by Daniel Kiracofe (daniel dot kiracofe at gmail dot com) is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License./' $I