文档介绍：会计学
1
快速傅里叶变换蝶形运算
2
引言
DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。
直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。
FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。
第2页/共53页
3
直接计算DFT的问题及改进的途径
DFT的运算量
设复序列x(n) 长度为N点，其DFT为
k=0，，…，N-1
（1）计算一个X(k) 值的运算量
复数乘法次数：
N
复数加法次数：
N－1
第3页/共53页
4
DFT的运算量
（2）计算全部N个X(k) 值的运算量
复数乘法次数：
N2
复数加法次数：
N(N－1)
（3）对应的实数运算量
第4页/共53页
5
一次复数乘法：
4次实数乘法
2次实数加法
＋
一个X(k) ：
4N次实数乘法
＋
2N+2(N-1)= 2(2N-1)次实数加法
所以
整个N点DFT运算共需要：
N×2(2N-1)= 2N(2N-1)
实数乘法次数：
4 N2
实数加法次数：
第5页/共53页
6
DFT运算量的结论
N点DFT的复数乘法次数举例
N
N2
N
N2
2
4
64
4049
4
16
128
16384
8
64
256
65 536
16
256
512
262 144
32
1028
1024
1 048 576
结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。
第6页/共53页
7
减少运算工作量的途径
主要原理是利用系数的以下特性对DFT进行分解：
（1）对称性
（2）周期性
（3）可约性
另外，
第7页/共53页
8
按时间抽取的基2-FFT算法
算法原理
按时间抽取基-2FFT算法与直接计算DFT运算量的比较
按时间抽取的FFT算法的特点
按时间抽取FFT算法的其它形式流程图
第8页/共53页
9
算法原理
设N＝2L，将x(n)按 n 的奇偶分为两组：
r =0，1，…，
则
第9页/共53页
10
式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。
另外，式中k的取值范围是：0，1， …，N/2－1 。
第10页/共53页