? 直接 DFT方法 / CZT方法：当要求准确的 N点
DFT，且 N是素数时五,N为复合数的 FFT算法
——混合基算法基 -2FFT算法,2LN?
2 LN?当时
补零使满足 2LN?
混合基 FFT算法,N是复合数
1,整数的多基多进制表示形式
1 2 2 1 0 2LLn n n n n n自然序
0 1 2 2 1 22 LLn n n n n n倒位序
1 2 21 2 2 1 010 2 2 2 2LLLLn n n n n n
120 1 2 110 2 2 2LL LLn n n n n
2L N?（ 1）二进制：
0,1in?其中
0,,1iL
（ 2） r进制,LNr?
1 2 2 11 2 2 1 010 LLLLn n r n r n r n r n
120 1 2 110 LL LLn n r n r n r n
1 2 2 1 0LL rn n n n n n 0,,1inr其中
0,,1iL0 1 2 2 1LL r
rn n n n n n
（ 3）多基多进制（混合基）,12 LN r r r?
121 2 1 0 LLL r r rn n n n n
1 2 3 2 3 4 1 010 L L L L Ln n r r r n r r r n r n
110 1,1Lnr其中,，
220,1,,1Lnr
0 0,1,,1Lnr
0,1,,1i L inr即 0,,1iL
0 1 2 1 1 1 2 2 2 1 110 L L L Ln n r r r n r r r n r n
2121 0 1 2 1 LL LL r r rr r rn n n n n
例,1244N r r
1 0 4 45 4 1 1 1 1
4 4 1 0105 1 1 4 1 1 5
1 0 4 46 4 1 2 1 2
1 0 4 41 1 4 2 3 2 3
4 4 1 0106 2 1 4 2 1 9
4 4 1 0101 1 3 2 4 3 2 1 4p
1 2 0 1 010 4n n r n n n
0 1 1 0 110 4n n r n n n
0 0,1,2,3n?
1 0,1,2,3n?
2 2 3 1 3 0 2 1 010 3 2 2n n r r n r n n n n
0 1 2 1 1 2 0 1 010 4 3 4n n r r n r n n n n
0 0,1n?2 0,1,2,3n? 1 0,1,2n?
1 2 34 3 2N r r r例：
1 0 4 3 22 3 3 2 3 2 2 1 3 2 1
2 3 4 1 0102 3 1 2 3 4 3 1 4 2 3 2 3
1 0 4 3 23 3 2 0 2 1 1 0 1 1
2 3 4 1 0103 1 1 0 4 3 1 4 1 0 1 8
1 0 4 3 21 4 3 2 2 2 1 0 2 1 0
2 3 4 1 0101 4 0 1 2 4 3 0 4 1 2 6
2,的快速算法12N r r?
12N r r? 1 2 0n n r n
11
2
02
0,1,,1
0,1,,1
nr nr
nr
为 进制
12
1
01
0 1,,1
0,1,,1
kr kr
kr
,为 进制
21N r r? 1 1 0k k r k
12N r r?
21N r r?
行 列1r 2r 1n 行序号 0n 列序号
1r 2r行 列 0k 行变量 1k 列变量
11 1 0 1 0
0
,
N
nk
N
n
X k X r k k X k k x n W
21 2 1 0 1 1 0
01
11
2 1 0
00
rr
r n n r k k
N
nn
x r n n W
21 2 1 0 1 0 1 0 0 1 2 1 1
01
11
10
00
,
rr
r n k r n k n k r r n k
N N N N
nn
x n n W W W W
21
1 0 0 0 0 1
12
01
11
10
00
,
rr
n k n k n k
r N r
nn
x n n W W W
2 0 0 0 12
0
1
1 0 0
0
,
r
n k n k
Nr
n
X k n W W
2 012
0
1
'
1 0 0 2 0 1
0
,,
r
nk
r
n
X k n W X k k
的 DFT 算法12N r r?
(1) 改写 成xn10,x n n
2 1 0 1 0,x n x r n n x n n11
02
0,1,,1
0,1,,1
nr
nr
(2) 做 个 点 DFT,得为参量，输入变量,输出变量 的 点 DFT
2r 1r1 0 0,X k n
0n 1n 0k 1r
(3) N个 （旋转因子） 001 0 0,nkNX k n W'1 0 0,X k n?
(4) 做 个 点 DFT，得为参量，输入变量,输出变量 的 点 DFT
1r 2r2 0 1,X k k
0k 1k0n 2r
(5) 整序10,X k k X k? 1 1 0k r k k
12 4 2 8N r r例
102n n n
1
0
0,1,2,3
0,1
n
n
104k k k
1
0
0,1
0,1,2,3
k
k
1 1 0 1 01
11
1 3
1 0 0 1 0 1 0 4
00
,,,
r
n k n k
r
nn
X k n x n n W x n n W
0 0 0 0'1 0 0 1 0 0 1 0 0 8,,,n k n kNX k n X k n W X k n W
2 0 1 0 12
00
1 1
''
2 0 1 1 0 0 1 0 0 2
00
,,,
r
n k n k
r
nn
X k k X k n W X k n W
10,X k k X k
当 N为高组合素数时,12 LN r r r?
个 点 DFT,乘以 旋转因子2 3 1LLr r r r?r
个 点 DFTLr1 2 2 1LLr r r rXk整 序个 点 DFT,乘以 旋转因子1 3 1LLr r r r? 2r
个 点 DFT,乘以 旋转因子1 2 2LLr r r r? 1Lr?
L级 r点 DFT
LNr?
称基 算法，r? 基 算法2r? 2?
混合基算法（基 算法）12 LN r r r? 12 Lr r r?
4r? 4?基 算法混合基算法的运算量
12N r r? 不计译序、整序工作量
（ 2） 乘 N个旋转因子 复乘 N
总计,222 1 1 2 1 2 1Fm r r N r r N r r
2 1 1 1 2 2 1 21 1 2Fa r r r r r r N r r
（ 1） 个 点 DFT 2r 1r
复乘 221rr
2 1 1 1r r r?复加
（ 3） 个 点 DFT2r1r
212rr
1 2 2 1r r r?
复乘复加
2 ( 1 )FFm N a N N直接计算：,
混合基节省的运算量
2
1 2 1 211
NN R
N r r r r
1212N r r R
12 LN r r r?
1
1
L
Fi
i
m N r L
1L? 次 乘 N个旋转因子个 点 DFT2 3 1LLr r r r?r
个 点 DFT1 3 1LLr r r r? 2r
个 点 DFTLr1 2 2 1LLr r r r
DFT，且 N是素数时五,N为复合数的 FFT算法
——混合基算法基 -2FFT算法,2LN?
2 LN?当时
补零使满足 2LN?
混合基 FFT算法,N是复合数
1,整数的多基多进制表示形式
1 2 2 1 0 2LLn n n n n n自然序
0 1 2 2 1 22 LLn n n n n n倒位序
1 2 21 2 2 1 010 2 2 2 2LLLLn n n n n n
120 1 2 110 2 2 2LL LLn n n n n
2L N?（ 1）二进制：
0,1in?其中
0,,1iL
（ 2） r进制,LNr?
1 2 2 11 2 2 1 010 LLLLn n r n r n r n r n
120 1 2 110 LL LLn n r n r n r n
1 2 2 1 0LL rn n n n n n 0,,1inr其中
0,,1iL0 1 2 2 1LL r
rn n n n n n
（ 3）多基多进制（混合基）,12 LN r r r?
121 2 1 0 LLL r r rn n n n n
1 2 3 2 3 4 1 010 L L L L Ln n r r r n r r r n r n
110 1,1Lnr其中,，
220,1,,1Lnr
0 0,1,,1Lnr
0,1,,1i L inr即 0,,1iL
0 1 2 1 1 1 2 2 2 1 110 L L L Ln n r r r n r r r n r n
2121 0 1 2 1 LL LL r r rr r rn n n n n
例,1244N r r
1 0 4 45 4 1 1 1 1
4 4 1 0105 1 1 4 1 1 5
1 0 4 46 4 1 2 1 2
1 0 4 41 1 4 2 3 2 3
4 4 1 0106 2 1 4 2 1 9
4 4 1 0101 1 3 2 4 3 2 1 4p
1 2 0 1 010 4n n r n n n
0 1 1 0 110 4n n r n n n
0 0,1,2,3n?
1 0,1,2,3n?
2 2 3 1 3 0 2 1 010 3 2 2n n r r n r n n n n
0 1 2 1 1 2 0 1 010 4 3 4n n r r n r n n n n
0 0,1n?2 0,1,2,3n? 1 0,1,2n?
1 2 34 3 2N r r r例：
1 0 4 3 22 3 3 2 3 2 2 1 3 2 1
2 3 4 1 0102 3 1 2 3 4 3 1 4 2 3 2 3
1 0 4 3 23 3 2 0 2 1 1 0 1 1
2 3 4 1 0103 1 1 0 4 3 1 4 1 0 1 8
1 0 4 3 21 4 3 2 2 2 1 0 2 1 0
2 3 4 1 0101 4 0 1 2 4 3 0 4 1 2 6
2,的快速算法12N r r?
12N r r? 1 2 0n n r n
11
2
02
0,1,,1
0,1,,1
nr nr
nr
为 进制
12
1
01
0 1,,1
0,1,,1
kr kr
kr
,为 进制
21N r r? 1 1 0k k r k
12N r r?
21N r r?
行 列1r 2r 1n 行序号 0n 列序号
1r 2r行 列 0k 行变量 1k 列变量
11 1 0 1 0
0
,
N
nk
N
n
X k X r k k X k k x n W
21 2 1 0 1 1 0
01
11
2 1 0
00
rr
r n n r k k
N
nn
x r n n W
21 2 1 0 1 0 1 0 0 1 2 1 1
01
11
10
00
,
rr
r n k r n k n k r r n k
N N N N
nn
x n n W W W W
21
1 0 0 0 0 1
12
01
11
10
00
,
rr
n k n k n k
r N r
nn
x n n W W W
2 0 0 0 12
0
1
1 0 0
0
,
r
n k n k
Nr
n
X k n W W
2 012
0
1
'
1 0 0 2 0 1
0
,,
r
nk
r
n
X k n W X k k
的 DFT 算法12N r r?
(1) 改写 成xn10,x n n
2 1 0 1 0,x n x r n n x n n11
02
0,1,,1
0,1,,1
nr
nr
(2) 做 个 点 DFT,得为参量，输入变量,输出变量 的 点 DFT
2r 1r1 0 0,X k n
0n 1n 0k 1r
(3) N个 （旋转因子） 001 0 0,nkNX k n W'1 0 0,X k n?
(4) 做 个 点 DFT，得为参量，输入变量,输出变量 的 点 DFT
1r 2r2 0 1,X k k
0k 1k0n 2r
(5) 整序10,X k k X k? 1 1 0k r k k
12 4 2 8N r r例
102n n n
1
0
0,1,2,3
0,1
n
n
104k k k
1
0
0,1
0,1,2,3
k
k
1 1 0 1 01
11
1 3
1 0 0 1 0 1 0 4
00
,,,
r
n k n k
r
nn
X k n x n n W x n n W
0 0 0 0'1 0 0 1 0 0 1 0 0 8,,,n k n kNX k n X k n W X k n W
2 0 1 0 12
00
1 1
''
2 0 1 1 0 0 1 0 0 2
00
,,,
r
n k n k
r
nn
X k k X k n W X k n W
10,X k k X k
当 N为高组合素数时,12 LN r r r?
个 点 DFT,乘以 旋转因子2 3 1LLr r r r?r
个 点 DFTLr1 2 2 1LLr r r rXk整 序个 点 DFT,乘以 旋转因子1 3 1LLr r r r? 2r
个 点 DFT,乘以 旋转因子1 2 2LLr r r r? 1Lr?
L级 r点 DFT
LNr?
称基 算法，r? 基 算法2r? 2?
混合基算法（基 算法）12 LN r r r? 12 Lr r r?
4r? 4?基 算法混合基算法的运算量
12N r r? 不计译序、整序工作量
（ 2） 乘 N个旋转因子 复乘 N
总计,222 1 1 2 1 2 1Fm r r N r r N r r
2 1 1 1 2 2 1 21 1 2Fa r r r r r r N r r
（ 1） 个 点 DFT 2r 1r
复乘 221rr
2 1 1 1r r r?复加
（ 3） 个 点 DFT2r1r
212rr
1 2 2 1r r r?
复乘复加
2 ( 1 )FFm N a N N直接计算：,
混合基节省的运算量
2
1 2 1 211
NN R
N r r r r
1212N r r R
12 LN r r r?
1
1
L
Fi
i
m N r L
1L? 次 乘 N个旋转因子个 点 DFT2 3 1LLr r r r?r
个 点 DFT1 3 1LLr r r r? 2r
个 点 DFTLr1 2 2 1LLr r r r
