Signal Processing Insights: Fast Fourier Transform and Intelligent Analyses

? Intelligent Signal Processing Test Angelo Ciaramella

Question 9 Question By the Fast Fourier Transform can be obtained a faster product a faster convolution a faster sum ISP Verification tests .

Introduction The Discrete Fourier Transform (DFT) has an important role for signal analysis In the sixties of the last century a fast approach for DFT was introduced by Cooley and Tukey Fast Fourier Transform ISP Verification tests

Classis Decimation in time The source signal x(n) is divided in shorter sequences Decimation in frequency The DFT coefficients X(k) are divided in shorter sequences ISP Verification tests

DFT 1 N Analysis = 0 kn N ( ) 0 1 x n W k N = ( ) X k 0 n altrove 1 1 N N ( ) k = k kn 0 1 X W n N N = ( ) x n 0 0 altrove Synthesis ISP Verification tests Re Im Re Im ( ) ( ) 1 N = n + + kn N kn N kn N kn N ( ) Re ( ) Im ( ) Re ( ) Im ( ) X k x n W x n W j x n W x n W = 0 = 1 , 0 ,..., 1 k N

DFT 1 N Analysis = 0 kn N ( ) 0 1 x n W k N = ( ) X k 0 n altrove 1 1 N N ( ) k = k kn 0 1 X W n N N = ( ) x n 0 0 altrove Synthesis ISP Verification tests Re Im Re Im ( ) ( ) 1 N = n + + kn N kn N kn N kn N ( ) Re ( ) Im ( ) Re ( ) Im ( ) X k x n W x n W j x n W x n W = 0 = 1 , 0 ,..., 1 k N X(k) needs of 4N real products and (4N-1) real sums for ech k. Totally, we have 4N2 real products e N(4N-1) real sums.

Time decimation We use the symmetry and periodicity of the complex exponential 2 j kn = kn N N W e The sequence is a power of two ISP Verification tests = v 2 N

Time decimation X(k) is calculated dividing x(n) in two subsequences 2 N 1 N j kn = n = ( ) ( ) X k x n e 0 ISP Verification tests 2 N 2 N 1 1 N N j kn j kn pari n n even dispari n n odd = + ( ) ( ) ( ) X k x n e x n e

Time decimation n = 2r+1 n = 2r / 2 1 x / 2 1 x N N = 1 x = r ( ) + = + + 2 2 1 rk r k ( ) 2 ( ) 2 ( ) 1 X k r W r W N N r 0 0 / 2 / 2 1 x N N = r = r = + + 2 2 rk k rk 2 ( )( ) 2 ( 1 )( ) r W W r W N N N 0 0 = = 2 2 ( 2 / ) j N W e N = 2 /( ) 2 / j N e W / 2 N ISP Verification tests / 2 1 / 2 1 N N = = = + ) 1 + rk N k rk N ( ) 2 ( x ) 2 ( x X k r W W r W / 2 / 2 N r 0 r 0 = + k ( ) ( ) G k W H k N

Flow graph ISP Verification tests Flow Graph for a DFT with N=8

Flow graph ISP Verification tests Flow Graph for a DFT with N=4

Flow graph ISP Verification tests Flow Graph for a DFT with N=2

FFT algorithm The FFT is obtained by a recursive algorithm based on a divide-et-impera strategy Fourier coefficients ISP Verification tests ? = (? 0 ,? 1 , ,? ? 1 )

FFT algorithm ISP Verification tests

Time complexity The asymptotic time complexity is = + = ( ) 2 ( ) 2 / ( ) ( log ) T N T N N N N It is the same also for the inverse transform ISP Verification tests

Convolution theorem A faster convolution can be obtained ( ) ) b DFT = 1 N DFT DFT * ( ) ( a b a 2 2 2 N N zero padding ISP Verification tests

References Material Slides Video Lessons Books Signal Processing Book (Ciaramella) free download on the e-learning platform Discrete-time signal processing, A. V. Oppenheim, R. W. Schafer, J.R. Buck, Upper Saddle River, N.J., Prentice Hall, 1999, ISBN 0-13-754920-2 Digital Signal Processing, J. Proakis, D. Manolakis, Prentice Hall, 4 edition, 2006 ISP Verification tests