3-离散傅立叶变换

1、Chap 2 reviewAliasing effectThe Nyquist criterionBand-pass sampling1Frequency ambiguity effects of equation Equation influences all digital signal processing schemes well see in Chapter 3 that the spectrum of any discrete series of sampled values contains periodic replications of the original contin

2、uous spectrum The period between these replicated spectra in the frequency domain will always be fs, and the spectral replications repeat all the way from DC to daylight in both directions of the frequency spectrum 2aliasing effect of discrete sequences The spectrum of any discrete series contains p

3、eriodic replications of the original continuous spectrumThe period between these replicated spectra in the frequency domain will always be fs, and the spectral replications repeat all the way from DC to daylight in both directions of the frequency spectrum spectral replications of the sampled signal

4、 when fs/2 B 3The Nyquist criterionIn practical A/D conversion schemes, fs is always greater than 2B to separate spectral replications at the folding frequencies of fs/2 Spectral replicationsfs=1.5B Hzfs2B Hz4Bandpass Sampling5Digital Signal ProcessingChap 3 Discrete Fourier Transform主讲 ：杨玉红 武汉大学国家多

5、媒体软件工程技术研究中心外网邮箱 : ahka_内网邮箱：傅立叶变换的本质？傅立叶变换属于调和分析的内容，通过对事物内部适当的分析达到增进对其本质理解的目的。 近代原子论试图把世界上所有物质的本源分析为原子，而原子不过数百种而已，相对物质世界的无限丰富，这种分析和分类无疑为认识事物的各种性质提供了很好的手段。傅里叶变换将“任意”的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类，这一想法跟化学上的原子论想法非常相似！7DFTs origin - CFT DFT is a mathematical procedure used to de

6、termine the harmonic, or frequency content of a discrete signal sequenceDFTs origin: the continuous Fourier transform X(f)CFT equationDFT equation (Exponential form)8contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT resolution, zero padding and f

7、requency-domain samplingDFT processing gainThe DFT of rectangular functionsThe DFT frequency response to a complex inputThe DFT frequency response to a real cosine inputThe DFT single-bin frequency response to real cosine inputInterpreting the DFT9DFT equationDFT equation has a tangled, almost unfri

8、endly, look about it. Lets get started by expressing in a different way using Eulers relationship ej = cos() jsin()Rectangular form:Exponential form:10DFT equation - rectangular formwith N input time-domain sample values, the DFT determines the spectral content of the input at N equally spaced frequ

9、ency points N determines how many input samples are needed, the resolution of the frequency-domain results, and the amount of processing time necessary to calculate an N-point DFT Rectangular form: j is merely a convenient abstraction that helps us compare the phase relationship between various sinu

10、soidal components of a signal 11DFT equation - exampleRectangular form for N=4:m=0:m=1:m=2:m=3:Each X(m) DFT output term is the sum of the point for point product between an input sequence of signal values and a complex sinusoid of the form cos() jsin() 12DFTs analysis frequencies sampling a continu

11、ous signal at a rate of 500 samples/s perform a 16-point DFT on the sampled data, the fundamental frequency of the sinusoids is fs/N = 500/16 or 31.25 Hz The other X(m) analysis frequencies are integral multiples of the fundamental frequency:The exact frequencies of the different sinusoids depend on

12、 both the sampling rate fs, at which the original signal was sampled, and the number of samples N The N separate DFT analysis frequencies are13DFT output value Trigonometric relationships of an individual DFT X(m) complex output value DFT output value the magnitude of X(m) the phase angle of X(m) Th

13、e power of X(m) 14DFT example 1 input signalthe input signal and the m = 1 sinusoids the input signal Example: perform an 8-point DFT on a continuous input signal containing components at 1 kHz and 2 kHz 8-element sequence x(n) :the DFT of x(n) :for m = 1, or the 1-kHz (mfs/N = 18000/8) DFT frequenc

14、y term with fs=8000 samples/s15DFT example 1 DFT output for m=1the input signal and the m = 1 sinusoids the input signal for m = 1, or the 1-kHz (mfs/N = 18000/8) DFT frequency term the DFT of x(n) :16DFT example 1 DFT output for m117DFT example 1 DFT output for m=0The X(0) frequency is the non time

