九、线性卷积和线性相关的 FFT算法
1、线性卷积的 FFT算法
dm L M?需运算量：
( ) ( 1 )h n h M n
若系统满足线性相位，即：
/2dm L M?则需运算量：
若 L点 x(n),M点 h(n)，
则直接计算其线性卷积 y(n)
1
0
( ) ( ) ( )
M
m
y n h m x n m

FFT法：以圆周卷积代替线性卷积
21mN M L令
( ) 0 1()
01
x n n Lxn
L n N


( ) 0 1()
01
h n n Mhn
M n N


2( 1 3 / 2 * l o g )Fm N N
1) H(k) = FFT [h(n)] N /2*log2N
4) y(n) = IFFT [Y(k)] N /2*log2N
3) Y(k) = H(k)X(k) N
2) X(k) =FFT [x(n)] N /2*log2N
N( ) ( ) * ( ) ( ) ( )y n x n h n x n h n则比较直接计算和 FFT法计算的运算量
22 ( 1 3 / 2 * l og )
d
m
F
m M LK
m N N
2
224 [ 1 3 / 2 * ( 1 l o g ) ] 1 0 6 l o g
m
MMK
M M M
22 3 l og
m
MK
L
讨论：
ML? 12N M L M则1）当
LM 1N M L L则2）当
mLK 需采用分段卷积
重叠相加法重叠保留法
1）重叠相加法
21mN M L令
0,1,...i?
( ) ( 1 ) 1()
0i
x n iL n i Lxn
n

其 它
( ) ( ) [ ( ) * ( )] [ ( ) ( )]i i i
i i i
y n y n x n h n x n h nN
()
()
x n L
L h n M
对长序列 分段，每段 点，
与 的长度 等数量级
1 ( ) [ ( ) ]iiX k F F T x n?）
2 ( ) [ ( ) ]H k F F T h n?）
3 ( ) ( ) ( )iiY k X k H k）
4 ( ) [ ( ) ]iiy n I F F T Y k?）
5 ( ) ( )i
i
y n y n）
2）重叠保留法舍弃 yi(n)的前 M-1个点，再将 yi(n)顺次连接，
即得 y(n)。
[ ( + 1 ) ] 0 1()
0i
x n i N M n Nxn
n

其 它分段
0 0 2()
[ ( 1 ) ] 1
nMxn
x n M M n


右移序列卷积 ( ) ( ) * ( ) ( ) ( )i i iy n x n h n x n h nN
2、线性相关的 FFT算法若 L点 x(n),M点 y(n)，计算线性相关：
1
*
0
( ) ( ) ( )
M
xy
m
r n x n m y m

21mN M L令
( ) 0 1()
01
x n n Lxn
L n N


( ) 0 1()
01
y n n Myn
M n N


1 ( ) [ ( ) ]X k F F T x n?）
( ) [ ( ) ]Y k F F T y n?2 ）
*3 ( ) ( ) ( )xyR k X k Y k）
4 ( ) [ ( ) ]x y x yr n I F F T R k?）
*11
*
00
11( ) ( ) ( )NN n k n k
x y x y N x y N
kk
r n R k W R k WNN




思考题：
1）频谱分析
23 ( ) jk
Nz re
Xz?
）计算
2）计算线性卷积
2mN?下列 DFT应用中，能否将 x(n)补零点使