DOC PREVIEW
UK EE 422G - Chapter 10: Discrete Fourier Transform & Fast Fourier Transform

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-1Chapter 10: Discrete Fourier Transform & Fast Fourier Transform An assortment of “Fourier” analysis methods: 1. Fourier Series – continuous-time periodic signals ∑∫∞−∞=−−==ktTjkktTjkkeXtxdtetxTXTTππ22)()(122:Synthesis :Analysis 2. Fourier Transform – general continuous-time signals ∫∫∞∞−∞∞−−==ωωωωωdejXtxdtetxjXtjtj)()(:Synthesis)()( :Analysis 3. Discrete-time Fourier Transform – general discrete-time signals ∫∑∞∞−∞−∞=−==ωωωωωdeeXnTxenTxeXTjnTjnTjnTj)()(:Synthesis)()( :Analysis x(nT) t ω -2π/T 0 2π/ T Tx(t) t ωPeriodic signal, x(t) t -4π/T -2π/T 0 2π/T 4π/T ωTEE 422G Notes: Chapter 10 Instructor: Cheung Page 10-2Signals Fourier Transform Characteristics Continuous in t & Periodic Fourier Series Discrete in ω Continuous in t Continuous-time Fourier Transform Continuous in ω Discrete in t Discrete-time Fourier Transform Continuous in ω & Periodic Discrete in t & Periodic Discrete Fourier Transform Discrete in ω & Periodic Now we introduce the fourth one, the Discrete Fourier Transform (DFT). ∑∑−=−=−−==−==1021021,...,1,0,1)(:Synthesis1,..,1,0,)( :AnalysisNknNkjkNnnNkjkNneXNnTxNkenTxXππ Why DFT? FOR “APPROXIMATING” DTFT OF A FINITE-DURATION SIGNAL In real-life computations, ALL SIGNALS ARE FINITE – the consequence is that you can apply periodic extension to create a periodic discrete-time signal: What is the relation between the DTFT of the finite duration signal x(nT) and the DFT of the periodic extended signal x’(nT)? DFT of x’(nT) are in fact FREQUENCY SAMPLES of the DTFT of x(nT) Finite-duration signal, x(nT) t N=4 Periodic signal, x’(nT) t N=4 Periodic signal, x(nT) t -π2-46π-44π-42π 0 42π44π46π π2 ω N=4EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-3Here is the definition of Discrete Fourier Transform (DFT) again: ∑∑−=−=−−==−==1021021,...,1,0,1)(:Synthesis1,..,1,0,)( :AnalysisNknNkjkNnnNkjkNneXNnTxNkenTxXππ Compared with the analysis formula of the DTFT of a finite-duration x(n): ∑−=−=10)()( NnTjnTjenTxeXωω It is easy to see that Xk equals X(ejωT) evaluated at NkTπω2= Question 1: What does it mean? Recall that X(ejωT) is periodic with period equal to the sampling frequency fs or 2π/T, thus Xk represents the k-th sample when sampling X(ejωT) with N samples per period. For example: if N=6, we have Question 2: Is there any loss in information (do we need something similar to the Nyquist theorem in Frequency domain)? No, as long as the number of samples per period is the same as or larger than the duration of the signal. Why? Xk is also the coefficient for the Discrete-time Fourier series of the periodic signal x’(nT). ω -2π/T 0 2π/ T H(ejωT) X0 X1 X2 X3 X4 X5EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-4Interpretation: Discrete-time Fourier series Recall the continuous-time Fourier Series for a periodic signal x(t) with period NT: ∑∫∞−∞=−==ktNTjkkNTtNTjkkeXtxdtetxNTXππ202~)(:Synthesis)(1~ :Analysis Now, we sample x(t) with sampling period T, the resulting discrete-time sequence x(nT) is also periodic with period = N: Now, we consider the continuous-time surrogate xs(t) of x(nT). ∑∞=−=0)()()(nsnTtnTxtxδ This is also a periodic signal with period NT, so we compute its Fourier Series coefficient by integrating the product of one single period with exp(-j2πk/(NT)): ∑∫∑−=−−=−=−=1020102)(1)()(1NnnNkjNTNntNTkjkenTxNTdtenTtnTxNTXππδ) If we definekkXNTXˆ= , then it coincides with the analysis formula of DFT: ∑−=−=102)( NnnNkjkenTxXπ Periodic signal, x(t) t NTEE 422G Notes: Chapter 10 Instructor: Cheung Page 10-5Plugging it back to the Fourier Series synthesis formula, we have ∑∑∞−∞=∞−∞==⇒=knNkjkktNTkjkseXNnTxeXNtxππ221)(1)( This is almost the same as the synthesis formula for DFT: ∑−=−==1021,...,1,0,1)(NknNkjkNneXNnTxπ Unlike continuous-time Fourier series which needs infinitely many harmonics, the discrete-time needs only N of them. The reason is that the discrete-time exponentials are themselves periodic in N as well: =+=+nNkjnjnNkjnNNkjππππ2exp22exp)(2exp Let’s consider the case when N=4. The real part: ()()()nnjkk4242cosexpRealππ= : 0 k=0: cos(0n) = u(n) n 0 k=1: cos(πn/2) n 0 k=2: cos(πn) n 0 k=3: cos(3πn/2) n 0 k=4: cos(2πn) = u(n) nEE 422G Notes: Chapter 10 Instructor: Cheung Page 10-6The imaginary part : ()()()nnjkk4242sinexpImππ= As you can see, nk42expπhas four distinct sequences before it starts repeating: ( )====nnnnnnnun23exp432exp,exp422exp,2exp42exp),(402expπππππππ DFT Theorem states that ANY periodic sequence x(n) with period = 4 can be written as a linear summation of these four sequences – the coefficients are the DFT of x(n): ( )+++= nXnXnXnuXnx23expexp2exp)()(3210πππ 0 k=0: sin(0n) = u(n) n 0 k=1: sin(πn/2) n k=2: sin(πn) 0 k=3: sin(3πn/2) n k=4: sin(2πn) = u(n) 0 n 0 nEE 422G Notes: Chapter 10 Instructor: Cheung Page 10-7Example: 011)(01111)(011)(41111)(346246146046104323344244144044104222342242142042104121104020=−−+=+++===−+−=+++===+−−=+++===+++==−−−−−=−−−−−−=−−−−−−=−−=−∑∑∑∑jjeeeeenTxXeeeeenTxXjjeeeeenTxXenTxXjjjjNnnjjjjjNnnjjjjjNnnjNnnjππππππππππππππππ Properties of the DFT 1. Linearity: )()()()(kBXkAXnBynAx+↔+ 2. Time Shift: mkNNkmjWkXekXmnx−−=↔− )()()(/2π 3. Frequency Shift: )()(/2mkXenxNmnj−↔π 4. Parseval’s Theorem


View Full Document

UK EE 422G - Chapter 10: Discrete Fourier Transform & Fast Fourier Transform

Documents in this Course
Load more
Download Chapter 10: Discrete Fourier Transform & Fast Fourier Transform
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 10: Discrete Fourier Transform & Fast Fourier Transform and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 10: Discrete Fourier Transform & Fast Fourier Transform 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?