Sampling and the Discrete Fourier Transform

MASSACHUSETTS INSTITUTE OF TECHNOLOGY DEPARTMENT OF MECHANICAL ENGINEERING 2.161 Signal Processing - Continuous and Discrete Sampling and the Discrete Fourier Transform 1 1 Sampling Consider a continuous function f (t) that is limited in extent, T1 ≤ t < T2 . In order to process this function in the computer it must be sampled and represented by a finite set of numbers. The most common sampling scheme is to use a fixed sampling interval ΔT and to form a sequence of length N : {fn } (n = 0 . . . N − 1), where fn = f (T1 + nΔT ). In subsequent processing the function f (t) is represented by the finite sequence {fn } and the sampling interval ΔT . In practice, sampling occurs in the time domain by the use of an analog-digital (A/D) converter. The mathematical operation of sampling (not to be confused with the physics of sampling) is most commonly described as a multiplicative operation, in which f (t) is multiplied by a Dirac comb sampling function s(t; ΔT ), consisting of a set of delayed Dirac delta functions: s(t; ΔT ) = ∞ δ(t − nΔT ). (1) n=−∞ We denote the sampled waveform f � (t) as f � (t) = s(t; ΔT )f (t) = ∞ � f (t)δ(t − nΔT ) (2) n=−∞ as shown in Fig. 1. Note that f � (t) is a set of delayed weighted delta functions, and that the waveform must be interpreted in the distribution sense by the strength (or area) of each component impulse. The implied process to produce the discrete sample sequence {fn } is by integration across each impulse, that is fn = � nΔT + nΔT − � f (t)dt = � nΔT + � ∞ nΔT − n=−∞ f (t)δ(t − nΔT )dt (3) or fn = f (nΔT ) (4) by the sifting property of δ(t). 1.0.1 Spectrum of the Sampled Waveform f � (t): Notice that sampling comb function s(t; ΔT ) is periodic and is therefore described by a Fourier series: ∞ 1 � s(t; ΔT ) = ejnΩ0 t ΔT n=−∞ 1 D. Rowell October 2, 2008 1 f(t) t s (t;D T ) t f * (t) = f(x )s (t;D T ) t Figure 1: Sampling by a comb impulse function. The function f (t) is multiplied by the sampling function s(t; ΔT ) to produce the sampled waveform f � (t). where all the Fourier coefficients are equal to (1/ΔT ). Using this form, the spectrum of the sampled waveform f � (t) may be written F � (jΩ) = � ∞ −∞ f � (t)e−jΩt dt = ∞ � ∞ 1 � f (t)ejnΩ0 t e−jΩt dt ΔT n=−∞ −∞ = ∞ 1 � F (j (Ω − nΩ0 )) ΔT n=−∞ = � � �� ∞ 1 � 2πn F j Ω− ΔT n=−∞ ΔT (5) where Ω0 = 2π/ΔT . This tells us that the Fourier transform of a sampled function f � (t) is periodic in the frequency domain with period Ω0 , and is a superposition of an infinite number of shifted Fourier transforms F (jΩ) of the original function, scaled by a factor of 1/ΔT . 1.1 The Nyquist Sampling Theorem Given a set of samples {fn } and its generating function f (t), an important question to ask is whether the sample set uniquely defines the function that generated it? In other words, given {fn } can we unambiguously reconstruct f (t)? The answer is clearly no, as shown in Fig. 2 where there are obviously many functions that will generate the given set of samples. In fact there are an infinity of candidate functions that will generate the same sample set. 2 f(t) t Figure 2: Demonstration that a set of samples does not uniquely define a continuous function. There are clearly many functions that would generate the same set of samples. The Nyquist sampling theorem places restrictions on the candidate functions and, if satisfied, will uniquely define the function that generated a given set of samples. The theorem may be stated in many equivalent ways, we present three of them here to illustrate different aspects of the theorem: • A function f (t), sampled at equal intervals ΔT , can not be unambiguously reconstructed from its sample set {fn } unless it is known a-priori that f (t) contains no spectral energy at or above a frequency of π/ΔT radians/s. • In order to uniquely represent a function f (t) by a set of samples, the sampling interval ΔT must be sufficiently small to capture more than two samples per cycle of the highest frequency component present in f (t). • There is only one function f (t) that is band-limited to below π/ΔT radians/s that is satisfied by a given set of samples {fn }. Note that the sampling rate, 1/ΔT , must be greater than twice the highest cyclic frequency fmax in f (t). Thus if the frequency content of f (t) is limited to Ωmax radians/s (or fmax cycles/s) the sampling interval ΔT must be chosen so that π Ωmax ΔT < or equivalently ΔT < 1 2fmax The minimum sampling rate to satisfy the sampling theorem fmin = Ωmax /π samples/s is known as the Nyquist rate. 1.2 Aliasing Consider a sinusoid f (t) = A sin(at + φ) sampled at intervals ΔT , so that the sample set is {fn } = {A sin(anΔT + φ)} , and noting that sin(t) = sin(t + 2kπ) for any integer k, �� fn = A sin(anΔT + φ) = A sin where m is an integer, giving the following important result: 3 � � 2πm a+ nΔT + φ ΔT (6) Given a sampling interval of ΔT , sinusoidal components with an angular frequency a and a + 2πm/ΔT , for any integer m, will generate the same sample set. Figure 3 shows a sinusoid sampled at three different rates. In Fig. 3(a) the waveform is sampled at a rate above the Nyquist rate, and the function is uniquely defied by the samples. In (b) the sampling interval ΔT is at the Nyquist rate (two samples/cycle) and the sample set is ambiguous; note that the function f (t) = 0 generates the same samples. In (c) The sinusoid is undersampled and a lower frequency sinusoid, shown as a dashed line, also satisfies the sample set. The phenomenon demonstrated in Fig. 3 is known as aliasing. After sampling any spectral component in F (jΩ) above the Nyquist frequency π/ΔT will “masquerade” as a lower frequency component within the reconstruction bandwidth, thus creating an erroneous reconstructed function. The phenomenon is also known as frequency folding since the high frequency components will be “folded” down into the assumed system bandwidth. One-half of the sampling frequency (i.e. 1/(2ΔT ) cycles/second, or π/ΔT radians/second) is known as the aliasing frequency, or folding frequency for these reasons. Equation (6) defines how frequency components above the folding frequency will be aliased into the range below the folding frequency. This is illustrated in Fig. 4. Figure 5 shows the effect of folding in another way. In Fig. 5(a) a function f (t) with Fourier transform F (jΩ) has two disjoint spectral regions. The sampling interval ΔT is chosen so that the folding frequency π/ΔT falls between the two regions. The spectrum of the sampled system between the limits −π/ΔT < Ω ≤ π/ΔT is shown in Fig. 5(b). The higher frequency components have been folded down into the region −π/ΔT < Ω ≤ π/ΔT . 1.2.1 Anti-Aliasing Filtering: Once a sample set {fn } has been taken, there is nothing that can be done to eliminate the effects of aliased frequency components. The only way to guarantee that the sample set unambiguously represents the generating function is to ensure that the sampling theorem criteria have been met, either by 1. Selecting a sampling interval ΔT sufficiently small to capture all spectral components, or 2. Processing the function f (t) to “eliminate” all components at or above the Nyquist rate. The second method involves the use of a continuous-domain processor before sampling f (t). A low-pass aanti-aliasing filter is used to eliminate (or at least attenuate) spectral components at or above the Nyquist frequency. Ideally the anti-aliasing filter would have a transfer function H(jΩ) = 1 for |Ω| < π/ΔT = 0 otherwise,. In practice it is not possible to design a filter with such characteristics, and a more realistic goal is to reduce the offending spectral components to insignificant levels, while maintaining the fidelity of components below the folding frequency. Figure 6 illustrates the use of an anti-aliasing filter. 2 Reconstruction of a Function from its Sample Set Equation (5) demonstrates that the spectrum F � (jΩ) of a sampled function f � (t) is infinite in extent and consists of a periodic extension of F (jΩ) with a period of 2π/ΔT , i.e. � � �� ∞ 1 � 2πn F (jΩ) = F j Ω− . ΔT n=−∞ ΔT � 4 f(t) o o o o o o 0 t ΔT o o o o o o o 0 (a) f(t) o 0 o o ΔT o o o o o t (b) f(t) o o o t ΔT 0 o o o o 0 (c) Figure 3: Demonstration that a set of samples does not necessarily uniquely define a continuous function. In (a) the sampling rate satisfies the sampling theorem and there is no ambiguity, in (b) and (c) the sampling theorem is not satisfied and lower frequency waveforms also generate the same sample set. 5 3 p /D T 5 p /D T p /D T 3 p /D T 0 - p /D T W p /D T - 3 p /D T - p /D T - 5 p /D T - 3 p /D T Figure 4: Folding of spectral components in the frequency domain. Spectral components at fre­ quencies labeled “X” can generate identical sample sets. F * ( jW ) F ( jW ) s a m p lin g a t D T a lia s e d s p e c tr a l c o m p o n e n ts - p /D T 0 p /D T W a lia s e d s p e c tr a l c o m p o n e n ts 0 - p /D T (a ) p /D T W (b ) Figure 5: The effect of sampling on a spectrum F (jΩ) with components above the Nyquist frequency Ω = π/ΔT . The higher frequency components are folded down below the Nyquist frequency. f(t) F ( jW ) A n ti- a lia s in g lo w - p a s s filte r H ( jW ) = 0 , |W |> p /T ~ f(t) F ( jW ) H ( jW ) c o n tin u o u s d o m a in S a m p le r D T {fn } d is c r e te d o m a in Figure 6: An anti-aliasing continuous-domain low-pass filter used to significantly attenuate spectral components above the folding frequency prior to sampling 6 If it is assumed that the sampling theorem was obeyed during sampling, the repetitions in F � (jΩ) will not overlap, and in fact f (t) will be entirely be specified by a single period of F � (jΩ). Therefore to reconstruct f (t) we can pass f � (t) through an ideal low-pass filter with transfer function H(jΩ) that will retain spectral components in the range −π/ΔT < Ω < π/ΔT and reject all other frequencies. Then f (t) = F −1 {F (jΩ)} = F −1 {F � (jΩ)H(jΩ)} . (7) If the transfer function of the reconstruction filter is H(jΩ) = ΔT |Ω| < π/ΔT = 0 otherwise its impulse response h(t) will be h(t) = F −1 {H(jΩ)} = sin (πt/ΔT ) πt/ΔT (8) The output from the reconstruction filter is the convolution of the input function f � (t) with the impulse response h(t), f (t) = f � (t) ⊗ h(t) = = = � ∞ ∞ h(σ) ∞ � f (t − σ)δ(t − nΔT − σ)dσ n=−∞ ∞ � ∞ � sin (πσ/ΔT ) πσ/ΔT n=−∞ ∞ ∞ � f (nΔT ) n=−∞ f (t − σ)δ(t − nΔT − σ)dσ sin (π(t − nΔT )/ΔT ) π(t − nΔT )/ΔT (9) or in the case of a finite data record of length N f (t) = N −1 � fn n=0 sin (π(t − nΔT )/ΔT ) π(t − nΔT )/ΔT (10) Equation (10) is known as the cardinal (or Whitaker) reconstruction function. It is a superposition of shifted sinc functions, with the important property that at t = nΔT , the reconstructed function f (t) = fn . This can be seen by letting t = nΔT , in which case only the nth term in the sum is nonzero. Between the sample points the interpolation is formed from the sum of the sinc functions. The reconstruction is demonstrated in Fig. 7 in which a sample set (N = 13) with three nonzero samples is reconstructed. The individual sinc functions are shown, together with the sum (dashed line). Notice how the zeros of the sinc functions fall at the sample points. 3 The Digital Impulse The discrete impulse δ(n) serves the the same function within discrete systems as the impulse δ(t) does in continuous system analysis. It is defined as � δ(n) = 0 1 7 n �= 0 n=0 (11) o o o o o o o o o o o o o −0.3 Figure 7: Cardinal reconstruction of a sample set with three non-zero samples. d (n ) 1 ... -2 -1 1 0 2 4 3 ... n Figure 8: The digital pulse sequence as shown in Fig. 8. The question is: what is the underlying continuous function δ̂(t) that will generate this sample set while satisfying the bandwidth limitations imposed by the sampling theorem? Clearly the function must have no frequency components at or above the folding frequency. The answer is given by the Whitaker reconstruction function (Eq. (10), which in this case generates a single sinc function: sin (πt/ΔT ) δ̂(t) = (12) πt/ΔT Figure 9 shows how the zeros of the continuous function fall at all of the sampling points, except for n = 0, thus generating the discrete pulse sequence. 4 The Discrete Fourier Transform (DFT) Consider the Fourier transform of the sampled function f � (t) F � (jΩ) = = � ∞ −∞ f � (t)e−jΩt dt = ∞ � � ∞ ∞ � −∞ n=−∞ fn e−jΩnΔT f (t)δ(t − nΔT )e−jΩt dt (13) n=−∞ 8 o ^ δ (t) o o o o o o o t o 0 Figure 9: The digital pulse sequence δ(n) and the sinc function δ̂(t) that generates it. using the sifting property of δ(t). F � (jΩ) is a continuous function of Ω, but is derived from the sample points in f (nΔT ) in f (t). We have shown that F � (jΩ) is periodic in Ω with period Ω0 = 2π/ΔT . We now restrict ourselves to computing a finite data set of N samples in a single period of F � (jΩ), from Ω = 0 to 2π/ΔT , that is at frequencies Ω= 2πm ; N ΔT m = 0, 1, 2, . . . , N − 1 (14) and writing Fm = F � (j2πm/N ΔT ), Eq. (13) becomes Fm = N −1 � fn e−j2πmn/N m = 0, 1, 2, . . . , N − 1 (15) n=0 Equation (15) is known as the Discrete Fourier Transform (DFT) and relates the sample set {fn } to its spectrum {Fm } at a set of sampled frequencies. The DFT can be inverted and the sample set {fn } recovered as follows: −1 1 N� fn = Fm ej2πmn/N N m=0 n = 0, 1, 2, . . . , N − 1 (16) which is known as the inverse DFT (IDFT). Equations (15) and (16) together form the DFT pair. The DFT operations are a transform pair between two sequences {fn } and {Fm }, and do not explicitly involve the sampling interval ΔT or the sampled frequency interval Ω = 2π/(nΔT ). Simple substitution into the formulas will show that both Fm and fn are periodic with period N , that is fn+pN = fn and Fm+pN = Fm for any integer p. As in the continuous Fourier transform case, we adopt the notations DFT {fn } ⇐⇒ {Fm } {Fm } = DFT {fn } {fn } = IDFT {Fm } to indicate DFT relationships. 9 4.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. 4.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. Equation (14) shows that the resolution, or line spacing, ΔΩ, in the DFT is 2π 2π = N ΔT T and the frequency range spanned by the N lines in the DFT is ΔΩ = N ΔΩ = 2π ΔT (17) (18) The sequence {Fm } represents both the positive and negative frequencies in a two-sided spectrum. The highest real frequency component in the spectrum is half of this range, that is π Ωmax = (19) Δ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 . 4.3 Properties of the Discrete Fourier Transform 1. Linearity: If DFT {fn } ⇐⇒ {Fm } and DFT {gn } ⇐⇒ {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 E {{fn }} ⇐⇒ � {{Fm }} and DFT O {{fn }} ⇐⇒ � {{Fm }} where E and O denote the even and odd parts respectively. 10 3. Shifting Properties: If DFT {fn } ⇐⇒ {Fm } then � {fn−n0 } ⇐⇒ e−jmn0 Fm DFT and � � � ejm0 n fn ⇐⇒ {Fm−m0 } DFT where n0 and m0 are constants. 4. Periodicity As noted above, both {fn } and {Fm } are periodic with period N . 4.4 Convolution in Time and Frequency The inverse DFT of the product of two DFT’s is a periodic or circular convolution sum, that is if then {Gm } = {Fm Hm } {gn } = N −1 � fm hn−m = m=0 N −1 � hn−m fm (20) m=0 where periodic extensions of {fn } and {hn } must be used to complete the summation. Similarly {gn } = {fn hn } if then {Gm } = −1 N −1 � 1 N� Fn Hm−n = Hn Fm−n N n=0 n=0 (21) where periodic extensions of {Fm } and {Hm } must be used to complete the summation. 4.5 The Fast Fourier Transform (FFT) The Fast Fourier Transform (FFT) is merely an algorithmic implementation of the DFT that recognizes that, because of the periodicity of the exponential term e−j2πmn/N , many of the complex multiplications in Eqs. (15) and (16) are redundant, and are repeated many timed in the calculation of the transform. By gathering together elements of the summation in a definite order, significant computational savings can be made, reducing the number of complex multiplications from N 2 to N log2 N . Most common FFT routines requite that N be an integer power of 2. The recognition of the savings afforded by the FFT in the 1960’s has revolutionized the field of digital signal processing. 5 Spectral Leakage and Apodizing (Windowing) Functions Often apparently spurious spectral components will appear in the output of a DFT computation. This phenomenon is known as spectral leakage. We examine the origin of this effect briefly here by considering a finite sample set (length N ) of a sinusoid of the form f (t) = cos(at) so that fn = cos(anΔT ) n = −N/2, . . . N/2 − 1 11 (22) Notice that in effect we have sampled a “windowed” version of f (t), or f˜(t) = f (t)rect(N ΔT ) where the rect function is defined � rect(t) = 1 0 (23) |t| < 1/2, otherwise The Fourier transform of the windowed sinusoid is the convolution of the two Fourier transforms F {cos(at)} = π (δ(Ω − a) + δ(Ω + a)) sin(ΩN ΔT /2) F {rect(N ΔT )} = N ΔT ΩN ΔT /2 and the Fourier transform of the product is F̃ (jΩ) = F {rect(N ΔT ) cos(at)} 1 = (F {rect(N ΔT )} ⊗ F {cos(at)}) 2π � � N ΔT sin ((Ω − a)N ΔT /2) sin ((Ω + a)N ΔT /2) = + 2 (Ω − a)N ΔT /2 (Ω + a)N ΔT /2 (24) and the spectrum of the sampled waveform is F̃ ∗ (jΩ) = = 1 F̂ (jΩ) ΔT� � N sin ((Ω − a)N ΔT /2) sin ((Ω + a)N ΔT /2) + 2 (Ω − a)N ΔT /2 (Ω + a)N ΔT /2 (25) which is a pair of sinc functions centered on frequencies Ω = a and Ω = −a. The spacing of the zeros of each of the sinc functions is at intervals of ΔΩ = 2π/N ΔT . We may consider the DFT as a comb filter that displays discrete lines of the spectrum F̃ ∗ (jΩ) at frequencies (Eq. (14)): Ω= 2πm ; N ΔT m = 0, 1, 2, . . . , N − 1 so that in the DFT, � Fm = F̃ ∗ 2πm N ΔT � Now consider what happens in two situations: (a) The frequency a in f (t) = cos(at) is such that the data record contains an integer number of periods. In this case the length of the data record N ΔT = M or a= 2πM , N ΔT 2π a for M integer Substitution into Eq. (25) gives Fm = N 2 � sin(π(m − M )) sin(π(m + M )) + π(m − M ) π(m + M ) � that is Fm = N/2 for m = ±M and Fm = 0 otherwise, which is what we would expect. 12 (26) (b) The frequency a in f (t) = cos(at) is such that the data record does not contain an integer number of periods. In this case the peak and zeros of the sinc functions in Eq. (25) will not line up with the frequencies 2πm/(N ΔT ) in the DFT and the results will (1) not show the peak of the sinc functions, and (2) will show finite components at all frequencies. This is the origin of spectral leakage. Spectral leakage occurs when frequency components in the input function f (t) are not harmonics of the fundamental frequency k0 = 2π/(N ΔT ), defined by the length of data record N ΔT . Under such conditions the lines in the DFT do not accurately reflect the amplitude of the component, and spurious components appear adjacent to the component. Figures 10 and 11 show two examples of DFT’s taken from a record length 16. In the first case the frequency of the the sinusoid is chosen so that there are four cycles in the data record. The DFT shows two clean components at the appropriate frequency with no evidence of leakage. In the second case, Fig. 11, the data record contains 3.5 cycles of the sinusoidal component. The spectral leakage is severe: both the height of the main peak is reduced, and signicant amplitudes are recorded for all spectral components. 5.1 Reduction of Leakage by an Apodizing (Windowing) Function The reason for the appearance of leakage components in the DFT of a truncated data set is the convolution of the data spectrum with that of the truncation window (the rect function in Eq. (23)). Each sinusoidal component in f (t) has a spectrum F (jΩ) that is a pair of impulses in the frequency domain: multiplication by the truncating function causes a spread in the width of the component. Leakage may be reduced (but not eliminated) by using a different function to truncate the series instead of the implicit rect function. These functions are known as an apodizing, or windowing, functions and are chosen to smoothly taper the data record to zero at the extremities, while minimizing the spectral spreading of each component. The data record then becomes f˜(t) = f (t)w(t) or in the samples f˜n = fn wn where w(t) (or wn ) is the windowing function. There are many windowing functions in common use, the following are perhaps the most common: Bartlett Window: This is a triangular ramp, tapered to zero at the extremities of the record � w(t) = � wn = 1 − |t − T /2| /(T /2) 0 0≤t < T otherwise, 1 − |n − N/2| /(N/2) 0 0≤n < N otherwise. Hanning Window This is a smoothly tapered window � w(t) = � wn = 0.5 (1.0 + cos(π(t − T /2)/(T /2))) 0 0.5 (1.0 + cos(π(n − N/2)/(N/2))) 0 13 0≤t < T otherwise, 0≤n < N otherwise. 1 f(t) 0.5 0 −0.5 −1 0 0.1 0.2 0.3 0.4 0.5 t (sec) 0.6 0.7 0.8 0.9 1 10 Magnitude 8 6 4 2 0 −8 −6 −4 −2 0 m 2 4 6 8 Figure 10: The DFT of a data record containing an integer number of periods of a sinusoidal function. Note the absence of spectral leakage. 1 f(t) 0.5 0 −0.5 −1 0 0.1 0.2 0.3 0.4 0.5 t (sec) 0.6 0.7 0.8 0.9 1 Magnitude 6 4 2 0 −8 −6 −4 −2 0 m 2 4 6 8 Figure 11: The DFT of a data record containing an non-integer number of periods of a sinusoidal function. Note the severe spectral leakage in the DFT. 14 Hamming Window This is a smoothly tapered window that is similar to the Hanning window � w(t) = � wn = 0.54 + 0.46 cos(π(t − T /2)/(T /2)) 0 0.54 + 0.46 cos(π(n − N/2)/(N/2)) 0 0≤t < T otherwise. 0≤n < N otherwise. The magnitude spectra of these three windows are shown in Fig. 12, in linear and logarithmic plots. In each case it can be noted: • The width of the central lobe is wider than that of the rectangular window, indicating that the main lobe will be approximately two lines in width. • The magnitude of the side-lobes is significantly reduced, indicating that leakage away from the main peak will be reduced. These two effects are demonstrated in Figs. 13 and 14. In Fig. 13 the same data set as used in Fig. 10 has been windowed using a Hanning function. The central peak has now been “smeared” to occupy three lines. In Fig. 14 the data set of Fig. 11, with 3.5 periods of a cosinusoid, has been windowed. Here it can be seen that the leakage components away from the main peak have been significantly attenuated. All windows are a compromise and trade-off the width of the central peak and attenuation of leakage components distant from the peak. Figure 12 shows the compromise between the Hanning and Hamming windows. The Hamming window has greater attenuation of components close to the cental peak, while the Hanning window has greater attenuation away from the peak. 6 Normalized Discrete-Time Frequencies Up to this point we have considered the frequency content of sampled signals in terms of true time t = nΔ . However, we have seen that discrete-time operations, such as the DFT, are operations between sequences – without regard for the sampling period ΔT . It is common in signal processing to define normalized frequencies so that instead of expressing a sampled sinusoid as x(nΔT ) = A sin(ΩnΔT + φ) = A sin(2πF nΔT + φ), where Ω = 2πF . In discrete-time operations we often write x(n) = A sin(ωn + φ) = A sin(2πf n + φ) where ω = ΩΔT is the normalized angular frequency, with units of radians/sample. Frequencies expressed as ω are therefore independent of the sampling interval. Similarly we use normalized frequency f = F ΔT where f has units cycles/sample, and f= 1 ω. 2π 15 Magnitude (dB) 0 Magnitude 1 Bartlett Bartlett 0.8 −20 0.6 −40 0.4 −60 0.2 0 −10 −5 0 5 10 Frequency −80 −10 −5 0 5 (a) 10 Frequency Magnitude (dB) 0 Magnitude 1 Hanning Hanning 0.8 −20 0.6 −40 0.4 −60 0.2 0 −10 −5 0 5 10 Frequency −80 −10 −5 0 5 (b) 10 Frequency Magnitude (dB) 0 Magnitude 1 Hamming Hamming 0.8 −20 0.6 −40 0.4 −60 0.2 0 −10 −5 0 5 10 Frequency −80 −10 −5 0 (c) 5 10 Frequency Figure 12: Comparison of the magnitude spectra of common window functions: (a) Bartlett, (b) Hanning, and (c) Hamming windows. In each case the spectrum is shown in linear and logarithmic (dB) form. The frequency scale is normalized to units of line spacing (2π/N ΔT ) radians/sec. The spectrum of the implicit rectangular window is shown as a dotted line in each case. It is interesting to consider aliasing in terms of discrete-time sinusoids. Clearly sin((ω0 + 2πk)n + φ) = sin(ω0 n + φ) so that all sinusoidal sequences xk (n) = A sin(ωk n + φ) where ωk = ω0 + 2kπ for k = 1, 2, . . . are indistinguishable. It is common to limit the values of ω to −π ≤ ω < π. In this course we will use both absolute frequency Ω and normalized frequency ω. 16 1 f(t) 0.5 0 −0.5 −1 0 0.1 0.2 0.3 0.4 0.5 t (sec) 0.6 0.7 0.8 0.9 1 5 Magnitude 4 3 2 1 0 −8 −6 −4 −2 0 m 2 4 6 8 Figure 13: The effect of windowing on a data record containing an integer number of periods of a sinusoidal function. The data set is the same as in Fig. 10, with a Hanning window applied. Note the spreading of the central peak. 1 f(t) 0.5 0 −0.5 −1 0 0.1 0.2 0.3 0.4 0.5 t (sec) 0.6 0.7 0.8 0.9 1 4 Magnitude 3 2 1 0 −8 −6 −4 −2 0 m 2 4 6 8 Figure 14: The effect of windowing on a data record containing an non-integer number of periods of a sinusoidal function. The data set is the same as in Fig. 11, with a Hanning window applied. Note the reduction of leakage away from the central peak. 17