W
0 N
运算即可求出
所有8点X(k)的
W
1 N
值。
W
2 N
W
3 N
分解一次后所需的运算量＝2个N/2的DFT＋N/2蝶形
-
14
运算量比较
N点DFT的运算量
每次蝶形含一次复数
复数乘法次数： N2
乘和两次复数加
复数加法次数： N(N－1)
分解一次后所需的运算量＝2个N/2的DFT＋ N/2蝶形：
复数乘法次数： 2*(N/2)2+N/2=N2/2+N/2
-
3
4.2 直接计算DFT的问题及改进的途径
DFT的运算量 设复序列x(n) 长度为N点，其DFT为
N1
X(k) x(n)WNnk n0
k=0，，…，N-1
（1）计算一个X(k) 值的运算量
复数乘法次数： N
复数加法次数： N－1
（2）计算全部N个X(k) 值的运算量
复数乘法次数： N2
复数加法次数： N(N－1)
-
5
4.2.2 减少运算工作量的途径
主要原理是利用系数
W
nk N
的以下特性对DFT进行分解：
（1）周期性 W N (nN)kW N n(kN)W N nk
（2）对称性
(WNnk )
W nk N
W k(N n) N
（3）可约性
Wmnk mN
WNnk
WNnk WNnk/m/m
另外，
WNN/2 1
W(kN/2) N
复数加法次数： 2*(N/2)(N/2－1)+2*N/2=N2/2
通过一次分解后，运算工作量减少了差不多一半。
-
15
进一步按奇偶分解
由于N＝2M，因而N/2仍是偶数 ，可以进一步把每个N/2点 子序列再按其奇偶部分分解为两个N/4点的子序列。
以N/2点序列x1(r)为例 则有
x1x(12(l2 l)1 )x3x(4l()l)
N1
N1
2
2
x(2r)W N 2rk x(2r1)W N (2r1)k
r0
r0
N1
N1
2
2
x1(r)WN rkWNk x2(r)WN rk X1(k)W N kX2(k)
r0
2
r0
2
式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。
另外，式中k的取值范围是：0，1， …，N/2－1 。
学习目的
理论上理解FFT算法 自己能编写FFT算法
-
1
本章目录
直接计算DFT的问题及改进的途径 按时间抽取的基2-FFT算法 按频率抽取的基2-FFT算法 快速傅里叶逆变换(IFFT)算法 Matlab实现
-
2
4.1 引言
DFT在实际应用中很重要: 可以计算信号的频谱、功率 谱和线性卷积等。
10
由前半部分X(k)
X(k)X 1(k)W N kX 2(k)
k=0，1， …，N/2－1
因此可得后半部分X(k)
X (k N 2) X 1 (k N 2) W N k N 2 X 2 (k N 2)
X1(k)W N kX2(k)
W(N2k) N
WNk
k=0，1， …，N/2－1
-
11
结论：
N 21
x(2r)x1(r)
r =0，1，…，N 1
2
x(2r1)x2(r)
则
N1
X(k)D FT[x(n)] x(n)W N nk
n0
N1
N1
x(n)WNnk x(n)WNnk
n0 n为偶数
n0 n为奇数
-
8
N1
N1
X(k) x(n)W N nk x(n)W N nk
n0 n为 偶 数
n0 n为 奇 数
-
9
因此，X(k)X 1(k)W N kX 2(k)只能计算出X(k)的前一半值。
后一半X(k) 值， N/2 ， N/2 ＋1， …，N-1 ？
N
X1( 2
k)
N 21
x1(r)WNr(2N 2k)
r0
同理可得
N 21
x1(r)WNrk2 X 1 (k )
r 0
X2(N2 k)X2(k)
-
直接按DFT变换进行计算，当序列长度N很大时，计算
量非常大，所需时间会很长,实时处理难以实现。 1965年，图基和库利发表了《机器计算快速傅立叶级
数的一种算法》论文后，很快形成了快速计算DFT的计 算机算法FFT。（Fast Fourier Transform) FFT并不是一种与DFT不同的变换，而是DFT的一种快速 计算的算法。
-
12
新概念：蝶形运算
X(k)X 1(k)W N kX 2(k)
X(kN 2)X1(k)W N kX2(k)
蝶形运算 信号流图符号
X1(k) X2(k)
蝶形运算式
蝶形运算的运算量：每次蝶形含一次复数乘和两
次复数加
-
13
以8点为例第一次按奇偶分解
以N=8为例，
分解为2个4点
的DFT，然后
做8/2=4次蝶形
X1(k) x1(r)WNrk2 r0
因此，只要 求出2个N/2 点的DFT，即
N 21
X2(k) x2(r)WNrk2 r0
X1(k)和X2(k)，
再经过这种
运算就可求
X (k)X 1(k) W N kX 2(k)
出全部X(k)
的值
X(kN 2)X1(k)W N kX2(k)
k=0，1， …，N/2－1
WNk
-
6
4.3 按时间抽取的基2-FFT算法
算法原理
DIT-FFT(Decimation-In-Time)
按时间抽取基-2FFT算法与直接计算 DFT运算量的比较
按时间抽取的FFT算法的特点
按时间抽取FFT算法的其它形式流程图
-
7
4.3.1 算法原理
设N＝2M，将x(n)按 n 的奇偶分为两组：
-
4
DFT运算量的结论
N点DFT的复数乘法次数举例
N
N2
N
N2
2
4
64
4049
4
16
128
1536
16
256
512
262 144
32
1024
1024
1 048 576
结论：当N很大时，其运算量很大，对实时性很强的信号 处理来说，要求计算速度快，因此需要改进DFT的计算 方法，以大大减少运算次数。
l0,1, ,N1 4
N 21
X1(k)
r0
x1(r)WNrk2N4 1 x1(2l)W N 2l2kN4 1 x1(2l1)W N (22 l 1)k
l0
l0
N41
N41
x3(l)W N lk4W N k2 x4(l)W N lk4
l0
l0
X3(k)W N k/2X4(k) k=0,1,…, N 1
4
-
16
且
X1N 4kX3(k)W N k/2X4(k)
k=0,1,…,
N 4
1
由此可见，一个N/2点DFT可分解成两个N/4点DFT。 同理，也可对x2(n)进行同样的分解，求出X2(k)。
-
17
以8点为例第二次按奇偶分解