数字信号处理（程佩青）：第四章k

§ 4-5线性卷积的 FFT算法
§ 4-3 DIF的 FFT算法
§ 4-4 IFFT算法
§ 4-2按时间抽取 (DIT)的 FFT算法
§ 4-1 引言
§ 4-1引言一,DFT的计算工作量两者的差别仅在指数的符号和因子 1/N,
1,,1,0,)()(
1
0

NkWnxkX
N
n
nk
N?

1
0
1,,1,0,)(
1
)(
N
k
nk
N NnWkXNnx?
通常 x(n)和 都是复数,所以计算一个
X(k)的值需要 N次复数乘法运算,和 次复数加法运算,那么,所有的 X(k)就要 N2次复数乘法运算,N(N-1)次复数加法运算,当 N很大时,运算量将是惊人的,如 N=1024,则要完成 1048576 次 (一百多万次 )运算,这样,难以做到实时处理,
nkNW
1?N
一个 X(k)的值的工作量,如 X(1)
1210 )1()2()1()0()1( NNNNN WNxWxWxWxX?
二,改进的途径
1,的对称性和周期性nk
NW;
,)(
)()(
*
Nkn
N
kNn
N
nk
N
nk
N
nk
N
WWW
WW


.
),1(1
),1(
)2/(
2/
)(2)()(
2
k
N
Nk
N
j
N
N
N
nkNn
N
Nk
N
nk
N
knN
N
kNn
N
WW
eWW
eWWWWW
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倍
§ 4-2 按时间抽取 (DIT)的 FFT算法
— 库利 -图基算法一,算法原理 (基 2FFT)
(一 )N/2点 DFT
1.先将 按 n的奇偶分为两组作 DFT,设 N=2L,
不足时,可补些零。这样有,
n为偶数时,
n为奇数时,1,,1,0 ),()12(
1,,1,0 ),()2(
22
21


N
N
rrxrx
rrxrx

1
0
)()]([)(
N
n
nk
NWnxnxD F TkX
因此，
)(nx
由于,
所以,上式可表示为,






1
0
2
2
1
0
2
1
1
0
)12(
1
0
2
1
0
1
0
22
22
))(())((
)12()2(
)()()(
NN
NN
r
rk
N
k
N
r
rk
N
r
kr
N
r
rk
N
N
n
N
n
nk
N
nk
N
WrxWWrx
WrxWrx
WnxWnxkX
(n为偶数 ) (n为奇数 )
2
22 )/(222 NNN WeeW jjN
)()()()()( 21
1
0
2
1
0
1
2
2
2
2
kXWkXWrxWWrxkX kN
r
rkk
N
r
rk
N
N
N
N
其中,
2.两点结论,
(1) X (k),X(k)均为 N/2点的 DFT。
(2) X(k)=X(k)+W X(k)只能确定出
X(k)的 k= 个；
即 前一半 的结果。
1 2
1 2
k
N




1
0
1
0
22
1
0
1
0
11
2
2
2
2
2
2
2
2
)12()()(
)2()()(
N
N
N
N
N
N
N
N
r
rk
r
rk
r
rk
r
rk
WrxWrxkX
WrxWrxkX
1,,1,0 2?N?
同理,
这就是说,X1(k),X2(k)的后一半,分别等于其前一半的值。
3.X(k)的后一半的确定
rkkr
N
N
N WW 2
2
2
)(
)()()()
2
( 1
1
0
1
)(
1
0
11
2
2
2
2
2
kXWrxWrxkNX
N
N
N
N
N
r
rkkr
r

由于 （周期性）,所以,
)()2( 22 kXkNX
可 见,X(k)的后一半，也完全由 X1(k),
X2(k)的前一半所确定。
*N点的 DFT可由两个 N/2点的 DFT来计算。
kNkNNkN WWWW NN 22 )(
)2()2()2( 21 2 NkXWNkXNkX
Nk
N
1,,1,0 ),()( 221 NkN kkXWkX?
又由于,所以实现上式运算的流图称作蝶形运算前一半
4.蝶形运算后一半
（ N/2个蝶形 )
(前一半 )
(后一半 )
1 1
1
1
-1
)()()(
)()()(
21
21
kXWkXkX
kXWkXkX
k
N
k
N


)1,,(
)1,,1,0(
2
2


Nk
k
N
N
)()()( 21 kXWkXkX kN
)()()2( 21 kXWkXkNX kN
)(1 kX
)(2 kX
kNW
由 X1(k),X 2(k)表示 X(k)的运算是一种特殊的运算 -碟形运算
(1)N/2点的 DFT运算量,复乘次数,
复加次数,
(2)两个 N/2点的 DFT运算量,复乘次数,
复加次数,
(3)N/2个蝶形运算的运算量,复乘次数,
复加次数,
5.计算工作量分析复乘,
复加,
4)2(
22 NN?
)12(2?NN
2
2N
)12(?NN
2
N
NN 22
2)12(
2NNNN
222
22 NNN总共运算量,
按奇、偶分组后的计算量：
*但是,N点 DFT的复乘为 N2 ;复加 N(N-1);与分解后相比可知,计算工作点差不多减少 一半 。
例如 N=8时的 DFT,可以分解为两个
N/2=4点的 DFT.具体方法如下,
(1)n为偶数时,即分别记作,
)(42/ 1 kXD F TN,得点的进行?
3,2,1,0
)2()()(
3
0
4
3
0
411


k
WrxWrxkX
r
rk
r
rk
);6()3(
),4()2(
),2()1(
),0()0(
1
1
1
1
xx
xx
xx
xx
);6(),4(),2(),0( xxxx
(2) n为奇数时,分别记作,
);7()3(
),5()2(
),3()1(
),1()0(
2
2
2
2
xx
xx
xx
xx
3,2,1,0
)12()()(
3
0
4
3
0
422


k
WrxWrxkX
r
rk
r
rk
)(42/ 2 kXD F TN,得点的进行?
3,2,1,0),()()4(
)()()(
21
21


kkXWkXkX
kXWkXkX
k
N
k
N
x1(0)=x(0)
x1(1)=x(2) N/2点
x1(2)=x(4) DFT
x1(3)=x(6)
x2(0)=x(1)
x2(1)=x(3) N/2点
x2(2)=x(5) DFT
x2(3)=x(7)
1 2
~ ~
X1(0)
X1(1)
X1(2)
X1(3)
X2(0)
X2(1)
X2(2)
X2(3)WN
2
WN1
WN0
WN3
-1
-1
-1
-1
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
(3)对 X(k)和 X(k)进行蝶形运算,前半部为
X(0) X(3),后半部分为 X(4) X(7)
整个过程如下图所示,
由于 N=2 L,所以 N/2仍为偶数,可以进一步把每个 N/2点的序列再按其奇偶部分分解为两个 N/4的子序列。例如,n为偶数时的 N/2点分解为,
(二 ) N/4点 DFT
1,,1,0),()2( 431 Nlxlx?
1,,1,0),()12( 441 Nlxlx?
进行 N/4点的 DFT,得到
kl
N
l
lk
N
l
lk
N
l
lk
N
l
WlxWlxkX
WlxWlxkX
NN
NN
)12(
2/
1
0
14/
1
0
44
2
2/
1
0
14/
1
0
33
)12()()(
)2()()(
44
44


(偶中偶 )
(偶中奇 )
)()()( 431
2
kXWkXkX kN
1,,1,0 4 Nk?
从而可得到前 N/4的 X1(k)
)()()4( 431
2
kXWkXkNX kN
后 N/4的 X1(k)为
1,,1,0 4 Nk?
(奇中偶 )


1
0
4/64/
1
0
26
1
0
4/5
1
0
4/25
44
44
)()12()(
)()2()(
NN
NN
l
lk
N
lk
N
l
l
lk
N
l
lk
N
WlxWlxkX
WlxWlxkX
(奇中奇 )
同样对 n为奇数时,N/2点分为两个 N/4点的序列进行 DFT,则有,
14,,1,0k; ( k )XW( k ) X( k ) X 6kN / 252 N?
14,,1,0k; ( k )XW( k ) Xk)4N( X 6kN / 252 N?
进行碟形运算，得：、由 )()( 65 kXkX
例如,N=8时的 DFT可分解为四个 N/4的 DFT,
具体步骤如下,
)4()2()1(
)0()0()0(
)()()(
13
13
13
xxx
xxx
nxrxlx



(1) 将原序列 x(n)的“偶中偶”部分,
构成 N/4点 DFT，从而得到 X3(0),X3(1)。
)6()3()1(
)2()1()0(
)()()(
14
14
14
xxx
xxx
nxrxlx



(2) 将原序列 x(n)的“偶中奇”部分,
构成 N/4点 DFT，从而得到 X4(0),X4(1)。
(3) 将原序列 x(n)的“奇中偶”部分,
)5()2()1(
)1()0()0(
)()()(
25
25
25
xxx
xxx
nxrxlx



构成 N/4点 DFT，从而得到 X5(0),X5(1)。
(4) 将原序列 x(n)的“奇中奇”部分,
)7()3()1(
)3()1()0(
)()()(
26
26
26
xxx
xxx
nxrxlx



构成 N/4点 DFT，从而得到 X6(0),X6(1)。
（ 5） 由 X3(0),X3(1),X4(0),X4(1)进行碟形运算,
得到 X1(0),X1(1),X1(2),X1(3)。
（ 6） 由 X5(0),X5(1),X6(0),X6(1)进行碟形运算,
得到 X2(0),X2(1),X2(2),X2(3)。
(0)= (0)= (0) N/4
(1)= (2)= (4) DFT
(0)= (1)= (2) N/4
(1)= (3)= (6) DFT
(0)= (0)= (1) N/4
(1)= (2)= (5) DFT
(0)= (1)= (3) N/4
(1)= (3)= (7) DFT
3 1
3 1
4 1
4 1
5 2
5 2
6 2
6 2
0
2
N
N
0
2
N
N
W
W
W
W
0
1
2
3
N
N
N
N
-1
-1
-1
-2
-1
-1
W
W
W
W
X(0)
X(1)
X(0)
X(1)
X(0)
X(1)
X(0)
X(1)
3
3
4
4
5
5
6
6
X(0)
X(1)
X(2)
X(3)
X(0)
X(1)
X(2)
X(3)
1
1
1
2
2
2
2
1
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
（ 7） 由 X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),
X2(3)进行碟形运算,得到
X(0),X(1),X(2),X(3) X(4),X(5),X(6),X(7) 。
这样,又一次分解,得到四个 N/4点 DFT,
两级 蝶形运算,其运算量有大约减少一半即为 N点 DFT的 1/4。
对于 N=8时 DFT,N/4点即为两点 DFT,因此
0,1k,)()(
0,1k,)()(
0,1k,)()(
0,1k,)()(
4/
1
0
66
1
0
4/55
1
0
4/44
1
0
4/33




lk
N
l
l
lk
N
l
lk
N
l
lk
N
WlxkX
WlxkX
WlxkX
WlxkX
亦即,
)4()0()1()0()1(
)4()0()1()0()0(
0
3
1
233
0
3
0
233
xWxxWxX
xWxxWxX
N
N


)6()2()1()0()1(
)6()2()1()0()0(
0
4
1
244
0
4
0
244
xWxxWxX
xWxxWxX
N
N


)5()1()1()0()1(
)5()1()1()0()0(
0
5
1
255
0
5
0
255
xWxxWxX
xWxxWxX
N
N


)7()3()1()0()1(
)7()3()1()0()0(
0
6
1
266
0
6
0
266
xWxxWxX
xWxxWxX
N
N


(0)
(4)
(2)
(6)
(1)
(5)
(3)
(7)
WN0
WN0
WN0
W 0N
-1
-1
-1
-1
X(0)
X(1)
X(0)
X(1)
X(0)
X(1)
X(0)
X(1)
3
3
4
4
5
5
6
6
WN0
WN2
WN0
WN2
-1
-1
-1
-1
X(0)
X(1)
X(2)
X(3)
X(0)
X(1)
X(2)
X(3)
1
1
1
2
1
2
2
2
W
W
W
W
N
0
N
1
N
2
N
3
-1
-1
-1
-1
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
x
x
x
x
x
x
x
x
因此,8点 DFT的 FFT的运算流图如下这种 FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的,所以称作按 时间 抽取的算法 。
二,运算量由上述分析可知,N=8需三级蝶形运算
N=2 =8,由此可知,N=2L 共需 L级蝶形运算,
而且每级都由 N/2个蝶形运算 组成,每个蝶形运算有一次复乘,两次复加。
(DIT)
3
因此,N点的 FFT的运算量为复乘,mF =（ N/2） L=（ N/2） log2 N
复加,aF =N L=N log2 N
由于计算机的乘法运算比加法运算所 需的时间多得多，故以乘法作为比较基准,如表 4-1所示 (pp.145）。
(0)=X0(0) X1(0) X2(0) X3(0)=X(0)
(4)=X0(1) X1(1) X2(1) X3(1)=X(1)
(2)=X0(2) X3(2)=X(2)
(6)=X0(3) X3(3)=X(3)
(1)=X0(4) X1(4) X2(4) X3(4)=X(4)
(5)=X0(5) X3(5)=X(5)
(3)=X0(6) X3(6)=X(6)
(7)=X0(7) X1(7) X2(7) X3(7)=X(7)
W
W
W
W
N
0
N
0
N
0
N0
-1
-1
-1
-1
W
W
W
W
N
0
N
2
N
0
N
2
-1
-1
-1
-1
W
W
W
WN
N
N
N
0
1
2
3
.
.
.
.
.
.
.
.
.
.
.
三,DIT的 FFT算法的特点
1.原位运算输入数据、中间运算结果和最后输出均用同一存储器。
x
x
x
x
x
x
x
x





r
Nmmm
r
Nmmm
WjXkXjX
WjXkXkX
)()()(
)()()(
11
11
),3()6(
),2()2(
),1()4(
),0()0(
0
0
0
0
Xx
Xx
Xx
Xx
).7()7(
),6()3(
),5()5(
),4()1(
0
0
0
0
Xx
Xx
Xx
Xx
设用 m(m=1,2,…,L)表示第 m列 ;用 k,j表示蝶形输入数据所在的（上 /下）行数 (0,1,2,…,N-1);这时任何一个蝶形运算可用下面通用式表示,即由 运算流图可知,一共有 N个输入 /出 行,一共有 log2 N=L列（级）蝶形运算 (基本迭代运算 ),
所以,当 m=1时,则有（前两个蝶形）
0
001
0
001
)1()0()1(
)1()0()0(
N
N
WXXX
WXXX


0
001
0
001
)3()2()3(
)3()2()2(
N
N
WXXX
WXXX


当 m=2时,则有（前两个蝶形）
当 m=3时,则有（前两个蝶形）






2
112
2
112
0
112
0
112
)3()1()3(
)3()1()1(
)2()0()2(
)2()0()0(
N
N
N
N
WXXX
WXXX
WXXX
WXXX






1
223
1
223
0
223
0
223
)5()1()5(
)5()1()1(
)4()0()4(
)4()0()0(
N
N
N
N
WXXX
WXXX
WXXX
WXXX
可见,在某列进行蝶形运算的任意两个节点 (行 )k和 j的节点变量就完全可以确定蝶形运算的结果,
与其它行 (节点 )无关。 这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组
(列 )有 N/2个蝶形 运算,所以只需 N个存储单元，可以节 省存储单元。
)(),( jXkX mm
)(),( 11 jXkX mm
2 倒位序规律由图可知,输出 X(k)按正常顺序排列在存储单元,而输入是按顺序,
这种顺序称作倒位序,即二进制数倒位。
）；）； 7(),3(),5(),1(6(),2(),4(),0( xxxxxxxx
n =00
n =10
n =01
n =11
n =01
n =11
0
1
0
1
0
1
0
1
x
x
x
x
x
x
x
x
),,( 012 nnnx
(n2)
x(000) 0 乾
x(100) 4 兑
x(010) 2 离
x(110) 6 震
x(001) 1巽
x(101) 5 坎
x(011) 3 艮
x(111) 7 坤
（偶）
（奇）
这是由奇偶分组造成的,以 N=8为例说明如下,
3.倒位序实现输入序列先按自然顺序存入存储单元,然后经变址运算来实现 倒位序排列设输入 序列的序号为 n,二进制为
(n2 n1 n0 )2,倒位序 顺序用 表示,其倒位序 二进制为 (n0 n1 n2 )2,例如,
N=8时如下表：
n?
0 0 0 0 00 0 0
1 0 0 1 10 0 4
2 0 1 0 01 0 2
3 0 1 1 11 0 6
4 1 0 0 00 1 1
5 1 0 1 10 1 5
6 1 1 0 01 1 3
7 1 1 1 11 1 7
自然顺序 n 二进制 n n n 倒位序二进制 n n n 倒位顺序 n^2 1 0 0 1 2
A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)
x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)
x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)
变址处理方法存储单元自然顺序变址倒位序
4.蝶形运算两节点的距离,2m-1
其中,m表示第 m列,且 m =1,…,L
例如 N=8=23,第一级 (列 )距离为 21-1=1,
第二级 (列 )距离为 22-1=2，
第三级 (列 )距离为 23-1=4。
5.WNr 的确定 (仅给出方法 )
考虑蝶形运算两节点的距离为 2m-1,蝶形运算可表为
Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr
Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr
由于 N为已知,所以将 r的值确定即可 。
为此,令 k=(n2n1n0)2,再 将 k= (n2n1n0)2
左 移 (L-m)位,右边位置补零,就可得到
(r)2 的值,即 (r)2 =(k)22L-m 。
例如 N=8=23
(1)k=2,m=3 的 r值,∵ k=2=(010)2
左移 L-m=3-3=0,∴ r=(010)2=2;
(2)k=3,m=3 的 r值 ; k=3=(011)2,
左移 0位,r=3；
(3)k=5,m=2的值 ; k=5=(101)2 左移 L-m=1位 r=(010)2 =2。
6.存储单元存输入序列 (n),n=0,1,,N-1,计 N
个单元 ;
存放系数,r=0,1,,（ N/2） -1,
需 N/2个存储单元；
共计 (N+N/2)个存储单元。
x?
r
NW
§ 4-3 DIF的 FFT算法 (桑德 — 图基算法 )
一,算法原理
1.N点 DFT的另一种表达形式
1
0
)()(
N
n
nk
NWnxkX




1
0
)(
1
0
1
2/
1
0
2
2
2
2
)
2
()(
)()(
N
N
N
N
n
kn
N
n
nk
N
N
Nn
nk
N
n
nk
N
W
N
nxWnx
WnxWnx
由于 故因此 X(k)可表为
nk
N
n
k
N WW
N
nxnx
N
N



1
0
2
2)
2
()(
,12jN eW N kkN NW )1(2
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
nr
N
n
N
N
N
W
N
nxnx
W
N
nxnx
2
2
2
1
0
2
1
0
)
2
()(
)
2
()(




)2( rX
r 1,,1,0 2 N?
k为偶数时：
可见,上面两式均为 N/2的 DFT。
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(


x x
k为奇数时：
1,,1,0 2 Nr?
-1
)2()( Nnxnx
1,,1,0 2 Nn?
n
NW
Nnxnx


)
2()(
3.蝶形运算进行如下碟形运算：和 )
2
()( Nnxnx?
nNW
)2( Nnx?
)(nx
-1
-1
-1
-1
W
W
W
W
N
N
N
N
0
1
2
3
4.N=8时,按 k的奇偶分解过程先蝶形运算,后 DFT:
)0(x
)1(x
)5(x
)4(x
)3(x
)2(x
)7(x
)6(x
)0(X
)2(X
)6(X
)1(X
)3(X
)5(X
)7(X
)4(XDFT
N
点
2
DFT
N
点
2
5.仿照 DIT的方法再将 N/2点 DFT按 k的奇偶分解为两个
N/4点的 DFT,如此进行下去,直至分解为
2点 DFT。
(0) X(0)
(1) X(4)
(2) X(2)
(3) X(6)
(4) X(1)
(5) X(5)
(6) X(3)
(7) X(7)
-1
-1
-1
-1
W
W
W
W
N
N
N
N
0
1
2
3
-1
-1
-1
-1
W
W
W
W
N
N
N
N
0
2
0
2
-1
-1
-1
-1
W
W
W
W
N
N
N
N
0
0
0
0
x
x
x
x
x
x
x
x
例如 N=8时 DIF的 FFT流图如下：
二,原位运算每级 (列 )都是由 N/2个蝶形运算构成,即
-1 WNr





r
Nmmm
mmm
WjXkXjX
jXkXkX
)]()([)(
)()()(
11
11
)(1 kX m?
)(1 jX m?
)()()( 11 jXkXkX mmm
rNmmm WjXkXjX )]()([)( 11
三,蝶形运算两节点的距离一般公式为 2L-m =N/2m
例如 N=23 =8,
(1)m=1 时的距离为 8/2=4；
(2)m=2 时的距离为 8/4=2;
(3)m=3 时的距离为 8/8=1。
r的求法,
k=(n2 n1 n0 ),左移 m-1位,右边空出补零,
得 (r)2,亦即 (r)2 =(k)2 2m-1,
例如,N=8:
(1)m=1,k=2,k=(010)2 左移 0位,(r)2=(010)2=2;
(2)m=2,k=1,k=(001)2 左移 1位,(r)2=(010)2=2;
(3)m=2,k=5,k=(101)2 左移 1位,(r)2=(010)2=2,





r
Nmmmmm
mmmm
W
N
kXkX
N
kX
N
kXkXkX
)]
2
()([)
2
(
)
2
()()(
11
11
四,的计算由于 DIF蝶形运算的两节点的距离为 N/2m,
所以蝶形运算可表为：
rNW
1.相同点
(1)进行原位运算；
(2)运算量相同,均为（ N/2)Log2N次复乘,NLog2N次复加。
2.不同点
(1)DIT输入为倒位序,输出为自然顺序；
DIF正好与此相反。但 DIT也有输入为自然顺序,输出为倒位序的情况。
五,DIF法与 DIT法的异同
rNmmm WjXkXjX )()()( 11
rNmmm WjXkXkX )()()( 11)(1 kX m?
)(1 jX m?
rNW 1?
(2)蝶形运算不同
a.(DIT)
用矩阵表示 )(kX
m
)( jX m
rNW
rNW?
)(1 kX m?
)(1 jX m?
=
1
1
rNmmm WjXkXjX )]()([)( 11
)()()( 11 jXkXkX mmm)(1 kX m?
)(1 jX m?
rNW1?
b.(DFT)
用矩阵表示 )(kX
m
)( jX m rNW rNW?
)(1 kX m?
)(1 jX m?
=
1 1
(3)两种蝶形运算的关系互为转置（矩阵）；
将流图的所有支路方向都反向,交换输入和输出，即可得到另一种蝶形。
a.(DIT) b.(DFT)
rNW
rNW?
1 11
1
rNW
rNW?
§ 4-4 IFFT算法一,稍微变动 FFT程序和参数可实现 IFFT


nk
N
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
二,不改 (FFT)的 程序 直接实现 IFFT
nk
N
N
k
N
k
nk
N
WkX
N
WkX
N
nx


1
0
1
0
*
)(
1
])(
1
[)(


)(
1
)(
1
1
0
kXD F T
N
WkX
N
nk
N
N
k)( nx因此，
BABAWW nkNnkN ][,][?
这就是说,先将 X(k)取共轭,即将 X(k)的虚部乘 -1,直接利用 FFT程序计算 DFT； 然后再取一次共轭；最后再乘 1/N,即得 (n)。所以 FFT,IFFT可用一个子程序 。
x
§ 4-5 线性卷积的 FFT算法一,线性卷积的长度设一离散线性移不变系统的冲激响应为,其输入信号为,其输出为,并且 的长度为 L点,的长度为 M点,则：
)(nx
)(nx)(nh
)(nh
)(ny)(nx )(nh

1
0
)()()()()(
L
m
mnhmxnhnxny
)(ny
以实例说明：
0 1 2 3
1 2
3)(mx
)(mh
0 1 2
1 1.。 1
。
0 1
1 2
3
)(mx
2 3
)( mh?
)1( mh?

3
0
0)()()0(
m
mhmxy

3
0
1)1()()1(
m
mhmxy。
。
0 1 2 3
)2( mh?
)3( mh?
。
0 1
1 2
3
)(mx
2 3
。

3
0
3)2()()2(
m
mhmxy

3
0
6)3()()3(
m
mhmxy
0 1 2 3 4
0 1 2 3 4 5
)4( mh?
)5( mh?
0 1
1 2
3
)(mx
2 3
。
。

3
0
5)4()()4(
m
mhmxy

3
0
3)5()()5(
m
mhmxy
0 1 2 3 4 5
1
3 3
5
6
6
)(ny
1)( MLny 的长度为可见，
。
二,用 FFT算 的步骤：)(ny;1)(),(.1 点补零点，至少为将 LMNnhnx
；求 )()(.2 nhFFTkH?
；求 )()(.3 nxF F TkX?；求 )()()(.4 kHkXkY?
。求 )()(.5 kYI F F Tny?
FFT
FFT
IFFTx
x(n)
h(n)
y(n)
X(k)
H(k)
Y(k)
流程图三,几点说明
1,当 M=L 时,用圆周卷积计算线性卷积的速度快,点数越多,速度越快,
N≥ 64时,速度增加明显,
2,L>>M 时,速度增加不太明显,为了增加速度,采用 (1)重叠相加法 (2)
重叠保留法 (从略 ).