九、线性卷积和线性相关所FFT算法 1、线性卷积的FF算法 若L点x(n),M点h(n), 则直接计算其线性卷积v(n) y(n)=∑h(m)xn-m) 需运算量:m=LM 若系统满足线性相位,即: h(n)=±h(M-1-n) 则需运算量:m,=LM/2
九、线性卷积和线性相关的FFT算法 1、线性卷积的FFT算法 需运算量： md LM h(n) h(M 1 n) 若系统满足线性相位，即： / 2 则需运算量： md LM 若L点x(n)，M点h(n)， 则直接计算其线性卷积y(n) 1 0 ( ) ( ) ( ) M m y n h m x n m
FFT法:以圆周卷积代替线性卷积 N=2"≥M+L-1 x(n)0≤n≤L-1 x(n 0L≤n≤N-1 h(n)=h(n)0≤n≤M-1 0M<n<N-1 y(n=x(n)*h(n)=x(n)h(n) H(h)= FFT[h(nN/2*log2 N 2)X(k)=FFTIx(nN/2*log2N 3)Y(k)=H(k)X(k) N 4)(n)=IFFT[Y( N/2*log2N mp=N(+3/2*log, N)
FFT法：以圆周卷积代替线性卷积 2 1 m 令 N M L ( ) 0 1 ( ) 0 1 x n n L x n L n N ( ) 0 1 ( ) 0 1 h n n M h n M n N 2 (1 3/ 2*log ) mF 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 则 y(n) x(n)*h(n) x(n) N h(n)
比较直接计算和FFT法计算的运算量 M m122N(1+3/2*log2N) 讨论: 1)当M≈L则N=M+L-1≈2M M K 4M[1+3/2*(+log2M)10+6log2M 2)当L>M则N=M+L-1≈L M K 2+3log L 重叠相加法 L个个K需采用分段卷积 重叠保留法
比较直接计算和FFT法计算的运算量 2 2 (1 3/ 2*log ) d m F m ML K m N N 2 2 2 4 [1 3/ 2*(1 log )] 10 6log m M M K M M M 2 2 3log m M K L 讨论： 1）当 M L 则N M L 1 2M 2）当 L M 则N M L 1 L L Km 需采用分段卷积 重叠相加法 重叠保留法
1)重叠相加法 对长序列x(m)分段,每段L点, L与h(m)的长度M等数量级 x(n)≤n≤(i+1)L-1 x,(m) i=0 其它n 令N=2m≥M+L-1 y(n)=∑(n)=∑[x,(m)*h(m)=∑[x(n)h(n 1)X, (k)=FFTIx, (n)] 4)y, (n)=IFFTIY, (k) 2)H(k)=FFT[h(n)] 5)y(n)=>y(n) 3)Y(k)=X1(k)H(k)
1）重叠相加法 2 1 m 令N M L i 0,1,... ( ) ( 1) 1 ( ) 0 i x n iL n i L x n n 其它 ( ) ( ) [ ( )* ( )] [ ( ) ( )] i i i i i i y n y n x n h n x n N h n ( ) ( ) x n L L h n M 对长序列 分段，每段 点， 与 的长度 等数量级 1 ( ) [ ( )] Xi i ） k FFT x n 2）H(k) FFT[h(n)] 3 ( ) ( ) ( ) Yi i ） k X k H k 4 ( ) [ ( )] i i ）y n IFFT Y k 5 ( ) ( ) i i ）y n y n
(n) x(n) x1() L+N-1 2L-1 2L+N-1 n Stertlitim-ny' yI(n)=x(n)/( y(m)=x2(m)④h(m) 2L+N1