L
Km
重叠相加法 需采用分段卷积 重叠保留法
1）重叠相加法
对长序列x(n )分段，每段L点， L与h(n )的长度M 等数量级
x(n) iL n (i 1) L 1 xi (n) 其它n 0
令N 2m M L 1
i 0,1,...
y ( n ) yi ( n ) [ xi ( n ) * h(n )] [ xi ( n ) (k ) FFT [ xi (n)]
2）H (k ) FFT [h(n )]
4）yi (n) IFFT [Yi (k )]
5）y ( n ) yi ( n )
FFT法：以圆周卷积代替线性卷积 令 N 2m M L 1 x ( n) 0 n L 1 x ( n) L n N 1 0
h( n) 0 n M 1 h( n) M n N 1 0 则 y ( n ) x ( n ) * h( n ) x ( n ) N h( n )
md ML Km mF 2 N (1 3/ 2*log 2 N )
讨论：
1）当 M L
则N M L 1 2 M
M2 M Km 4M [1 3/ 2*(1 log 2 M )] 10 6log 2 M
2）当 L
M
则N M L 1 L
M Km 2 3log 2 L
x ( n) 0 n L 1 x ( n) L n N 1 0 y ( n) 0 n M 1 y ( n) M n N 1 0
yi (n) xi (n) * h(n) xi (n)
N
h( n )
舍弃yi(n)的前M-1个点，再将yi(n)顺次连接， 即得y(n)。
2、线性相关的FFT算法
若L点x(n)，M点y(n)，计算线性相关：
rxy (n) x(n m) y* (m)
m 0 M 1
令N 2m M L 1
九、线性卷积和线性相关的FFT算法
1、线性卷积的FFT算法
若L点x(n)，M点h(n)， 则直接计算其线性卷积y(n)
y (n ) h(m) x (n m)
m 0
M 1
需运算量： md LM 若系统满足线性相位，即：
h( n) h( M 1 n)
则需运算量： md LM / 2
1) H(k) = FFT [h(n)]
2) X(k) =FFT [x(n)]
N /2*log2N
N /2*log2N
3) Y(k) = H(k)X(k)
4) y(n) = IFFT [Y(k)]
N
N /2*log2N
mF N (1 3/ 2*log 2 N )
比较直接计算和FFT法计算的运算量
i
3）Yi (k ) X i (k ) H (k )
2）重叠保留法
0 0 n M 2 右移序列 x(n) M 1 n x[n ( M 1)]
分段 卷积
x[n i( N M +1)] 0 n N 1 xi (n) 0 其它n