DFT计算卷积教学课件

数字信号处理

(DigitalSignalProcessing)信号与系统系列课程组国家电工电子教学基地DFT计算卷积离散傅里叶变换(DFT)

问题的提出有限长序列的傅里叶分析离散傅里叶变换的性质

利用DFT计算线性卷积利用DFT分析信号的频谱DFT计算卷积计算卷积计算卷积

利用DFT计算序列线性卷积的步骤长序列和短序列的线性卷积利用DFT计算序列线性卷积DFT计算卷积计算卷积计算卷积问题提出：实际需要：LTI系统响应y[k]=x[k]

h[k]可否利用DFT计算线性卷积？两个有限长序列的线性卷积DFT计算卷积计算卷积计算卷积两个有限长序列的线性卷积设x[k]的非零范围是0

k

N-1g[k]的非零范围是0

k

M-1y[k]=x[k]

h[k]非零范围序列y[k]的长度为0

k

N+M-2L=N+M-1至少要做L=N+M-1点的循环卷积DFT计算卷积计算卷积计算卷积利用DFT计算序列线性卷积的步骤

若x[k]的长度为N，h[k]的长度为M，则L

N+M-1点循环卷积等于x[k]与h[k]的线性卷积。DFT计算卷积计算卷积计算卷积例：利用MATLAB由DFT计算x[k]*h[k]。

x[k]={1,2,0,1},h[k]={2,2,1,1}%CalculateLinearConvolutionbyDFTx=[1201];h=[2211];%determinethelengthforzeropaddingL=length(x)+length(h)-1;%ComputetheDFTsbyzero-paddingXE=fft(x,L);HE=fft(h,L);%DeterminetheIDFToftheproducty1=ifft(XE.*HE);DFT计算卷积计算卷积计算卷积直接计算与由DFT间接计算结果比较DFT计算卷积计算卷积计算卷积长序列和短序列的线性卷积

直接利用DFT计算的缺点：(1)信号要全部输入后才能进行计算，延迟太多(2)内存要求大(3)算法效率不高

解决问题方法：采用分段卷积分段卷积可采用重叠相加法和重叠保留法DFT计算卷积计算卷积计算卷积长序列和短序列的线性卷积1.重叠相加法（overlapadd）将长序列x[k]分为若干段长度为L的序列定义(短序列h[k]的长度为M)DFT计算卷积计算卷积计算卷积长序列和短序列的线性卷积1.重叠相加法（overlapadd）y0[k]的非零范围y1[k-L]的非零范围序列y0[k],y1[k]的重叠部分重叠的点数L+M-2-L+1=M-1

依次将相邻两段的M-1个重叠点相加，即得到最终的线性卷积结果。DFT计算卷积计算卷积计算卷积重叠相加法分段卷积举例DFT计算卷积计算卷积计算卷积重叠相加法分段卷积举例(L=7,M=4)DFT计算卷积计算卷积计算卷积解:

重叠相加法(M=3)y[k]=x[k]*h[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}x1[k]={2,3,4,5,6}x2[k]={7,8,9,10,11}x3[k]={12,13,14,0,0}y1[k]=x1[k]*h[k]={2,7,12,16,20,17,6}y2[k]=x2[k]*h[k]={7,22,32,36,40,32,11}y3[k]=x3[k]*h[k]={12,37,52,41,14,0,0}例:

已知序列x[k]=k+2,0

k

12,h[k]={1,2,1}试利用重叠相加法计算线性卷积,取L=5。DFT计算卷积计算卷积计算卷积fftfilt(h,x,n)h:FIRfilterx:inputsequencen

为DFT点数，一般取2的整数次幂利用MATLAB实现分段卷积DFT计算卷积计算卷积计算卷积利用MATLAB实现分段卷积%GeneratethenoisesequenceN=64;d=rand(1,N)-0.5;%Generatetheuncorruptedsequenceandaddnoisen=0:N-1;s=2*n.*((0.9).^n);x=s+d;%thelengthofmovingaveragefilterM=4;%Generatethemovingaveragefiltercoefficientsh=ones(1,M)/M;%Performtheoverlap-addfilteringoperationy=fftfilt(h,x,8);DFT计算卷积计算卷积计算卷积4点滑动平均系统去噪结果DFT计算卷积计算卷积计算卷积若x1[k]为M

点序列,x2[k]为L

点序列，L>Mx1[k]L

x2[k]中哪些点不是线性卷积的点?问题讨论DFT计算卷积计算卷积计算卷积0

k

M-2不是线性卷积的结果，即前(M-1)个点与线性卷积不一样。DFT计算卷积计算卷积计算卷积对比图DFT计算卷积计算卷积计算卷积

x1[k]L

x2[k]k=0~M-2,前M-1个点不是线性卷积的点k=M-1~L-1,L-M+1个点与线性卷积的点对应线性卷积L~L+M-2后M-1点没有计算

则L点循环卷积结论若x1[k]为M

点序列,x2[k]为L

点序列，L>MDFT计算卷积计算卷积计算卷积2.重叠保留法（overlapsave）方法：

(1)

将x[k]长序列分段，每段长度为L。

(2)

各段序列xn[k]与M点短序列h[k]循环卷积。

(3)

从各段循环卷积中提取线性卷积结果。前M-1个点不是线性卷积的点，因yn[k]=xn[k]Lh[k]故分段时，每段与其前一段有M-1个点重叠。长序列和短序列的线性卷积DFT计算卷积计算卷积计算卷积长序列和短序列的线性卷积2.重叠保留法（overlapsave）--x[k(M1)]M-1--L(M1)L-1x0[k]x1[k]2L-Mk第一段前需补M-1个零DFT计算卷积计算卷积计算卷积2.重叠保留法（overlapsave）记：yn[k]=xn[k]Lh[k]长序列和短序列的线性卷积DFT计算卷积计算卷积计算卷积解:

重叠保留法y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}x1[k]={0,0,2,3,4}x2[k]={3,4,5,6,7}x3[k]={6,7,8,9,10}y1[k]=x1[k]⑤h[k]={11,4,2,7,12}x4[k]={9,10,11,12,13}y2[k]=x2[k]⑤

h[k]={23,17,16,20,24}y3[k]=x3[k]⑤

h[k]={35,29,28,32,36}y4[k]=x4[k]⑤

h[k]={47,41,40,44,48}x5[k]