Discrete Fourier Transform (DFT) Recall the DTFT: X(ω) = ∞ ∑ As a result, the summation in the Discrete Fourier Series (DFS) should contain only N terms:
Previous PDF | Next PDF |
[PDF] Discrete Fourier Series & Discrete Fourier Transform - CityU EE
Discrete Fourier Series DTFT may not be practical for analyzing because is a function of the continuous frequency variable and we cannot use a digital
[PDF] Fourier series and the discrete Fourier transform
Prove (3 9) Summation by parts allows us to investigate the convergence of special type of trigonometric series Theorem 1 Suppose that cn > 0
[PDF] Signals and Systems - Lecture 5: Discrete Fourier Series
Response to Complex Exponential Sequences Relation between DFS and the DT Fourier Transform Discrete Fourier series representation of a periodic signal
[PDF] Discrete-time Fourier Series (DTFS) - NPTEL
The Fourier transform of a sum of discrete-time (aperiodic) signals is the respective sum of transforms Arun K Tangirala (IIT Madras) Applied Time- Series
[PDF] Lecture 7 - The Discrete Fourier Transform
The Discrete Fourier Transform (DFT) is the equivalent of the continuous Fourier Transform for signals known only at instants separated by sample times ¡ (i e
[PDF] Discrete-Time Fourier Series and Transforms - UBC Math
Discrete–time Fourier Series and Fourier Transforms We now start considering discrete–time signals A discrete–time signal is a function (real or complex
[PDF] Fourier Transform - Stanford Engineering Everywhere
6 5 Getting to Know Your Discrete Fourier Transform http://epubs siam org/ sam-bin/getfile/SIREV/articles/38228 pdf 1 8 The Math, the Majesty, the End
[PDF] Fourier Series and the Discrete Fourier Transform - Eecs Umich
The Fourier Series (FS) and the Discrete Fourier Transform (DFT) should be thought of as playing similar roles for periodic signals in either continuous time ( FS)
[PDF] Fourier series of periodic discrete-time signals
Fourier series of discrete-time periodic signal An N-periodic discrete-time signal can be expanded as x(n) = N−1 ∑ k=0 dke j2πkn/N where dN−k = d ∗ k 9
[PDF] Discrete Fourier Transform (DFT)
Discrete Fourier Transform (DFT) Recall the DTFT: X(ω) = ∞ ∑ As a result, the summation in the Discrete Fourier Series (DFS) should contain only N terms:
[PDF] discrete fourier transform (examples and solutions)
[PDF] discrete fourier transform code in matlab
[PDF] discrete fourier transform equation explained
[PDF] discrete fourier transform in image processing
[PDF] discrete fourier transform in image processing ppt
[PDF] discrete fourier transform matlab code
[PDF] discrete fourier transform normalization
[PDF] discrete fourier transform of sine wave
[PDF] discrete fourier transform python code
[PDF] discrete low pass filter matlab
[PDF] discrete low pass filter simulink
[PDF] discrete low pass filter z transform
[PDF] discrete math symbols meaning
[PDF] discrete mathematics
Discrete Fourier Transform (DFT)Recall the DTFT:
X(ω) =∞?
n=-∞x(n)e-jωn.DTFT is not suitable for DSP applications because•In DSP, we are able to compute the spectrum only at specific
discrete values ofω,•Any signal in any DSP application can be measured only in a finite number of points.A finite signal measured atNpoints:
x(n) =? ?0, n <0,0, n≥N,
wherey(n)are the measurements taken atNpoints.EE 524, Fall 2004, # 51Sample the spectrumX(ω)in frequency so that
X(k) =X(kΔω),Δω=2πN=?
X(k) =N-1?
n=0x(n)e-j2πknNDFT.Theinverse DFTis given by:
x(n) =1NN-1? k=0X(k)ej2πknN. x(n) =1NN-1? k=0? N-1? m=0x(m)e-j2πkmN? e j2πknN N-1? m=0x(m)?1NN-1?
k=0e -j2πk(m-n)N?δ(m-n)=x(n).EE 524, Fall 2004, # 52
The DFT pair:X(k) =N-1?
n=0x(n)e-j2πknNanalysis x(n) =1NN-1? k=0X(k)ej2πknNsynthesis.Alternative formulation:X(k) =N-1?
n=0x(n)Wkn←-W=e-j2πN x(n) =1NN-1? k=0X(k)W-kn.EE 524, Fall 2004, # 53EE 524, Fall 2004, # 54
Periodicity of DFT SpectrumX(k+N) =N-1?
n=0x(n)e-j2π(k+N)nN N-1? n=0x(n)e-j2πknN? e -j2πn =X(k)e-j2πn=X(k) =? the DFT spectrum is periodic with periodN(which is expected, since the DTFT spectrum is periodic as well, but with period2π).
Example:DFT of a rectangular pulse:
0,otherwise.
X(k) =N-1?
n=0e -j2πknN=Nδ(k) =? the rectangular pulse is "interpreted" by the DFT as a spectral line at frequencyω= 0.EE 524, Fall 2004, # 55 DFT and DTFT of a rectangular pulse (N=5)EE 524, Fall 2004, # 56 Zero PaddingWhat happens with the DFT of this rectangular pulse if we increaseNbyzero padding: {y(n)}={x(0),...,x(M-1),0,0,...,0????N-Mpositions},
wherex(0) =···=x(M-1) = 1. Hence, DFT isY(k) =N-1?
n=0y(n)e-j2πknN=M-1? n=0y(n)e-j2πknN sin(πkMN)sin(πkN)e-jπk(M-1)N.EE 524, Fall 2004, # 57DFT and DTFT of a Rectangular Pulse with
Zero Padding (N= 10, M= 5)Remarks:•Zero padding of analyzed sequence results in "approximating" its DTFT better,•Zero padding cannot improve the resolution of spectral components, because the resolution is "proportional" to1/Mrather than1/N,•Zero padding is very important for fast DFT implementation
(FFT).EE 524, Fall 2004, # 58 Matrix Formulation of DFTIntroduce theN×1vectors x=? ??x(0) x(1)... x(N-1)? ??,X=? ??X(0)X(1)...
X(N-1)?
and theN×Nmatrix W=? ?????W0W0W0···W0
W0W1W2···WN-1
W0W2W4···W2(N-1)
W0WN-1W2(N-1)···W(N-1)2?
DFT in a matrix form:
X=Wx.Result:Inverse DFT is given by
x=1NWHX,EE 524, Fall 2004, # 59 which follows easily by checkingWHW=WWH=NI, where Idenotes the identity matrix. Hermitian transpose: xH= (xT)?= [x(1)?,x(2)?,...,x(N)?].
Also, "
?" denotes complex conjugation. Frequency Interval/Resolution:DFT"s frequency resolution F res≂1NT[Hz] and covered frequency intervalΔF=NΔFres=1T=Fs[Hz].
Frequency resolution is determined only by the length of the 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, # 510 Answer:No, because resolution is determined by the length of observation interval, and zero padding does not increase this length. Example (DFT Resolution):Two complex exponentials with two close frequenciesF1= 10Hz andF2= 12Hz sampled with the sampling intervalT= 0.02seconds. Consider various data lengthsN= 10,15,30,100with zero padding to 512 points.DFT withN= 10and zero padding to 512 points. Not resolved:F2-F1= 2Hz<1/(NT) = 5Hz.EE 524, Fall 2004, # 511DFT withN= 15and zero padding to 512 points.
Not resolved:F2-F1= 2Hz<1/(NT)≈
3.3Hz.DFT withN= 30and zero padding to 512 points.
Resolved:F2-F1= 2Hz>1/(NT)≈1.7Hz.EE 524, Fall 2004, # 512DFT withN= 100and zero padding to 512
points. Resolved:F2-F1= 2Hz>1/(NT) =0.5Hz.EE 524, Fall 2004, # 513
DFT Interpretation Using
Discrete Fourier SeriesConstruct a periodic sequenceby periodic repetition ofx(n) everyNsamples: {?x(n)}={...,x(0),...,x(N-1)???? {x(n)},x(0),...,x(N-1)???? {x(n)},...} The discrete version of the Fourier Series can be written as ?x(n) =? kX kej2πknN=1N? k?X(k)ej2πknN=1N?
k?X(k)W-kn,
where ?X(k) =NXk. Note that, for integer values ofm, we have W As a result, the summation in the Discrete Fourier Series (DFS) should contain onlyNterms: ?x(n) =1NN-1? k=0?X(k)ej2πknNDFS.EE 524, Fall 2004, # 514
Inverse DFS
The DFS coefficients are given by
X(k) =N-1?
n=0?x(n)e-j2πknNinverse DFS.Proof. N-1? n=0?x(n)e-j2πknN=N-1? n=0? ?1NN-1? p=0?X(p)ej2πpnN?
e-j2πknN N-1? p=0? X(p)?1NN-1?
n=0e j2π(p-k)nN?δ(p-k)=
?X(k).The DFS coefficients are given by
X(k) =N-1?
n=0?x(n)e-j2πknNanalysis, ?x(n) =1NN-1? k=0?X(k)ej2πknNsynthesis.EE 524, Fall 2004, # 515
•DFS and DFT pairs are identical, except that-DFT is applied to finite sequencex(n),-DFS is applied to periodic sequence?x(n).•Conventional (continuous-time) FS vs. DFS-CFS represents a continuous periodic signal using an
infinite number of complex exponentials, whereas-DFS represents a discrete periodic signal using a finite number of complex exponentials.EE 524, Fall 2004, # 516