Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341:DISCRETE-TIME SIGNAL PROCESSING OpenCourse Ware 2006 Lecture 15 The Discrete Fourier Transform (DFT) Reading:Sections 8.1-8.6 in Oppenheim,Schafer Buck (OSB). Here are some basic points about the discrete Fourier Transform (DFT),the discrete-time Fourier Transform (DTFT),and the fast Fourier transform (FFT). 1.The DTFT can't be computed 2.The DFT can be computed 3.The DFT isn't the DTFT 4.The FFT isn't the DFT 5.The FFT is not necessarily the best/most effient way to compute whatever it is that it computes In this lecture,we will cover the first three points,and discuss the FFT in lecture 19. Sampling in Frequency The DTFT of xIn]is defined as follows: x(e)=∑rmle-om n Since w is a continuous variable,there are an infinite number of possible values of w from 0 to 2m or from-to Thus,X(ej)can be computed only at a finite set of frequencies: X(eiae)=∑zmle-un n As a special case,we use N samples equally spaced around the unit circle: 2πk Wk= N, k=0,1,,N-1 and define the N samples of X(ew): 1
Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing OpenCourseWare 2006 Lecture 15 The Discrete Fourier Transform (DFT) Reading: Sections 8.1 - 8.6 in Oppenheim, Schafer & Buck (OSB). Here are some basic points about the discrete Fourier Transform (DFT), the discrete-time Fourier Transform (DTFT), and the fast Fourier transform (FFT). 1. The DTFT can’t be computed 2. The DFT can be computed 3. The DFT isn’t the DTFT 4. The FFT isn’t the DFT 5. The FFT is not necessarily the best/most effient way to compute whatever it is that it computes In this lecture, we will cover the first three points, and discuss the FFT in lecture 19. Sampling in Frequency The DTFT of x[n] is defined as follows: e X −jωn (ejω) = �x[n] n Since ω is a continuous variable, there are an infinite number of possible values of ω from 0 to 2π or from −π to π. Thus, X(ejω) can be computed only at a finite set of frequencies: e X −jωkn (ejωk ) = �x[n] n As a special case, we use N samples equally spaced around the unit circle: 2πk ωk = N , k = 0, 1, . . . , N − 1 and define the N samples of X(ejω): 1
X内色X(e“)儿w=袋= r[nle-j2xkn/N For convenience in notation,we define Wwei祭 then 十00 X内=∑cmw. n=-00 However,we still can not compute X[k]since xn]can be infinitely long and we are summing for all n.Even if x[n]is finite,we can not always recover x[n]perfectly from X[k]because X[k]s are essentially the samples of the DTFT.So there are some necessary conditions for which we will be able to recover x[n]from X[k]. In order to find these conditions,first speculate the sampling theorem in the continuous-time domain: X.(j2) 0 X,(j) △T () 2m 2 △T △T Sampling in time corresponds to replication in the frequency domain.In order to recover Xe(jn) perfectly by low-pass filtering Xs(jn),frequency aliasing should be avoided.Therefore,x(t) should be bandlimited to o,and sampling interval should be short enough so that △T< 2n We can apply the time-frequency duality to illustrate the sampling process in the frequency domain.If the sampling interval in frequency is not short enough,we get time aliasing.If the 2
+∞ X[k] � X(ejω)| ω= 2πk = � x[n]e−j2πkn/N N n=−∞ For convenience in notation, we define −j 2π WN � e N then +∞ X nk [k] = � x[n]WN . n=−∞ However, we still can not compute X[k] since x[n] can be infinitely long and we are summing for all n. Even if x[n] is finite, we can not always recover x[n] perfectly from X[k] because X[k]s are essentially the samples of the DTFT. So there are some necessary conditions for which we will be able to recover x[n] from X[k]. In order to find these conditions, first speculate the sampling theorem in the continuous-time domain: Sampling in time corresponds to replication in the frequency domain. In order to recover Xc(jΩ) perfectly by low-pass filtering Xs(jΩ), frequency aliasing should be avoided. Therefore, x(t) should be bandlimited to Ω0, and sampling interval should be short enough so that 2π ΔT < . Ω0 We can apply the time-frequency duality to illustrate the sampling process in the frequency domain. If the sampling interval in frequency is not short enough, we get time aliasing. If the 2
sampling interval in the frequency domain is An,it corresponds to replication of signals in time domain at every 2/An.In order to recover x(t)from i(t)by time windowing,x(t)should be time-limited toTo,and sampling interval should be small enough so that △0M. Under this condition,x[n]can be perfectly recovered from the samples of the DTFT: 4W=六∑X肉w,n=0.1w-1 w-1 k=0 The Discrete Fourier Series Let n]be a periodic signal with period N(We will use to denote periodic signals).Consider representing this signal by a Fourier series corresponding to a linear combination of harmonically related complex exponentials,where ek n]=eikn 3
sampling interval in the frequency domain is ΔΩ, it corresponds to replication of signals in time domain at every 2π/ΔΩ. In order to recover x(t) from x˜(t) by time windowing, x(t) should be time-limited to T0, and sampling interval should be small enough so that 2π ΔΩ M. Δω Under this condition, x[n] can be perfectly recovered from the samples of the DTFT: 1 N−1 x[n] = � X[k]W−nk, n = 0, 1, . . . , N − 1. N N k=0 The Discrete Fourier Series Let x˜[n] be a periodic signal with period N (We will use ˜ to denote periodic signals). Consider representing this signal by a Fourier series corresponding to a linear combination of harmonically 2πk related complex exponentials ejωn, where ω = N . ek[n] = e 3 2π j N kn
Notice that exin]ex+ninj. Therefore,the Fourier series of a discrete-time periodic signal n]only requires N complex exponentials,so it has the form N-1 1 N-1 =0 k=0 Here,1/N is included in the definition for convenience in future. To obtainXk]fromn], N-1 zn]w, n=0 which can be verified by direct substitution.Thus,n]is periodic in n with period N,and Xk]is periodic in k with period N. Consider two periodic sequences n and yn both with period N,such that n→X[内 and m←一Y[. OSB Figure 8.3 illustrates the periodic convolution of two periodic sequences.Note that as the sequences 2n-m]shifts to the right or left,values that leave the interval between the dotted lines at one end reappear at the other end because of the periodicity. The periodic convolution of periodic sequences corresponds to multiplication of the correspond- ing periodic sequences of Fourier series coefficients. N-1 mn-m一[[ m=0 Other properties of the DFS are discussed in OSB section 5.2. The Discrete Fourier Transform Consider a finite sequence x[n]with length N,which is zero except at n =0,1,...,N-1. Then,we can think about extending this sequence into a periodic sequence of period N. in]=xIn+rN]=x[n mod N]=x[((n))N] 4
� � Notice that ek[n] = ek+N [n]. Therefore, the Fourier series of a discrete-time periodic signal x˜[n] only requires N complex exponentials, so it has the form N−1 X˜[k] N−1 ˜ W−nk X[k] N . 1 1 ej 2π N nk x˜[n] = = N N k=0 k=0 Here, 1/N is included in the definition for convenience in future. To obtain X[k] from ˜ ˜ x[n], N−1 Wnk, ˜X[k] = ˜[n] � x N n=0 which can be verified by direct substitution. Thus, x˜[n] is periodic in n with period N, and X˜[k] is periodic in k with period N. Consider two periodic sequences x˜[n] and y˜[n] both with period N, such that x ˜ ˜[n] ←→ X[k] and y˜[n] Y˜ ←→ [k]. OSB Figure 8.3 illustrates the periodic convolution of two periodic sequences. Note that as the sequences x˜2[n − m] shifts to the right or left, values that leave the interval between the dotted lines at one end reappear at the other end because of the periodicity. The periodic convolution of periodic sequences corresponds to multiplication of the corresponding periodic sequences of Fourier series coefficients. N−1 ˜ � x ˜ [m]y˜[n − m] X[k]Y˜ ←→ [k] m=0 Other properties of the DFS are discussed in OSB section 5.2. The Discrete Fourier Transform Consider a finite sequence x[n] with length N, which is zero except at n = 0, 1, . . . , N − 1. Then, we can think about extending this sequence into a periodic sequence of period N. x˜[n] = x[n + rN] = x[n mod N] = x[((n))N ] 4
As long as there is no time aliasing,we can recover xn]perfectly from n]. xin]in]RnIn], where RN[n]is a rectangular window: Rw[m=1n=0,1,.,N-1 0 otherwise The discrete Fourier transform of a finite sequence x[n is defined as the discrete Fourier series of iin. N- N-1 X[内= ∑mWW=∑z[n]Wkk=0,1,V-1 0 n=0 m=∑X[网Wkn=0,1,w、 k=0 Consider a finite-duration sequence shown in OSB Figure 8.10(a).If we consider xin]as a sequence of length N =5,the corresponding periodic sequence is in]in OSB Figure 8.10(b). Fourier series coefficients X[k]for n]is shown in OSB Figure 8.10(c).To emphasize that the Fourier series coefficients are samples of the Fourier transform,X(ew)is also shown.The 5-point DFT X[k]corresponds to one period of X[k],as shown in OSB Figure 8.10(d). If we consider zn]to be a sequence of length N =10,however,we get completely different DFT values.The corresponding periodic sequence i[n]is shown in OSB Figure 8.11(b).The 10-point DFT X[k]is shown in OSB Figure 8.11(c)and (d). We can interpret the relationship between a finite-length sequence x[n]and a periodic sequence n by displaying x[n]around the circumference of a cylinder with a circumference of exactly N points.As we repeatedly traverse the circumference of the cylinder,the sequence that we see is the periodic sequence n.Then,a linear shift of this sequence corresponds to a rota- tion of the cylinder.Such a shift is called a circular shift,which is illustrated in OSB Figure 8.12. A circular shift in time results in multiplying the DFT of the sequence by a linear phase factor. x(n-m)wl,0≤n≤N-1一e-2mk/NmX[ Consider two finite-duration sequences zin]and z2[n],both of length N,with DFTs X1[k]and X2[k],respectively.Then,X3k]=Xi[k]X2[k]corresponds to the DFT of the N-point circular convolution of zi[n and x2[n],defined as follows: N-1 x3m=∑xmx2l(n-m)wl,0≤n≤N-1. m=0 OSB Figure 8.14 illustrates the circular convolution of two finite-length sequences. 5
As long as there is no time aliasing, we can recover x[n] perfectly from x˜[n]. x[n] = x˜[n]RN [n], where RN [n] is a rectangular window: RN [n] = 1 n = 0, 1, . . . , N − 1 0 otherwise The discrete Fourier transform of a finite sequence x[n] is defined as the discrete Fourier series of x˜[n]. N−1 N−1 X Wnk [k] = � x[n] = � x[n]Wnk ˜ N N k = 0, 1, . . . , N − 1 n=0 n=0 N−1 1 x[n] = � X[k]W−nk n = 0, 1, . . . , N − 1 N N k=0 Consider a finite-duration sequence shown in OSB Figure 8.10(a). If we consider x[n] as a sequence of length N = 5, the corresponding periodic sequence is x˜[n] in OSB Figure 8.10(b). Fourier series coefficients X[k] for ˜ ˜ x[n] is shown in OSB Figure 8.10(c). To emphasize that the Fourier series coefficients are samples of the Fourier transform, |X(ejω)| is also shown. The 5-point DFT X[k] corresponds to one period of X˜[k], as shown in OSB Figure 8.10(d). If we consider x[n] to be a sequence of length N = 10, however, we get completely different DFT values. The corresponding periodic sequence x˜[n] is shown in OSB Figure 8.11(b). The 10-point DFT X[k] is shown in OSB Figure 8.11(c) and (d). We can interpret the relationship between a finite-length sequence x[n] and a periodic sequence x˜[n] by displaying x[n] around the circumference of a cylinder with a circumference of exactly N points. As we repeatedly traverse the circumference of the cylinder, the sequence that we see is the periodic sequence x˜[n]. Then, a linear shift of this sequence corresponds to a rotation of the cylinder. Such a shift is called a circular shift, which is illustrated in OSB Figure 8.12. A circular shift in time results in multiplying the DFT of the sequence by a linear phase factor. e x[((n − m))N ], 0 ≤ n ≤ N − 1 ↔ −j(2πk/N)mX[k] Consider two finite-duration sequences x1[n] and x2[n], both of length N, with DFTs X1[k] and X2[k], respectively. Then, X3[k] = X1[k]X2[k] corresponds to the DFT of the N-point circular convolution of x1[n] and x2[n], defined as follows: N−1 x3[n] = � x1[m]x2[((n − m))N ], 0 ≤ n ≤ N − 1. m=0 OSB Figure 8.14 illustrates the circular convolution of two finite-length sequences. 5
Summary 1.z[n]arbitrary length DTFT X(ejv) X(e“)= ∑ xnje-jwn n=-0 2.[n]periodic-DFS[附 N- [= ∑nw, Wv=e-i装 n= = ∑[njExlnjW n=-0 =DTFT{njRNin])l.=装 3.x[n]finite length (0,1,....N-1)DFT[] 网=m》州=∑+rW xIn]in]Rv(n] DFT of ln]DFS of [((n))N]DTFT {n The following figure summarizes this lecture. DTFT Finite Length Signal X(e) x[n] 1 X[k]DFT 1 Periodic Sequence (n] [附 DFS 6
Summary 1. x[n] arbitrary length DTFT X(ejω ↔ ) ∞ e X −jωn (ejω) = � x[n] n=−∞ x[n] periodic DFS ˜ 2. ˜ ↔ X[k] N−1 Wnk X[k] = , � ˜ x˜[n] N N WN = e−j 2π n=0 ∞ Wnk = � x˜[n]RN [n] N n=−∞ = DT F T {x˜[n]RN [n] 2πk N }|ω= 3. x[n] finite length (0, 1, . . . , N − 1) ↔ DFT X[k] x˜[n] = x[((n))N ] = �x[n + rN] r x[n] = x˜[n]RN [n] DFT of x[n] = DFS of x[((n))N ] = DTFT {x[n] 2πk N }|ω= The following figure summarizes this lecture. 6
