Fourier Representation of Signals and Systems

HST582J/6.555J/16.456J Biomedical Signal and Image Processing Spring 2007 Chapter 3 - FOURIER REPRESENTATION OF SIGNALS AND SYSTEMS
Introduction In Chapter 2, we studied the operation of linear, time-invariant filters in the time domain. Further insights and greater simplicity in the analysis are provided when filters are studied in the frequency domain, that is, when sinusoidal signals (or equivalently, complex exponentials) are used as inputs. The key to this simplicity is twofold: (1) The response of a linear, timeinvariant system to a sum of sine waves is always a sum of sine waves at the same frequencies. (2) Fourier’s theorem expresses any reasonably well-behaved signal as an infinite sum of sine waves. Therefore understanding the response to sine waves suffices to predict responses to arbitrary signals. Frequency-domain analysis is particularly useful for separating signal from noise when the signal and the noise occupy different frequency bands, or at least when the signal-to-noise ratio differs for different frequency regions. The frequency-domain properties of filters can be introduced with either discrete-time or continuoustime signals. We will first present detailed results for discrete-time signals and systems and then extend these results to continuous-time signals. In Chapter 5, we will consider sampling theorems that provide a relation between these two types of signals. The frequency representation of random signals will be studied in Chapter 12. 3.1 Frequency response of LTI systems According to the convolution theorem introduced in Chapter 2, the responses of linear, timeinvariant (LTI) systems to arbitrary inputs can be computed if the unit-sample response is known. Indeed, convolution is usually the simplest method to compute the output of a digital filter if either the input or the impulse response is only a few samples in duration. There is another condition for which the responses of LTI systems can be readily computed: when the inputs are complex exponentials of the form ej2πf n . Specifically, let us consider the response of a system with unit-sample response h[n] to a complex exponential with frequency f : y[n] = h[n] ∗ ej2πf n = ∞
h[m] ej2πf (n−m) m=−∞ This can be written as: y[n] = ej 2πf n ∞
m=−∞ h[m] e−j2πf m = H(f ) x[n] with ∞
 H(f ) = h[n] e−j2πf n (3.1) n=−∞ Thus, the output is equal to the input multiplied by the complex constant H(f ). When considered as a function of frequency, H(f ) is called the frequency response of the system. The frequency response H(f ) is related to the unit sample response h[n] by Eq. 3.1, which is the definition of the discrete-time Fourier transform (DTFT) 1 . The frequency response H(f ) is a periodic function of frequency with period 1. This is to be expected because discrete-time sine waves whose frequencies differ by multiples of 1 are indistinguishable. 3.1.1 Responses to sums of complex exponentials An advantage of using the frequency response for describing LTI systems is that, if the input is a weighted sum of complex exponentials x[n] = N −1
