X(
N k +k = X 2 (k ) ) X 1 (k ) − WN 2
按时间抽取的 8 点 FFT 算法
x ( 0) x1 (0) = x(0) x3 (0) = x1 (0) = x(0) x(1) x (1) = x(2) x3 (l ) x3 (1) = x1 (2) = x(4) 1 x1 (r ) x ( 2) x1 (2) = x(4) x4 (0) = x1 (1) = x(2) x4 (l ) x4 (1) = x1 (3) = x(6) x1 (3) = x(6) x(3) x (n) ⇒ ⇒ x5 (0) = x2 (0) = x(1) x2 (0) = x(1) x ( 4) x5 (l ) x(5) x5 (1) = x2 (2) = x(5) x2 (1) = x(3) x2 ( r ) x x x = = ( 0 ) ( 1 ) ( 3 ) x x ( 2 ) ( 5 ) = x ( 6 ) 6 2 2 x6 (l ) x (7 ) x x x = = ( 1 ) ( 3 ) ( 7 ) x x ( 3 ) ( 7 ) = 6 2 2

(2)
显然： X (2r ), X (2r + 1)对应两个N / 2点的DFT。
令：
N x ( n ) x ( n ) x ( n = + + 1 2) n N x2 (n) = [ x(n) − x(n + 2 )] WN
用蝶型结构图表示为：
x ( n) x(n + )
N 2
x ( n) + x ( n + N 2)
x ( 2)
W
0 N
2 WN
X ( 2)
X (3)
0 WN
x ( 6)
x(1)
W
0 N
W
1 N
X ( 4)
x(5)
0 WN
X (5)
2 WN
3 WN
x(3)W0 NFra bibliotek2 WN
X ( 6)
X (7 )
x (7 )
第一级
m=0
.... ...... .......... .. .......... ..........
第四章 快速傅里叶变换 （FFT）
主要内容
DIT-FFT算法 DIF-FFT算法 重叠相加法 重叠保留法
学习目标
理解按时间抽选的基-2FFT算法的算法原理、 运算流图、所需计算量和算法特点 理解按频率抽选的基-2FFT算法的算法原理、 运算流图、所需计算量和算法特点 理解IFFT算法 了解混合基算法 理解线性卷积的FFT算法及分段卷积方法
§4.2 直接计算DFT的问题及改进途径
1、 DFT与IDFT
N 点有限长序列x(n)
X (k ) = ∑ x(n)W
n =0 N −1 kn N
1 x ( n) = N
复数加法 N–1 N (N – 1)
∑ X (k )W
k =0
N −1
− kn N
一个X(k) N个X(k) (N点DFT)
复数乘法 N N2
W
2 2 W N N
x2(2)
3 3 W NN W x2(3)
x1(0)
x3(0) N/4点 DFT
X3(0)=X1(0)=X(0)
x1(1)
x3(1)
X3(1)=X1(2)=X(4)
x1(2)
-1
0 0 W WN / 2N x4(0)
k WN
k X 1 ( k ) + WN X 2 (k )
-1
k X 1 ( k ) − WN X 2 (k )
注：a. 上支路为加法，下支路为减法； b. 乘法运算的支路标箭头和系数。
N =8=2 用“蝶形结”表示上面运算的分解：
3
X = (k ) X 1 (k ) + WNk X 2 (k )
mF ( DFT ) N2 2N = = mF ( FFT ) N log N log 2 N 2 2
§4.4 按频率抽取（DIF）的FFT算法
（Decimation In Frequency) 一、算法原理
与DIT-FFT算法类似分解，但是抽取的是X(k)。 即分解X(k)成奇数与偶数序号的两个序列。 设： N = 2L，L 为整数。将X(k)按k的奇偶分 组前，先将输入x(n)按n的顺序分成前后两半：
[
]
n为偶
n为奇
=
rk k rk x r W + W x r W ( ) ( ) ∑ N /2 1 N ∑ 2 N /2 r =0 r =0 X1 ( k ) X 2 (k )
N / 2 −1
N / 2 −1
2 rk rk = r , k 0,1,... N / 2 − 1 （这一步利用： WN ） = WN /2
−j 2π mnk mN
− nk N
( N −n ) k N
n ( N −k ) N
周期性 = W W = W
可约性
↓
−j 2π N ⋅ N 2
e = e = −1 e ↑ 0 ( k + N / 2) k 特殊点： WN = 1 WNN / 2 = −1 WN = −WN
− jπ
FFT 算法的基本思想： 利用DFT 系数的特性，合并DFT 运算中的某些项， 把长序列DFT → 短序列DFT，从而减少其运算量。
X (2 = r + 1) =
N / 2 −1
k = 2 r , 2 r + 1 的 X ( k )：
2 rn N ( ) ( ) x n x n W + + N 2 nr N ( ) ( ) x n x n W + + 2 N /2 x1 ( n )
x ( n + ) WN
k
]
nk
Nk / 2 N
= (−1)
=
N / 2 −1
∑
n =0
N nk k x ( n ) + ( −1) x n + 2 WN
= k 0,1,..., N − 1
按k的奇偶将X(k)分成两部分：
下面讨论
X (2 r) = =
1． N=2L时，共有L级运算；每一级有N/2个蝶形结, 每个蝶形有1次复数乘法2次复数加法。 2．每一级有N个中间数据，且每级只用到本级的转 入中间数据，适合于迭代运算。 3．计算量： N N mF = L log 2 N 复数乘法： = 2 2 复数加法： a = NL = N log 2 N F 比较DFT
X = (k ) X 1 (k ) + W X 2 (k )
k N
再利用周期性求X(k)的后半部分
W
r ( N / 2+ k ) N /2
=W
rk N /2
N / 2 −1 N / 2 −1 N / 2+ k ) rk ( ) X 1 + k = ∑ x1 (r )WNr (/ N x r W = ∑ 2 N / 2 = X 1 (k ) 1 r =0 2 r =0 N + k N k k X 2 + k = X 2 (k ) 又WN 2 = WNN / 2WN = −WN 2
第二级
m =1
第三级
m=2
(2) W 因子的分布
k N
X 1 (k )
X 2 (k )
WNk
X 1 (k ) + WNk X 2 (k )
X 1 (k ) − WNk X 2 (k )
由上可知： m = 0级，W m = 1级，W
k 2 0 2 k 4 k 8 0 4
-1
k = 0 W =W
0 8 1 4 0 8 2 8 3 8
k X k X k W ( ) ( ) = + N X 2 ( k )，k = 0,1,2,...N / 2 − 1 1 (2) X ( N + k ) = X ( N + k ) + W ( N / 2+ k ) X ( N + k ) N 1 2 2 2 2 N k X( +k = k 0,1, 2,... N / 2 − 1 ) X 1 (k ) − WN X 2 (k )，= 2
3、降低DFT运算量的考虑
W 的特性 WNnk = e
对称性
nk * N
nk N
−j
2π nk N
= W = W (W= ) W ↓ ↓ − nk nN − nk ⋅ WN WN WNNk ⋅ WN
nk N ( N +n ) k N n ( N +k ) N
nk mnk nk nk / m WN = WmN WN = WN /m
FFT算法分类:
时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency
§4.3 按时间抽取（DIT）的FFT算法
（Decimation In Time）
1、算法原理
设序列点数 N = 2L，L 为整数。 若不满足，则补零
∑
n =0
N / 2 −1
∑
n =0
n =0

(1)
N / 2 −1
∑
(2 r +1) n N x ( n ) − x ( n + ) W N 2
N / 2 −1
∑
n =0
n nr N x ( n ) − x ( n + ) W W N N /2 2 x2 ( n )