文档介绍：2017/7/16
信息与通信工程学院
1
第四章快速傅立叶变换
FFT-Fast Fourier Transform
§ 引言
§ 按时间抽取的基-2 FFT算法
§ 按频率抽取的基-2 FFT算法
§ 离散傅立叶反变换的快速计算方法- IFFT
本章主要内容:
2017/7/16
2
§ 引言
FFT不是新的变换形式,只是DFT的一种快速算法,且根据对序列分解与选取方法的不同而产生了FFT的多种算法,应用很广。
一 DFT直接计算存在的问题
设x(n)为N点有限长序列,正反变换计算量相同
例N=4:
信息与通信工程学院
2017/7/16
3
例N=4:
N点DFT的直接计算量
1. 乘法次数:
对每一个k:N次复数乘法【4N次实乘和2N次实加】
N个k: 次复数乘法
信息与通信工程学院
2017/7/16
4
加法次数:
对每一个k: N-1次复加【2(N-1)次实加】
N个k: N(N-1)次复加
即和成正比。
例N=1024,则有1048576次复乘(约400万次实乘),假定运算器的指令速度为100MIPS,则计算时间大约为4秒。
信息与通信工程学院
2017/7/16
5
旋转因子的对称性和周期性
例 N=4,旋转因子W的矩阵形式为:
二、改进途径
信息与通信工程学院
2017/7/16
6
旋转因子W的性质:
对称性:
周期性:
得:
可约性:
信息与通信工程学院
2017/7/16
7
如前所述,N点DFT的复乘次数与N的平方成比例,显然N较小时乘法次数大大减少。利用上述旋转因子的特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度。
1965年,库利(cooley)和图基(Tukey)首先提出FFT算法。对于N点DFT,仅需(N/2)log2N 次复数乘法运算。
例如N=1024=210时,需要
(1024/2)log2210=512*10=5120 次复乘运算,
5120/1048576=% ,速度提高20倍。
分解有时域抽取(DIT)和频域抽取(DIF)两大类。
改进方法概述
信息与通信工程学院
2017/7/16
8
§ 按时间抽取的基-2 FFT算法(Decimation In Time FFT)
仍以 N=4为例
A
B
A
B
C
D
C
D
运算流图
A
-1
C
-1
B
D
-1
-1
信息与通信工程学院
2017/7/16
9
一算法原理
先将x(n)按n的奇偶分为两组作DFT,设N=2L (L大于等于2),不足时,可补些零,这样一个N点的DFT分解为两个N/2点的DFT。
(一) N/2点DFT
信息与通信工程学院
2017/7/16
10
DIT-FFT分解说明:
上式中
E(k)和F(k)均为N/2点的DFT;
因W 是以N为周期,故X(k)是以N为周期;
X(k)=E(k)+W F(k)只能确定出X(k)的k= 个值,即前一半的结果。
k
N
k
N
信息与通信工程学院