离散傅单叶变换快速算法为什么研究FFT算法FFT算法的历史沿革解决问题的基本思想
◆ 为什么研究FFT算法 ◆ FFT算法的历史沿革 ◆ 解决问题的基本思想 离散傅里叶变换快速算法
为什么研究FFT算法x(t)X(jo)理论上FTX(ej?)x[k]？方法上x[k]X[m]DFT
x k[ ] j X(e ) x k[ ] X m[ ] 理论上 方法上 FT DFT x t( ) X ( j ) 为什么研究FFT算法
为什么研究FFT算法4点序列2，3，3，2?DFT的计算复杂度N-X[m]-2x[kJW", m=0,],, N-1Wkm=ek=0X[0]= 2W +3W +3W +2W=10复数加法N(N-1)X[1]= 2W +3W +3W+2W = -1- jN2复数乘法X[2] =2W +3W+3W4 +2W = 0随着N的增大，DFT的X[3] = 2W +3W +3W° +2W = -1+ j计算复杂度急剧增加
4点序列{2，3，3，2} DFT的计算复杂度 1 0 [ ] [ ] , 0,1, , 1 − = = = − N km N k X m x k W m N 0 0 0 0 X W W W W [0] 2 3 3 2 10 = + + + = N N N N 0 1 2 3 X W W W W [1] 2 3 3 2 1 j = + + + = − − N N N N 0 2 4 6 X W W W W [2] 2 3 3 2 0 = + + + = N N N N 0 3 6 9 X W W W W [3] 2 3 3 2 1 j = + + + = − + N N N N 复数加法 N(N-1) 复数乘法 N 2 随着N的增大，DFT的 计算复杂度急剧增加。 2π j e km km N WN − = 为什么研究FFT算法
为什么研究FFT算法序列DFT点数N复数乘法复数加法N28645616256240329921024644096403212816384162562566553665280512262144261632102410485761047552204841943044192256N4096167772161677312081926710886467100672
为什么研究FFT算法 序列 DFT 点数N 复数乘法 复数加法 8 16 32 64 128 256 512 1024 2048 4096 8192 64 256 1024 4096 16384 65536 262144 1048576 4194304 16777216 67108864 56 240 992 4032 16256 65280 261632 1047552 4192256 16773120 67100672 复乘次数 N N 2
为什么研究FFT算法DFT在数字信号处理中的重要意义早已被人们所认识，但其得到广泛应用却经历了较长时间，原因就是其计算量太大而难以实用。二十世纪中叶以来，信号处理快速算法研究取得长足进展，其中包括DFT的快速算法，即快速傅里叶变换(FastFourierTransform，简称FFT），FFT是各种DFT快速算法的统称
二十世纪中叶以来，信号处理快速算法研究取得长足进展， 其中包括DFT的快速算法，即快速傅里叶变换（Fast Fourier Transform，简称FFT），FFT是各种DFT快速算法的统称。 DFT在数字信号处理中的重要意义早已被人们所认识，但 其得到广泛应用却经历了较长时间，原因就是其计算量太大而 难以实用。 为什么研究FFT算法