2
X
4
(k
)
,
k
0,1, ,
N
/
4
1
(4.2.10)
第4章 快速傅里叶变换(FFT)
用同样的方法可计算出
X X
2 2
(k (k
) X5(k N / 4)
) WNk X5k
/2
X 6 (k Wk
N /2
) X
6
(k
)
,
k
0,1, N
/
4
1
其中
N / 41
X5(k)
x5(l)WNkl/ 4 DFT [x5(l)]
x2 (r)WNkr/ 2 DFT [x2 (r)]
r0
(4.2.6)
由于X1(k)和X2(k)均以N/2为周期，且
kN
WN 2
WNk
，所以X(k)又可表示为
X (k) X1(k) WNk X 2(k)
k 0,1, N 1 2
X (k
N 2
)
X1(k)
WNk
X 2 (k )
k 0,1, N 1 2
A(7 )
x(7 )
W
0 N
A(0 )
A(1 )
A(2 )
W
0 N
A(3 )
W
2 N
A(4 )
A(5 )
A(6 )
W
0 N
A(7 )
W
2 N
A(0 )
A(1 )
A(2 )
A(3 )
A(4 )
W
0 N
A(5 )
W
1 N
A(6 )
W
2 N
A(7 )
W
3 N
图4.2.4 N点DIT―FFT运算流图(N=8)
WNm WNN m 或者 [WNN m ] WNm
m N
WN 2
WNm
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理 FFT 算 法 基 本 上 分 为 两 大 类 ： 时 域 抽 取 法
FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取 法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 下面先介绍DIF―FFT算法。
第4章 快速傅里叶变换(FFT)
4.2 基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为
N 1
X (k) x(n)WNkn, k 0,1,, N 1
n0
(4.2.1)
考虑x(n)为复数序列的一般情况，对某一个k值，
直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次
XL(J ) XR(J ) j(J )
则
X R (J ) X R (J ) TR
X I (J ) X I(J ) TI
X R (J B) X R (J ) TR
X I (J B) X I(J ) TI
4. 编程思想及程序框图
图4.2.6 DIT―FFT运算和程序框图
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
观察图4.2.4不难发现，第L级共有2 L-1个不同的旋 转因子。N=23=8时的各级旋转因子表示如下：
L=1时，WpN=WJ N/4=WJ2L， J=0 L=2时， WpN =WJ N/2=WJ2L， J=0，1 L=3时， WpN =WJN=WJ2L， J=0，1，2，3 对N=2M的一般情况，第L级的旋转因子为
W
2 N
X2(3 )
W
3 N
X(6 ) X(7 )
图4.2.3 N点DFT的第二次时域抽取分解图(N=8)
第4章 快速傅里叶变换(FFT)
A(0 ) x(0 )
A(1 )
x(4 )
A(2 )
W
0 N
x(2 )
A(3 )
x(6 )
A(4 )
W
0 N
x(1 )
A(5 )
x(5 )
A(6 )
W
0 N
x(3 )
n
n
N / 21
N / 21
x(2r)WN2kr
x(2r 1)WNk (2r1)
r0
r0
N / 21
N / 21
x1(r) WNk
x2 (r)WN2kr
由于
r0
r0
W 2kr N
j 2 2kr
eN
j
2 N
kr
e 2
W 2kr N /2
所以
N / 21
N / 21
X (k)
x1(r)WNkr/ 2 WNk
WNp W2J L, J 0,1, 2, , 2L1 1 2L 2M 2LM N 2LM
WNP
WJ N g2LM
WNJ g2M L , J
0,1, 2, , 2L1 1
(4.2.12)
p J g2M L
(4.2.13)
第4章 快速傅里叶变换(FFT)
3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。 如果蝶形运算的两个输入数据相距B个点，应用原位计 算，则蝶形运算可表示成如下形式：
长的子序列x3(l)和x4(l)，即
x3 (l ) x4 (l )
x2 x1
(2l (2l
)
1)
,
l
0,1, ,
N 4
1
那么，X1(k)又可表示为
N / 41
N / 41
X1(k)
x1(2l
)WN2
kl /2
x1(2l
1)WNk
(2l 1) /2
i0
i0
N / 41
N / 41
x4(k)
x4 (l)WNkl/ 4 DFT [x4 (l)]
i0
同理，由X3(k)和X4(k)的周期性和Wm N/2的对称
性 Wk+N/4 N/2=-Wk N/2 最后得到：
X X
1 1
(k (k
) X3(k N / 4)
) WNk / 2 X 4 (k ) X 3(k ) WNk /
CM (2)
N 2
M
N 2
log2
N
复数加次数为
CA(2) N M N log2 N 例如，N=210=1024时
N2
1048576 204.8
(N / 2) log2 N 5120
第4章 快速傅里叶变换(FFT) 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线
第4章 快速傅里叶变换(FFT)
x3(l )WNkl/ 4 WNk / 2
x4 (l )WNkl/ 4
i0
i0
x3(k ) WNk /2 X 4 (k ), k 0,1, N / 2 1
(4.2.9)
第4章 快速傅里叶变换(FFT)
式中
N / 41
x3(k)
x3(l)WNkl/ 4 DFT [x3(l)]
i0
N / 41
设序列x(n)的长度为N，且满足
N 2M , M 为自然数
按n的奇偶把x(n)分解为两个N/2点的子序列
x1(r) x(2r),
r 0,1, N 1 2
x2(r) x(2r 1),
r 0,1, N 1 2
第4章 快速傅里叶变换(FFT)
则x(n)的DFT为
X (k ) x(n)WNkn x(n)WNkn
4.2.4 DIT―FFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出，DIT―FFT的运算过程很有规
律。N=2M点的FFT共进行M级运算，每级由N/2个蝶 形运算组成。
2.旋转因子的变化规律 如上所述，N点DIT―FFT运算流图中，每级都有 N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转 因子，p称为旋转因子的指数。
i0
N / 41
X 6(k)
x6 (l)WNkl/ 4 DFT [x6(l)]
i0
x5 (l ) x6 (l )
x2 (2l ) x2(2l
1)
,
l
0,1, N
/
4
1
(4.2.11)
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点 X3(0 )
X1(0 )
X(0 )
x(4 )
DFT X3(1 )
X1(1 )
X(1 )
x(2 )
N/4点
X4(0 )
W
0 N
2
X1(2 )
X(2 )
x(6 )
DFT
X4(1 )
W
1 N
2
X1(3 )
X(3 )
x(1 )
N/点
X2(0 )
W
0 N
X(4 )
x(5 )
DFT
X2(1 )
W
1 N
X(5 )
x(3 )
N/4点
x(7 )
DFT
W
0 N
2
W
1 N
2
X2(2 )
001 1 101 5 011 3 111 7
图4.2.7 形成倒序的树状图(N=23)
第4章 快速傅里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表
第4章 快速傅里叶变换(FFT)
x(0 ) x(1 ) x(2 ) x(3 ) x(4 ) x(5 ) x(6 ) x(7 ) A(0 ) A(1 ) A(2 ) A(3 ) A(4 ) A(5 ) A(6 ) A(7 )