ch3 1基2时间抽取FFT..ppt

ch3_1基2时间抽取FFT.数字信号处理(Digital Signal Processing)
信号与系统系列课程组
国家电工电子教学基地
离散傅里叶变换快速算法(FFT)
问题的提出
解决问题的思路与方法
基2时间抽取FFT算法
基2频率抽取FFT算法
FFT算法的实际应用——
实序列的DFT计算
IDFT的快速计算方法
时间抽取FFT
问题的提出
4点序列{2,3,3,2} DFT的计算复杂度
复数加法
N(N-1)
复数乘法
N 2
如何提高DFT的运算效率?
时间抽取FFT
一般性
DFT:
直接计算的计算量:
复数乘法
N
对N个不同X[m]:
复数加法
N(N-1)
复数乘法
N2
对一固定的m:
复数加法 N-1
如计算1024点DFT:
复数乘法次数: N2 =10242 = 220 = 1048576
时间抽取FFT
解决问题的思路
1. 将长序列DFT分解为短序列的DFT
2. 利用旋转因子的周期性、对称性、可约性。
时间抽取FFT
(1)周期性(periodicity)
(2)plex conjugate)
(3)当N是偶数时
旋转因子的性质
时间抽取FFT
解决问题的方法
将时域序列逐次分解为一组子序列,利用旋转因子的特性,由子序列的DFT来实现整个序列的DFT。
基2时间抽取(Decimation in time)FFT算法
基2频率抽取(Decimation in frequency)FFT算法
时间抽取FFT
基2时间抽取FFT算法推导
基2时间抽取FFT算法流图
基2时间抽取FFT算法的计算复杂度
基2时间抽取FFT算法流图规律
基2时域抽取FFT算法
时间抽取FFT
基2时间抽取FFT算法推导
算法推导: N=2M时域抽取(时域按奇偶分组)
时间抽取FFT
因此有:
由于X1[m] 和X2[m]隐含有周期性,可得
可见X1[m]是x[k]偶分量的DFT,X2[m]是x[k]奇分量的DFT.