第四章 快速傅立叶变换 (FFT)
主要内容：
DFT的问题及解决途径
FFT的原理和复杂性
按时间抽取的 FFT算法
按频率抽取的 FFT算法
离散傅立叶反变换的快速算法
线性调频 z变换（ chirp－ z 变换）算法
线性卷积的 FFT算法
DFT算法存在的问题
DFT直接计算存在的问题：
设 x(n)为 N点有限长序列，正反变换计算量相同
1
0
1
0
1-Nn0 )(
1
)()(
1-Nk0 )()()(
N
k
nk
N
N
n
nk
N
WkX
N
kXI D F Tnx
WnxnxD F TkX
，
，
)3()2()1()0()()( 34244043
0
4
kkkk
n
nk WxWxWxWxWnxkX
)3()2()1()0()3(
)3()2()1()0()2(
)3()2()1()0()1(
)3()2()1()0()0(
9
4
6
4
3
4
0
4
6
4
4
4
2
4
0
4
3
4
2
4
1
4
0
4
0
4
0
4
0
4
0
4
WxWxWxWxX
WxWxWxWxX
WxWxWxWxX
WxWxWxWxX
例 N＝ 4：
N点 DFT的直接计算量,
DFT算法存在的问题
1,乘法次数：
对每一个 k,N次复数乘法 【 4N次实乘和 2N次实加 】
1个 复乘 等于 4 四个实乘和 2 个实加；
N个 k,次复数乘法
2,加法次数：
对每一个 k,N－ 1次复加 【 2（ N－ 1）次实加 】
N个 k,N（ N－ 1）次复加即和 成正比。2N
例 N＝ 1024，则有 1048576次复乘（约 400万次实乘），假定运算器的指令速度为 100MIPS，则计算时间大约为 4秒。
2N
)())(( adcbjbdacjdcjba
DFT算法存在的问题
改进办法：
1,旋转因子 的对称性和周期性m
NW
例：求当 N＝ 4时,X(2)的值
（ 1) 对称性：
（ 2) 周期性,
kNNkN WW )2/(
kNnNknNnNkN WWW )()(
)() ] }3()1([)]2()0({[
)()]3()1([)]2()0([
)3()2()1()0()()2(
0
4
2
4
0
4
6
4
4
4
2
4
0
4
3
0
2
4
对称性－＝
周期性
Wxxxx
WxxWxx
WxWxWxWxWnxX
n
n
通过合并，使乘法次数由 4次减少到 1次，运算量减少。
mkn mNm knmNknN WWW //（ 3)可约性,
0NW2
N
NW
kNW
kNW?
kN?20
DFT算法存在的问题
N点 DFT的复乘次数与 N的平方成比例,显然 N较小时乘法次数大大减少 。 利用上述旋转因子的特性,可以将有些项 合并,并将 DFT分解为短序列,从而降低运算次数,提高运算速度 。
1965年,库利 (cooley)和图基 (Tukey)首先提出 FFT算法 。 对于 N点 DFT,仅需 (N/2)log2N 次复数乘法运算 。
例如 N=1024=210 时,需要 (1024/2)log2 210
=512*10=5120次 。 5120/1048576=4.88%,速度提高
20倍 。
分为时域抽取 （ DIT） 和频域抽取 （ DIF） 两大类 。
按时间抽取的基－ 2 FFT算法以 N＝ 4为例
)3()1()2()0( )3()2()1()0()3(
)3()1()2()0( )3()2()1()0()2(
)3()1()2()0( )3()2()1()0()1(
)3()1()2()0( )3()2()1()0()0(
1
4
1
4
1
4
1
4
1
4
1
4
xxWxxWxxWxxX
xxxxxxxxX
xxWxxWxxWxxX
xxxxxxxxX
A B
A B
C D
C D
运算流图
)0(x
)2(x
)1(x
)3(x
A
-1
C
-1
B
D 14W
)0(X
)2(X-1
)1(X
)3(X-1
按时间抽取的基－ 2 FFT算法一、算法原理
1,先将 x(n)按 n的奇偶分为两组作 DFT,设 N=2L （ L大于等于 2）,不足时,可补些零,这样一个 N点的 DFT分解为两个 N/2点的 DFT。
)()(
)12()2(
)12()2(
1
0
2
1
0
2
1
0
)12(
1
0
2
22
22
kFWkE
WrxWWrx
WrxWrx
k
N
r
rk
N
k
N
r
rk
N
r
kr
N
r
rk
N
NN
NN
1
0
1
0
1
0
)()()()(
N
n
n
N
n
n
kn
N
kn
N
N
n
kn
N WnxWnxWnxkX
为偶数 为奇数
(一 )N/2点 DFT
2,分解说明：
120 )2()(
1
0 2
2
NkWrxkE N
r
rk
N
120 )12()(
1
0 2
2
NkWrxkF N
r
rk
N
E(k)和 F(k)均为 N/2点的 DFT,均以 N/2为周期 ；
因 W 是以 N为周期，故 X(k)是以 N为周期；
X(k)=E(k)+W F(k)只能确定出 X(k)的 k=
个值，即前一半的结果。 1,,1,0 2?N?
k
N
k
N
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法
3,X(k)后一半的确定由旋转因子的周期性,
rkkr
N
N
N WW 222
)(
)()2()2()2(
1
0
)(
1
0
2
2
2
2
2
kEWrxWrxkNE
N
N
N
N
N
r
rkkr
r
这就是说,E(k)和 F(k)的后一半分别等于其前一半的值。
同理：
)()2( kFkNF
kNkNNkN WWWW NN 22 )(?
120 )()()2()2()2( 2 NkkFWkENkFWNkENkX kNkN N
可 见,X(k)的后一半，也完全由 E(k)和 F(k)的前一半确定。
即 N点的 DFT可由两个 N/2点的 DFT来计算。
4,蝶形运算－－流图表示蝶形运算流图 （ N/2个蝶形 ):
-1
)(kX
)2( kNX?
)(kE
)(kF
kNW
)()()
2
(
)()()(
kFWkENkX
kFWkEkX
k
N
k
N
)1,,1,0(
)1,,1,0(
2
2
N
N
k
k
由 E(k),F(k)表示 X(k)的运算是一种特殊的运算 -碟形运算按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法
(二 ) N/4点 DFT
由于 N=2 L,所以 N/2仍为偶数,可以进一步把每个 N/2
点的序列再按其奇偶部分分解为两个 N/4的子序列。
)()()
4
(
)()()(
2
2
kBWkA
N
kE
kBWkAkE
k
N
k
N
)1,,1,0( 4 Nk?
)()()
4
(
)()()(
2
2
kDWkC
N
kF
kDWkCkF
k
N
k
N
其中,
kl
l
N
N
WlxkA
4
4 1
0
)4()(?
kl
l
N
N
WlxkB
4
4 1
0
)24()(?
kl
l
N
N
WlxkC
4
4 1
0
)14()(?
kl
l
N
N
WlxkD
4
4 1
0
)34()(?
蝶形图同上类似。
按时间抽取的基－ 2 FFT算法按上述办法不断划分下去，直到最后剩下 2点 DFT,2
点 DFT实际上只有加减运算。
这种 FFT算法，是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法。
例：作 N＝ 8时 FFT的运算流图由上推证：
3
0
4)2()(
r
rkWrxkE?
3
0
4)12()(
r
rkWrxkF
kl
l
WlxkA 2
1
0
)4()(?
kl
l
WlxkB 2
1
0
)24()(?
kl
l
WlxkC 2
1
0
)14()(?
kl
l
WlxkD 2
1
0
)34()(?
(三 ) 2点 DFT
按时间抽取的基－ 2 FFT算法例续,N＝ 8时 FFT的运算
)4()0()4()0()1(
)4()0()4()0()0(
1
2
0
2
xxxWxA
xxxWxA
展开得：
)7()3()1(
)7()3()0(
)5()1()1(
)5()1()0(
)6()2()1(
)6()2()0(
xxD
xxD
xxC
xxC
xxB
xxB
例续,N=8点 FFT的运算流图：
)0(x
)4(x
)2(x
)6(x
)1(x
)5(x
)3(x
)7(x
WN0
A(0)
-1
A(1)
WN0
WN0
W 0N
-1
-1
-1
B(0)
B(1)
D(0)
C(0)
C(1)
D(1)
WN0
E(0)
E(2)
-1W
N
2
WN0
WN2
E(1)
E(3)
F(0)
F(1)
F(2)
F(3)
X(0)
X(4)N0W-1
-1
-1
-1
-1
-1
-1
X(1)
X(2)
X(3)
X(5)
X(6)
X(7)
N
1
N
2
N
3
W
W
W
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法由上例分析可知,N=8= 需三级蝶形运算,由此可知：32
N=2L 共需 L级蝶形运算,L＝ log2 N ；
每级都由 N/2个蝶形运算组成；
每个蝶形运算有一次复乘,两次复加 。
因此,N点的 FFT的运算量为：
复乘,mF =（ N/2） *L=（ N/2） *log2 N
复加,aF =2*（ N/2） *L=N*log2 N
即计算量远比 DFT的计算量小。
N越大,FFT的优点越明显。
二 运算量分析按时间抽取的基－ 2 FFT算法三 DIT－ FFT算法的特点
1.原位运算,输入数据,中间结果和输出均用同一存储器 。
)0(x
)4(x
)2(x
)6(x
)1(x
)5(x
)3(x
)7(x
WN0
A(0)
-1
A(1)
WN0
WN0
W 0N
-1
-1
-1
B(0)
B(1)
D(0)
C(0)
C(1)
D(1)
WN0
E(0)
E(2)
-1W
N2
WN0
WN2
-1
-1
-1
E(1)
E(3)
F(0)
F(1)
F(2)
F(3)
X(0)
X(4)N0W
-1
-1
-1
-1
X(1)
X(2)
X(3)
X(5)
X(6)
X(7)
N1
N2
N3
W
W
W
也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。原位运算的结构可以节省存储单元，降低设备成本。
按时间抽取的基－ 2 FFT算法
2,倒位序规律由图知输出 X(k)按自然顺序排列在存储单元，而输入是按下列顺序排列,
）；）； 7(),3(),5(),1(6(),2(),4(),0( xxxxxxxx
这种顺序称作倒位序,即二进制数倒位。
造成倒位序的原因在于输入 x(n)按标号 n的奇偶不断分组。
自然顺序 二进制表示 码位倒置 码位倒置顺序
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
按时间抽取的基－ 2 FFT算法
2,倒位序规律码位倒置变换后,X(k)按照正常序列，但 x(n)不再是自然顺序，
如 N=8，有
x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)
但其对应于二进制编码有
x(000),x(100),x(010),x(110),x(001),x(101),x(011),
x(111)
将上述码翻转后有
x(000),x(001),x(010),x(011),x(100),x(101),x(110),
x(111)，刚好是
x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)
为自然顺序，这样的规律有利于编程。
3.,级”与“组”（或群）
N点 FFT共有 L级迭代，流图中的每一列为一级迭代；
每一级中，由交叉蝶形组成一个群。
第一级有 N/2个群，第二级 N/4个群，依次类推，最后一级 1个群。
按时间抽取的基－ 2 FFT算法四 DIT－ FFT其它形式流图输入自然顺序、输出倒位序的 DIT―FFT运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3W N
2
W N
0
W N
0
W N
0
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法输入输出均为自然顺序的 DIT―FFT运算流图。
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3
W N
2
W N
0
W N
0
W N
0
按频率抽取（ DIF）的基－ 2 FFT算法一 算法原理
1,N点 DFT的另一种表达形式
1
0
)()(
N
n
nk
NWnxkX
1
2/
1
0
)()(
2 N
Nn
nk
N
n
nk
N WnxWnx
N
nk
N
n
k
N WW
Nnxnx
N
N?
1
0
2
2)
2
()(
1
0
)(
1
0
2
2
2
)
2
()(
N
N
N
n
kn
N
n
nk
N W
NnxWnx
])1([ 2 kkNNW
nk
N
n
k WNnxnxkX
N
1
0
2
)
2
()1()()( 1,,1,0 Nk?
2,N点 DFT按 k的奇偶分组分为两个 N/2点的 DFT
当 k为偶数，即 k=2r时,(-1)k =1；
当 k为奇数，即 k=2r+1 时,(-1)k =-1 。
这时 X(k) 可分为两部分：
nr
N
n
WNnxnxrX
N
2
1
0
2
)2()()2(?
1,,1,0 2 Nr?
nr
n
N
N
WNnxnx
2
2 1
0
)2()(?
nr
n
n
N
rn
N
n
N
N
N
WW
N
nxnx
W
N
nxnxrX
2
2
2
1
0
)12(
1
0
)
2
()(
)
2
()()12(
1,,1,0 2 Nr?
上面两式均为 N/2的 DFT。
按频率抽取（ DIF）的基－ 2 FFT算法
蝶形运算令：
-1
)2()()(11 Nnxnxnx
n
NW
Nnxnxnx
)
2
()()(12
nNW
)2( Nnx?
)(nx
1,,1,0 2 Nn?
n
NW
NnxnxnxNnxnxnx )
2()()( )2()()( 1211
则蝶形运算图如下：
按频率抽取（ DIF）的基－ 2 FFT算法按频率抽取（ DIF）的基－ 2 FFT算法
3,再将 N/2点 DFT按 k的奇偶各分解为两个 N/4点的
DFT
令 r＝ 2l与 r＝ 2l+1
nr
N
n
WnxrX
N
2
1
0
11
2
)()2(?
nl
N
n
WNnxnxlX
N
4
1
0
1111
4
)4()()4(?
1
0 2
1111
4
4
)4()()24(
N
N
n
nln
N WW
NnxnxlX
1,,1,0
1,,1,0
4
4
N
N
n
l
nr
N
n
WnxrX
N
2
1
0
12
2
)()12(?
nl
N
n
WNnxnxlX
N
4
1
0
1212
4
)4()()14(?
nl
n
n
N N
N
WWNnxnxlX
4
4 1
0 2
1212 )4()()34(?
按频率抽取（ DIF）的基－ 2 FFT算法
4,2点 DFT
依上述方法，按 k的奇偶不断分解 L－ 1次，直至最终只有 2点的 DFT
这种分解方法是先把输入序列分成前后两半，然后把输出序列按序号 k的奇偶进行分解为短序列，即在频域进行抽取，简称 DIF―FFT。
二 例如 N=8时 DIF－ FFT的运算规则
7,,2,1,0k
7
0
8)()(
n
nkWnxkX
3
0
8)4()1()(
n
nkk Wnxnx
122 rrk 与令
3
0
4)4()()2(
n
rnWnxnxrX
3
0
48)4()( )12(
n
rnn WWnxnxrX 3,2,1,0
3,2,1,0
n
r
nWnxnxnxnxnxnx 81211 )4()()( )4()()(令
3
0
412
3
0
411 )()12( )()2(
n
rn
n
rn WnxrXWnxrX则按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF的运算规则
122 llr 与再令
1
0
241212
1
0
21212
1
0
241111
1
0
21111
)2()( )34(
)2()()14(
)2()( )24(
)2()()4(
n
nln
n
nl
n
nln
n
nl
WWnxnxlX
WnxnxlX
WWnxnxlX
WnxnxlX则
1,0
1,0
n
l
按频率抽取（ DIF）的基－ 2 FFT算法按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF的运算规则
nWnxnxnx
nxnxnx
812
11
)4()()(
)4()()( 已知 3,2,1,0?n
n
n
Wnxnxnx
nxnxnx
Wnxnxnx
nxnxnx
4121224
121223
4111122
111121
)2()()(
)2()()(
)2()()(
)2()()(
令 1,0?n
1
0
224
1
0
223
1
0
222
1
0
221
)()34( )()14(
)()24( )()4(
n
nl
n
nl
n
nl
n
nl
WnxlXWnxlX
WnxlXWnxlX
则
1,0
1,0
n
l
按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF－ FFT的信号流图
)0(x
)1(x
)2(x
)3(x
)4(x
)5(x
)6(x
)7(x
)0(11x
-1
08W )0(12x
)1(11x
-1
18W )1(12x
-1
)2(11x
28W )2(12x
-1
)3(11x
38W )3(12x
)0(21x
-1
08W )0(22x
-1
)1(21x
28W )1(22x
)0(23x
08W )0(24x
-1
-1
)1(23x
28W )1(24x
)0(X
)4(X
08W
-1
)2(X
)6(X
08W
-1
)1(X
)5(X
08W
-1
)3(X
)7(X
08W
-1
四 DIF－ FFT的运算特点
1,原位运算蝶形运算的通用表达式
r
Nmmm
mmm
WjXkXjX
jXkXkX
)]()([)(
)()()(
11
11
-1 WNr
)(1 kXm?
)(1 jXm?
)()()( 11 jXkXkX mmm
rNmmm WjXkXjX )]()([)( 11
蝶形图按频率抽取（ DIF）的基－ 2 FFT算法三 DIF－ FFT的运算量分析复乘：
NN
2l o g21
复加,NN NN
22 l o gl o g22
即和 DIT－ FFT的计算量相同。
五 DIF法与 DIT法的异同
1,相同点
(1)进行 原位运算 ；
(2)运算量相同,复乘（ N/2) Log2N次,复加 N Log2N次。
2,不同点
(1) DIT输入为倒位序,输出为自然顺序； DIF正好与此相反。但 DIT
也有输入为自然顺序,输出为倒位序的情况。
(2) 蝶形运算不同,
两种蝶形运算 流图 互为转置：将流图的所有支路方向都反向，
交换输入和输出，节点变量值不变。
基本蝶形的复乘,DIT在输入端、先乘后加；
DIF在输出端、先加后乘。
按频率抽取（ DIF）的基－ 2 FFT算法离散傅立叶反变换的快速计算方法－ IFFT
一 稍微变动 FFT程序和参数实现 IFFT
nkN
N
k
N
n
nk
N
WkX
N
kXI D F Tnx
WnxnxD F TkX
1
0
1
0
)(
1
)()(
)()()(
比较两式可知：
只要 DFT的每个系数 换成,最后再乘以常数
1/N就可以得到 IDFT的快速算法 --IFFT。
可以将常数 1/N分配到每级运算中,∵,
也就是每级 蝶形运算均乘以 1/2。
nkNW nkNW?
L
LN )2
1(
2
11
DIT―IFFT的运算流图
W
N
0
2
1
21 x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
21
21
21
W
N
1
2
1
W
N
2
2
1
W
N
3
2
1
21
21
W
N
0
2
1
W
N
2
2
1
21
21
W
N
0
2
1
W
N
2
2
1
21
W
N
0
2
1
21
W
N
0
2
1
21
21
W
N
0
2
1
W
N
0
2
1
离散傅立叶反变换的快速计算方法－ IFFT
离散傅立叶反变换 (IDFT)的快速计算方法由定义,
1
0
)(1)]([)( N
k
knNWkXNkXI D F Tnx
1
0
)()]([)( N
k
knNWnxnxD F TkX
两者作比较，得到启发方法一,修改 DFT运算中的各个系数 -----将 改为knNW knNW?,最后乘以 1/N
N1同时将常数 分解为,分散到各级中，即每一级都乘以因子 21M)21(
方法二,不修改 FFT的程序和参数，利用共轭变换的方法
∵
1N
0k
knN** )(1)( WkXNnx
***1N
0k
knN* )]}([{1])([1)( kXD F TNWkXNnx
∴
)(* kX取共轭 )]}([{ * kXD F T直接访问FFT程序*取共轭 乘系数 )(1 * nxN?)(kX即三 实序列的 FFT算法设 x(n)为 N点实序列，取 x(n)的偶数点和奇数点分别作为新构造序列
y(n)的实部和虚部，即
12,,1,0),12()(),2()( 21 Nnnxnxnxnx?
12,,1,0),2()(1 Nnnjxnxy?
对 y(n)进行 N/2点 FFT,输出 Y(k),则
12,,1,0,)()()(
)()()(
22
11
Nk
kjYnxD F TkX
kYnxD F TkX
op
ep?
由 DIT― FFT的思想得
12,,1,0),()()( 21 NkkXWkXkX kN?
由于 x(n)为实序列，所以 X(k)具有共轭对称性,X(k)的另外 N/2点的值为,
12,2,1),()( * NKKXKNX?
例题 1：
设 x(n)是长度为 2N的有限长实序列,X(k)为 x(n)的 2N
点 DFT。要求：试设计用一次 N点 FFT完成计算 X(k)的高效算法。
解：
本题的解题思路是 DIT－ FFT思想；
在时域分别抽取偶数点和奇数点 x(n)，得到两个 N点实序列 x1(n)
和 x2(n)：
x1(n) = x(2n),n = 0,1,……,N-1
x2(n) = x(2n+1),n = 0,1,……,N-1
根据 DIT－ FFT的思想，只要求得 x1(n)和 x2(n)的 N点 DFT，再经过简单的一级蝶形运算就可得到 x(n)的 2N点 DFT。
因为 x1(n)和 x2(n)均为实序列，所以根据 DFT的共轭对称性，可用一次 N点 FFT求得 X1(k)和 X2(k)。做法如下：
令 y(n) = x1(n) + jx2(n)? Y(k) = DFT[y(n)]
则 X1(k)=DFT[x1(n)]=Yep(k)=[Y(k)+Y*(N-k)]/2
jX2(k)=DFT[x2(n)]=Yop(k)=[Y(k)-Y*(N-k)]/2
2N点 DFT[x(n)] = X(k)可由 X1(k)和 X2(k)得到：
X(k) = X1(k) + W2NkX2(k)
X(k+N) = X1(k) - W2NkX2(k),k=0,1,…,N-1
因此，通过一次 N点 FFT计算完成了计算 2N点 DFT。
例题 2：
设 x(n)是长度为 2N的有限长实序列,X(k)为 x(n)的 2N
点 DFT。若已知 X(k)，要求：试设计用一次 N点 IFFT完成计算 x(n )的高效算法。
解：设 x1(n) = x(2n),n = 0,1,……,N -1
x2(n) = x(2n+1),n = 0,1,……,N -1
X1(k) = DFT[x1(n)],k = 1,1,…,N -1
X2(k) = DFT[x2(n)],k = 1,1,…,N -1
由 DIT－ FFT的算法，有以下关系式：
X(k) = X1(k) + W2NkX2(k),k = 1,1,…,N -1
X(k+N) = X1(k) - W2NkX2(k)
由以上两可解出 X1(k)和 X2(k) 。
X1(k) = [X(k) + X(k+N)]/2
X2(k) = W2N-K[X(k) – X(k+N)]/2
由上面分析可得出运算过程如下：
（ 1）由 X(k)计算出 X1(k)和 X2(k)；
（ 2）由 X1(k)和 X2(k)构成 N点频域序列 Y(k)：
Y(k) = X1(k) + jX2(k) = Yep(k) + Yop(k)
对 Y(k) 进行 N点 IFFT得到 y(n)
x1(n) = yep(n),jx2(n) = yop(k),进行 N点 IFFT运算，得到由 x1(n)和 x2(n)合成 x(n)：
当 n = 偶数（ n = 0,1,…,2N-1）时 x(n) = x1(n/2)
当 n = 奇数（ n = 0,1,…,2N-1）时 x(n) = x2((n-1)/2)
其他快速算法
1、频率抽取基 4 FFT算法令 N=4M，对 N点的 DFT可按如下方法作频率抽取，
)()()()()(
1
4/3
14/3
2/
12/
4/
14/
0
N
Nn
nk
N
N
Nn
nk
N
N
Nn
nk
N
N
n
nk
N WnxWnxWnxWnxkX
其他快速算法
2、分裂算法基 2频率抽取算法在每一级中每一组的上半部的输出都没有乘以旋转因子（对应于偶序列号），分裂算法是对偶序列号使用基 2算法，对奇序列号使用基 4算法。
在针对 N=2M的算法中，分裂基算法被认为是最好的快速傅里叶算法。
其他快速算法
3、离散哈特莱变换（ DHT）
DHT的快速算法基本思想与 DFT类似，有基于 2的、基于 4的和分裂基快速算法。
只是＆函数不同，所以计算公式和运算流程机构不同。
主要内容：
DFT的问题及解决途径
FFT的原理和复杂性
按时间抽取的 FFT算法
按频率抽取的 FFT算法
离散傅立叶反变换的快速算法
线性调频 z变换（ chirp－ z 变换）算法
线性卷积的 FFT算法
DFT算法存在的问题
DFT直接计算存在的问题：
设 x(n)为 N点有限长序列，正反变换计算量相同
1
0
1
0
1-Nn0 )(
1
)()(
1-Nk0 )()()(
N
k
nk
N
N
n
nk
N
WkX
N
kXI D F Tnx
WnxnxD F TkX
，
，
)3()2()1()0()()( 34244043
0
4
kkkk
n
nk WxWxWxWxWnxkX
)3()2()1()0()3(
)3()2()1()0()2(
)3()2()1()0()1(
)3()2()1()0()0(
9
4
6
4
3
4
0
4
6
4
4
4
2
4
0
4
3
4
2
4
1
4
0
4
0
4
0
4
0
4
0
4
WxWxWxWxX
WxWxWxWxX
WxWxWxWxX
WxWxWxWxX
例 N＝ 4：
N点 DFT的直接计算量,
DFT算法存在的问题
1,乘法次数：
对每一个 k,N次复数乘法 【 4N次实乘和 2N次实加 】
1个 复乘 等于 4 四个实乘和 2 个实加；
N个 k,次复数乘法
2,加法次数：
对每一个 k,N－ 1次复加 【 2（ N－ 1）次实加 】
N个 k,N（ N－ 1）次复加即和 成正比。2N
例 N＝ 1024，则有 1048576次复乘（约 400万次实乘），假定运算器的指令速度为 100MIPS，则计算时间大约为 4秒。
2N
)())(( adcbjbdacjdcjba
DFT算法存在的问题
改进办法：
1,旋转因子 的对称性和周期性m
NW
例：求当 N＝ 4时,X(2)的值
（ 1) 对称性：
（ 2) 周期性,
kNNkN WW )2/(
kNnNknNnNkN WWW )()(
)() ] }3()1([)]2()0({[
)()]3()1([)]2()0([
)3()2()1()0()()2(
0
4
2
4
0
4
6
4
4
4
2
4
0
4
3
0
2
4
对称性－＝
周期性
Wxxxx
WxxWxx
WxWxWxWxWnxX
n
n
通过合并，使乘法次数由 4次减少到 1次，运算量减少。
mkn mNm knmNknN WWW //（ 3)可约性,
0NW2
N
NW
kNW
kNW?
kN?20
DFT算法存在的问题
N点 DFT的复乘次数与 N的平方成比例,显然 N较小时乘法次数大大减少 。 利用上述旋转因子的特性,可以将有些项 合并,并将 DFT分解为短序列,从而降低运算次数,提高运算速度 。
1965年,库利 (cooley)和图基 (Tukey)首先提出 FFT算法 。 对于 N点 DFT,仅需 (N/2)log2N 次复数乘法运算 。
例如 N=1024=210 时,需要 (1024/2)log2 210
=512*10=5120次 。 5120/1048576=4.88%,速度提高
20倍 。
分为时域抽取 （ DIT） 和频域抽取 （ DIF） 两大类 。
按时间抽取的基－ 2 FFT算法以 N＝ 4为例
)3()1()2()0( )3()2()1()0()3(
)3()1()2()0( )3()2()1()0()2(
)3()1()2()0( )3()2()1()0()1(
)3()1()2()0( )3()2()1()0()0(
1
4
1
4
1
4
1
4
1
4
1
4
xxWxxWxxWxxX
xxxxxxxxX
xxWxxWxxWxxX
xxxxxxxxX
A B
A B
C D
C D
运算流图
)0(x
)2(x
)1(x
)3(x
A
-1
C
-1
B
D 14W
)0(X
)2(X-1
)1(X
)3(X-1
按时间抽取的基－ 2 FFT算法一、算法原理
1,先将 x(n)按 n的奇偶分为两组作 DFT,设 N=2L （ L大于等于 2）,不足时,可补些零,这样一个 N点的 DFT分解为两个 N/2点的 DFT。
)()(
)12()2(
)12()2(
1
0
2
1
0
2
1
0
)12(
1
0
2
22
22
kFWkE
WrxWWrx
WrxWrx
k
N
r
rk
N
k
N
r
rk
N
r
kr
N
r
rk
N
NN
NN
1
0
1
0
1
0
)()()()(
N
n
n
N
n
n
kn
N
kn
N
N
n
kn
N WnxWnxWnxkX
为偶数 为奇数
(一 )N/2点 DFT
2,分解说明：
120 )2()(
1
0 2
2
NkWrxkE N
r
rk
N
120 )12()(
1
0 2
2
NkWrxkF N
r
rk
N
E(k)和 F(k)均为 N/2点的 DFT,均以 N/2为周期 ；
因 W 是以 N为周期，故 X(k)是以 N为周期；
X(k)=E(k)+W F(k)只能确定出 X(k)的 k=
个值，即前一半的结果。 1,,1,0 2?N?
k
N
k
N
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法
3,X(k)后一半的确定由旋转因子的周期性,
rkkr
N
N
N WW 222
)(
)()2()2()2(
1
0
)(
1
0
2
2
2
2
2
kEWrxWrxkNE
N
N
N
N
N
r
rkkr
r
这就是说,E(k)和 F(k)的后一半分别等于其前一半的值。
同理：
)()2( kFkNF
kNkNNkN WWWW NN 22 )(?
120 )()()2()2()2( 2 NkkFWkENkFWNkENkX kNkN N
可 见,X(k)的后一半，也完全由 E(k)和 F(k)的前一半确定。
即 N点的 DFT可由两个 N/2点的 DFT来计算。
4,蝶形运算－－流图表示蝶形运算流图 （ N/2个蝶形 ):
-1
)(kX
)2( kNX?
)(kE
)(kF
kNW
)()()
2
(
)()()(
kFWkENkX
kFWkEkX
k
N
k
N
)1,,1,0(
)1,,1,0(
2
2
N
N
k
k
由 E(k),F(k)表示 X(k)的运算是一种特殊的运算 -碟形运算按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法
(二 ) N/4点 DFT
由于 N=2 L,所以 N/2仍为偶数,可以进一步把每个 N/2
点的序列再按其奇偶部分分解为两个 N/4的子序列。
)()()
4
(
)()()(
2
2
kBWkA
N
kE
kBWkAkE
k
N
k
N
)1,,1,0( 4 Nk?
)()()
4
(
)()()(
2
2
kDWkC
N
kF
kDWkCkF
k
N
k
N
其中,
kl
l
N
N
WlxkA
4
4 1
0
)4()(?
kl
l
N
N
WlxkB
4
4 1
0
)24()(?
kl
l
N
N
WlxkC
4
4 1
0
)14()(?
kl
l
N
N
WlxkD
4
4 1
0
)34()(?
蝶形图同上类似。
按时间抽取的基－ 2 FFT算法按上述办法不断划分下去，直到最后剩下 2点 DFT,2
点 DFT实际上只有加减运算。
这种 FFT算法，是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法。
例：作 N＝ 8时 FFT的运算流图由上推证：
3
0
4)2()(
r
rkWrxkE?
3
0
4)12()(
r
rkWrxkF
kl
l
WlxkA 2
1
0
)4()(?
kl
l
WlxkB 2
1
0
)24()(?
kl
l
WlxkC 2
1
0
)14()(?
kl
l
WlxkD 2
1
0
)34()(?
(三 ) 2点 DFT
按时间抽取的基－ 2 FFT算法例续,N＝ 8时 FFT的运算
)4()0()4()0()1(
)4()0()4()0()0(
1
2
0
2
xxxWxA
xxxWxA
展开得：
)7()3()1(
)7()3()0(
)5()1()1(
)5()1()0(
)6()2()1(
)6()2()0(
xxD
xxD
xxC
xxC
xxB
xxB
例续,N=8点 FFT的运算流图：
)0(x
)4(x
)2(x
)6(x
)1(x
)5(x
)3(x
)7(x
WN0
A(0)
-1
A(1)
WN0
WN0
W 0N
-1
-1
-1
B(0)
B(1)
D(0)
C(0)
C(1)
D(1)
WN0
E(0)
E(2)
-1W
N
2
WN0
WN2
E(1)
E(3)
F(0)
F(1)
F(2)
F(3)
X(0)
X(4)N0W-1
-1
-1
-1
-1
-1
-1
X(1)
X(2)
X(3)
X(5)
X(6)
X(7)
N
1
N
2
N
3
W
W
W
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法由上例分析可知,N=8= 需三级蝶形运算,由此可知：32
N=2L 共需 L级蝶形运算,L＝ log2 N ；
每级都由 N/2个蝶形运算组成；
每个蝶形运算有一次复乘,两次复加 。
因此,N点的 FFT的运算量为：
复乘,mF =（ N/2） *L=（ N/2） *log2 N
复加,aF =2*（ N/2） *L=N*log2 N
即计算量远比 DFT的计算量小。
N越大,FFT的优点越明显。
二 运算量分析按时间抽取的基－ 2 FFT算法三 DIT－ FFT算法的特点
1.原位运算,输入数据,中间结果和输出均用同一存储器 。
)0(x
)4(x
)2(x
)6(x
)1(x
)5(x
)3(x
)7(x
WN0
A(0)
-1
A(1)
WN0
WN0
W 0N
-1
-1
-1
B(0)
B(1)
D(0)
C(0)
C(1)
D(1)
WN0
E(0)
E(2)
-1W
N2
WN0
WN2
-1
-1
-1
E(1)
E(3)
F(0)
F(1)
F(2)
F(3)
X(0)
X(4)N0W
-1
-1
-1
-1
X(1)
X(2)
X(3)
X(5)
X(6)
X(7)
N1
N2
N3
W
W
W
也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。原位运算的结构可以节省存储单元，降低设备成本。
按时间抽取的基－ 2 FFT算法
2,倒位序规律由图知输出 X(k)按自然顺序排列在存储单元，而输入是按下列顺序排列,
）；）； 7(),3(),5(),1(6(),2(),4(),0( xxxxxxxx
这种顺序称作倒位序,即二进制数倒位。
造成倒位序的原因在于输入 x(n)按标号 n的奇偶不断分组。
自然顺序 二进制表示 码位倒置 码位倒置顺序
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
按时间抽取的基－ 2 FFT算法
2,倒位序规律码位倒置变换后,X(k)按照正常序列，但 x(n)不再是自然顺序，
如 N=8，有
x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)
但其对应于二进制编码有
x(000),x(100),x(010),x(110),x(001),x(101),x(011),
x(111)
将上述码翻转后有
x(000),x(001),x(010),x(011),x(100),x(101),x(110),
x(111)，刚好是
x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)
为自然顺序，这样的规律有利于编程。
3.,级”与“组”（或群）
N点 FFT共有 L级迭代，流图中的每一列为一级迭代；
每一级中，由交叉蝶形组成一个群。
第一级有 N/2个群，第二级 N/4个群，依次类推，最后一级 1个群。
按时间抽取的基－ 2 FFT算法四 DIT－ FFT其它形式流图输入自然顺序、输出倒位序的 DIT―FFT运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3W N
2
W N
0
W N
0
W N
0
按时间抽取的基－ 2 FFT算法按时间抽取的基－ 2 FFT算法输入输出均为自然顺序的 DIT―FFT运算流图。
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3
W N
2
W N
0
W N
0
W N
0
按频率抽取（ DIF）的基－ 2 FFT算法一 算法原理
1,N点 DFT的另一种表达形式
1
0
)()(
N
n
nk
NWnxkX
1
2/
1
0
)()(
2 N
Nn
nk
N
n
nk
N WnxWnx
N
nk
N
n
k
N WW
Nnxnx
N
N?
1
0
2
2)
2
()(
1
0
)(
1
0
2
2
2
)
2
()(
N
N
N
n
kn
N
n
nk
N W
NnxWnx
])1([ 2 kkNNW
nk
N
n
k WNnxnxkX
N
1
0
2
)
2
()1()()( 1,,1,0 Nk?
2,N点 DFT按 k的奇偶分组分为两个 N/2点的 DFT
当 k为偶数，即 k=2r时,(-1)k =1；
当 k为奇数，即 k=2r+1 时,(-1)k =-1 。
这时 X(k) 可分为两部分：
nr
N
n
WNnxnxrX
N
2
1
0
2
)2()()2(?
1,,1,0 2 Nr?
nr
n
N
N
WNnxnx
2
2 1
0
)2()(?
nr
n
n
N
rn
N
n
N
N
N
WW
N
nxnx
W
N
nxnxrX
2
2
2
1
0
)12(
1
0
)
2
()(
)
2
()()12(
1,,1,0 2 Nr?
上面两式均为 N/2的 DFT。
按频率抽取（ DIF）的基－ 2 FFT算法
蝶形运算令：
-1
)2()()(11 Nnxnxnx
n
NW
Nnxnxnx
)
2
()()(12
nNW
)2( Nnx?
)(nx
1,,1,0 2 Nn?
n
NW
NnxnxnxNnxnxnx )
2()()( )2()()( 1211
则蝶形运算图如下：
按频率抽取（ DIF）的基－ 2 FFT算法按频率抽取（ DIF）的基－ 2 FFT算法
3,再将 N/2点 DFT按 k的奇偶各分解为两个 N/4点的
DFT
令 r＝ 2l与 r＝ 2l+1
nr
N
n
WnxrX
N
2
1
0
11
2
)()2(?
nl
N
n
WNnxnxlX
N
4
1
0
1111
4
)4()()4(?
1
0 2
1111
4
4
)4()()24(
N
N
n
nln
N WW
NnxnxlX
1,,1,0
1,,1,0
4
4
N
N
n
l
nr
N
n
WnxrX
N
2
1
0
12
2
)()12(?
nl
N
n
WNnxnxlX
N
4
1
0
1212
4
)4()()14(?
nl
n
n
N N
N
WWNnxnxlX
4
4 1
0 2
1212 )4()()34(?
按频率抽取（ DIF）的基－ 2 FFT算法
4,2点 DFT
依上述方法，按 k的奇偶不断分解 L－ 1次，直至最终只有 2点的 DFT
这种分解方法是先把输入序列分成前后两半，然后把输出序列按序号 k的奇偶进行分解为短序列，即在频域进行抽取，简称 DIF―FFT。
二 例如 N=8时 DIF－ FFT的运算规则
7,,2,1,0k
7
0
8)()(
n
nkWnxkX
3
0
8)4()1()(
n
nkk Wnxnx
122 rrk 与令
3
0
4)4()()2(
n
rnWnxnxrX
3
0
48)4()( )12(
n
rnn WWnxnxrX 3,2,1,0
3,2,1,0
n
r
nWnxnxnxnxnxnx 81211 )4()()( )4()()(令
3
0
412
3
0
411 )()12( )()2(
n
rn
n
rn WnxrXWnxrX则按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF的运算规则
122 llr 与再令
1
0
241212
1
0
21212
1
0
241111
1
0
21111
)2()( )34(
)2()()14(
)2()( )24(
)2()()4(
n
nln
n
nl
n
nln
n
nl
WWnxnxlX
WnxnxlX
WWnxnxlX
WnxnxlX则
1,0
1,0
n
l
按频率抽取（ DIF）的基－ 2 FFT算法按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF的运算规则
nWnxnxnx
nxnxnx
812
11
)4()()(
)4()()( 已知 3,2,1,0?n
n
n
Wnxnxnx
nxnxnx
Wnxnxnx
nxnxnx
4121224
121223
4111122
111121
)2()()(
)2()()(
)2()()(
)2()()(
令 1,0?n
1
0
224
1
0
223
1
0
222
1
0
221
)()34( )()14(
)()24( )()4(
n
nl
n
nl
n
nl
n
nl
WnxlXWnxlX
WnxlXWnxlX
则
1,0
1,0
n
l
按频率抽取（ DIF）的基－ 2 FFT算法例续 N=8时 DIF－ FFT的信号流图
)0(x
)1(x
)2(x
)3(x
)4(x
)5(x
)6(x
)7(x
)0(11x
-1
08W )0(12x
)1(11x
-1
18W )1(12x
-1
)2(11x
28W )2(12x
-1
)3(11x
38W )3(12x
)0(21x
-1
08W )0(22x
-1
)1(21x
28W )1(22x
)0(23x
08W )0(24x
-1
-1
)1(23x
28W )1(24x
)0(X
)4(X
08W
-1
)2(X
)6(X
08W
-1
)1(X
)5(X
08W
-1
)3(X
)7(X
08W
-1
四 DIF－ FFT的运算特点
1,原位运算蝶形运算的通用表达式
r
Nmmm
mmm
WjXkXjX
jXkXkX
)]()([)(
)()()(
11
11
-1 WNr
)(1 kXm?
)(1 jXm?
)()()( 11 jXkXkX mmm
rNmmm WjXkXjX )]()([)( 11
蝶形图按频率抽取（ DIF）的基－ 2 FFT算法三 DIF－ FFT的运算量分析复乘：
NN
2l o g21
复加,NN NN
22 l o gl o g22
即和 DIT－ FFT的计算量相同。
五 DIF法与 DIT法的异同
1,相同点
(1)进行 原位运算 ；
(2)运算量相同,复乘（ N/2) Log2N次,复加 N Log2N次。
2,不同点
(1) DIT输入为倒位序,输出为自然顺序； DIF正好与此相反。但 DIT
也有输入为自然顺序,输出为倒位序的情况。
(2) 蝶形运算不同,
两种蝶形运算 流图 互为转置：将流图的所有支路方向都反向，
交换输入和输出，节点变量值不变。
基本蝶形的复乘,DIT在输入端、先乘后加；
DIF在输出端、先加后乘。
按频率抽取（ DIF）的基－ 2 FFT算法离散傅立叶反变换的快速计算方法－ IFFT
一 稍微变动 FFT程序和参数实现 IFFT
nkN
N
k
N
n
nk
N
WkX
N
kXI D F Tnx
WnxnxD F TkX
1
0
1
0
)(
1
)()(
)()()(
比较两式可知：
只要 DFT的每个系数 换成,最后再乘以常数
1/N就可以得到 IDFT的快速算法 --IFFT。
可以将常数 1/N分配到每级运算中,∵,
也就是每级 蝶形运算均乘以 1/2。
nkNW nkNW?
L
LN )2
1(
2
11
DIT―IFFT的运算流图
W
N
0
2
1
21 x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
21
21
21
W
N
1
2
1
W
N
2
2
1
W
N
3
2
1
21
21
W
N
0
2
1
W
N
2
2
1
21
21
W
N
0
2
1
W
N
2
2
1
21
W
N
0
2
1
21
W
N
0
2
1
21
21
W
N
0
2
1
W
N
0
2
1
离散傅立叶反变换的快速计算方法－ IFFT
离散傅立叶反变换 (IDFT)的快速计算方法由定义,
1
0
)(1)]([)( N
k
knNWkXNkXI D F Tnx
1
0
)()]([)( N
k
knNWnxnxD F TkX
两者作比较，得到启发方法一,修改 DFT运算中的各个系数 -----将 改为knNW knNW?,最后乘以 1/N
N1同时将常数 分解为,分散到各级中，即每一级都乘以因子 21M)21(
方法二,不修改 FFT的程序和参数，利用共轭变换的方法
∵
1N
0k
knN** )(1)( WkXNnx
***1N
0k
knN* )]}([{1])([1)( kXD F TNWkXNnx
∴
)(* kX取共轭 )]}([{ * kXD F T直接访问FFT程序*取共轭 乘系数 )(1 * nxN?)(kX即三 实序列的 FFT算法设 x(n)为 N点实序列，取 x(n)的偶数点和奇数点分别作为新构造序列
y(n)的实部和虚部，即
12,,1,0),12()(),2()( 21 Nnnxnxnxnx?
12,,1,0),2()(1 Nnnjxnxy?
对 y(n)进行 N/2点 FFT,输出 Y(k),则
12,,1,0,)()()(
)()()(
22
11
Nk
kjYnxD F TkX
kYnxD F TkX
op
ep?
由 DIT― FFT的思想得
12,,1,0),()()( 21 NkkXWkXkX kN?
由于 x(n)为实序列，所以 X(k)具有共轭对称性,X(k)的另外 N/2点的值为,
12,2,1),()( * NKKXKNX?
例题 1：
设 x(n)是长度为 2N的有限长实序列,X(k)为 x(n)的 2N
点 DFT。要求：试设计用一次 N点 FFT完成计算 X(k)的高效算法。
解：
本题的解题思路是 DIT－ FFT思想；
在时域分别抽取偶数点和奇数点 x(n)，得到两个 N点实序列 x1(n)
和 x2(n)：
x1(n) = x(2n),n = 0,1,……,N-1
x2(n) = x(2n+1),n = 0,1,……,N-1
根据 DIT－ FFT的思想，只要求得 x1(n)和 x2(n)的 N点 DFT，再经过简单的一级蝶形运算就可得到 x(n)的 2N点 DFT。
因为 x1(n)和 x2(n)均为实序列，所以根据 DFT的共轭对称性，可用一次 N点 FFT求得 X1(k)和 X2(k)。做法如下：
令 y(n) = x1(n) + jx2(n)? Y(k) = DFT[y(n)]
则 X1(k)=DFT[x1(n)]=Yep(k)=[Y(k)+Y*(N-k)]/2
jX2(k)=DFT[x2(n)]=Yop(k)=[Y(k)-Y*(N-k)]/2
2N点 DFT[x(n)] = X(k)可由 X1(k)和 X2(k)得到：
X(k) = X1(k) + W2NkX2(k)
X(k+N) = X1(k) - W2NkX2(k),k=0,1,…,N-1
因此，通过一次 N点 FFT计算完成了计算 2N点 DFT。
例题 2：
设 x(n)是长度为 2N的有限长实序列,X(k)为 x(n)的 2N
点 DFT。若已知 X(k)，要求：试设计用一次 N点 IFFT完成计算 x(n )的高效算法。
解：设 x1(n) = x(2n),n = 0,1,……,N -1
x2(n) = x(2n+1),n = 0,1,……,N -1
X1(k) = DFT[x1(n)],k = 1,1,…,N -1
X2(k) = DFT[x2(n)],k = 1,1,…,N -1
由 DIT－ FFT的算法，有以下关系式：
X(k) = X1(k) + W2NkX2(k),k = 1,1,…,N -1
X(k+N) = X1(k) - W2NkX2(k)
由以上两可解出 X1(k)和 X2(k) 。
X1(k) = [X(k) + X(k+N)]/2
X2(k) = W2N-K[X(k) – X(k+N)]/2
由上面分析可得出运算过程如下：
（ 1）由 X(k)计算出 X1(k)和 X2(k)；
（ 2）由 X1(k)和 X2(k)构成 N点频域序列 Y(k)：
Y(k) = X1(k) + jX2(k) = Yep(k) + Yop(k)
对 Y(k) 进行 N点 IFFT得到 y(n)
x1(n) = yep(n),jx2(n) = yop(k),进行 N点 IFFT运算，得到由 x1(n)和 x2(n)合成 x(n)：
当 n = 偶数（ n = 0,1,…,2N-1）时 x(n) = x1(n/2)
当 n = 奇数（ n = 0,1,…,2N-1）时 x(n) = x2((n-1)/2)
其他快速算法
1、频率抽取基 4 FFT算法令 N=4M，对 N点的 DFT可按如下方法作频率抽取，
)()()()()(
1
4/3
14/3
2/
12/
4/
14/
0
N
Nn
nk
N
N
Nn
nk
N
N
Nn
nk
N
N
n
nk
N WnxWnxWnxWnxkX
其他快速算法
2、分裂算法基 2频率抽取算法在每一级中每一组的上半部的输出都没有乘以旋转因子（对应于偶序列号），分裂算法是对偶序列号使用基 2算法，对奇序列号使用基 4算法。
在针对 N=2M的算法中，分裂基算法被认为是最好的快速傅里叶算法。
其他快速算法
3、离散哈特莱变换（ DHT）
DHT的快速算法基本思想与 DFT类似，有基于 2的、基于 4的和分裂基快速算法。
只是＆函数不同，所以计算公式和运算流程机构不同。
