CHAPTER The Discrete Fourier Transform

1 141 CHAPTER8 The Discrete Fourier TransformFourier analysis is a family of mathematical techniques, all based on decomposing signals intosinusoids. The Discrete Fourier Transform (DFT) is the family member used with digitizedsignals. This is the first of four chapters on the real DFT, a version of the Discrete Fouriertransform that uses real numbers to represent the input and output signals. The complex DFT,a more advanced technique that uses complex numbers, will be discussed in CHAPTER 31. In thischapter we look at the mathematics and algorithms of the Fourier decomposition, the heart of Family of Fourier TransformFourier analysis is named after Jean Baptiste Joseph Fourier (1768-1830),a French mathematician and physicist.

2 ( Fourier is pronounced: , and isfor@ e@ aalways capitalized). While many contributed to the field, Fourier is honoredfor his mathematical discoveries and insight into the practical usefulness of thetechniques. Fourier was interested in heat propagation, and presented a paperin 1807 to the Institut de France on the use of sinusoids to representtemperature distributions. The paper contained the controversial claim that anycontinuous periodic signal could be represented as the sum of properly chosensinusoidal waves. Among the reviewers were two of history's most famousmathematicians, Joseph Louis Lagrange (1736-1813), and Pierre Simon deLaplace (1749-1827).

3 While Laplace and the other reviewers voted to publish the paper, Lagrangeadamantly protested. For nearly 50 years, Lagrange had insisted that such anapproach could not be used to represent signals with corners, ,discontinuous slopes, such as in square waves. The Institut de France bowedto the prestige of Lagrange, and rejected Fourier 's work. It was only afterLagrange died that the paper was finally published, some 15 years , Fourier had other things to keep him busy, political activities,expeditions to Egypt with Napoleon, and trying to avoid the guillotine after theFrench Revolution (literally!)

4 The Scientist and Engineer's Guide to Digital Signal Processing142 Sample number0481216-40-20020406080 DECOMPOSESYNTHESIZEFIGURE 8-1a(see facing page)AmplitudeWho was right? It's a split decision. Lagrange was correct in his assertion thata summation of sinusoids cannot form a signal with a corner. However, youcan get very close. So close that the difference between the two has zeroenergy. In this sense, Fourier was right, although 18th century science knewlittle about the concept of energy. This phenomenon now goes by the name:Gibbs Effect, and will be discussed in CHAPTER 11. Figure 8-1 illustrates how a signal can be decomposed into sine and cosinewaves.

5 Figure (a) shows an example signal, 16 points long, running fromsample number 0 to 15. Figure (b) shows the Fourier decomposition of thissignal, nine cosine waves and nine sine waves, each with a differentfrequency and amplitude. Although far from obvious, these 18 sinusoidsadd to produce the waveform in (a). It should be noted that the objectionmade by Lagrange only applies to continuous signals. For Discrete signals,this decomposition is mathematically exact. There is no difference between thesignal in (a) and the sum of the signals in (b), just as there is no differencebetween 7 and 3+ are sinusoids used instead of, for instance, square or triangular waves?

6 Remember, there are an infinite number of ways that a signal can bedecomposed. The goal of decomposition is to end up with something easier todeal with than the original signal. For example, impulse decomposition allowssignals to be examined one point at a time, leading to the powerful techniqueof convolution. The component sine and cosine waves are simpler than theoriginal signal because they have a property that the original signal does nothave: sinusoidal fidelity. As discussed in CHAPTER 5, a sinusoidal input to asystem is guaranteed to produce a sinusoidal output. Only the amplitude andphase of the signal can change; the frequency and wave shape must remain thesame.

7 Sinusoids are the only waveform that have this useful property. Whilesquare and triangular decompositions are possible, there is no general reasonfor them to be useful. The general term: Fourier Transform , can be broken into four categories,resulting from the four basic types of signals that can be 8- The Discrete Fourier Transform1430246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-40480246810121416-8-404802468101 21416-8-4048 Cosine WavesSine WavesFIGURE 8-1bExample of Fourier decomposition.

8 A 16 point signal (opposite page) is decomposed into 9 cosinewaves and 9 sine waves. The frequency of each sinusoid is fixed; only the amplitude is changeddepending on the shape of the waveform being decomposed. The Scientist and Engineer's Guide to Digital Signal Processing144A signal can be either continuous or Discrete , and it can be either periodic oraperiodic. The combination of these two features generates the four categories,described below and illustrated in Fig. 8-2. Aperiodic-ContinuousThis includes, for example, decaying exponentials and the Gaussian signals extend to both positive and negative infinity without repeating ina periodic pattern.

9 The Fourier Transform for this type of signal is simplycalled the Fourier Transform . Periodic-ContinuousHere the examples include: sine waves, square waves, and any waveform thatrepeats itself in a regular pattern from negative to positive infinity. Thisversion of the Fourier Transform is called the Fourier signals are only defined at Discrete points between positive and negativeinfinity, and do not repeat themselves in a periodic fashion. This type ofFourier Transform is called the Discrete Time Fourier Transform . Periodic-DiscreteThese are Discrete signals that repeat themselves in a periodic fashion fromnegative to positive infinity.

10 This class of Fourier Transform is sometimescalled the Discrete Fourier series , but is most often called the DiscreteFourier Transform . You might be thinking that the names given to these four types of Fouriertransforms are confusing and poorly organized. You're right; the names haveevolved rather haphazardly over 200 years. There is nothing you can do butmemorize them and move on. These four classes of signals all extend to positive and negative infinity. Holdon, you say! What if you only have a finite number of samples stored in yourcomputer, say a signal formed from 1024 points. Isn't there a version of theFourier Transform that uses finite length signals?