三,按频率抽选的基 -2FFT算法
1、算法原理设序列点数 N=2L,L为整数。
将 X(k)按 k的奇偶分组前，先将输入 x(n)按 n的顺序分成前后两半：
1 / 2 1 1
0 0 / 2
( ) ( ) ( ) ( )
N N N
nk nk nk
N N N
n n n N
X k x n W x n W x n W



/ 2 1 / 2 1
2
00
() 2
NNN nk
nk
NN
nn
Nx n W x n W



/ 2 1
/2
0
() 2
N
N k nk
NN
n
Nx n x n W W?


/ 2 1
0
( ) ( 1 ) 2
N
k nk
N
n
Nx n x n W?


0,1,.,,,1kN
/2 1NNW
按 k的奇偶将 X(k)分成两部分：
2
21
kr
kr


0,1,.,,,/ 2 1rN
/ 2 1
2
0
( 2 ) ( ) 2
N
nr
N
n
NX r x n x n W?


/ 2 1
( 2 1)
0
( 2 1 ) ( ) 2
N
nr
N
n
NX r x n x n W


/ 2 1
/2
0
() 2
N
nr
N
n
Nx n x n W?


/ 2 1
/2
0
() 2
N
n n r
NN
n
Nx n x n W W?



令
1
2
( ) ( )
2
( ) ( )
2
n
N
N
x n x n x n
N
x n x n x n W






0,1,...,12Nn
则 X(2r)和 X(2r+1)分别是 x1(n)和 x2(n)的 N / 2
点 DFT，记为 X1(k)和 X2(k)
x1(0)
x1(1)
-1
x1(2)
x1(3)
-1
x2(0)
x2(1)
-1
x2(2)
x2(3)
-1
N/2点
DFT
N/2点
DFT
x(0)
x(7)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
X1(0)=X(0)
X2(0)=X(1)
X1(1)=X(2)
X1(2)=X(4)
X1(3)=X(6)
X2(1)=X(3)
X2(2)=X(5)
X2(3)=X(7)
1NW
0NW
2NW
3NW
N /2仍为偶数，进一步分解,N /2 N /4?
3 1 1
4 1 1 / 2
( ) ( ) ( / 4 )
( ) [ ( ) ( / 4 ) ] nN
x n x n x n N
x n x n x n N W


0,1,..,,14Nn
3 1 3
4 1 4
( ) ( 2 ) [ ( ) ]
( ) ( 2 1 ) [ ( ) ]
X k X k D F T x n
X k X k D F T x n


0,1,...,14Nk
x3(0)
x3(1)
-1
-1
x4(0)
x4(1)
N/4点
DFT
N/4点
DFT
x1(0)
x1(1)
x1(2)
x1(3)
X3(0)=X1(0)=X(0)
X4(0)=X1(1)=X(2)
X3(1)=X1(2)=X(4)
X4(1)=X1(3)=X(6)
0/2NW
1/2NW
0,1,...,14Nk5 2 5
6 2 6
( ) ( 2 ) [ ( ) ]
( ) ( 2 1 ) [ ( ) ]
X k X k D F T x n
X k X k D F T x n


同理：
其中：
5 2 2
6 2 2 / 2
( ) ( ) ( / 4 )
( ) [ ( ) ( / 4 )] nN
x n x n x n N
x n x n x n N W


0,1,..,,14Nn
逐级分解，直到 2点 DFT
00
3 3 2 2 3 3 3
0 1 0
3 3 2 2 3 3 3
( 0 ) ( 0 ) ( 0 ) ( 1 ) ( 0 ) ( 1 )
( 4 ) ( 1 ) ( 0 ) ( 1 ) [ ( 0 ) ( 1 )] N
X X x W W x x x
X X x W W x x x W


/ 4 1 1
3 3 / 4 3 / 4
00
( ) ( ) ( )
N
lk lk
NN
ll
X k x l W x l W

0,1k?
当 N=8时，即分解到 x3(n),x4(n),x5(n)，
x6(n),n=0,1
00
4 4 2 2 4 4 4
0 1 0
4 4 2 2 4 4 4
( 2 ) ( 0 ) ( 0 ) ( 1 ) ( 0 ) ( 1 )
( 6 ) ( 1 ) ( 0 ) ( 1 ) [ ( 0 ) ( 1 )] N
X X x W W x x x
X X x W W x x x W


/ 4 1 1
4 4 / 4 4 / 4
00
( ) ( ) ( )
N
l k l k
NN
ll
X k x l W x l W

0,1k?
2、算法特点
1）原位计算
11
11
( ) ( ) ( )
( ) [ ( ) ( ) ]
m m m
r
m m m N
X k X k X j
X j X k X j W




rNW
1 ()mXk?
1 ()mXj?
()mXk
()mXj-1
L级蝶形运算，每级 N/2个蝶形，每个蝶形结构：
m表示第 m级迭代,k,j表示数据所在的行数
2）蝶形运算对 N=2L点 FFT，输入自然序，输出倒位序，
两节点距离,2L-m=N / 2m
11
11
( ) ( )
2
()
22
m m m m
r
m m m Nmm
N
X k X k X k
NN
X k X k X k W








第 m级运算：
蝶形运算两节点的第一个节点为 k值，表示成 L位二进制数，左移 m-1位，把右边空出的位置补零，结果为 r的二进制数。
rNW 的确定
12( ) 2 mrk
3,DIT与 DIF的异同
基本蝶形不同
2l o g2F
NmN?
2l o gFa N N?
– DIT,先复乘后加减
– DIF,先减后复乘
运算量相同
都可原位运算
DIT和 DIF的基本蝶形互为转置