第四章9线性卷积和线性相关的FFT算法 同济大学数字信号处理课件.ppt

2017-2-20 信号处理九、线性卷积和线性相关的 FFT 算法 1、线性卷积的 FFT 算法 d m LM ?需运算量: ( ) ( 1 ) h n h M n ?? ??若系统满足线性相位,即: / 2 d m LM ?则需运算量: 若L点x(n),M点h(n), 则直接计算其线性卷积 y(n) 10 ( ) ( ) ( ) Mm y n h m x n m ??? ?? 2017-2-20 信号处理 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 ) F m N N ? ? 1) H(k ) = FFT [h(n )] N /2* log 2N 4) y(n ) = IFFT [Y(k )] N /2* log 2N 3) Y(k ) = H(k)X(k ) N 2) X(k ) = FFT [x(n )] N /2* log 2N N ( ) ( ) * ( ) ( ) ( ) y n x n h n x n h n ? ?则 2017-2-20 信号处理比较直接计算和 FFT 法计算的运算量 2 2 (1 3/ 2*log ) dmF 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 mMKL ??讨论: M L ? 1 2 N M L M ? ???则 1)当 L M ?1 N M L L ? ???则 2)当 m L K ?? ?需采用分段卷积???重叠相加法重叠保留法 2017-2-20 信号处理 1)重叠相加法 2 1 m N M L ? ???令 0,1,... i?( ) ( 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 h n ? ? ?? ? ? N ( ) ( ) x n L L h n M 对长序列分段,每段点, 与 的长度等数量级 1 ( ) [ ( )] i i X k FFT x n ?) 2 ( ) [ ( )] H k FFT h n ?) 3 ( ) ( ) ( ) i i Y k X k H k ? ?) 4 ( ) [ ( )] i i y n IFFT Y k ?) 5 ( ) ( ) ii y n y n ??) 2017-2-20 信号处理 2017-2-20 信号处理 2)重叠保留法舍弃 y i(n)的前 M -1个点,再将 y i(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 h n ? ? N 2017-2-20 信号处理 2017-2-20 信号处理 2017-2-20 信号处理 2、线性相关的 FFT 算法若L点x(n),M点y(n),计算线性相关: 1*0 ( ) ( ) ( )