第 4章 快速傅立叶变换
? 问题的提出
? 解决问题的思路与方法
? 基 2时间抽取 FFT算法
? 基 2时间抽取 FFT算法的计算复杂度
? 基 2时间抽取 FFT算法流图规律
? 基 2频率抽取 FFT算法
? FFT算法的实际应用
问题的提出
4点序列 {2,3,3,2} DFT的计算复杂度
1,1,0,][][
1
0
??? ?
?
?
NmWkxmX kmN
N
k
?
102332]0[ 0000 ????? NNNN WWWWX
jWWWWX NNNN ??????? 12332]1[ 3210
02332]2[ 6420 ????? NNNN WWWWX
jWWWWX NNNN ??????? 12332]3[ 9630
复数加法 N(N-1) 复数乘法 N 2
如
何
提
高DFT
的
运
算
效
率?
解决问题的思路
1,将长序列 DFT分解为短序列的 DFT
2,利用旋转因子 的周期性、对称性、可约性。km
NW
旋转因子 的性质km
NW
kmNNmkNmNkN WWW ?? ?? )()(
1)周期性
2) 对称性
? ? mkNkmN WW ?? ?
3)可约性
mk
N
Nmk
N WW ??
? 2
n m knNmkN WW ?
为整数nNWW nmk nNmkN /,//?
解决问题的方法
将时域序列逐次分解为一组子序列，利用旋转因子
的特性，由子序列的 DFT来实现整个序列的 DFT。
基 2时间抽取 (Decimation in time)FFT算法
12,1,0]12[ ]2[][ ??
??
?
??
Nr
rx
rxkx ?
基 2频率抽取 (Decimation in frequency)FFT算法
?
?
?
?? ]12[
]2[][
mX
mXmX
基 2时间抽取 FFT算法流图
N=2 x[k]={x[0],x[1]}
]1[]0[]0[ 02 xWxX ??
]1[]0[]1[ 12 xWxX ??
]0[x
]1[x
]0[X
-1
0
2W ]1[X
]1[]0[ 02 xWx ??
4点基 2时间抽取 FFT算法流图
x[0]
x[2]
x[1]
x[3]
X1[0]
X1[1]
X2[0]
X2[1]
2点 DFT
2点 DFT ?1
?1
?1
?1
04W
14W
02W
02W
X [0]
X [1]
X [2]
X [3]
1,0],[][][ 241 ??? mmXWmXmX m
1,0],[][]2[ 241 ???? mmXWmXmX m
4点基 2时间抽取 FFT算法流图
x [ 0 ]
x [ 2 ]
x [ 1 ]
x [ 3 ]
? 1
? 1
? 1
? 1
X [ 0 ]
X [ 2 ]
X [ 1 ]
X [ 3 ]
X
1
[ 0 ]
X
2
[ 0 ]
X
1
[ 1 ]
X
2
[ 1 ]
0
4W 14W
0
4W 0
4W
8点基 2时间抽取 FFT算法流图
4点 DFT
4点 DFT
x[0]
x[2]
x[4]
x[6]
x[1]
x[3]
x[5]
x[7]
X1[0]
X1[1]
X1[2]
X1[3]
X2[0]
X2[1]
X2[2]
X2[3]
X [0]
X [1]
X [2]
X [3]
X [4]
X [5]
X [6]
X [7]
?1
?1
?1
?1
08W
18W
28W
38W
3,2,1,0],[][]4[ 281 ???? mmXWmXmX m
3,2,1,0],[][][ 281 ??? mmXWmXmX m
4点 DFT
4点 DFT
x[0]
x[2]
x[4]
x[6]
x[1]
x[3]
x[5]
x[7]
X1[0]
X1[1]
X1[2]
X1[3]
X2[0]
X2[1]
X2[2]
X2[3]
X [0]
X [1]
X [2]
X [3]
X [4]
X [5]
X [6]
X [7]
?1
?1
?1
?1
08W
18W
28W
38W
2 点 D F T
2 点 D F T
x [ 0 ]
x [ 4 ]
x [ 2 ]
x [ 6 ]
? 1
14WX 1 1 [ 0 ]
X
1 1
[ 1 ]
X
1 2
[ 0 ]
X
1 2
[ 1 ]
04
2 点 D F T
2 点 D F T
? 1
? 1
X
2 1
[ 0 ]
X
2 1
[ 1 ]
X
2 2
[ 0 ]
X
2 2
[ 1 ]
x [ 1 ]
x [ 5 ]
x [ 3 ]
x [ 7 ]
14W 04? 1
? 1
? 1
? 1
x [ 0 ]
x [ 4 ]
x [ 2 ]
2808W08W 08W
X
1 1
[ 0 ]
X
1 1
[ 1 ]
X
1 2
[ 0 ]
X
1 2
[ 1 ]
? 1
? 1
280808 08W
X
2 1
[ 0 ]
X
2 1
[ 1 ]
X
2 2
[ 0 ]
X
2 2
[ 1 ]
8点基 2时间抽取 FFT算法流图
基 2时间抽取 FFT算法
x [ 0 ]
x [ 4 ]
x [ 2 ]
x [ 6 ]
X [ 0 ]
X [ 2 ]
X [ 1 ]
X [ 3 ]
? 1
? 1
? 1
? 1
0
8W 0
8W
0
8W
x [ 1 ]
x [ 5 ]
x [ 3 ]
x [ 7 ]
X [ 0 ]
X [ 2 ]
X [ 1 ]
X [ 3 ]
? 1
? 1
? 1
? 1
0
8W 0
8W
0
8W
1
8W
0
8W 3
8W
2
8W
2
8W
2
8W
? 1
? 1
? 1
? 1
第一级 第二级 第三级
算法的计算复杂度
复乘次数 NN
2lo g2
复乘次数
N
N 2
NN 2log2
基 2时间抽取 FFT算法流图
x [ 0 ]
x [ 4 ]
x [ 2 ]
x [ 6 ]
X [ 0 ]
X [ 2 ]
X [ 1 ]
X [ 3 ]
? 1
? 1
? 1
? 1
0
8W 0
8W
0
8W
x [ 1 ]
x [ 5 ]
x [ 3 ]
x [ 7 ]
X [ 0 ]
X [ 2 ]
X [ 1 ]
X [ 3 ]
? 1
? 1
? 1
? 1
0
8W 0
8W
0
8W
1
8W
0
8W 3
8W
2
8W
2
8W
2
8W
? 1
? 1
? 1
? 1
第一级 第二级 第三级
FFT算法流图 旋转因子 规律P
NW
第二级 的蝶形系数为,蝶形节点的距离为 2。4/0,N
NN WW
第一级 的蝶形系数均为,蝶形节点的距离为 1。0
NW
第三级 的蝶形系数为,蝶形
节点的距离为 4。
8/38/28/0,,,NNNNNNN WWWW
第 M级 的蝶形系数为,蝶形
节点的距离为 N /2。
)12/(10,,,?NNNN WWW ?
倒序
k0 k1 k2
x[k2 k1k0]
x[000]
x[100]
x[010]
0
1
0
1
1]12 x[k k
0]x[k2 k10
1
x[110]
x[001]
x[101]
x[011]
x[111]
0
1
0
1
0
1
0
1
基 2频率抽取 FFT算法
mk
N
N
Nk
mk
N
N
k
WkxWkxmX ][][][
1
2/
12/
0
??
?
?
?
?
??
)2/(
12/
0
12/
0
]2/[][ NkmN
N
k
mk
N
N
k
WNkxWkx ?
?
?
?
?
??? ??
? ? mkNmN
k
WNkxkx ]2/[)1(][
12/
0
???? ?
?
?
? ? rkN
N
k
WNkxkxrX 2/
12/
0
]2/[][]2[ ??? ?
?
?
? ? rkNkN
N
k
WWNkxkxrX 2/
12/
0
]2/[][]12[ ???? ?
?
?
? ? rkNN
k
WNkxkxrX 2/
12/
0
]2/[][]2[ ??? ?
?
?
? ? rkNkNN
k
WWNkxkxrX 2/
12/
0
]2/[][]12[ ???? ?
?
?
12/1,0 ?? Nr ?
3
NW
-1
2
NW
-1
1
NW
-1
0
NW
-1
x[0]
x[4]
x[1]
x[5]
x[2]
x[6]
x[3]
x[7]
4点
DFT
X[0]
X[6]
X[2]
X[4]
4点
DFT
X[1]
X[3]
X[5]
X[7]
X[0]
X[6]
X[4]
X[2]
X[1]
X[5]
X[3]
X[7]
0
NW
1
NW
2
NW
3
NW-1
-1
-1
-1
x[0]
x[3]
x[1]
x[2]
x[4]
x[5]
x[6]
x[7]
0
NW
2
NW
2点
DFT
-1
-1
2
NW
0
NW
-1
-1
2点
DFT
2点
DFT
2点
DFT
0
NW
1
NW
2
NW
3
NW-1
-1
-1
-1
x[0]
x[3]
x[1]
x[2]
x[4]
x[5]
x[6]
x[7]
0
NW
2
NW
2
NW
0
NW
X[0]
X[6]
X[4]
X[2]
X[1]
X[5]
X[3]
X[7]
0
NW
0
NW
0
NW
0
NW
-1
-1
-1
-1
-1
-1
-1
-1
FFT算法应用
? 利用 N点复序列的 FFT计算两个 N点实序列 FFT
? 利用 N点复序列的 FFT，计算 2N点序列的 FFT
? 利用 FFT计算 IFFT
利用 N点复序列的 FFT算法计算
两个 N点实序列 FFT
x1[k],x2[k]是实序列，
将其构成复序列 y[k]=x1[k]+j x2[k]
DFT{x1[k]+j x2[k]}=YR [m]+jYI [m]
? ??][1 ?kxD F T
? ??][2 ?kxD F T
? ? ?? ][][ 21 kjxkxD F T ])[(])[( NINR mjYmY ???
? ? ? ?]))[(][(])[(][21][1 NIINRR mYmYjmYmYkxDF T ??????
? ? ? ?]))[(][(])[(][2 1][2 NIINRR mYmYjmYmYjkxD F T ??????
利用 N点复序列的 FFT，计算 2N点序列的 FFT
y[k]是一个长度为 2N的序列
1,1,0]12[][ ]2[][][
2
1 ??
?
?
?
??
?? Nk
kykx
kykxky ?
1,,1,0
][][][
][][][
221
221 ??
???
?? Nm
mXWmXNmY
mXWmXmY
m
N
m
N ?
问题：如何 利用 N点 FFT，计算 4N点序列的 FFT？
利用 FFT实现 IFFT
? ? mkNN
k
WkxkxD F TmX ][][][
1
0
? ?
?
??
? ? mkNN
m
WmXNmXI D F Tkx ?
?
?
??? ][1][][ 1
0
?
?
?
?
???
?
???
?? ? mk
N
N
m
WmX
N
kx ][1][
1
0
步骤,A) 将 X [m]取共轭
]}[{) mXD F TF F TB ?流图计算用
C) 对 B)中结果取共轭并除以 N