北京交通大学：《数字信号处理》课程教学课件（讲稿）第2章 离散傅里叶变换 2.3.DFT计算线性卷积

离散傅里叶变换有限长序列傅里叶分析1离散傅里叶变换的性质利用DFT计算线性卷积1利用DFT分析信号频谱面利用MATLAB计算DFT

离散傅里叶变换 u 有限长序列傅里叶分析 u 离散傅里叶变换的性质 u 利用DFT计算线性卷积 u 利用DFT分析信号频谱 u 利用MATLAB计算DFT

利用DFT计算线性卷积由DFT计算线性卷积的步骤u长序列和短序列的线性卷积u

利用DFT计算线性卷积 u 由DFT计算线性卷积的步骤 u 长序列和短序列的线性卷积

利用DFT计算线性卷积为什么利用DFT计算线性卷积？x[0]x[1] x[2] x[3]234110h[0]5x[K] -y[k]离散LTI系统h[1]6h[2]y[k] = x[k] * h[k]x[kl的长度为N，h[kl的长度为M，则线性卷积乘法次数是？乘法次数是NxM如何实现线性卷积的快速计算？

利用DFT计算线性卷积 为什么利用DFT计算线性卷积？ x[k]的长度为N，h[k]的长度为M，则线性卷积乘法次数是？ 乘法次数是N×M 如何实现线性卷积的快速计算？

利用DFT计算线性卷积利用DFT的循环卷积特性，可由DFT计算线性卷积。循环卷积和线性卷积存在什么关系？若序列x[k]的长度为N，序列h[k]的长度为M,则LN+M-1点循环卷积等于x[k]与h[k]的线性卷积。x[k] * h[k] = x,[k]D h,[k] - ? X,[m]H,[m]x[k]* h[k] = IDFT(X,[m]H,[m]}

利用DFT计算线性卷积 若序列x[k]的长度为 N，序列h[k]的长度为 M， 则 L￾N+M-1 点循环卷积等于x[k]与h[k]的线性卷积。 利用DFT的循环卷积特性，可由DFT计算线性卷积。 循环卷积和线性卷积存在什么关系？

利用DFT计算线性卷积序列x[k]的长度为 N，序列h[k]的长度为 M序列xi[k]的长度为L，序列h,[k]的长度为Lx[k] *h[k]= IDFT(X,[m]H,[m]}x,[k]x[k]X,[m]补LN零L点DFTNLy[k]L点IDFTLh[k]h,[k]补LM零L点DFTH,[m]LM1LN+M-1乘法总次数为+ Llog252

利用DFT计算线性卷积 序列x[k]的长度为 N，序列h[k]的长度为 M 序列x1 [k]的长度为 L，序列h1 [k]的长度为L 乘法总次数为 L￾N+M-1

例：已知x[k]=1,2,3,4}，h[k]={5,6,7}，试利用DFT计算x[k]与h[k] 的线性卷积。x = [1 2 3 4]; h = [5 6 7];L = length(x)+length(h)-1; % Determine the length for zero paddingXE = fft(x, L);%ComputetheDFTsbyzero-paddingHE = fft(h, L);y = ifft(XE.*HE);%DeterminetheIDFToftheproduct5163452=y4528

x = [1 2 3 4]; h = [5 6 7]; L = length(x)+length(h)-1; % Determine the length for zero padding XE = fft(x, L); % Compute the DFTs by zero-padding HE = fft(h, L); y = ifft(XE.*HE); % Determine the IDFT of the product 例: 已知x[k]= {1, 2, 3, 4}，h [k]={5, 6, 7}，试利用DFT计算x[k]与 h[k] 的线性卷积。 y = 5 16 34 52 45 28

利用DFT计算线性卷积乘法运算次数比较L=N+M=217N = 216, M = 216N"M=232直接计算线性卷积3'log, L +L =53°216由DFT计算线性卷积2232216》210两者乘法次数之比53°21653是否任何情况下，采因为DFT存在快速算法FFT(FastFourierTransform)，用DFT计算线性卷积均可减少乘法次数采用DFT(FFT)计算线性卷积，可大幅减少乘法次数。？

利用DFT计算线性卷积 乘法运算次数比较 因为DFT存在快速算法FFT (Fast Fourier Transform), 采用 DFT(FFT)计算线性卷积，可大幅减少乘法次数。 直接计算线性卷积 由DFT计算线性卷积 L=N+M=2 17 两者乘法次数之比 是否任何情况下，采 用 DFT计算线性卷 积均可减少乘法次数 ？

利用DFT计算线性卷积乘法运算次数比较L≥N+M-1，取L=217N = 216,M = 24NM=220直接计算线性卷积Llog2L+L=532163°由DFT计算线性卷积2220240.3》两者乘法次数之比2165353″由DFT计算长序列与短序列的卷积，其乘法次数反而增加

利用DFT计算线性卷积 乘法运算次数比较 直接计算线性卷积 由DFT计算线性卷积 两者乘法次数之比 由DFT计算长序列与短序列的卷积，其乘法次数反而增加。 L≥N+M-1，取L=2 17

长序列与短序列的线性卷积直接利用DFT计算长序列与短序列的卷积，存在缺点：(1）信号要全部输入后才能进行计算，延迟太多；(2)内存要求较大;③)算法效率不高。1.重叠相加法采用分段卷积2.重叠保留法

长序列与短序列的线性卷积 直接利用DFT计算长序列与短序列的卷积，存在缺点： (1) 信号要全部输入后才能进行计算，延迟太多； (2) 内存要求较大； (3) 算法效率不高。 采用分段卷积 1. 重叠相加法 2. 重叠保留法

重叠相加法将长序列x[]分为若干段长度为L的短序列x[k]3LL2 LofkfL-li x[k + nLl定义x,[k]=其他10

重叠相加法 将长序列 x[k] 分为若干段长度为 L 的短序列 定义