九、线性卷积和线性相关所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
2)重叠保留法 0 0<n<M-2 右移序列x(n) xn-(M-1)M-1≤n 分段 x(m)=m+(N-M+10≤n≤N-1 0 其它n 卷积y(mn)=x(m)*h(n)=x(m)h(m) 舍弃y(n)的前M1个点,再将ym)顺次连接, 即得v(m)
2）重叠保留法 舍弃yi(n)的前M-1个点，再将yi(n)顺次连接， 即得y(n)。 [ ( +1)] 0 1 ( ) 0 i x n i N M n N x n n 其它 分段 0 0 2 ( ) [ ( 1)] 1 n M x n x n M M n 右移序列 卷积 ( ) ( )* ( ) ( ) ( ) i i i y n x n h n x n N h n
MM∠ M-1 x1(m) M-2 yo(n) M-2 nTIIITttH M-2 y2(n) M-1
hn(m xdm) h((O-m))NRM(m) h((M-2-))NRM(m) n=M-2 h((M-1-m))NRM(m) n=-1 h((N-1-m))NRN(m) y (n) M-2
2、线性相关的FFT算法 若L点x(mn),M点y(m),计算线性相关: (m)=∑ x(n+m)y(m 0 令N=2m≥M+L-1 x(m)Jx(m)0≤n≤L-1 0L<n<N-1 1(n)=/y(n)0≤n≤M-1 0M<n<N-1
2、线性相关的FFT算法 若L点x(n)，M点y(n)，计算线性相关： 1 * 0 ( ) ( ) ( ) M xy m r n x n m y m 2 1 m 令N M L ( ) 0 1 ( ) 0 1 x n n L x n L n N ( ) 0 1 ( ) 0 1 y n n M y n M n N
1) X(k)= FFTIx(n) 2) Y(k)=FITly(n) 3)R(k)=X(k)·Y(k) 4)r,(n)=IFFTIR,,(k) (以)1 R,(k)w k N ∑Rn(k) k=0 N
1）X (k) FFT[x(n)] 2）Y (k) FFT[ y(n)] * 3 ( ) ( ) ( ) Rxy ） k X k Y k 4 ( ) [ ( )] xy xy ）r n IFFT R k * 1 1 * 0 0 1 1 ( ) ( ) ( ) N N nk nk xy xy N xy N k k r n R k W R k W N N