数字信号处理chap9_第1讲

( N −k )n WNk ( N − n ) = WN = WN− kn = (WNkn )*
(ii) periodicity in n and k :
k ( n + rN ) ( k + rN ) n kn WN = WN = WN
(iii) 可约性:
mnk /m WNnk = WmN , WNnk = WNnk /m
k 2k W = W ( N/2 N )
X 3 [0]
X1[0]
X[0]
X 3 [1]
0 X 4 [0] WN
X1[1]
X[1]
X[2]
X [3]
X1[2]
X1[3]
0 X2[0] WN
x4 [1] = x1[3] = x[6]
x5 [0] = x2 [0] = x[1]
2 X 4 [1] WN
X 5 [0] X 5 [1]
N −1
+ j (Re{ x[ n ]} ⋅ Im{W Nnk } + Im{ x[ n ]} ⋅ Re{W Nnk })]
Complex Mul Complex Add Real Mul Real Add
one X[k] N-point DFT
N
N2
N-1 N(N-1)
4N
4N 2
2N+2(N-1) = 4N-2
当 N = 2v 时，共有 v = log2 N 级蝶形；每级都由N/2个蝶形运算组 成，每个蝶形有1次复乘、2次复加，因此每级运算需N/2次复乘 和N次复加。 v级运算总共需要 (N / 2)log2 N 复乘和 N log2 N 复加。
Comparison of the computation of DFT and DIT-FFT
(N =2v)
(i) The DIT-FFT N complex mul: log 2 N
Let
x[n]: 0 ≤ n ≤ N − 1, N = 2v
—— radix-2 FFT (i) Decompose x[n] into two sequences according n is even or odd ( N → N / 2)
⎧ x[2r ] = x1[r ] ⎨ ⎩ x[2r + 1] = x2 [r ] N r = 0,1,", − 1 2
0 N /2 − j (2π / N ) N /2 − jπ W = 1, W = e = e = −1, (iv) N N
( k + N / 2) k WN = −WN

FFT算法的基本思路
z
kn 利用 WN 的周期性、对称性、可约性，使DFT运 算中某些项合并
z
将长序列的DFT分解为若干短序列的DFT Decimation-In-Time FFT (DIT-FFT) Decimation-In-Frequency FFT (DIF-FFT)
A N-point DFT is decomposed into two N/2-point DFTs Butterfly Computation:
X1[k ]
X 2[k ]
k WN
X 1[k ] + WNk X 2 [k ]
−1
X 1[k ] − WNk X 2 [k ]
one complex multiplication + two complex addition
X 3 [0] = x3 [0] + W20 x3 [1] = x[0] + W20 x[4] = x [0] + W N0 x [4] X 3 [1] = x3 [0] + W21 x3 [1] = x[0] + W21 x[4] = x [0] − W N0 x [4]
0 ⎧ X 4 [0] = x[2] + WN x[6] ⎨ 0 X = x − W [1] [2] N x[6] ⎩ 4 0 ⎧ X 5 [0] = x[1] + WN x[5] ⎨ 0 X = x − W [1] [1] N x[5] ⎩ 5 0 ⎧ X 6 [0] = x[3] + WN x[7] ⎨ 0 X = x − W [1] [3] N x[7] ⎩ 6
X [4] X [5]
X [6] X [7]
1 X2[1] WN
2 X2[2] WN
3 X2[3] WN
Computation = two N/2-point DFTs + N/2 butterflies
complex mul: complex add:
N N N ⎞ N 2 ×⎛ + 1 × = + ⎜ ⎟ 2 ⎝ 2 ⎠ 2 2 2 ⎛ N ⎞⎛ N ⎞ ⎛N⎞ N 2 × ⎜ ⎟⎜ − 1⎟ +2 × ⎜ ⎟ = ⎝ 2 ⎠⎝ 2 ⎠ 2 ⎝2⎠
butterfly
So, the 8-point DIT-FFT:
x[0]
X [0]
0 WN 0 WN
0 WN
x[4]
X [1]
X [2]
x[2]
x[6]
2 WN
0 WN
X [3]
X [4]
X [5] X [6] X [7]
x[1]
x[5]
0 WN
1 WN
0 WN
x[3]
x[7]
0 WN
2 WN
3 WN
(iii) Further decomposition until 2-point DFTs are left e. g. N = 8 = 2 3
X3[k ] =
N / 4−1 1
∑
l =0
lk lk x3[l ]WN = x [ l ] W ∑ 3 N / 4 , k = 0,1 /4 l =0
2r +1) k
k 2rk 2rk = ∑x1[r] WN +WN x [ r ] W ∑2 N r =0 r =0
k rk = ∑ x1[r ]WNrk + W x [ r ] W N N∑ 2 2 2 r =0 r =0
= X 1[ k ] + WNk X 2 [ k ],
0 ≤ k ≤ N / 2 −1
z
For this reason, we are interested in computational procedures that reduce the number of multiplications and additions.

Approaches to reduce the computation of DFT by kn using the Properties of WN (i) complex conjugate symmetry:
2 WN
Computation of DIT-FFT
x[0]
X [0]
0 WN 0 WN 0 WN
x[4]
X [1]
X [2]
X [3]
0 WN
x[2]
x[6]
2 WN
x[1]
x[5]
0 WN 0 WN
0 WN
X [4] X [5]
X [6]
1 WN
x[3]
2 WN
3 WN
x[7]
2 WN
X [7]
9.0 Introduction
The Fast Fourier Transform (FFT) is not a new algorithm which is different from the DFT, but an efficient algorithm for fast computation of the DFT.
x3[0] = x1[0] = x[0]
x3[1] = x1[2] = x[4]
x4 [0] = x1[1] = x[2]
X 3 [0]
X 3 [1]
0 ≤ k ≤ N / 4 −1
X1[0]
X1[1]
0 X 4 [0] WN /2
X1[2]
X1[3]
x4 [1] = x1[3] = x[6]
1 X 4 [1] WN /2
Then,
nk X [k ] = ∑ x[n]WN = n =0
N −1 2
N −1
n even
N −1 2
∑
nk nk x[n] WN + ∑ x[n]WN n odd
N −1 2 N −1 2
( 2rk = ∑x[2r] WN + ∑x[2r +1] WN
r =0 r =0
N −1 2 N −1 2
2
2
计算量减少大约一半
(ii) The 2nd decomposition: N → N
2 4
⎧ x1[2l ] = x3[l ] ⎨ ⎩ x1[2l + 1] = x4 [l ]
N l = 0,1,", − 1 4
⎧ X 1[ k ] = X 3 [ k ] + W Nk / 2 X 4 [ k ] ⎨ k N + = − X [ k ] X [ k ] W N / 2 X 4 [k ] 3 ⎩ 1 4
Similarly,
⎧ x2 [2l ] = x5[l ] ⎨ ⎩ x2 [2l + 1] = x6 [l ] N l = 0,1,", − 1 4
⎧ X 2 [ k ] = X 5 [ k ] + W Nk / 2 X 6 [ k ] ⎨ k N + = − X [ k ] X [ k ] W N / 2 X 6 [k ] 5 ⎩ 2 4
9.3. Decimation-In-Time FFT algorithms