六、基 -4FFT算法当混合基 FFT算法中 时，
即为基 -4FFT算法,n,k都为 4进制数
12 4Lr r r
个 点 DFT 乘 N个旋转因子1r
1
N
r
个 点 DFT 乘 N个旋转因子2r
2
N
r
个 点 DFTLr
L
N
rXk?整 序
21 6 4N
10
10
4
4
n n n
k k k


1 0 0 0 0 1
01
33
44
10
00
,n k n k n kN N N
nn
X k x n n W W W


10
1
3
1 0 0 1 0 4
0
1 ),,nk
n
X k n x n n W

00'1 0 0 1 0 02 ),,nkNX k n X k n W?
01
0
3
'
2 0 1 1 0 0 4
0
3 ),,nk
n
X k k X k n W

0 0 0 01 0 4 0 4 0 4 0 4 00,0,1,2,3,X n W x n W x n W x n W x n
0 1 2 31 0 4 0 4 0 4 0 4 01,0,1,2,3,X n W x n W x n W x n W x n
10,nk1) 的 4点 DFT
10
1
3
1 0 0 1 0 4
0
,,nk
n
X k n x n n W

0 2 4 61 0 4 0 4 0 4 0 4 02,0,1,2,3,X n W x n W x n W x n W x n
0 2 0 24 0 4 0 4 0 4 00,1,2,3,W x n W x n W x n W x n
0 3 6 91 0 4 0 4 0 4 0 4 03,0,1,2,3,X n W x n W x n W x n W x n
0 3 2 14 0 4 0 4 0 4 00,1,2,3,W x n W x n W x n W x n








0 0 0 0
1 0 04 4 4 4
0 1 2 3
1 0 04 4 4 4
0 2 0 2
1 0 04 4 4 4
0 3 2 1
1 0 04 4 4 4
0,0,
1,1,
2,2,
3,3,
X n x nW W W W
X n x nW W W W
X n x nW W W W
X n x nW W W W










0
0
0
0
0,1 1 1 1
1,11
2,1 1 1 1
3,11
xn
xnjj
xn
xnjj







的四进制数 按二进制倒位序排列成0k0,1,2,30,2,1,3








1 0 0
1 0 0
1 0 0
1 0 0
0,0,1 1 1 1
2,1,1 1 1 1
1,2,11
3,3,11
X n x n
X n x n
X n x njj
X n x njj






00 '1 0 0 1 0 02 ),,nkNX k n W X k n?
01,nk3) 的 4点 DFT








0
0
0
00 0 0 0
20 1 0 1 64 4 4 4
0 1 2 3
20 1 0 1 64 4 4 4
20 2 0 2
20 1 0 1 64 4 4 4
30 3 2 1
20 1 0 1 64 4 4 4
,0,0
,1,1
,2,2
,3,3
k
k
k
Xk X k WW W W W
Xk X k WW W W W
Xk X k WW W W W
Xk X k WW W W W










0
0
0
0
1 0 1 6
1 0 1 6
2
1 0 1 6
3
1 0 1 6
,01 1 1 1
,111
,21 1 1 1
,311
k
k
k
X k W
X k Wjj
X k W
X k Wjj







233 1 l o g48F Nm L N N
0 1NW?
一个 4点 FFT不需乘法，只需 3次乘旋转因子
（ 除外）
2l o g2F
NmN?而基 -2FFT
4LN?基 -4FFT运算量：
每级有 N/4个 4点 FFT，共 L级（ L-1级要乘旋转因子）