七、分裂基 FFT算法对偶序号使用基 -2FFT算法，对奇序号使用基 -
4FFT算法,称分裂基 FFT算法针对 的算法中具有最少乘法次数，且同 址 运算。
2LN?
将 分成三个序列。?xn 2LNxn
1 2x r x r? 0,,12Nr


2
3
4 1
0,,1
443
x l x l N
l
x l x l



1
0
N
nk
N
n
X k x n W


1 1 1
2 4 4
4 1 4 32
0 0 0
2 4 1 4 3
N N N
l k l krk
N N N
r l l
x r W x l W x l W





1 1 1
2 4 4
3
1 2 2 4 3 4
0 0 0
N N N
rk k lk k lk
N N N N N
r l l
x r W W x l W W x l W



31 2 3kkNNX k W X k W X k
偶序号的 点 DFT2N 奇 序号的 点 DFT4N
利用周期性 分成四段：Xk
31 2 3kkNNX k X k W X k W X k
31 2 344 kkNNNNX k X k jW X k jW X k
31 2 33 44 kkNNNNX k X k jW X k jW X k
31 2 32 kkNNNX k X k W X k W X k
0,,14Nk
的第一级分解得 4个分裂基21 6 4NXk
2Xk3Xk1Xk同样对,,作进一步分解。
2Xk3Xk和 的第二级分解分别是基 -4的 4点 DFT。
1Xk的第二级分解得 2个分裂基。
一个基 -4的 4点 DFT和 2个基 -2的 4点 DFT。
基 -2，基 -4等基本碟形结都没有乘法，只有每个分裂基有两次复乘。
运算量,2LN?
2L? 2 0B?
3L? 3 2B?
4L? 24 3 22 2 6LB B B
5L? 25 4 32 2 1 8LB B B
分裂基碟形数,21222LL L LB B B
2
1 l og
3Fm N N? 22
31lo g lo g
82N N N N