Discrete Fourier Transformation 2.9 2001/12/31 2003/07/24 10:50:43 GMT-5 Phil Schniter schniter@ee.eng.ohio-state.edu Mariyah Poonawala mariyah@rice.edu Prashant Singh prash@ece.rice.edu DFT Dirichlet sinc DTFT FFT This module covers the fundamentals of Discrete-Fourier Transformations.

N-point Discrete Fourier Transform (DFT) X k n 0 N 1 x n 2 n k n k k 0 … N 1 x n 1 N k 0 N 1 X k 2 n k n n n 0 … N 1 Note that: X k is the DTFT evaluated at ω 2 N k k k 0 … N 1 Zero-padding x n to M samples prior to the DFT yields an M-point uniform sampled version of the DTFT: X 2 M k n 0 N 1 x n 2 M k X 2 M k n 0 N 1 x zp n 2 M k X 2 M k X zp k k k 0 … M 1 The N-pt DFT is sufficient to reconstruct the entire DTFT of an N-pt sequence: X ω n 0 N 1 x n ω n X ω n 0 N 1 1 N k 0 N 1 X k 2 N k n ω n X ω k 0 N 1 X k 1 N k 0 N 1 ω 2 N k n X ω k 0 N 1 X k 1 N ω N 2 k 2 ω N 2 k 2 N ω 2 N k N 1 2

Dirichlet sinc, 1 N ω N 2 ω 2

The DFT has a convenient matrix representation. Defining W N 2 N , X 0 X 1 ⋮ X N 1 W N 0 W N 0 W N 0 W N 0 … W N 0 W N 1 W N 2 W N 3 … W N 0 W N 2 W N 4 W N 6 … ⋮ ⋮ ⋮ ⋮ ⋮ x 0 x 1 ⋮ x N 1 where X W x respectively. W has the following properties: W is Vandermonde: the nth column of W is a polynomial in W N n W is symmetric: W W 1 N W is unitary: 1 N W 1 N W H 1 N W H 1 N W I 1 N W W -1 , the IDFT matrix. For N a power of 2, the FFT can be used to compute the DFT using about N 2 2 N rather than N 2 operations. N N 2 2 N N 2 16 32 256 64 192 4096 256 1024 65536 1024 5120 1048576