李洁《数字信号处理》20058 数字信号处理 Digital Signal processing 第四章快速 Fourier变换(FFT 主讲教师:李洁 形影x去 首先,FFT并不是一种新的 Fourier变换,只是DFT的一种快速算法 X(k)=DFx(m=2∑xmHk=01…,N-1,we 直接计算D由W如的周期性和对 称性,会使计算过程出现许多冗余 直接计算DFT总共需要N次 复数乘法和N(N-1)次复数o 加法! FTRadix-2 FT∝N FFT o Nlog2N 1281638448 102410485765120 李洁一《数字信号处理 2|30 Digital Signal processing Jie Li 2005李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 1 数字信号处理 第四章 快速Fourier变换(FFT) Digital Signal Processing 主讲教师：李洁 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 2 / 30 0 500 1000 1500 2000 0 10 20 30 40 Number of samples, N Number of Operations DFT ∝ N2 FFT ∝ N log2N 直接计算DFT DFT 由于WN kn 的周期性和对 称性，会使计算过程出现许多冗余 直接计算DFT总共需要N2次 复数乘法和N（N-1）次复数 加法！ VERY BAD VERY BAD ! 首先，FFT并不是一种新的Fourier变换，只是DFT的一种快速算法。 ( ) [ ( )] ( ) 0,1, , 1 1 0 = = ∑ = − − = X k DFT x n x n W k N N n kn N L W8 0 W8 4 W8 2 W8 5 W8 6 W8 3 W8 7 W8 1 1024 1048576 5120 128 16384 448 32 1024 80 4 16 4 N DFT Radix-2