The Scientist and Engineer's Guide to
Digital Signal Processing
By Steven W. Smith, Ph.D.
Book Search
Table of contents
- 1: The Breadth and Depth of DSP
- 2: Statistics, Probability and Noise
- 3: ADC and DAC
- 4: DSP Software
- 5: Linear Systems
- 6: Convolution
- 7: Properties of Convolution
- 8: The Discrete Fourier Transform
- 9: Applications of the DFT
- 10: Fourier Transform Properties
- 11: Fourier Transform Pairs
- 12: The Fast Fourier Transform
- 13: Continuous Signal Processing
- 14: Introduction to Digital Filters
- 15: Moving Average Filters
- 16: Windowed-Sinc Filters
- 17: Custom Filters
- 18: FFT Convolution
- 19: Recursive Filters
- 20: Chebyshev Filters
- 21: Filter Comparison
- 22: Audio Processing
- 23: Image Formation & Display
- 24: Linear Image Processing
- 25: Special Imaging Techniques
- 26: Neural Networks (and more!)
- 27: Data Compression
- 28: Digital Signal Processors
- 29: Getting Started with DSPs
- 30: Complex Numbers
- 31: The Complex Fourier Transform
- 32: The Laplace Transform
- 33: The z-Transform
- 34: Explaining Benford's Law
How to order your own hardcover copy
Wouldn't you rather have a bound book instead of 640 loose pages?Your laser printer will thank you!
Order fromAmazon.com.
Chapter 10: Fourier Transform Properties
Unlike the other three Fourier Transforms, the DFT viewsboth the time domainand the frequency domain asperiodic. This can be confusing and inconvenientsince most of the signals used in DSP arenot periodic. Nevertheless, if youwant to use the DFT, you must conform with the DFT's view of the world.
Figure 10-8 shows two different interpretations of the time domain signal. First,look at the upper signal, the time domain viewed asN points. This representshow digital signals are typically acquired in scientific experiments andengineering applications. For instance, these 128 samples might have beenacquired by sampling some parameter at regular intervals oftime. Sample 0 isdistinct and separate from sample 127 because they were acquired atdifferenttimes. From the way this signal was formed, there is no reason to think that thesamples on the left of the signal are even related to the samples on the right.
Unfortunately, the DFT doesn't see things this way. As shown in the lowerfigure, the DFT views these 128 points to be a single period of an infinitely longperiodic signal. This means that the left side of the acquired signal is connectedto the right side of a duplicate signal. Likewise, the right side of the acquiredsignal is connected to the left side of an identical period. This can also bethought of as the right side of the acquired signal wrapping around andconnecting to its left side. In this view, sample 127 occurs next to sample 0, justas sample 43 occurs next to sample 44. This is referred to as beingcircular,and is identical to viewing the signal as beingperiodic.
The most serious consequence of this periodicity istime domain aliasing. Toillustrate this, suppose we take a time domain signal and pass it through theDFT to find its frequency spectrum. We could immediately pass this frequencyspectrum through an Inverse DFT to reconstruct the original time domainsignal, but the entire procedure wouldn't be very interesting. Instead, we willmodify the frequency spectrum in some manner before using the Inverse DFT. For instance, selected frequencies might be deleted, changed in amplitude orphase, shifted around, etc. These are the kinds of things routinely done in DSP. Unfortunately, these changes in the frequency domain can create a time domainsignal that is too long to fit into
a single period. This forces the signal to spill over from one period into theadjacent periods. When the time domain is viewed ascircular, portions of thesignal that overflow on the right suddenly seem to reappear on the left side ofthe signal, and vice versa. That is, the overflowing portions of the signalaliasthemselves to a new location in the time domain. If this new location happensto already contain an existing signal, the whole mess adds, resulting in a loss ofinformation. Circular convolution resulting from frequency domainmultiplication (discussed in Chapter 9), is an excellent example of this type ofaliasing.
Periodicity in the frequency domain behaves in much the same way, but is morecomplicated. Figure 10-9 shows an example. The upper figures show themagnitude and phase of the frequency spectrum, viewed as being composed ofN/2 + 1 samples spread between 0 and 0.5 of the sampling rate. This is thesimplest way of viewing the frequency spectrum, but it doesn't explain manyof the DFT's properties.
The lower two figures show how the DFT views this frequency spectrum asbeing periodic. The key feature is that the frequency spectrum between 0 and0.5 appears to have amirror image of frequencies that run between 0 and -0.5. This mirror image ofnegative frequencies is slightly different for themagnitude and the phase signals. In the magnitude, the signal is flipped left-for-right. In the phase, the signal is flipped left-for-right,and changed in sign. As you recall, these two types of symmetry are given names: the magnitude issaid to be aneven signal (it haseven symmetry), while the phase is said to beanodd signal (it hasodd symmetry). If the frequency spectrum is convertedinto the real and imaginary parts, thereal part will always beeven, while theimaginary part will always beodd.
Taking these negative frequencies into account, the DFT views the frequencydomain as periodic, with a period of 1.0 times the sampling rate, such as -0.5 to0.5, or 0 to 1.0. In terms of sample numbers, this makes the length of thefrequency domain period equal toN, the same as in the time domain.
The periodicity of the frequency domain makes it susceptible tofrequencydomain aliasing, completely analogous to the previously described time domainaliasing. Imagine a time domain signal that corresponds to some frequencyspectrum. If the time domain signal is modified, it is obvious that the frequencyspectrum will also be changed. If the modified frequency spectrum cannot fitin the space provided, it will push into the adjacent periods. Just as before, thisaliasing causes two problems: frequencies aren't where they should be, andoverlapping frequencies from different periods add, destroying information.
Frequency domain aliasing is more difficult to understand than time domainaliasing, since the periodic pattern is more complicated in the frequencydomain. Consider a single frequency that is being forced to move from 0.01 to0.49 in the frequency domain. The corresponding negative frequency istherefore moving from -0.01 to -0.49. When the positive frequency moves
across the 0.5 barrier, the negative frequency is pushed across the -0.5 barrier. Since the frequency domain is periodic, these same events are occurring in theother periods, such as between 0.5 and 1.5. A clone of the positive frequencyis crossing frequency 1.5 from left to right, while a clone of the negativefrequency is crossing 0.5 from right to left. Now imagine what this looks likeif you can only see the frequency band of 0 to 0.5. It appears that a frequencyleaving to theright, reappears on theright, but moving in the opposite direction.
Figure 10-10 illustrates how aliasing appears in the time and frequency domainswhen only a single period is viewed. As shown in (a), if one end of a timedomain signal is too long to fit inside a single period, the protruding end will becut off andpasted onto the other side. In comparison, (b) shows that when afrequency domain signal overflows the period, the protruding end isfolded over. Regardless of where the aliased segment ends up, it adds to whatever signal isalready there, destroying information.
Let's take a closer look at these strange things callednegative frequencies.Are they just some bizarre artifact of the mathematics, or do they have a realworld meaning? Figure 10-11 shows what they are about. Figure (a) is adiscrete signal composed of 32 samples. Imagine that you are given the taskof finding the frequency spectrum that corresponds to these 32 points. To make your job easier, you are told that these points represent a discrete cosine wave. In other words, you must find the frequency and phase shift (f and θ) such thatx[n] = cos(2πnf/N + θ) matches the given samples. It isn't long before you come up with the solution shown in (b), that is,f = 3 and θ = -π/4.
If you stopped your analysis at this point, you only get 1/3 credit for theproblem. This is because there are two other solutions that you have missed. As shown in (c), the second solution isf = -3 and θ = π/4. Even if the idea ofanegative frequency offends your sensibilities, it doesn't
change the fact that it is a mathematically valid solution to the defined problem. Everypositive frequency sinusoid can alternately be expressed as anegativefrequency sinusoid. This applies to continuous as well as discrete signals.
The third solution is not a single answer, but an infinite family of solutions. Asshown in (d), the sinusoid withf = 35 and θ = -π/4 passes through all of thediscrete points, and is therefore a correct solution. The fact that it showsoscillation between the samples may be confusing, but it doesn't disqualify itfrom being an authentic answer. Likewise,f = ±29,f = ?35,f = ?61, andf = ?67 are all solutions with multiple oscillations between the points. Thisthird group of solutions requires the original signal to be discrete, rather thancontinuous. With continuous signals, you can't have oscillations between thesamples, because you don't have samples.
Each of these three solutions corresponds to a different section of the frequencyspectrum. For discrete signals, the first solution corresponds to frequenciesbetween 0 and 0.5 of the sampling rate. The second solution results infrequencies between 0 and -0.5. Lastly, the third solution makes up the infinitenumber of duplicated frequencies below -0.5 and above 0.5. With continuoussignals, the first solution results in frequencies from zero to positive infinity,while the second solution results in frequencies from zero to negative infinity.
Many DSP techniques do not require the use of negative frequencies, or anunderstanding of the DFT's periodicity. For example, two common ones weredescribed in the last chapter,spectral analysis, and thefrequency response ofsystems. For these applications, it is completely sufficient to view the timedomain as extending from sample 0 toN-1, and the frequency domain from zeroto one-half of the sampling frequency. These techniques can use a simplerview of the world because they never result in portions of one period movinginto another period. With this restriction, looking at a single period is nodifferent from looking at the entire periodic signal.
However, certain procedures canonly be analyzed by considering how signalsoverflow between periods. Two examples of this have already been presented,circular convolution andanalog-to-digital conversion. In circular convolution,multiplication of the frequency spectra results in the time domain signals beingconvolved. If the resulting time domain signal is too long to fit inside a singleperiod, it overflows into the adjacent periods, resulting intime domain aliasing. In contrast, analog-to-digital conversion is an example offrequency domainaliasing. A nonlinear action is taken in the time domain, that is, changing acontinuous signal into a discrete signal by sampling. The problem is, thespectrum of the original analog signal may be too long to fit inside the discretesignal's spectrum. When we force the situation, the ends of the spectrumprotrude into adjacent periods. Let's look at two more examples where theperiodic nature of the DFT is important,compression & expansion of signals,andamplitude modulation.