Discrete Fourier Transform DFT Recall the DTFT X X x n e j n 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 at N points n 0 0 y n 0 n N 1 x n 0 n N where y n are the measurements taken at N points EE 524 Fall 2004 5 1 Sample the spectrum X in frequency so that X k X k X k N 1 X j2 kn N x n e 2 N DFT n 0 The inverse DFT is given by N 1 kn 1 X x n X k ej2 N N k 0 1 x n N N 1 X N 1 X k 0 m 0 N 1 X x m m 0 EE 524 Fall 2004 5 j2 km N x m e 1 N N 1 X j2 e j2 kn N e k m n N x n k 0 z m n 2 The DFT pair X k N 1 X kn x n e j2 N analysis n 0 x n N 1 1 X j2 kn X k e N N synthesis k 0 Alternative formulation X k N 1 X x n W kn 2 W e j N n 0 x n N 1 1 X X k W kn N k 0 EE 524 Fall 2004 5 3 EE 524 Fall 2004 5 4 Periodicity of DFT Spectrum X k N N 1 X j2 x n e k N n N n 0 N 1 X j2 kn N x n e e j2 n n 0 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 period 2 Example DFT of a rectangular pulse x n X k 1 0 n N 1 0 otherwise N 1 X kn e j2 N N k n 0 the rectangular pulse is interpreted by the DFT as a spectral line at frequency 0 EE 524 Fall 2004 5 5 DFT and DTFT of a rectangular pulse N 5 EE 524 Fall 2004 5 6 Zero Padding What happens with the DFT of this rectangular pulse if we increase 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 is Y k N 1 X j2 kn N y n e M 1 X n 0 EE 524 Fall 2004 5 sin kM N sin Nk j2 kn N y n e n 0 j e k M 1 N 7 DFT and DTFT of a Rectangular Pulse with Zero Padding N 10 M 5 Remarks Zero padding of analyzed sequence approximating its DTFT better results in Zero padding cannot improve the resolution of spectral components because the resolution is proportional to 1 M rather than 1 N Zero padding is very important for fast DFT implementation FFT EE 524 Fall 2004 5 8 Matrix Formulation of DFT Introduce the N 1 vectors x 0 x 1 x x N 1 X 0 X 1 X X N 1 and the N N matrix W 0 0 0 W W W W0 W1 W2 W0 W2 W4 W 0 W N 1 W 2 N 1 0 W W N 1 W 2 N 1 N 1 2 W DFT in a matrix form X Wx Result Inverse DFT is given by x EE 524 Fall 2004 5 1 H W X N 9 which follows easily by checking W H W WW H N I where I denotes the identity matrix Hermitian transpose xH xT x 1 x 2 x N Also denotes complex conjugation Frequency Interval Resolution DFT s frequency resolution Fres 1 NT Hz and covered frequency interval F N Fres 1 Fs T Hz Frequency resolution is determined only by the length of the observation interval whereas the frequency interval is determined 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 10 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 frequencies F1 10 Hz and F2 12 Hz sampled with the sampling interval T 0 02 seconds Consider various data lengths N 10 15 30 100 with zero padding to 512 points DFT with N 10 and zero padding to 512 points Not resolved F2 F1 2 Hz 1 N T 5 Hz EE 524 Fall 2004 5 11 DFT with N 15 and zero padding to 512 points Not resolved F2 F1 2 Hz 1 N T 3 3 Hz DFT with N 30 and zero padding to 512 points Resolved F2 F1 2 Hz 1 N T 1 7 Hz EE 524 Fall 2004 5 12 DFT with N 100 and zero padding to 512 points Resolved F2 F1 2 Hz 1 N T 0 5 Hz EE 524 Fall 2004 5 13 DFT Interpretation Using Discrete Fourier Series Construct a periodic sequence by periodic repetition of x n every N samples e x n x 0 x N 1 x 0 x N 1 z z x n x n The discrete version of the Fourier Series can be written as x e n X j2 kn N Xk e k 1 X e 1 X e j2 kn X k e N X k W kn N N k k e where X k N Xk Note that for integer values of m we have W kn j2 kn N e j2 e k mN n N W k mN n As a result the summation in the Discrete Fourier Series DFS should contain only N terms N 1 1 X e j2 kn x e n X k e N N DFS k 0 EE 524 Fall 2004 5 14 Inverse DFS The DFS coefficients are given by e X k N 1 X kn x e n e j2 N inverse DFS n 0 Proof N 1 X j2 kn N x e n e n 0 N 1 N 1 X 1 X e j2 pn j2 kn N N X p e e N n 0 p 0 N 1 X e X p p 0 1 N N 1 X j2 e p k n N e X k n 0 z p k 2 The DFS coefficients are given by e X k N 1 X kn x e n e j2 N analysis n 0 x e n N 1 1 X e j2 kn X k e N N synthesis k 0 EE 524 Fall 2004 5 15 DFS and DFT pairs are identical except that DFT is applied to …