MIT OpenCourseWare http://ocw.mit.edu 2.161 Signal Processing: Continuous and Discrete Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.� � F m m Massachusetts Institute of Technology Department of Mechanical Engineering 2.161 Signal Processing - Continuous and Discrete Fall Term 2008 Lecture 111 Reading: • Class Handout: Sampling and the Discrete Fourier Transform • Class Handout: The Fast Fourier Transform • Proakis and Manolakis (4th Ed.) Ch. 7 • Oppenheim, Schafer & Buck (2nd Ed.) Chs. 8 & 9 1 The Discrete Fourier Transform – continued In Lecture 10 the DFT pair associated with a sample set {fn} of length N was defined as N−1 Fm = fn e −j2πmn/N n=0 N−11 fn = Fm ej2πmn/N N m=0 The value Fm was interpreted as F∗(j Ω) evaluated at Ω = 2π/NΔT . 1.1 Organization of the DFT The N components in a DFT represent one period of a periodic spectrum. The first N/2 lines in the spectrum represent physical frequencies 0 ...(π/ΔT ) radians/second. The components in the upper half of the sequence, FN/2+1 ...FN−1, may be considered to be the negative frequency components F−N/2+1 ...F−1 in the spectrum. It is common to translate the upper half of the record to the the left side of a plot to enhance the physical meaning. F N e q u i - s pm i n o n e p e N - 1 a c e d s a m p l e s r i o d o f Fm i n t e r p r e t t o p N / 2 v a l u e s a s r e p r e s e n t i n g n e g a t i v e f r e q u e n c i e s i n F * ( j 9 ) . 0 N / 2 N - 1 N / 2 - 10 1copyright cD.Rowell 2008 11–1� � 1.2 Spectral Resolution of the DFT The DFT pair provide a transform relationship between a pair of (complex) data sets {fn}and {Fm}, each of length N. If the sampling interval associated with {fn} is ΔT units, the record duration is T = NΔT. The frequency resolution, or line spacing, ΔΩ, in the DFT is 2π 2π 1 ΔΩ = = rad/s, or ΔF = Hz. (1)NΔT T T and the frequency range spanned by the N lines in the DFT is 2π 1 NΔΩ = rad/s, or NΔF = Hz. (2)ΔT ΔT The sequence {Fm} represents both the positive and negative frequencies in a two-sided spectrum. The highest (positive) frequency component in the spectrum is half of this range (the Nyquist frequency), that is π 1 Ωmax = rad/s, or Fmax = Hz. (3)ΔT 2ΔT We conclude therefore, that the resolution within the DFT depends on the duration T of the data record, and the maximum frequency depends on the sampling interval ΔT . 1.3 Properties of the Discrete Fourier Transform Because the DFT is derived directly as a sampled continuous Fourier transform, it inherits most of the properties of the Fourier transform. We repeat some of the important properties here. In addition other properties are based on the assumed periodicity of {fn} and {Fm}: 1. Linearity: If {fn} and {gn} are both length N, and {fn} DFT⇐⇒ { Fm} and {gn} DFT⇐⇒ { Gm} then DFT a {fn} + b {gn} ⇐⇒ a {Fm} + b {Gm} 2. Symmetry Properties of the DFT: If {fn} is a real-valued sequence then {Fm} = F−m from which it follows that {{Fm}} is an even function of m and {{Fm}} is an odd function of m. Similarly the magnitude of {Fm} is an even function, and the phase is an odd function. In addition DFT DFTE{{fn}} ⇐⇒  { { Fm}} and O{{fn}} ⇐⇒  { { Fm}} where E and O denote the even and odd parts respectively. 11–2� � 0 N - 1 n � � � 3. Shifting Properties: If DFT{ fn} ⇐⇒ { Fm} then DFT � � { fn−n0 } ⇐⇒ e −jmn0 Fm and DFTejm0nfn ⇐⇒ { Fm−m0 } where n0 and m0 are constants. 4. Periodicity As noted above, both { fn} and { Fm} are periodic with period N. Example 1 What is the effect of zero-padding (adding extra zero amplitude samples) to a data record { fn} before taking the DFT? n f n o r i g i n a l r e c o r d ( l e n g t h N ) 0 f n M a d d e d z e r o s z e r o - p a d d e d r e c o r d ( l e n g t h N + M ) N - 1 N + M - 1 • Assume that the original N samples encapsulate f (t), so that f(t) ≡ 0 for T>NΔT . Then let FN denote the DFT of the original length N recordm N−1 FN −j2πmn/N = fn em n=0 We note that when related back to the continuous time domain, the Nyquist frequency is ΩN = π/ΔT , and the line spacing is Δω =2π/NΔT . • When we ad M zeros to the end of the record N+M−1 N−1 FN+M = fn e −j2πmn/(N +M) = fn e −j2πmn/(N +M) m n=0 n=0 since the M extra data point do not contribute to the DFT sums. However we now have N + M spectral samples with the same Nyquist frequency ΩN = π/ΔT, but with a new line spacing ΔΩ = 2π/(N + M)ΔT . The result is that padding the data record with zeros has increased the spec-tral resolution of the DFT. 11–3� � Note that if the number of added zeros is an integer multiple of the original record length (M = kN, for k =1, 2, 3,...), the original DFT samples FN willm be preserved and k − 1 new samples will be interpolated between the original samples. kN−1 N−1 FkN = fn e −j2πmn/(kN) = fn e −j2πmn/(kN) m n=0 n=0 so that FN = FkN m km . Example: The waveform below was sampled with ΔT = 1 sec to give a length 16 record. 0 5 1 0 1 5 - 4 - 3 - 2 - 1 0 1 2 3 4 f ( t ) t ( s e c ) The data record length was then extended to a length of 256 by zero-padding with 240 zeros, and the FFT was then computed again. The following plot, demonstrating the interpolation in the DFT was generated from the MATLAB fragment: k = 0:7; f16 = [cos(2.*pi*k/8) + 3*cos(4*pi*k/8)+ sin(6*pi*k/8) zeros(1,8)]; f256 = [f16 zeros(1,240)]; plot(0:255,abs(fft(f256)),’o’); hold; stem(0:16:255, abs(fft(f16)),’filled’); 11–4m N - 1 0 m m 0 5 0 1 0 0 1 5 0 2 0 0 2 5 0 0 2 4 6 8 1 0 1 2 1 4 m F m The original 16 DFT points are shown as filled circles (produced by the stem() function). The interpolation of 15 new …