Discrete Fourier Transform (DFT)Recall the DTFT:X(ω) =∞Xn=−∞x(n)e−jωn.DTFT is not suitable for DSP applications because• In DSP, we are able to compute the spectrum only at specificdiscrete values of ω,• Any signal in any DSP application can be measured only ina finite number of points.A finite signal measured at N points:x(n) =0, n < 0,y(n), 0 ≤ n ≤ (N − 1),0, n ≥ N,where y(n) are the me asurements t aken at N points.EE 524, Fall 2004, # 5 1Sample the spectrum X(ω) in frequency so thatX(k) = X(k∆ω), ∆ω =2πN=⇒X(k) =N−1Xn=0x(n)e−j2πknNDFT.The inverse DFT is given by:x(n) =1NN−1Xk=0X(k)ej2πknN.x(n) =1NN−1Xk=0(N−1Xm=0x(m)e−j2πkmN)ej2πknN=N−1Xm=0x(m)(1NN−1Xk=0e−j2πk(m−n)N)| {z }δ(m−n)= x(n).EE 524, Fall 2004, # 5 2The DFT pair:X(k) =N−1Xn=0x(n)e−j2πknNanalysisx(n) =1NN−1Xk=0X(k)ej2πknNsynthesis.Alternative formulation:X(k) =N−1Xn=0x(n)Wkn←− W = e−j2πNx(n) =1NN−1Xk=0X(k)W−kn.EE 524, Fall 2004, # 5 3EE 524, Fall 2004, # 5 4Periodicity of DFT SpectrumX(k + N) =N−1Xn=0x(n)e−j2π(k+N)nN= N−1Xn=0x(n)e−j2πknN!e−j2πn= X(k)e−j2πn= X(k) =⇒the DFT spectrum is periodic with period N (which is expected,since the DTFT spectrum is periodic as well, but with period2π).Example: DFT of a rectangular pulse:x(n) =1, 0 ≤ n ≤ (N − 1),0, otherwise.X(k) =N−1Xn=0e−j2πknN= Nδ(k) =⇒the rectangular pulse is “interpreted” by the DFT as a spectralline at frequency ω = 0.EE 524, Fall 2004, # 5 5DFT and DTFT of a rectangular pulse (N=5)EE 524, Fall 2004, # 5 6Zero PaddingWhat happens with the DFT of this rectangular pulse if weincrease N by zero padding:{y(n)} = {x(0), . . . , x(M − 1),0, 0, . . . , 0| {z }N−M positions},where x(0) = · · · = x(M − 1) = 1. Hence, DFT isY (k) =N−1Xn=0y(n)e−j2πknN=M−1Xn=0y(n)e−j2πknN=sin(πkMN)sin(πkN)e−jπk(M−1)N.EE 524, Fall 2004, # 5 7DFT and DTFT of a Rectangular Pulse withZero Padding (N = 10, M = 5)Remarks:• Zero padding of analyzed sequence results in“approximating” its DTFT better,• Zero padding cannot improve the resolution of spectralcomponents, because the resolution is “proportional” to1/M rather than 1/N,• Zero padding is very important for fast DFT implementation(FFT).EE 524, Fall 2004, # 5 8Matrix Formulation of DFTIntroduce the N × 1 vectorsx =x(0)x(1)...x(N − 1), X =X(0)X(1)...X(N − 1).and the N × N matrixW =W0W0W0· · · W0W0W1W2· · · WN−1W0W2W4· · · W2(N−1)...............W0WN−1W2(N−1)· · · W(N−1)2.DFT in a matrix form:X = Wx.Result: Inverse DFT is given byx =1NWHX,EE 524, Fall 2004, # 5 9which follows easily by checking WHW = WWH= NI, whereI denotes the identity matrix. Hermitian transpose:xH= (xT)∗= [x(1)∗, x(2)∗, . . . , x(N)∗].Also, “∗” denotes complex conjugation.Frequency Interval/Resolution: DFT’s frequency resolutionFres∼1NT[Hz]and covered frequency interval∆F = N∆Fres=1T= Fs[Hz].Frequency resolution is determined only by the length ofthe observation interval, whereas the frequency interval isdetermined by the length of sampling interval. Thus• Increase sampling rate =⇒ expand frequency interval,• Increase observation time =⇒ improve frequency resolution.Question: Does zero padding alter the frequency resolution?EE 524, Fall 2004, # 5 10Answer: No, because resolution is determined by the length ofobservation interval, and zero padding does not increase thislength.Example (DFT Resolution): Two complex exponentials withtwo close frequencies F1= 10 Hz and F2= 12 Hz sampledwith the sampling interval T = 0.02 seconds. Consider variousdata lengths N = 10, 15, 30, 100 with zero padding to 512points.DFT with N = 10 and zero padding to 512 points.Not resolved: F2− F1= 2 Hz < 1/(NT ) = 5 Hz.EE 524, Fall 2004, # 5 11DFT with N = 15 and zero padding to 512 points.Not resolved: F2− F1= 2 Hz < 1/(NT ) ≈3.3 Hz.DFT with N = 30 and zero padding to 512 points.Resolved: F2− F1= 2 Hz > 1/(NT ) ≈ 1.7 Hz.EE 524, Fall 2004, # 5 12DFT with N = 100 and zero padding to 512points. Resolved: F2− F1= 2 Hz > 1/(NT ) =0.5 Hz.EE 524, Fall 2004, # 5 13DFT Interpretation UsingDiscrete Fourier SeriesConstruct a periodic sequence by periodic repetition of x(n)every N samples:{ex(n)} = {. . . , x(0), . . . , x(N − 1)| {z }{x(n)}, x(0), . . . , x(N − 1)| {z }{x(n)}, . . .}The discrete version of the Fourier Series can be written asex(n) =XkXkej2πknN=1NXkeX(k)ej2πknN=1NXkeX(k)W−kn,whereeX(k) = NXk. Note that, for integer values of m, wehaveW−kn= ej2πknN= ej2π(k+mN)nN= W−(k+mN)n.As a result, the summation in the Discrete Fourier Series (DFS)should contain only N terms:ex(n) =1NN−1Xk=0eX(k)ej2πknNDFS.EE 524, Fall 2004, # 5 14Inverse DFSThe DFS coefficients are given byeX(k) =N−1Xn=0ex(n)e−j2πknNinverse DFS.Proof.N−1Xn=0ex(n)e−j2πknN=N−1Xn=01NN−1Xp=0eX(p)ej2πpnNe−j2πknN=N−1Xp=0eX(p)(1NN−1Xn=0ej2π(p−k)nN)| {z }δ(p−k)=eX(k).2The DFS coefficients are given byeX(k) =N−1Xn=0ex(n)e−j2πknNanalysis,ex(n) =1NN−1Xk=0eX(k)ej2πknNsynthesis.EE 524, Fall 2004, # 5 15• DFS and DFT pairs are identical, except that− DFT is applied to finite sequence x(n),− DFS is applied to periodic sequence ex(n).• Conventional (continuous-time) FS vs. DFS− CFS represents a continuous periodic signal using aninfinite number of complex exponentials,whereas− DFS represents a discrete periodic signal using a finitenumber of complex exponentials.EE 524, Fall 2004, # 5 16DFT: PropertiesLinearityCircular shift of a sequence: if X(k) = DFT {x(n)} thenX(k)e−j2πkmN= DFT {x((n − m) mod N)}Also if x(n) = DFT−1{X(k)} thenx((n − m) mod N) = DFT−1{X(k)e−j2πkmN}where the operation mod N denotes the pe riodic extensionex(n) of the signal x(n):ex(n) = x(n mod N).EE 524, Fall 2004, # 5 17DFT: Circular ShiftN−1Xn=0x((n − m)modN)Wkn= WkmN−1Xn=0x((n − m)modN)Wk(n−m)EE 524, Fall 2004, # 5 18= WkmN−1Xn=0x((n − m)modN)Wk(n−m)modN= WkmX(k),where we use the facts that Wk(lmodN)= Wkland that theorder of summation in DFT does not change its result.Similarly, if X(k) = DFT {x(n)}, thenX((k − m)modN) = DFT {x(n)ej2πmnN}.DFT: Parseval’s TheoremN−1Xn=0x(n)y∗(n) =1NN−1Xk=0X(k)Y∗(k)Using the matrix formulation of the DFT, we obtainyHx =1NWHYH1NWHY=1N2YHW WH| {z }NIX =1NYHX.EE 524, Fall 2004, # 5 19DFT: