二,按时间抽选的基 -2FFT算法
1、算法原理设序列点数 N = 2L,L 为整数。
若不满足，则补零
1
2
2
21
x r x r
x r x r
0,1,.,,,/ 2 1rN
将序列 x(n)按 n的奇偶分成两组：
N为 2的整数幂的 FFT算法称基 -2FFT算法。
则 x(n)的 DFT:
1 1 1
0 0 0
N N N
n k n k n k
N N N
n n n
X k x n W x n W x n W
n为 偶 数 n为 奇 数
/ 2 1 / 2 1 212
00
2 2 1
NN rk
rk
NN
rr
x r W x r W
/ 2 1 / 2 12212
00
NN r k r k
k
N N N
rr
x r W W x r W
/ 2 1 / 2 11 / 2 2 / 2
00
NN
r k k r k
N N N
rr
x r W W x r W
12 kNX k W X k,0,1,..,/ 2 1r k N
再利用周期性求 X(k)的后半部分
12
12
( ) ( ) ( )
( ) ( ) ( )
2
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,.,,,/ 2 1kN
12
1 1 2 2
,/ 2
22
X k X k N
NN
X k X k X k X k
是以 为周期的
/22Nk N k k
N N N NW W W W
又分解后的运算量：
复数乘法 复数加法一个 N / 2点 DFT (N / 2)2 N / 2 (N / 2 –1)
两个 N / 2点 DFT N 2 / 2 N (N / 2 –1)
一个蝶形 1 2
N / 2个蝶形 N / 2 N
总计 2
2
/ 2 / 2
/2
NN
N
2
/ 2 1
/2
N N N
N
运算量减少了近一半
13
14
( 2 ) ( )
( 2 1 ) ( )
x l x l
x l x l
0,1,.,,,/ 4 1lN
1 3 / 2 4
1 3 / 2 4
( ) ( ) ( )
( ) ( ) ( )
4
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,...,14Nk
N / 2仍为偶数，进一步分解,N / 2 N / 4
2 5 / 2 6
2 5 / 2 6
( ) ( ) ( )
( ) ( ) ( )
4
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,...,14Nk
同理：
其中：
5 5 2( ) [ ( ) ] [ ( 2 ) ]X k D F T x l D F T x l
6 6 2( ) [ ( ) ] [ ( 2 1 ) ]X k D F T x l D F T x l
0,1,.,,,/ 4 1lN
2/2kkNNWW?统一系数：
这样逐级分解，直到 2点 DFT
当 N = 8时，即分解到 X3(k),X4(k),X5(k)，
X6(k),k = 0,1
0 0 0
3 3 2 2 3
0 1 0
3 3 2 2 3
( 0 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )
( 1 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )
N
N
X x W W x x W x
X x W W x x W x
/ 4 1 1
3 3 / 4 3 / 4
00
( ) ( ) ( )
N
lk lk
NN
ll
X k x l W x l W
0,1k?
0 0 0
4 4 2 2 4
0 1 0
4 4 2 2 4
( 0 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )
( 1 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )
N
N
X x W W x x W x
X x W W x x W x
/ 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、运算量当 N = 2L时，共有 L级蝶形，每级 N / 2个蝶形，每个蝶形有 1次复数乘法 2次复数加法。
2l o g22F
NNm L N复数乘法：
2l o gFa N L N N复数加法：
2
2
2
( ) 2
( ) l o gl o g
2
F
F
m D F T N N
Nm F F T NN
比较 DFT
3、算法特点
1）原位计算
11
11
( ) ( ) ( )
( ) ( ) ( )
r
m m m N
r
m m m N
X k X k X j W
X j X k X j W
m表示第 m级迭代,k,j表示数据所在的行数
2）倒位序倒位序 自然序
000 0 0 000
100 4 1 001
010 2 2 010
110 6 3 011
001 1 4 100
101 5 5 101
011 3 6 110
111 7 7 111
n0 n1 n2
0 0 0
1
1 0
1
1 0 0
1
1 0
1
2 1 0 2( ) ( )x n n n n n?
2 1 0 2()n n n n?0 1 2 2()n n n n?
3）蝶形运算对 N = 2L点 FFT，输入倒位序，输出自然序，
第 m级运算每个蝶形的两节点距离为 2m–1
第 m级运算：
1
11
11
11
( ) ( ) ( 2 )
( 2 ) ( ) ( 2 )
mr
m m m N
m m r
m m m N
X k X k X k W
X k X k X k W
蝶形运算两节点的第一个节点为 k值，表示成 L位二进制数，左移 L – m位，把右边空出的位置补零，结果为 r的二进制数。
rNW 的确定
2( ) 2 Lmrk
4）存储单元输入序列 x(n),N个存储单元
rNW系数,N / 2个存储单元
4,DIT算法的其他形式流图
输入倒位序输出自然序
输入自然序输出倒位序
输入输出均自然序
相同几何形状
– 输入倒位序输出自然序
– 输入自然序输出倒位序
1、算法原理设序列点数 N = 2L,L 为整数。
若不满足，则补零
1
2
2
21
x r x r
x r x r
0,1,.,,,/ 2 1rN
将序列 x(n)按 n的奇偶分成两组：
N为 2的整数幂的 FFT算法称基 -2FFT算法。
则 x(n)的 DFT:
1 1 1
0 0 0
N N N
n k n k n k
N N N
n n n
X k x n W x n W x n W
n为 偶 数 n为 奇 数
/ 2 1 / 2 1 212
00
2 2 1
NN rk
rk
NN
rr
x r W x r W
/ 2 1 / 2 12212
00
NN r k r k
k
N N N
rr
x r W W x r W
/ 2 1 / 2 11 / 2 2 / 2
00
NN
r k k r k
N N N
rr
x r W W x r W
12 kNX k W X k,0,1,..,/ 2 1r k N
再利用周期性求 X(k)的后半部分
12
12
( ) ( ) ( )
( ) ( ) ( )
2
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,.,,,/ 2 1kN
12
1 1 2 2
,/ 2
22
X k X k N
NN
X k X k X k X k
是以 为周期的
/22Nk N k k
N N N NW W W W
又分解后的运算量：
复数乘法 复数加法一个 N / 2点 DFT (N / 2)2 N / 2 (N / 2 –1)
两个 N / 2点 DFT N 2 / 2 N (N / 2 –1)
一个蝶形 1 2
N / 2个蝶形 N / 2 N
总计 2
2
/ 2 / 2
/2
NN
N
2
/ 2 1
/2
N N N
N
运算量减少了近一半
13
14
( 2 ) ( )
( 2 1 ) ( )
x l x l
x l x l
0,1,.,,,/ 4 1lN
1 3 / 2 4
1 3 / 2 4
( ) ( ) ( )
( ) ( ) ( )
4
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,...,14Nk
N / 2仍为偶数，进一步分解,N / 2 N / 4
2 5 / 2 6
2 5 / 2 6
( ) ( ) ( )
( ) ( ) ( )
4
k
N
k
N
X k X k W X k
N
X k X k W X k
0,1,...,14Nk
同理：
其中：
5 5 2( ) [ ( ) ] [ ( 2 ) ]X k D F T x l D F T x l
6 6 2( ) [ ( ) ] [ ( 2 1 ) ]X k D F T x l D F T x l
0,1,.,,,/ 4 1lN
2/2kkNNWW?统一系数：
这样逐级分解，直到 2点 DFT
当 N = 8时，即分解到 X3(k),X4(k),X5(k)，
X6(k),k = 0,1
0 0 0
3 3 2 2 3
0 1 0
3 3 2 2 3
( 0 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )
( 1 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )
N
N
X x W W x x W x
X x W W x x W x
/ 4 1 1
3 3 / 4 3 / 4
00
( ) ( ) ( )
N
lk lk
NN
ll
X k x l W x l W
0,1k?
0 0 0
4 4 2 2 4
0 1 0
4 4 2 2 4
( 0 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )
( 1 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )
N
N
X x W W x x W x
X x W W x x W x
/ 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、运算量当 N = 2L时，共有 L级蝶形，每级 N / 2个蝶形，每个蝶形有 1次复数乘法 2次复数加法。
2l o g22F
NNm L N复数乘法：
2l o gFa N L N N复数加法：
2
2
2
( ) 2
( ) l o gl o g
2
F
F
m D F T N N
Nm F F T NN
比较 DFT
3、算法特点
1）原位计算
11
11
( ) ( ) ( )
( ) ( ) ( )
r
m m m N
r
m m m N
X k X k X j W
X j X k X j W
m表示第 m级迭代,k,j表示数据所在的行数
2）倒位序倒位序 自然序
000 0 0 000
100 4 1 001
010 2 2 010
110 6 3 011
001 1 4 100
101 5 5 101
011 3 6 110
111 7 7 111
n0 n1 n2
0 0 0
1
1 0
1
1 0 0
1
1 0
1
2 1 0 2( ) ( )x n n n n n?
2 1 0 2()n n n n?0 1 2 2()n n n n?
3）蝶形运算对 N = 2L点 FFT，输入倒位序，输出自然序，
第 m级运算每个蝶形的两节点距离为 2m–1
第 m级运算：
1
11
11
11
( ) ( ) ( 2 )
( 2 ) ( ) ( 2 )
mr
m m m N
m m r
m m m N
X k X k X k W
X k X k X k W
蝶形运算两节点的第一个节点为 k值，表示成 L位二进制数，左移 L – m位，把右边空出的位置补零，结果为 r的二进制数。
rNW 的确定
2( ) 2 Lmrk
4）存储单元输入序列 x(n),N个存储单元
rNW系数,N / 2个存储单元
4,DIT算法的其他形式流图
输入倒位序输出自然序
输入自然序输出倒位序
输入输出均自然序
相同几何形状
– 输入倒位序输出自然序
– 输入自然序输出倒位序
