文档介绍：第五章
快速傅里叶变换
4
5
2
本章目录
■直接计算DFT的问题及改进的途径 ■按时间抽取的基2-FFT算法 ■按频率挾取的基2-FFT算法 ■快速傅里叶逆变换(IFFT)算法 ■ Matlab 实现
4
3
2
5J引言
■ DFT在实际应用中很重要:可以计算信号的频
谱、功率谱和线性卷积等。
■直接按DFT变换进行计算，当序列长度汕艮
大时，计算量非常大，所需时间会很长。
■ FFT并不是一种与DFT不同的变换，而是
4
5
2
DFT的一种快速计算的算法。
4
5
2
竺亘斟算DFT的问题及改进的途径
DFT的运算量
#
#
#
8
7
#
设复序列MG)长度为N点，其DFT为
N—1
X(Q = 2>(曲
n=0
k=0,,…，AM
(1)计算一个X(k)值的运算量
复数乘法次数：N
8
7
#
复数加法次数：NT
8
9
#
DFT的运算量
(2)计算全部N个X(k)值的运算量
复数乘法次数：/V2
复数加法次数：N(N—1)
(3)对应的实数运算量
N—l N7
X 伙)=工兀(〃)比篇=[Re x(n) + jlmx(n)]\RcW^k + jImW^k]
n=0 n=0
10
7
#
N-l
= ^{[Rex(n)・ReW^k — Imx(n)・ImW^k]
w=0
+y[Re x(n)・ Im W^k + Im x(n)・ Re ]}
#
11
#
一次复数乘法：4次实数乘法
+ 2次实数加法
一个X(k):
4N次实数乘法+
2A/+2(AM)= 2(2 AM)次实数加法
所以整个N点DFT运算共需要：
实数乘法次数：4/V2
实数加法次数：NX2(2AM)=2N(2AM)
12
11
#
*2!!^算量的结论
N点DFT的复数乘法次数举例
N
N2
2
4
4
16
8
64
16
256
32
1028
N
N2
64
4049
128
16384
256
65 536
512
262 144
1024
1 048 576
结论：当M艮大时，其运算量很大，对实时性很强的信号 处理来说，要求计算速度快，因此需要改进DFT的计算 方法，以大大减少运算次数。