当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

同济大学:《数字信号处理(DSP)》课程教学资源(PPT课件讲稿)第四章 快速傅里叶变换(9/9)

资源类别:文库,文档格式:PPT,文档页数:11,文件大小:570KB,团购合买
点击下载完整版文档(PPT)

九、线性卷积和线性相关所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               

点击下载完整版文档(PPT)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共11页,试读已结束,阅读完整版请下载
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有