15、-varying (DC) component of x(n)If X(0) were nonzero, the x(n) is riding on a DC bias and has some nonzero average value18DFT example 1 DFT results characteristics (a) magnitude f X(m); (b) phase of X(m); (c) real part of X(m); (d) imaginary part of X(m) Any individual X(m) output value is nothing mo

16、re than the sum of the term-by-term products, a correlation, of an input signal sample sequence with a cosine and a sinewave whose frequencies are m complete cycles in the total N samplesThe symmetry of the DFT output terms with real input samplesWhat do those nonzero magnitude values at m=6 and m=7

17、 mean?Why do the magnitude seems four times larger than we would expect?19contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT resolution, zero padding and frequency-domain samplingDFT processing gainThe DFT of rectangular functionsThe DFT frequency

18、 response to a complex inputThe DFT frequency response to a real cosine inputThe DFT single-bin frequency response to real cosine inputInterpreting the DFT20DFT symmetry for real signalsAlthough the standard DFT is designed to accept complex input sequences, most physical DFT inputs (such as digitiz

19、ed values of some continuous signal) are referred to as realFor real input, the DFT output has an obvious conjugate symmetry conjugate symmetryExpressing the DFT in the exponential form has a terrific advantage over the rectangular formproducts of terms become the addition of exponents and, with due

20、 respect to Euler, we dont have all those trigonometric relationships to memorize21DFT symmetry for real signalsDFT outputs for m = 1 to m = (N/2) 1 are redundant with frequency output values for m (N/2) only the first N/2+1 terms are independent (a) magnitude f X(m); (b) phase of X(m); (c) real par

21、t of X(m); (d) imaginary part of X(m) 22DFT LINEARITYWithout this property of linearity, the DFT would be useless as an analytical tool because we could transform only those input signals that contain a single sinewave. The real-world signals that we want to analyze are much more complicated than a

22、single sinewave the DFT of the sum of two signals is equal to the sum of the transforms of each signal23DFT MagnitudesWhen a real input signal contains a sinewave component of peak amplitude Ao with an integral number of cycles over N input samples, the output magnitude of the DFT for that particula

23、r sinewave is MrIf the DFT input is a complex sinusoid of magnitude Ao with an integral number of cycles over N samples, the output magnitude of the DFT is Mc if the DFT input was riding on a DC value equal to Do, the magnitude of the DFTs X(0) output will be we have to be aware that the output of a

24、 real sinewave input can be as large as N/2 times the peak value of the input24DFT Magnitudes other DFT expressionThe 1/N scale factor makes the amplitudes of X(m) equal to half the time-domain input sinusoids peak value at the expense of the additional division by N computationtheres no scale chang

25、e when transforming in either directionWhen analyzing signal spectra in practice, were normally more interested in the relative magnitudes rather than absolute magnitudes of the individual DFT outputs, so scaling factors arent usually that important to us25DFT frequency axisthe DFTs frequency resolu

26、tion is fs/Nwhen m = N/2, corresponds to half the sample rate, i.e., the folding (Nyquist) frequency fs/2if fs = 8000 samples/s, then the frequency associated with the largest DFT magnitude term isif fs = 75 samples/s, then the frequency associated with the largest DFT magnitude term is now26DFT SHI

27、FTING THEOREMthe shifting theorem: a shift in time of a periodic x(n) input sequence manifests itself as a constant phase shift in the angles associated with the DFT resultssample x(n) starting at n equals some integer k, as opposed to n = 0, the DFT of those time-shifted sample values is Xshifted(m

28、) where27DFT SHIFTING THEOREM comparison between examplesDFT example2: Suppose we sampled our DFT Example 1 input sequence later in time by k = 3 samplesComparison of sampling times between DFT Example 1 and DFT Example 228DFT SHIFTING THEOREM comparison between examplesthe magnitude of Xshifted(m)

29、is unchanged from that of X(m)There is a linear phase shift of 2pkm/N in the phase of Xshifted(m)29contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT resolution, zero padding and frequency-domain samplingDFT processing gainThe DFT of rectangular f

