EE 422G Notes Chapter 10 Instructor Zhang Chapter 10 The Discrete Fourier Transform and Fast Fourier Transform Algorithms 10 1 Introduction 1 x t Continuous time signal X f Fourier Transform frequency characteristics Can we find X f x t e j 2 ft dt if we don t have a mathematical equation for x t No 2 What can we do 1 Sample x t x0 x1 xN 1 over T for example 1000 seconds Sampling period interval t N samples over T t T N Can we have infinite T and N Impossible 2 Discrete Fourier Transform DFT N 1 j 2 kn N X k x n e k 1 2 N n 0 for the line spectrum at frequency k 2 3 Limited N and T limited frequency resolution 2 k T 1 T limited frequency band from to in Fourier transform to 0 2 N T 1 N 1 j 2 kn N 4 xn N X k e periodic function period N k 0 x t general function sampling and inverse transform xn periodic function 5 X k k 2 N 1 k T X k xn e n 0 line spectrum j 2 kn N period function period N Page 10 1 EE 422G Notes Chapter 10 Instructor Zhang 10 2 Error Sources in the DFT 1 Preparations 1 Ideal sampling waveform y s t t m mTs y s t f s f nf s n fs 1 Ts Fourier Transform Pair in DFT Ts t T N 2 Rectangular Pulse window t t0 T sin c Tf e T width of the window when t0 0 Center of the window j 2 t 0 f sin x x sin Tf sin c Tf Tf sin cX t T sin c Tf T 3 x1 t x2 t X 1 f X 2 f 4 x1 t x2 t X 1 f X 2 f 2 Illustration of Error Sources Example 10 1 Continuous time signal two sided exponential signal x t e t Its Fourier transform Page 10 2 EE 422G Notes Chapter 10 1 If we Instructor Zhang 2 X f 1 2 f 2 sample x t in not lim ited as in with sampling frequency fs DFT t sampled signal x t y t e s s its Fourier transform X s f Ys f F e X s f fs t Ys f X f X f nf s 2 f s n 1 1 2 f nf n s 2 sampling 1 possible overlapping if f s 2 f h is not held 2 periodic function introduce frequencies beyond fs 2 Limited T over which x t is sampled to collect data for DFT window t T t x sw t x s t T X sw f 2 f s 1 2 f nf s 2 1 T sin c Tf n Fourier transform given by sampled data in limited window T X sw f is a worse estimate of X f than Xs f due to the introduction of Tsinc Tf for convolution Effect of limited T X f 3 Dose DFT give s for every f No only discrete frequencies DFT as an estimate for X f even worse than X s f due to the limited frequency resolution Page 10 3 EE 422G Notes Chapter 10 Instructor Zhang 3 Effect of sampling frequency or number of points on accuracy when T is given Example use t 4 t for e 4 Effect of T window size Compare t 4 and t 8 for e t Page 10 4 EE 422G Notes Chapter 10 Instructor Zhang Page 10 5 EE 422G Notes Chapter 10 Instructor Zhang 5 DFT Errors 1 Aliasing X s f fs X f n superposition of the analog signal spectrum X f and its translates X f nfs n 0 nf s Caused by sampling Overlapping of X f and its translates aliasing sampling effect 2 Leakage Effect limited window size T t X s f X s f F T t T t f F T worse than Xs f as approximation of X f X s f contribution of X s f f to X s f determined by weight f frequency energy leaks from one frequency to another 3 Picket Fence Effect As an estimation of X f does X s f have picket fence effect No DFT discrete frequencies not blocked by the fence 6 Minimization of DFT Error Effects Major ways increase T and fs Problem DFT for large N 10 3 Examples Illustrating the computation of the DFT Preparation for Mathematical Derivation of FFT Page 10 6 EE 422G Notes Chapter 10 Instructor Zhang 1 DFT Algorithm N 1 X k x n e N 1 n 0 Denote WN e n 0 j 2 N x n e j 2 N j 2 kn N nk then N 1 X k x n WN nk n 0 Properties of WN m 1 WN 0 e j 2 N 0 e0 1 N m m W N 2 W N WN N m e e j 2 N N m j 2 N N e 1 e WN N e j 2 1 j 2 N m WN m j 2 N m 3 WN N 2 e j 2 N 2 N e j 1 WN N 4 e j 2 N 4 N e j 2 j WN 3N 4 e j 2 3 N 4 N e j 3 2 j 2 Examples Example 10 3 Two Point DFT 1 nk x 0 x 1 X k x n W2 k 0 1 n 0 1 1 n 0 n 0 X 0 x n W2 n 0 x n x 0 x 1 1 X 1 x n W2 n 0 n1 1 x n W2 n 0 0 x 0 W2 x 1 W2 x 0 x 1 W2 n 1 1 2 2 x 0 x 1 1 x 0 x 1 Example 10 4 Generalization of derivation in example 10 3 to a four point DFT x 0 x 1 x 2 x 3 3 X k x n W4 nk k 0 1 2 3 n 0 Page 10 7 EE 422G Notes Chapter 10 Instructor Zhang 3 3 n 0 n 0 X 0 x n W4 n 0 x n x 0 x 1 x 2 x 3 3 X 1 x n W4 x 0 W4 x 1 W4 x 2 W4 x 3 W4 n 0 1 2 3 n 0 x 0 jx 1 x 2 jx 3 3 X 2 x n W4 2n 0 2 4 6 6 9 x 0 W4 x 1 W4 x 2 W4 x 3 W4 n 0 x 0 x 1 1 x 2 1 x 3 W4 2 x 0 x 1 x 2 x 3 3 X 3 x n W4 3n 0 3 x 0 W4 x 1 W4 x 2 W4 x 3 W4 n 0 3 2 x 0 x 1 W4 x 2 1 W4 x …