第五章 快速傅里叶变换
第五章 快速傅里叶变换
本章目录 直接计算DFT的问题及改进的途径 ■按时间抽取的基2-FT算法 按频率抽取的基2FFT算法 a快速傅里叶逆变换(FFT算法 Matlab实现
2 本章目录 ◼ 直接计算DFT的问题及改进的途径 ◼ 按时间抽取的基2-FFT算法 ◼ 按频率抽取的基2-FFT算法 ◼ 快速傅里叶逆变换(IFFT)算法 ◼ Matlab实现
51引言 DFT在实际应用中很重要:可以计算信号的频 谱、功率谱和线性卷积等。 ■直接按DFT变换进行计算,当序列长度N很 大时,计算量非常大,所需时间会很长。 ■FFT并不是一种与DFT不同的变换,而是 DFT的一种快速计算的算法
3 5.1 引言 ◼ DFT在实际应用中很重要: 可以计算信号的频 谱、功率谱和线性卷积等。 ◼ 直接按DFT变换进行计算，当序列长度N很 大时，计算量非常大，所需时间会很长。 ◼ FFT并不是一种与DFT不同的变换，而是 DFT的一种快速计算的算法
52直接计算DFT的问题及改进的途径 DFT的运算量 设复序列x(m)长度为N点,其DFT为 X(k)=∑x(mWkc=0,,,N1 n=0 (1)计算一个X(k)值的运算量 复数乘法次数:N 复数加法次数:N一1
4 5.2 直接计算DFT的问题及改进的途径 ◼ DFT的运算量 设复序列x(n) 长度为N点，其DFT为 1 0 ( ) ( ) N nk N n X k x n W − = = k=0，，…，N-1 （1）计算一个X(k) 值的运算量 复数乘法次数： N 复数加法次数： N－1
521DFT的运算量 (2)计算全部N个Ⅺ(k)值的运算量 复数乘法次数:N2 复数加法次数:NN1) (3)对应的实数运算量 N-1 X(k)=∑x(m形X=∑[Rex(m)+jmx(m)ReW+jmW] x(n)wN n=0 2IRex(n).ReWN-Imx(n) Im W] +j[Rex(n). ImWN +Imx(n). ReWI
5 5.2.1 DFT的运算量 （2）计算全部N个X(k) 值的运算量 复数乘法次数： N2 复数加法次数： N(N－1) （3）对应的实数运算量 1 1 0 0 ( ) ( ) [Re ( ) Im ( )][Re Im ] N N nk nk nk N N N n n X k x n W x n j x n W j W − − = = = = + + 1 0 {[Re ( ) Re Im ( ) Im ] N nk nk N N n x n W x n W − = = − [Re ( ) Im Im ( ) Re ]} nk nk N N + + j x n W x n W