30、unctionsThe DFT frequency response to a complex inputThe DFT frequency response to a real cosine inputThe DFT single-bin frequency response to real cosine inputInterpreting the DFT30Inverse DFTIDFT: transforming frequency-domain data into a time-domain representationa discrete time- domain signal ca

31、n be considered the sum of various sinusoidal analytical frequencies the X(m) outputs of the DFT are a set of N complex values indicating the magnitude and phase of each analysis frequency comprising that sumExponential form:Rectangular form:Notice that IDFT expression differs from the DFTs only by

32、a 1/N scale factor and a change in the sign of the exponentOther than the magnitude of the results, every characteristic that weve covered thus far regarding the DFT also applies to the IDFT31contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT reso

33、lution, zero padding and frequency-domain samplingDFT processing gainThe DFT of rectangular functionsThe DFT frequency response to a complex inputThe DFT frequency response to a real cosine inputThe DFT single-bin frequency response to real cosine inputInterpreting the DFT32DFT leakage ideal caseHer

34、es where the DFT starts to get really interesting. The two previous DFT examples gave us correct results because the input x(n) sequences were very carefully chosen sinusoidsA characteristic, known as leakage, causes our DFT results to be only an approximation of the true spectra of the original inp

35、ut signals prior to digital samplinginput sequence of three cycles and the m = 4 analysis frequency sinusoid DFT output magnitude 64 point DFT33DFT leakage ideal caseDFT produces correct results only when the input data sequence contains energy precisely at the analysis frequencies, at integral mult

36、iples of our fundamental frequency fs/Ninput sequence of three cycles and the m = 4 analysis frequency sinusoid DFT output magnitude 64 point DFT34DFT leakage practical caseIf the input has a signal component at some intermediate frequency between our analytical frequencies of mfs/N, say 1.5fs/N, th

37、is input signal will show up to some degree in all of the N output analysis frequencies of our DFT!To understand the effects of leakage, we need to know the amplitude response of a DFT when the DFTs input is an arbitrary, real sinusoidinput sequence of 3.4 cycles and the m = 4 analysis frequency sin

38、usoid DFT output magnitude 64 point DFT35DFT leakage - frequency response of a DFT for a real cosine input having k cycles in the N-point input time sequence, the amplitude response of an N-point DFT bin in terms of the bin index m is approximated by the sinc functionamplitude response as a function

39、 of bin index m magnitude response as a function of frequency in Hz DFT positive frequency response due to an N-point input sequence containing k cycles of a real cosine 36DFT leakage - frequency response of a DFT comprising a main lobe and periodic peaks and valleys known as sidelobes, as the conti

40、nuous positive spectrum of an N-point, real cosine time sequence having k complete cycles in the N-point input time intervalThe DFTs outputs are discrete samples that reside on the curves; that is, our DFT output will be a sampled version of the continuous spectrumamplitude response as a function of

41、 bin index m magnitude response as a function of frequency in Hz DFT positive frequency response due to an N-point input sequence containing k cycles of a real cosine 37DFT leakageAssume a real 8-kHz sinusoid, unity amplitude, fs = 32,000 samples/s. If we take a 32-point DFT of the samples, the DFTs

42、 frequency resolution, is fs/N = 32,000/32 Hz = 1.0 kHzDFT bin positive frequency responses 38DFT leakage asymmetrical spectrum?If the continuous spectra that were sampling are symmetrical, why does the DFT output look so asymmetrical?“at an abscissa value of 0.4 gives a magnitude scale factor of 0.

43、75. Applying 0.75 to the DFTs maximum possible peak magnitude of 32, a third bin magnitude of approximately 32 0.75 = 24but it shows that the third-bin magnitude is slightly greater than 253.4 cycles sequences DFT output magnitude (N = 64)39DFT leakageFigure shows some of the additional replications

44、 in the spectrum for the 3.4 cycles per sample interval example The leakage wraparound at the m = 0 frequency accounts for the asymmetry about the DFTs m = 3 bin Cyclic representation of the DFTs spectral replication when the DFT input is 3.4 cycles per sample interval (N = 64)Spectral replication w

