《数字信号处理》课程教学课件（PPT讲稿）ch2_3 DFT计算卷积

利用DFT计算线性卷积一、两个有限长序列的线性卷积DFT(x[k] @ x2[k]= X,[m]X,[m]问题提出：LTI系统响应实际需要：y[K]=x [K]*h[k]可否利用DFT计算线性卷积？例: xi[K]={1,1,1}, x 2[K]={1,1,0,1} , N=4xi[k]*x2[k], x,[k]x2[k]7/2/2025通信、信息-2002

7/2/2025 通信、信息 -2002- 利用DFT计算线性卷积 问题提出: DFT [ ] [ ] [ ] [ ] x1 k  x2 k = X1 m X2 m 实际需要： LTI系统响应 y[k]=x [k]h[k] 可否利用DFT计算线性卷积？ 例：x1 [k]={1,1,1}, x 2 [k]={1,1,0,1} , N=4 一、两个有限长序列的线性卷积 [ ] [ ], [ ] [ ] 1 2 1 2 x k  x k x k  x k

若xk的长度为N，hk的长度为M，则L=N+M-1点循环卷积等于XK与h[K的线性卷积xi [k]x[k]补L-N零L点DFTy[k]L点IDFTh[k]hi[k]补L-M零L点DFTxi[k] hi[k] = x[k] * h[k]7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 若x[k]的长度为N，h[k]的长度为M，则 L=N+M-1点循环卷积等于x[k] 与h[k]的线性卷积。 补L-N零 补L-M零 L点DFT L点DFT L点IDFT x[k] h[k] y[k] x1[k] h1[k] [ ] [ ] [ ] [ ] 1 1 x k h k = x k h k

例：利用MATLAB由DFT计算x[K]＊h[K]。x[k]={1, 2, 0, 1}, h[k]=[2, 2, 1, 1]%CalculateLinearConvolution byDFTx = [1 2 0 1];h = [2 2 1 1];% determine the length for zero paddingL = length(x)+length(h)-1;% Compute theDFTs by zero-paddingXE = fft(x,L);HE = fft(h,L);%Determine theIDFT of the producty1 = ifft(XE.*HE):7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- % Calculate Linear Convolution by DFT x = [1 2 0 1]; h = [2 2 1 1]; % determine the length for zero padding L = length(x)+length(h)-1; % Compute the DFTs by zero-padding XE = fft(x,L); HE = fft(h,L); % Determine the IDFT of the product y1 = ifft(XE.*HE); 例：利用MATLAB由DFT计算x[k]* h[k]。 x[k]={1, 2, 0, 1}, h[k]={2, 2, 1, 1}

长序列和短序列的线性卷积直接利用DFT计算的缺点：(1)信号要全部输入后才能进行计算，延迟太多(2) 内存要求大(3)算法效率不高解决问题方法：采用分段卷积分段卷积可采用重叠相加法和重叠保留法7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 长序列和短序列的线性卷积 直接利用DFT计算的缺点： (1) 信号要全部输入后才能进行计算，延迟太多 (2) 内存要求大 (3) 算法效率不高 解决问题方法：采用分段卷积 分段卷积可采用重叠相加法 和 重叠保留法

1.重叠相加（overlap add）将长序列x[Kl分为若于段长度为L的序列Kxo[k]x[k]x[k]x2[k]k3LL2L8Zx[k] =x,[k-nL]n=00≤k≤L-1x[k + nL]xn[k] =其中0其它7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 1. 重叠相加（overlap add） 将长序列x[k] 分为若干段长度为L的序列 [ ] [ ] 0 x k xn k nL n =  -  =    +   - = 0 [ ] 0 1 [ ] 其它 x k nL k L x k n k x[k] [ ] 0 x k [ ] 1x k [ ] 2 x k [ ] 3 x k L 2L 3L 其中

记: yn[k] = xn[k]*h[k]x,[k-nL]*h[k] =Z yn[k- nL][k]*h[k]=, n=0n=00≤k≤L+M-2yo[Kk]的非零范围yi[k-L]的非零范围L<k<2L+M-2L≤k<L+M-2序列yo[k]，yi[k]的重叠部分重叠的点数L+M-2-L+1=M-1依次将相邻两段的M-1个重叠点相加，即得到最终的线性卷积结果7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- [ ] [ ] [ ] [ ] 0 x k h k x k nL h k n n  =  -   = [ ] 0 yn k nL n =  -  = y0 [k]的非零范围 0  k  L + M - 2 y1 [k-L]的非零范围 L  k  2L + M - 2 序列 y0 [k], y1 [k]的重叠部分 L  k  L + M - 2 重叠的点数 L+M-2-L+1=M-1 : y [k] x [k] h[k] 记 n = n  依次将相邻两段的M-1个重叠点相加，即得到最终的 线性卷积结果

重叠相加法分段卷积举例2M=40 1 2 M-1L=7rk012L-17/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 0 1 1 k 2 h[k] M-1 M=4 0 1 1 k 2 x[k] L-1 L=7 重叠相加法分段卷积举例

yo[k]962 301yi[k - L]01297y[k] = Zy,[k - nL]201237/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 0 1 k 2 [ ] 0 y k 4 3 1 2 3 6 9 0 1 k 2 [ ] y1 k - L 4 7 9 1 2 3 0 1 k 2 y[k] y [k nL] =  n - 4 3 1 2 3

利用MATLAB实现分段卷积.fftfilt(h,x,n)h: FIR filterx: input sequencen为DFT点数，一般取2的整数次幂7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- •fftfilt(h,x,n) h: FIR filter x: input sequence n 为DFT点数，一般取2的整数次幂 利用MATLAB实现分段卷积

2.重叠保留法(overlapsave)方法：(1)将x[kl长序列分段，每段长度为L；(2)各段序列x，[kl与M点短序列h[kl循环卷积：(3）从各段循环卷积中提取线性卷积结果因 yn[k]=xn [k](Lh[k]前M-1个点不是线性卷积的点故分段时，每段与其前一段有M-1个点重叠。7/2/2025通信、信息-2002-

7/2/2025 通信、信息 -2002- 方法： (1) 将x[k]长序列分段，每段长度为L； (2) 各段序列xn [k]与 M点短序列h[k]循环卷积； (3) 从各段循环卷积中提取线性卷积结果。 2.重叠保留法(overlap save) 因 yn [k]=xn [k] L h[k] 前M-1个点不是线性卷积的点 故分段时，每段与其前一段有M-1个点重叠