ci ej2πfi n (3.2a) i=0 then, by linearity, the output can be expressed as a weighted sum of the same complex exponentials, with the output weights being equal to the input weights multiplied by the values of the frequency response at the input frequencies: y[n] = N −1
ci H(fi ) ej2πfi n (3.2b) i=0 In other words, an LTI system cannot create new frequency components, it can only amplify (or attenuate) and delay the frequency components present in the input. This fundamental property does not hold for even simple nonlinear systems such as a square function y[n] = x[n]2 . Example 1 Any sinusoidal signal can be written as a sum of two complex exponentials: x[n] = A cos (2πf n + φ) = A −jφ −j2πf n A jφ j2πf n + e e e e 2 2 Therefore, the sinusoidal response of a system with frequency response H(f ) is: y[n] = H(f ) A −jφ −j2πf n A jφ j2πf n + H(−f ) e e e e 2 2 Let us decompose the complex frequency response H(f ) into its magnitude |H(f )| and phase  H(f ):  H(f ) = |H(f )| ej H(f ) 1 The discrete-time Fourier transform (DTFT) should not be confused with the discrete Fourier transform (DFT), which we will study in Chapters 4 and 5. The DTFT is a continuous function of frequency, while the DFT is a discrete function of frequency. In fact, we will see that the DFT corresponds to frequency samples of the DTFT. 2 From the definition of the frequency response (Eq. 3.1), it is clear that, for real h[n], H(−f ) =  H ∗ (f ) = |H(f )| e−j H(f ) . Therefore, y[n] becomes: y[n] = A |H(f )| cos (2πf n + φ +  H(f )) (3.3) The magnitude of the output is the magnitude of the input multiplied by the magnitude of the frequency response, and the phase of the output is the phase of the input plus the phase of the frequency response. Example 2 We saw in Chapter 1 that periodic, discrete-time signals with period N can be expressed as discrete Fourier series: [N ] 2
x[n] = Xk ej 2πkn/N (3.4a) k=−[ N ] 2 From the preceding results, we can directly write the Fourier series for the response of a linear system with frequency response H(f ) [N ] 2
y[n] = Xk H( k=−[ N ] 2 k ) ej2πkn/N N (3.4b) The Fourier coefficients for the output signal are simply Yk = Xk H( Nk ). 3.1.2 Example frequency responses of LTI systems 1. Gain G: H(f ) = G 2. Delay by n0 samples: H(f ) = e−j2πf n0 The magnitude is 1, and the phase is a linear function of frequency. 3. Two-point smoother y[n] = 1 2 (x[n] + x[n − 1]) (Fig. 3.1a): H(f ) = (1 + e−j2πf ) = e−jπf cos πf 2 The magnitude is 1 at low frequencies, and approaches 0 for f = 12 . This behavior is characteristic for lowpass filters. 4. Euler’s approximation to the derivative y[n] = H(f ) = 1 Ts (x[n] − x[n − 1]) (Fig. 3.1b): 1 2 1 sin πf e−jπ(f − 2 ) (1 − e−j 2πf ) = Ts Ts 3 The magnitude of H(f ) is approximately 2πf Ts for low frequencies. This is appropriate because the magnitude of the derivative of a continuous-time sine wave of frequency F = Tfs is 2πF times the magnitude of the input. There is also a − π2 phase shift, consistent with the fact that the derivative of a sine is a cosine. 5. First-order recursive lowpass filter y[n] = a y[n − 1] + x[n] (Fig. 3.1c): H(f ) = 1 1 − a e−j2πf The magnitude is |H(f )| = 1 (1 + a2 1 − 2 a cos 2πf ) 2 and the phase is  H(f ) = − tan−1 a sin 2πf 1 − a cos 2πf Clearly, the closer a approaches 1, the lower the cutoff frequency of the lowpass filter. 3.2 Fourier representation of discrete-time signals We have seen so far that, if an input signal can be expressed as a sum of complex exponentials, then the response of an arbitrary LTI system to this input can be computed if we know its frequency response. Thus, if all discrete-time signals could be expressed as a sum of complex exponentials, the frequency response would constitute a complete characterization of LTI systems. This is precisely what Fourier’s theorem for discrete-time signals states: Except for mild restrictions, any discrete-time signal can be expressed as an infinite ”sum” (actually an integral) of complex exponentials. This can be considered as a limit of the discrete Fourier series when the period N tends to infinity: the spectral lines at fk = Nk get closer and closer so that the sum over harmonic number k in Eq. 3.4a tends to an integral over frequency. 3.2.1 Discrete-time Fourier transform (DTFT) Fourier’s theorem for discrete-time signals can also be derived from the Fourier series for continuous signals if we exchange the roles of time and frequency. For this purpose we reproduce the definition of the discrete-time Fourier transform of x[n] from Eq. 3.1: ∞
X(f ) = x[n] e−j2πf n (3.6a) n=−∞ Because X(f ) is periodic, it must have a Fourier series, and, in fact, Eq. 3.6a does provide a Fourier series expansion for X(f ) in which the Fourier coefficients are the samples x[n]. Making use of the formula for computing the Fourier coefficients of a continuous, periodic signal, the signal x[n] can be expressed as a function of X(f ):  x[n] = 1 2 − 12 X(f ) ej2πf n df 4 (3.6b) Together, Eqs. 3.6a and 3.6b constitute the Fourier transform pair for discrete-time signals. Note that, even though the range of integration in Eq. 3.6b is from − 12 to 12 , because H(f ) is periodic, we could also integrate over any one period, e.g. from 0 to 1. In the following, we will use the notation x[n] ←→ X(f ) to indicate DTFT pairs. Equation 3.6b expresses an arbitrary signal x[n] as a ”sum” of complex exponentials. Therefore, the output of a system with frequency response H(f ) to the input x[n] is the ”sum” of the input exponentials, each one being weighted by the frequency response:  y[n] = 1 2 − 12 H(f ) X(f ) ej2πf n df (3.7a) This expression is of the same form as Eq. 3.6b if we define Y (f ) = H(f ) X(f ) (3.7b) This means that the Fourier transform of the convolution x[n] ∗ h[n] is the product of the Fourier transforms: x[n] ∗ h[n] ←→ X(f ) H(f ) Much of the power in the frequency approach to LTI systems is due to this convolution theorem. Example 1 To illustrate the use of Eq. 3.6a, consider the Fourier transform of the symmetric rectangular pulse:  1 if − N ≤ n ≤ N  w[n] = ΠN [n] = 0 otherwise From Eq. 3.6a: N
sin π(2N + 1)f e−j2πf n = W (f ) = sin πf n=−N This signal and its transform are shown in Fig. 3.2a for N = 4. Note that, from Eq. 3.6a, one has ∞ W (0) =
w[n] = 2N + 1 n=−∞ The DC component of w[n] is the sum of the signal samples, a result that holds for arbitrary signals. Example 2 We will now use the inverse Fourier transform relation Eq. 3.6b to compute the impulse response of the ideal digital lowpass filter H(f ):   H(f ) = ΠW (f ) = 5 1 0 |f | ≤ W W < |f | ≤ 1 2 Values of H(f ) for |f | > 1 2 are found by periodicity. From Eq. 3.6b:  W h[n] = ej2πf n df = −W sin 2πW n πn This signal and its transform are shown in Fig. 3.2b. It can be verified from Eq. 3.6b that:  h[0] = 1 2 H(f ) df = 2W − 12 Thus, the value of a signal at the origin is the area under its Fourier transform. 3.3 3.3.1 Properties of the Discrete-Time Fourier Transform Linearity The DTFT is a linear operation because one has a x[n] + b y[n] ←→ a X(f ) + b Y (f ) for a and b arbitrary real or complex constants. 3.3.2 Symmetry properties 1. If x[n] is a real signal, then Eq. 3.6a shows that X(−f ) = X ∗ (f ), where * denotes the complex conjugate. This implies that the real part of X(f ) is even, and its imaginary part is odd: XI (−f ) = −XI (f ) (3.8a) XR (−f ) = XR (f ) Similarly, the magnitude of X(f ) is even, and the phase is odd: |X(−f )| = |X(f )|  X(−f ) = −  X(f ) (3.8b) 2. If x[n] is real and even, X(f ) is also real and even, and the Fourier transform pair can be written with purely real functions: X(f ) = x[0] + 2 ∞
x[n] cos 2πf n (3.9a) n=1  x[n] = 2 1 2 0 X(f ) cos 2πf n df (3.9b) 3. If x[n] is real and odd, X(f ) is purely imaginary and odd, and the transform pair can be written as ∞ X(f ) = −2j
n=1 6 x[n] sin 2πf n (3.10a)  x[n] = 2j 1 2 X(f ) sin 2πf n df 0 (3.10b) 4. Any signal can be decomposed into the sum of an even part xe [n] and an odd part xo [n]. The above results imply that the following transform pairs hold:  1 (3.11a) xe [n] = (x[n] + x[−n]) ←→ XR (f ) 2  1 (3.11b) xo [n] = (x[n] − x[−n]) ←→ j XI (f ) 2 3.3.3 Some simple transform pairs In the following, we use the convention that, if G(f ) is an arbitrary function of frequency, then G̃(f ) is the periodic function formed by repeating G(f ) at frequency intervals of 1:  G̃(f ) = ∞
G(f − k) k=−∞ G̃(f ) is called a frequency-aliased version of G(f ). With this convention, we can write the following transform pairs. δ[n] ←→ 1 −j2πf n0 δ[n − n0 ] ←→ e sin π(2N + 1)f ΠN [n] ←→ sin πf ˜ ) 1 ←→ δ(f ˜ − f0 ) ej2πf0 n ←→ δ(f δ̃(f − f0 ) + δ̃(f + f0 ) 2 ˜ + f0 ) δ̃(f − f0 ) − δ(f sin 2πf0 n ←→ 2j 1 an u[n] ←→ 1 − a e−j2πf 1 (n + 1) an u[n] ←→ 2 (1 − a e−j2πf ) 1 1 δ̃(f ) + u[n] ←→ −j2πf 2 1 − e j  δ̃ (f ) n ←→ 2π sin 2πW n ←→ Π̃W (f ) πn ∞ ∞ 1
k 
δ[n − rN ] ←→ pN [n] = δ(f − ) N k=−∞ N r=−∞ cos 2πf0 n ←→ (3.12a) (3.12b) (3.12c) (3.12d) (3.12e) (3.12f ) (3.12g) (3.12h) (3.12i) (3.12j) (3.12k) (3.12l) (3.12m) All of the above relations, with the exception of (3.12m), are direct consequences of applying either Eq. 3.6a or Eq. 3.6b. 7 3.3.4 DTFT of an impulse train Equation 3.12m states that the transform of an infinite train of impulses spaced at intervals of N samples is a train of impulses in frequency spaced at intervals of 1/N . To prove this, we will apply the inverse transform relation Eq 3.6b to  X(f ) = 1 N ∞
δ(f − k=−∞ k ) N The inverse transform is x[n] =  1 1 N 0 ∞
δ(f − k=−∞ k ) ej2πf n df N Interchanging the order of summations, and making use of the definition of δ(f − becomes: −1 1 N
ej2πkn/N x[n] = N k=0 k N ), this The infinite sum over k reduces to a sum from k = 0 to N − 1 because we are only integrating the δ functions for f between 0 and 1. Using the orthogonality of complex exponentials: N −1
j2πkn/N e  = k=0 N 0 if n is a multiple of N otherwise we verify that x[n] is the periodic impulse train pN [n]. 3.3.5 Convolution theorem With Eq. 3.7, we have already proved the convolution theorem: x[n] ∗ y[n] ←→ X(f ) Y (f ) (3.13) An important special case of this relation is the time-delay theorem: x[n − n0 ] = x[n] ∗ δ[n − n0 ] ←→ X(f ) e−j2πf n0 (3.14) Another important application of Eq. 3.13 gives the DTFT of the deterministic autocorrelation function of x[n]  R̃x [n] = x[n] ∗ x[−n] ←→ |X(f )|2 = X(f ) X(−f ) (3.15a) Expressing Eq. 3.15a at time zero gives Parseval’s theorem for discrete-time signals Ex = ∞
x[n]2 = n=−∞  1 2 − 12 |X(f )|2 df (3.15b) which states that the total energy in the signal is equal to the integral over frequency of the energy density spectrum |X(f )|2 . This name is justified by the observation that, if x[n] is processed by a narrow bandpass filter with center frequency f0 and bandwidth ∆f , then the energy in the bandpass filtered signal is approximately |X(f0 )|2 ∆f . 8 Frequency response of filters defined by a difference equation Since the convolution theorem reveals that Y (f ) = X(f )H(f ), it follows that the frequency response H(f ) of an LTI system can be determined by dividing the DTFT of the output, Y (f ), by the DTFT of the input, X(f ). This is used to determine the frequency response of the general class of digital filters defined by a linear constant coefficient difference equation (LCCDE): y[n] = K
ak y[n − k] + k =1 M
m=0 bm x[n − m]. Using the linearity of the DTFT along with the time delay theorem (Eq. 3.14) gives Y (f ) = K
ak Y (f )e−j2πf k + k =1 M
bm X(f )e−j2πf m , m=1 which can be rearranged to give the frequency response of the filter defined by the LCCDE:  H(f ) = 3.3.6 M −j2πf m Y (f ) m=0 bm e = . K −j2πf k X(f ) 1 − k=1 ak e Product theorem - Cyclic convolution Because the transform of a convolution is the product of the transforms, we might expect that, by duality, the DTFT of a product would be the convolution of the transforms. However, time and frequency are not completely interchangeable for the DTFT because the time domain is discrete, while the frequency domain is continuous and periodic. Indeed, the convolution of two periodic functions is always undefined. We need to introduce the cyclic convolution of two periodic functions X(f ) and W (f ), which differs from the usual (linear) convolution in that the range of integration is over one period rather than from −∞ to ∞:  X(f )
∗ W (f ) =  1 2 − 12 X(φ)W (f − φ)dφ = W (f )
∗ X(f ) (3.16a) Strictly speaking, this operation should be denoted
∗1 to indicate that the range of integration is 1, but this information is omitted because we know that DTFT’s always have period 1. Using this definition, we can state the product theorem: x[n] w[n] ←→ X(f )
∗ W (f ) (3.16b) In order to prove this theorem, we express the product x[n] w[n] in terms of the Fourier transforms of these two signals:  x[n] w[n] = 1 2 − 12 X(φ) ej2πφn dφ  1 2 − 12 W (θ) ej2πθn dθ =  1 2 − 12  1 2 − 12 X(φ) W (θ) ej2π(φ+θ)n dφ dθ Figure 3.3 shows that, because the function to be integrated is periodic in both φ and θ, integration over the square − 12 ≤ φ, θ ≤ 12 is equivalent to integration over the parallelogram 9 defined by − 12 ≤ φ ≤ 21 and − 12 ≤ φ + θ ≤ 12 . Making the change of variable f = θ + φ, and interchanging the orders of integration, this yields  x[n] w[n] = 1 2 − 21  1 2 − 12  X(φ) W (f − φ) dφ ej2πf n df We recognize this expression as being the inverse Fourier transform of the term between brackets, which is X(f )
∗ W (f ). Important special cases of the product theorem give the sinusoidal modulation (or frequency translation) and ramp-multiplication (or frequency derivative) theorems: ˜ − f0 ) x[n] ej2πf0 n ←→ X(f − f0 ) = X(f )
∗ δ(f n x[n] ←→ 3.4 3.4.1 j  j ∗ δ̃ (f ) X  (f ) = X(f )
2π 2π Filter design Gibbs’ phenomenon A common problem in signal processing is to design filters with sharp cutoffs. For example, consider the ideal lowpass filter H(f ) = ΠW (f ), shown in Figure 3.4A for W = 0.1. Its 2πW n is of infinite duration, and cannot be realized by a unit sample response h[n] = sin πn finite difference equation. A simple idea is to truncate the unit-sample response to the interval  [−N, N ], giving the finite impulse response hN [n] = h[n] ΠN [n]. Because h[n] is a Fourier series for H(f ), such truncation yields a least-squares approximation to H(f ). The frequency response HN (f ) of hN [n] can be related to the desired frequency response H(f ) by means of the product theorem: ∗ hN [n] = h[n] ΠN [n] ←→ HN (f ) = H(f )
sin π(2N + 1)f sin πf Figure 3.4B shows the rectangular function ΠN [n] and its DTFT for N = 7, and Figure 3.4C shows the resulting filter and its frequency response, HN (f ). The frequency response deviates from that of the ideal lowpass filter in that (1) the transition from the passband to the stop band has a finite width ∆f ≈ 1/N , and (2) there are ripples in both the passband and the stopband. These ripples are due to the oscillations at frequency 1/N in the DTFT of the rectangular function. It might seem at first sight that these ripples could be decreased by increasing the number of samples in the finite impulse response. However, Figures 3.4D and 3.4E show that this is not the case: Increasing N from 7 to 30 has little effect on the size of the ripple in the frequency response HN (f ), although it does make the transition width narrower. The presence of ripples whose amplitude does not decrease with increasing length of the unit-sample response is called Gibbs’ phenomenon. It occurs whenever the frequency response of the desired filter shows abrupt discontinuities, in particular for lowpass, highpass, bandpass, and bandstop filters. 10 3.4.2 Filter design using windows One technique for reducing ripple in the frequency responses of filters with sharp cutoffs is to multiply the unit-sample response of the desired filter by a tapered window, w[n], rather than by ∗ W (f ). a rectangular pulse. The frequency response of the FIR filter is then HN (f ) = H(f )
If w[n] can be chosen so that W (f ) shows minimal oscillations, then HN (f ) will not have large ripple. A number of commonly used windows are shown in Fig. 3.5, together with their DTFTs. The DTFTs of the tapered windows (Fig. 3.5D,F,H,J) have much smaller sidelobes than the DTFT of a rectangular window of the same length (Fig. 3.5B). On the other hand, the mainlobes are roughly two times wider than that of the rectangular window. As a result of these differences, lowpass filters designed with tapered windows have larger transition widths and smaller ripple amplitudes than those designed with a rectangular window of the same length (Fig. 3.6A-D). Thus, by selecting different windows, it is possible to trade ripple amplitude for the width of the transition band, while keeping the length of the impulse response constant. The transition width can always be made arbitrarily small by increasing the length of the window. 3.4.3 Filter design using the Parks-McClellan algorithm Windowing is only one of many methods used in designing filters with sharp cutoffs. Another method is to minimize the maximum deviation between the desired frequency response and the actual frequency response. Filters designed using the Parks-McClellan method (an iterative algorithm based on Chebyshev approximations) have ripple with the same amplitude throughout the passband and the stopband. Figure 3.6 compares the frequency responses of three FIR lowpass filters of the same length designed with a rectangular window, a Hamming window, and the Parks-McClellan algorithm. The filter designed using the Parks-McClellan algorithm has approximately equal ripple and somewhat better stopband attenuation than the window designs. 3.5 3.5.1 Continuous-time Fourier transforms Frequency responses of LTI systems The convolution integral is often a cumbersome way to compute the response of a continuoustime linear system. Just as in the case of discrete-time systems, simpler results are obtained by using complex exponentials as inputs. Specifically, consider the output of a system with impulse response h(t) for the input x(t) = ej2πF t : y(t) = h(t) ∗ x(t) = where  ∞ −∞  H(F ) = h(τ ) ej2πF (t−τ ) dτ = H(F ) x(t)  ∞ −∞ h(t) e−j2πF t dt (3.17) is the continuous-time Fourier transform (CTFT) of the impulse response h(t). As in the case of discrete-time systems, H(F ) is called the frequency response of the system. For stable signals, 11 the CTFT is the Laplace transform evaluated for s = j2πF , i.e. on the imaginary axis. 3.5.2 Fourier transform of continuous-time signals For the frequency response to constitute a complete characterization of an LTI system, we need to express arbitrary signals as a sum of complex exponentials. Fourier’s theorem provides such a representation for a wide class of signals:  ∞ x(t) = −∞ X(F ) ej2πF t dF (3.18a) x(t) e−j2πF t dt (3.18b)  ∞ with X(F ) = −∞ As for the DTFT, we will use the short hand notation x(t) ←→ X(F ) to indicate the CTFT pair Eq. 3.18. Note the symmetry between Eqs. 3.18a and 3.18b; the only difference between the two formulas is the minus sign in the argument of the complex exponential for the direct transform (Eq. 3.18b). Thus, for continuous-time signals, the roles of time and frequency can be readily interchanged in Fourier transform formulas, a property known as duality. Duality is less obvious for discrete-time signals because the time domain is discrete, while the frequency domain is continuous and periodic. Using Eqs. 3.18a and 3.17, we deduce that the response of an LTI system with frequency response H(F ) to an arbitrary input x(t) can be expressed as:  ∞ y(t) = −∞ H(F ) X(F ) ej2πF t dF In other words, the Fourier transform of the convolution x(t) ∗ h(t) is the product of the Fourier transforms X(F ) H(F ), exactly as for discrete-time signals x(t) ∗ h(t) ←→ X(F ) H(F ) 3.5.3 The CTFT as a limit of the DTFT Equation 3.18a expresses an arbitrary continuous-time signal as a ”sum” of complex exponentials and can be considered as a limit of the inverse DTFT formula (Eq. 3.6b) when the sampling frequency becomes very high. To show this, x(t) is sampled at intervals ∆T and the sampled signal is expressed as a functions of its DTFT X̃(f ):  x[n] = x(n∆T ) =  1 2 − 12 j2πf n X̃(f ) e  df = Fs 2 − F2s ∆T X̃(F/Fs ) ej 2πF n∆T dF (3.19a)   where F = f /∆T is the analog frequency, Fs = 1/∆T is the sampling frequency, and  X̃(f ) = X̃(F/Fs ) = ∞
x[n] e−j2πF n/Fs = n=−∞ ∞
n=−∞ 12 x(n∆T ) e−j2πF n∆T (3.19b) When ∆T goes to zero (or, equivalently, when Fs goes to infinity), Eqs. 3.19a and 3.19b approach x(t) ≈ x(n∆T ) =  ∞  −∞ and ∆T X̃ (F/Fs ) ≈  X̃(F/Fs ) ∆T  ∞ −∞ ej2πF t dF x(t) e−j2πF t dt, respectively. These equations are the same as Eq. 3.18 if we define the CTFT as  X(F ) = lim ∆T →0 3.5.4 X̃(F/Fs ) ∆T Some simple transform pairs δ(t) ←→ 1 (3.20a) δ(t − t0 ) ←→ e−j2πF t0 (3.20b) 1 ←→ δ(F ) (3.20c) ej2πF0 t ←→ δ(F − F0 ) (3.20d) δ (t) ←→ j2πF (3.20e) j  δ (F ) 2π sin 2πF T ΠT (t) ←→ πF sin 2πW t ←→ ΠW (F ) πt 1 1 δ(F ) + u(t) ←→ 2 j2πF t ←→ e−αt u(t) ←→ tk e−αt u(t) ←→  pT (t) = ∞
δ(t − nT ) ←→ n=−∞ 2 e−π(t/τ ) 3.5.5 (3.20f ) (3.20g) (3.20h) (3.20i) 1 α + j2πF (3.20j) 1 (α + j2πF )k (3.20k) 1 T ∞
δ(F − k=−∞ k ) T 2 ←→ τ e−π(F τ ) (3.20l) (3.20m) Properties of the continuous-time Fourier transform Linearity and symmetry properties of the continuous-time Fourier transform are the same as those of the discrete-time Fourier transform. 13 3.5.6 Convolution and multiplication We have already argued that x(t) ∗ h(t) ←→ X(F ) H(F ) (3.21) Some important special cases of this relation are: x(t − t0 ) = x(t) ∗ δ(t − t0 ) ←→ X(F ) e−j2πF t0 (3.22a) x (t) = x(t) ∗ δ (t) ←→ j2πF X(F ) (3.22b)  R̃x (t) = x(t) ∗ x(−t) ←→ |X(F )|2 (3.22c) Expressed at time zero, Eq. 3.22c yields Parseval’s theorem for continuous-time signals  ∞ Ex = −∞ x(t)2 dt =  ∞ −∞ |X(F )|2 dF (3.23) By symmetry between the roles of time and frequency in Eq. 3.6 it is clear that one has x(t) w(t) ←→ X(F ) ∗ W (F ) (3.24) where convolution in the frequency domain is defined in exactly the same way as time-domain convolution  ∞  X(φ) W (F − φ) dφ X(F ) ∗ W (F ) = −∞ Again, special cases of this theorem are ej2πF0 t x(t) ←→ X(F − F0 ) = X(F ) ∗ δ(F − F0 ) t x(t) ←→ 3.6 3.6.1 jδ (F ) j X  (F ) = X(F ) ∗ 2π 2π (3.25a) (3.25b) Time and frequency resolution - The uncertainty principle Time and frequency resolution The time resolution of a signal-processing operation is its ability to distinguish between the response to two impulses that are closely spaced in time and the response to a single impulse. To be more specific, consider a signal consisting of two unit samples separated by an interval ∆N . The time resolution of a filter is the smallest interval ∆N for which the response of the filter shows two distinct local maxima. For example, Fig. 3.7a shows the response of a 100-point raised-cosine filter n ) Π50 [n − 50] h[n] = 0.5 (1 − cos 2π 100 to pairs of impulses separated by intervals of 0, 25, 50, and 75 samples. The two pulses are resolved in the output if ∆N > 50, which is half the duration of the raised-cosine window. 14 The frequency resolution of a system is defined in the same way as time resolution if we interchange the roles of time and frequency. In this case, the Fourier transforms of the signals to be resolved are impulses in frequency, i.e the time signals are complex exponentials ej2πf n . Consider specifically a signal x[n] which is the sum of two complex exponentials whose frequencies are separated by an interval ∆f . The frequency resolution of a window function w[n] is the smallest ∆f for which the Fourier transform of w[n] x[n] shows two distinct frequency peaks. From the product theorem, this transform is W (f )
∗ X(f ), so that the frequency resolution depends on the bandwidth of W (f ). For example, Figure 3.7b shows the Fourier transform of the product of a 100-point raised-cosine window with a sum of two sine waves whose frequencies are separated by intervals of 0, 0.01, 0.02 and 0.03. The two sine waves are resolved when the frequency separation exceeds 0.02. This corresponds to half the width of the mainlobe of the transform of the 100-point raised-cosine window.2 Thus, for this window, the time resolution is 50 samples, and the frequency resolution is 0.02 cycle/sample, so that the product of time resolution and frequency resolution is about 1. Similar time-bandwidth products hold for other types of windows. 3.6.2 Uncertainty principle for continuous-time signals To summarize the preceding discussion, the time resolution of a window depends on its duration, while its frequency resolution depends on its bandwidth. It is remarkable that, regardless of the window shape, the product of the duration and the bandwidth exceeds a lower bound which is of the order of unity. Such uncertainty relations impose a limit on the time resolution and the frequency resolution that can be simultaneously achieved. There exist a variety of uncertainty relations whose formulations depend on the exact definition of ”duration” and ”bandwidth”. We will prove one form of uncertainty relation using definitions of duration and bandwidth which apply to a broad class of signals, and lead to mathematically-simple results. This relation will be derived for continuous-time signals because they provide greater symmetry between time and frequency domains than do discrete-time signals. Specifically, we will treat the square of a signal h(t) as if it were a probability density function, and define the duration to be twice the standard deviation of this p.d.f. We use the square of h(t) rather than the signal itself because a p.d.f must always be positive. First, we define the center of gravity T̄ in a manner analogous to the mean of a random variable: ∞ t h(t)2 dt  T¯ = −∞ ∞ 2 −∞ h(t) dt The denominator is a normalizing factor ensuring that the area under the ”p.d.f.” is one. Then, we define the r.m.s. duration ∆T to characterize the dispersion of the signal around its center of gravity: ∞ 2 2 −∞ (t − T̄ ) h(t) dt 2  (3.26) ∆T = 4 ∞ 2 −∞ h(t) dt The factor of 4 comes from the observation that the width of a p.d.f is approximately twice the standard deviation. With no loss of generality, we can assume that the center of gravity is at the origin because this can always be achieved by a change of origin without changing the r.m.s. duration. 2 A more conservative definition of frequency resolution, requiring the frequency separation to equal or exceed the mainlobe width (instead of half the mainlobe width), may be preferable in some applications. 15 The r.m.s. bandwidth ∆F is defined in a manner analogous to the r.m.s. duration by treating the magnitude squared of the transform |H(F )|2 as a probability density function: ∆F 2  =4 ∞ 2 2 −∞ F |H(F )| dF ∞ 2 −∞ |H(F )| dF (3.27) With the definitions of Eqs. 3.26 and 3.27, we can formulate the uncertainty principle, which states that, if the signal h(t) decays to zero faster than 1/ |t| for large |t|, the product of the r.m.s. duration and the r.m.s. bandwidth is greater than 1/π: 1 π ∆T ∆F ≥ (3.28) This means that the duration and the bandwidth of a signal cannot simultaneously be made arbitrarily small. A measurement interpretation is that the accuracy in measuring the frequency of a signal is proportional to the signal duration. In quantum physics, Eq. 3.28 is the basis for Heisenberg’s uncertainty principle, which asserts the impossibility of simultaneously specifying the position and momentum of a particle. To prove Eq. 3.28, we first write Parseval’s theorem for the signal h(t)  ∞  ∞ h(t)2 dt = −∞ −∞ |H(F )|2 dF and for its derivative h (t) whose transform is j2πF H(F )  ∞  −∞ 2 h (t) dt = 4π  ∞ 2 −∞ F 2 |H(F )|2 dF Combining these formulas with Eq. 3.26 and 3.27, we obtain (∆T ∆F )2 = 4 π2 ∞ −∞ t2 h(t)2 dt  ∞ −∞ ∞ −∞ h(t)2 dt h (t)2 dt 2 Taking the square root, and applying Schwarz’ inequality to the two functions in the numerator t h(t) and h (t), we obtain: 2 ∆T ∆F ≥ π ∞ −∞ t h(t) h (t) dt ∞ 2 −∞ h(t) (3.29) dt Integrating the numerator by parts yields  ∞ 2 −∞  t h(t) h (t) dt = 2 t h(t) ∞ −∞ −  ∞ −∞ h(t)2 dt The quantity between brackets is zero because we have assumed that |t| h(t) vanishes at infinity. Reporting the value of the integral in the numerator of Eq. 3.29 completes the proof of the uncertainty principle. 16 3.6.3 Gaussian signals It is interesting to determine whether there exist any signals h(t) for which the lower limit on the time-bandwidth product is achieved. We have already seen that Schwarz’ inequality becomes an equality if and only if the two functions are the same within a constant multiplicative factor. Therefore, one must have: h (t) = −α t h(t) where α is a constant. Integrating this differential equation yields: t2 /2 h(t) = C e−α If α is positive, this is a Gaussian function. Negative α is excluded because the signal would not vanish at infinity. By symmetry between the roles of time and frequency, it is not surprising that the Fourier transform of a Gaussian is also a Gaussian. The transform pair takes a particularly   1 : symmetric form if we introduce ∆T = 2/α and ∆F = π ∆T 1 2 1 2 √ e−(t/∆T ) ←→ √ e−(F/∆F ) ∆F ∆T An alternative form more consistent with statistical practice is: 2 2 1 1 e−F /2σf with σt σf = 2π 2π σf √ √ The two alternative forms are related by ∆T = 2 σt and ∆F = 2 σf . 2 /2σ 2 t e−t 3.6.4 ←→ √ Uncertainty principle for discrete-time signals For discrete-time signals h[n], we can obtain a form of uncertainty principle by replacing the integral by a sum in the definition of the r.m.s. duration: ∆N ∆f ≥ where 1 π (3.30a) ∞ n2 h[n]2 (3.30b) 2 n=−∞ h[n] and ∆f is defined in the same manner as ∆F except that the range of integration is from f = − 12 to 12 . If a discrete-time signal h[n] is obtained by sampling a continuous-time signal h(t), Eq. 3.30a is equivalent to Eq. 3.28 if we define ∆N = ∆T /Ts and ∆f = ∆F/Fs . 2 (∆N ) 3.7 = 4 n=−∞  ∞ Summary When a sinusoidal signal with frequency f is used as input to a linear, shift invariant system, the output is the product of the input by the frequency response H(f ), which is the discrete-time Fourier transform of the unit-sample response h[n]: H(f ) = ∞
n=−∞ 17 h[n] e−j2πf n This property is important because Fourier’s theorem provides a decomposition of any stable signal x[n] into a ”sum” of sinusoidal components:  x[n] = 1 2 − 12 X(f ) ej2πf n df Thus, for computing the responses of linear filters, Fourier transforms allow the complex oper ation of convolution to be replaced by the simpler operation of multiplication: y[n] = x[n] ∗ h[n] ←→ Y (f ) = X(f ) H(f ) Similarly, the DTFT of a product of signals is the cyclic convolution of their transforms x[n] w[n] ←→ X(f )
∗ W (f ) This product theorem is the basis for the windowing method of filter design, which limits the ripple for filters whose frequency response shows sharp discontinuities (Gibbs’ phenomenon). These properties of Fourier transforms also apply to continuous-time signals and systems, with the added advantage that there is greater symmetry between time and frequency domains. In particular, the uncertainty principle states that there exists a lower bound on the product of the duration and the bandwidth of a signal, so that signal processing operations cannot simultaneous achieve fine time resolution and fine frequency resolution. The discrete-time Fourier transform can be treated as a special case of the continuous-time Fourier transform, if discrete signals are interpreted as weighted sums of delta functions spaced at regular time intervals. This interpretation is useful for deriving the sampling theorem, and for implementing continuous-time linear systems as digital filters. 3.8 Further reading Siebert: Chapters 13 and 16; Chapter 18, Sections 1 and 2. Oppenheim and Schafer: Chapter 2, Sections 6-9; Chapters 5 and 7. Oppenheim, Willsky, and Nawab: Chapters 4, 5 and 6 Karu, Chapters 3, 16 and 17 18 Figure 3.1: Frequency responses of simple digital filters. (A) Two-point smoother. (B) Euler’s derivative for Ts = 2. (C) First-order recursive lowpass filter for a = 0.5 (solid), a = 0.7 (dash-dot), and a = 0.9 (dotted). (D) Digital resonator for a1 = 0.56 and a2 = −0.81. 19 Figure 3.2: (A) The rectangular pulse Π4 [n] and its DTFT. (B) The ideal lowpass filter Π0.1 (f ) and inverse DTFT. Figure 3.3: Regions of integration used for proving the product theorem. 20 Figure 3.4: Example of filter design by windowing. (A) Specifications for the ideal lowpass filter with cutoff frequency fc = 0.1; the desired frequency response, H(f ) = Π0.1 (f ), and the corresponding impulse response, h[n]. (B) The 15-point rectangular window w1 [n] = Π7 [n] and its DTFT. (C) The 15-point FIR filter designed by windowing, h7 [n] = h[n]w1 [n], and its DTFT. The frequency response results from convolving the desired response in (A) with DTFT of the ∗ W1 (f ). (D) The 61-point rectangular window w2 [n] = Π30 [n] window in (B), H7 (f ) = H(f )
and its DTFT. (E) Similar to (C) for the 61-point FIR filter designed using the rectangular window in (D). 21 Figure 3.5: (A) 61-point rectangular window, Π30 [n]. (B) DTFT of rectangular window. (C) 61point Bartlett (triangular) window. (D) DTFT of Bartlett window. (E) 61-point Hanning (raised cosine) window. (F) DTFT of Hanning window. (G) 61-point Hamming window, wH [n] = (0.54 + 0.46 cos(πn/N ))Π[n]. (H) DTFT of Hamming window. (I) 61-point Kaiser windows, with β = 3 (open circles) and β = 6 (filled circles). (J) DTFT of Kaiser windows with β = 3 (solid line) and β = 6 (broken line). The parameter β controls the tradeoff between mainlobe width and sidelobe ripple. 22 Figure 3.6: (A) and (B) Frequency response of 61-point lowpass filter designed with a rectangular window (logarithmic and linear magnitude scales). (C) and (D) Frequency response of 61-point lowpass filter designed with a Hamming window (logarithmic and linear magnitude scales). (E) and (F) Frequency response of 61-point lowpass filter designed using the Parks-McClellan algorithm for a transition bandwidth of ∆f = 0.06 (logarithmic and linear magnitude scales). 23 Figure 3.7: (A) Convolution of a 100-point raised cosine (hanning) window with two impulses separated by intervals of 0, 25, 50, and 75 samples. (B) Fourier transforms of the product of a 100-point raised cosine window with the sum of two sine waves separated by 0, 0.01, 0.02, and 0.03 cycles/sample. 24