45、hen the DFT input is 3.4 cycles per sample interval 40DFT leakagethe DFT exhibits leakage wraparound about the m = 0 and m = N/2 binsMinimum leakage asymmetry will occur near the N/4th bin DFT output magnitude (N=64)41DFT leakagethe DFT exhibits leakage wraparound about the m = 0 and m = N/2 binsMin

46、imum leakage asymmetry will occur near the N/4th bin DFT output magnitude (N=64)42DFT leakageDFT leakage effect is troublesome because the bins containing low-level signals are corrupted by the sidelobe levels from neighboring bins containing high-amplitude signals.Although theres no way to eliminat

47、e leakage completely, an important technique known as windowing is the most common remedy to reduce its unpleasant effectsfull output spectrum view close-up view 43contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT resolution, zero padding and fre

48、quency-domain samplingDFT processing gainThe DFT of rectangular functionsThe DFT frequency response to a complex inputThe DFT frequency response to a real cosine inputThe DFT single-bin frequency response to real cosine inputInterpreting the DFT44windowsAnytime we take the DFT of a finite-extent inp

49、ut sequence we are multiplying that sequence by a window of all ones and effectively multiplying the input values outside that window by zerosSinc functions sin(x)/x shape, is caused by this rectangular window because the continuous Fourier transform of the rectangular window is the sinc functioninf

50、inite duration input sinusoid rectangular window due to finite-time sample interval the magnitude of sinc functionWindowing reduces DFT leakage by minimizing the magnitude of sinc functions sin(x)/x sidelobes45windowsthe rectangular windows abrupt changes between one and zero cause the sidelobes in

51、the the sinc functionmultiplied by the triangular or Hanning window function to minimize the spectral leakage caused by those sidelobes, the final input signal appear to be the same at the beginning and end of the sample intervalproduct of rectangular window product of Hanning window product of tria

52、ngular window 46Windows mathematical expression47Windows magnitude responseBecause the Hamming, Hanning, and triangular windows reduce the time-domain signal levels applied to the DFT, their main lobe peak values are reduced relative to the rectangular windowthe rectangular windows magnitude respons

53、es main lobe is the most narrow, fs/N. However, its first sidelobe level is only 13 dB below the main lobe peak, which is not so goodWindow magnitude responses The various nonrectangular windows wide main lobes degrade the windowed DFTs frequency resolution by almost a factor of two48Windows magnitu

54、de response in dBthe important benefits of leakage reduction usually outweigh the loss in DFT frequency resolutionthe further reduction of the first sidelobe level, and the rapid sidelobe roll-off of the Hanning window. The Hamming window has even lower first sidelobe levels, but this windows sidelo

55、bes roll off slowly relative to the Hanning windowWindow magnitude responses in dB 49Windows hanning window the shape of the Hanning windows response looks broader and has a lower peak amplitude, but its sidelobe leakage is noticeably reduced from that of the rectangular window64-sample product of a

56、 Hanning window and a 3.4 cycles per sample interval input sinewave Hanning DFT output response vs. rectangular window DFT output response 50Windows Increased signal detection sensitivity afforded using windowingthe DFT of the windowed data shown as the triangles makes it easier for us to detect the

57、 presence of the m = 7 low-energy signal component64-sample product of a Hanning window and the sum of a 3.4 cycles and a 7 cycles per sample interval sinewaves reduced leakage Hanning DFT output response vs. rectangular window DFT output response 51Windows summary From a practical standpoint, overa

58、ll frequency resolution and signal sensitivity are affected much more by the size and shape of their window function than the mere size of their DFTs The use of any particular window depends on the application. Window selection is a trade-off between main lobe widening, first sidelobe levels, and ho

59、w fast the sidelobes decrease with increased frequencyWindows are used to improve DFT spectrum analysis accuracy, to design digital filters, to simulate antenna radiation patterns, and even in the hardware world to improve the performance of certain mechanical force to voltage conversion devicesthe

60、Chebyshev and Kaiser window functions, which have adjustable parameters, enabling us to strike a compromise between widening main lobe width and reducing sidelobe levels52contentUnderstanding the DFT equationDFT properties Inverse DFTDFT leakageWindowsDFT scalloping lossDFT resolution, zero padding