发布时间 : 星期三 文章第四章快速傅里叶变换更新完毕开始阅读
第四章 快速傅里叶变换
教学目的要求
? 快速傅里叶变换（FFT）； ? 按时间抽取的FFT（DIT-FFT）； ? 按频率抽取的FFT（DIF-FFT）； ? 离散傅里叶反变换的快速算法(IFFT)； ? 快速傅里叶变换的应用。
教学重点和难点
重点：DIT-FFT和DIF-FFT的原理，快速傅里叶变换的应用。 难点：DIT-FFT和DIF-FFT的原理。
4.1 引言 1、重要性
DFT和卷积信号处理中两个最基本也是常用的运算，它们涉及到信号与系统的分析与综合。
2、DFT计算量估算
N?1?nk?X(k)??x(n)WN,?n?0?N?1?nk?x(n)?1X(k)WN,??Nk?0?k?0,1,...N?1定义：
n?0,1,...,N?1
（1）计算X(k)，假定x(n)为复数
●计算每个X(k)，需要N次复数乘法，N-1次复数加法。
●对所有N个X(k)值，共需N2次复数乘法和N(N?1)次复数加法，实现一次复数乘法需要4次实数乘2次实数相加，实现一次复数相加需要2次实数相加
4-1
.
例如：若N=1024，则需要1048576次复数乘法，即4194304次实数乘法，所需时间过长，难于“实时“实现。对于2?D图象处理，所需计算量更是大 得惊人。
●计算IDFT的x(n)，也是同样的道理
3、为什么可以大量减小DFT的计算量，WN因子有如下所述的周期性及对称性
? （1） WNnk的对称性： (WNnk)*?WNnk
k(?nk)N （2）周期性： WNnk?W(N?n （3）可约性： W结论：（1）W?1,W0N2nkN)N?WNnkm
?WnmkmN?WN
m??1；
N2?r （2）WNN?r?WNr;WN??WN或WNr?m?WNN?m或[WNN?m*]?WNm
例如：对四点DFT，按公式计算需要42?16次复数乘按上述周期及对称性 写成如下矩阵形式：
1w1?X(0)??1???X(1)1??? ??X(2)??1???X(3)???11?11?11?1?w1??x(0)??1???wx(1)??? ?1??x(2)??1??w??x(3)?将上式矩阵的第二、三列交换得：
?X(0)??1???X(1)1?????X(2)??1???X(3)???11?1111w1?1?w11??x(0)??1???wx(2)??? ?1??x(1)??1??w??x(3)?由此可得
X(0)?[x(0)?x(2)]?[x(1)?x(3)] X(1)?[x(0)?x(2)]?[x(1)?x(3)]w1 X(2)?x[(0?)x
?x[(0?)x X(3)(?2)x](?2)x][?x(1 )[?x(1) w(3)]1从上可知，求出四点DFT实际只需要一次复数乘法，问题的关键是如何巧妙地运用w因子的周期性及对称性，导出一个高效的快速算法。上面算法最早
4-2
.
由J.W.Cooley和J.W.Tukey于1965年提出。
上面FFT使N点DFT的乘法计算量由N2降到
N2log2N次，例如N=1024，计
算量降为5120次，仅为原来的4.88%，因此这一发现是数字信号处理发展史上
的里程碑,在此算法之后，新的算法不断涌现，显示人们极大的兴趣。
总结FFT发展有两个方向：
? 一个是针对N等于2的整数次幂的算法，如基2，基4，实因子和分裂
基算法。
? 另一个上N不等于2的整数次幂的算法，以Winograd为代表。
4.2 基2FFT算法
1、时域抽取法基2FFT基本原理
（1）旋转因子WNm具有明显的周期性和对称性 周期： WNm?N?WNm
对称性：W?mN?WN?mN,WNm?N2??WN,[WNmN?m*]?WN
m（2）分类：时域抽取法FFT(Decimation-In-Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation-In-Frequency FFT,简称DIF-FFT) （3）DIT-FFT基本原理
设序列x(n)的长度为N，且满足N?2M（基2），M为自然数，可将x(n)按奇、偶分成两组，即令n?2r及n?2r?1，r?0,1,2,...,N2?1
N2?1
子序列：x1(r)?x(2r),x2(r)?x(2r?1),r?0,1,2,...,●第一次分解：将x(n)的DFT进行第一次分解
N/2?1N2rkN?/21(r2?k1) X(k)??r?0x(2r)W??r?0kNx(2r?1)WN
N/2?1N/2?1??r?0x1(r)W2krrkN/2?W?r?0x2(r)WN/2rk
W2krN?e?j2?N?e?j2?N/2kr?WN/2
2kr WN(2r?1)k?WNk?WNkr/2
4-3 .
因此 X(k)?X1(k)?WNkX2(k),(k?0,1,...,N?1) 其中，X1(k)，X2(k)分别为x1(r)和x2(r)的N/2点DFT，即
N/2?1 X1(k)??r?0N/2?1x1r(W)N?DFTx[1r( )]2rk X2(k)?那么
?r?0x2(r)WN?DFT[x2(r)]
2rk X(k)?X1(k)?WNkX2(k), X(k?
定义蝶形运算符号
A(k?0,1,...,N2?1)N2
?1)N2)?X1(k)?WNX2(k),k(k?0,1,...,
A＋ BCBCA－ BC 图1
由图1可见，完成一次蝶形运算，需要一次复数乘法和两次复数加法运算
N点DFT的一次时域抽取分解图如下（N=8）
x(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)N/2点N/2点X1(0)X1(1)X1(2)DFTX1(3)X2(0)X2(1)X2(2)DFTX2(3)X(0)X(1)X(2)X(3)WW0N1NX(4)X(5)X(6)X(7)WW2N3N
图2 N点DFT的一次时域抽取分解图（N=8）
4-4
.