利用FFT实现IFFT
N 1
X [m] DFT x[k] x[k]WNmk k 0
x[k] IDFT X [m]
1 N
N 1 m0
X [m]WNmk
x[k]
1 N

N 1 m0
X [m]WNmk
步骤：A) 将X [m]取共轭
X[0]
X[1]
X[2]
W80 1
W81 1
W82 1
W83 1
X[3] X[0] X[1] X[2] X[3]
算法的计算复杂度
复乘次数
N 2
log 2
N
N2
复乘次数
N 2
log2
N
N
基2时间抽取FFT算法流图
第一级
x[0]
x[4]
W80
1
x[2]
x[6]
W80
1
x[1]
x[5]
W80
倒序
x[k2 k1k0]
k0
k1
0
0 x[k2 k10] 1
0
1 x[k2 k11] 1
k2 0 x[000]
1 x[100] 0 x[010]
1 x[110] 0 x[001] 1 x[101] 0 x[011] 1 x[111]
基2频率抽取FFT算法
N / 21
N 1
X[m]

x[k

N
/
2]
W
NkW
rk N/
2
k0
x[0]
X[0]
x[1]
4点
X[2]
x[2]
DFT
X[4]
x[3]
x[4] -1 x[5] -1 x[6]
-1
x[7]
-1
WN0
WN1 WN2
4点 DFT
WN3
X[6] X[1] X[3] X[5] X[7]
x[0]
2点
X[0]
x[1]
DFT
X[4]
x[2]
x[0]
X [0]
x[1] W20
-1
X [1]
X [m] X1[m] W4m X 2[m], m 0,1
X [4m点基2]2时X间1[m抽]取 WF4FmTX算2[m法],流图m 0,1
x[0]
x[2] W20
x[1]
x[3] W20
X1[0]
2点DFT X1[1] 1
X2[0]
DFTx1[k]
1 2
YR
[m]

YR
[(m)
N
]
j(YI [m] YI [(m) N
])
DFT x2[k]
1 2j
YR
[m]

YR
[(
m)
N
]
j(YI [m] YI [(m) N ])
利用N点复序列的FFT，计算2N点序列的FFT
y[k]是一个长度为2N的序列
X [0]
X [1]
X [2]
X [3]
1 X [4] 1 X [5] 1 X [6]
X [7]
1
基2时间抽取FFT算法
第一级
x[0]
x[4]
W80
1
x[2]
x[6]
W80
1
x[1]
x[5]
W80
1
x[3]
x[7]
W80
1
第二级
W80 1
W82 1
W80 1
W82 1
第三级
复数加法 N(N-1)
复数乘法 N 2
效 率
?
解决问题的思路
1. 将长序列DFT分解为短序列的DFT
2. 利用旋转因子 WNkm的周期性、对称性、可约性。
旋转因子 WNkm 的性质
1)周期性
WN(kN)m WNk(mN) WNkm
2) 对称性
mk N
WN 2

W
mk N
WNkm WNmk
r 0,1, N 1 2
基2频率抽取(Decimation in frequency)FFT算法
X
[m]

X X
[2m] [2m 1]
基2时间抽取FFT算法流图
N=2
x[k]={x[0], x[1]}
X[0] x[0] W20 x[1] X [1] x[0] W21x[1] x[0] W20 x[1]
何 提
k 0
高
X[0] 2WN0 3WN0 3WN0 2WN0 10
DFT
X[1] 2WN0 3WN1 3WN2 2WN3 1 j
的
X[2] 2WN0 3WN2 3WN4 2WN6 0
运 算
X[3] 2WN0 3WN3 3WN6 2WN9 1 j
B) 用FFT流图计算 DFT {X [m]}
C) 对B)中结果取共轭并除以N
x[0]
X1[0]
X [0]
x[2]
X1[1]
X [1]
x[4]
4点DFT
X1[2]
X [2]
x[6]
X1[3]
X [3]
x[1] x[3] x[5]
4点DFT
X2[0] W80 X2[1] W81 X2[2] W82
1 X [4]
1 X [5] X [6]
x[7]
X2[3] W83
1
X [7]
X[0]
WN0
-1
WN2
-1
-1
WN0 X[4]
X[2]
-1
WN0 X[6]
W0 N
X[1]
W1 N
-1
WN0 X[5]
W2 N
WN0
-1
X[3]
W3 N
WN2
-1
-1
WN0 X[7]
FFT算法应用
▪ 利用N点复序列的FFT计算两个N点实序列FFT ▪ 利用N点复序列的FFT，计算2N点序列的FFT ▪ 利用FFT计算IFFT
WN0
-1
2点
X[2]
x[3]
WN2 DFT
-1
X[6]
x[4] -1
W0 N
x[5] -1
WN1
2点
X[1]
DFT
X[5]
x[6] -1 x[7] -1
WN2 WN3
WN0Leabharlann -12点X[3]WN2 DFT
-1
X[7]
x[0] x[1] x[2] x[3] x[4] -1 x[5] -1 x[6] -1 x[7] -1
3)可约性
WNmk WnnNmk
WNmk WNm/kn/ n , N / n为整数
解决问题的方法
将时域序列逐次分解为一组子序列，利用旋转因子 的特性，由子序列的DFT来实现整个序列的DFT。
基2时间抽取(Decimation in time)FFT算法
x[2r] x[k] x[2r 1]
1
x[3]
x[7]
W80
1
第二级
W80 1
W82 1
W80 1
W82 1
第三级
X[0]
X[1]
X[2]
W80 1
W81 1
W82 1
W83 1
X[3] X[0] X[1] X[2] X[3]
FFT算法流图旋转因子 WNP 规律
第一级的蝶形系数均为 WN0 ，蝶形节点的距离为1。 第二级的蝶形系数为 WN0 , WNN / 4 ，蝶形节点的距离为2。 第三级的蝶形系数为 WN0 , WNN /8, WN2N /8, WN3N /8 ，蝶形 节点的距离为4。 第M级 的蝶形系数为 WN0 , WN1 , , WN(N / 21) ，蝶形 节点的距离为N /2。
y[k
]


x1[k ] x2[k]

y[2k ] y[2k
1]
k 0,1, N 1
Y[m] X1[m] W2mN X 2[m] Y[m N ] X1[m] W2mN X 2[m]
m 0,1, , N 1
问题：如何利用N点FFT，计算4N点序列的FFT？
2点DFT X2[1]
1
W40
1
W41
1
X [0] X [1] X [2] X [3]
4点基2时间抽取FFT算法流图
x[0]
x[2]
W40
x[1]
x[3]
W40
X1[0]
X1[1] 1
X2[0]
W40 1
X2[1]
W41
1
1
X[0] X[1] X[2] X[3]
X[mX8[m点4]]基 X2X时11[[mm间]]抽WW取88mmFXXF22T[[mm算]],,法mm流图00,,11,,22,,33

N
/
2]
W
rk N/
2
k0
N / 21
X[2r 1]
x[k]
x[k

N
/
2]
W
NkW
rk N/
2
k0
N / 21
X[2r]
x[k]
x[k

N
/
2]
W
rk N/
2
r 0,1 N / 2 1
k0
N / 21
X[2r 1]
x[k ]
1
8点基2时间抽取FFT算法流图
xx[[00]]
XX111[10[]0]