利用DFT计算线性卷积.ppt

1、,广州大学物理与电子工程学院,2.4 利用DFT计算线性卷积,第二章 离散Fourier变换,主要内容,一、 两个有限长序列的线性卷积 二、有限长序列和无穷长序列的线性卷积,重点与难点,重点 1、有限长序列的线性卷积,难点 1、无限长序列的线性卷积,问题提出：,LTI系统响应： yk=x khk,可否利用DFT计算线性卷积？,一、两个有限长序列的线性卷积,为什么要利用DFT计算线性卷积？,因为DFT有快速算法！,例1：x1k=1,1,1, x 2k=1,1,0,1 , 计算,解:,(1) x1k和x2k的线性卷积y1k ；,(2) x1k和x2k的4点循环卷积y4k ；,(3) x1k和x2k

2、的5点、6点和7点循环卷积。,线性卷积与循环卷积的关系：,4点循环卷积,线性卷积与循环卷积的关系,线性卷积与循环卷积的关系,5点循环卷积,线性卷积与循环卷积的关系,6点循环卷积,解:,(1) x1k和x2k的线性卷积；,(2) x1k和x2k的4点循环卷积；,(3) x1k和x2k的5点、6点和7点循环卷积。,x1k和x2k的线性卷积y1k为:,y1k=1，2，2，2，1，1,例1：x1k=1,1,1, x 2k=1,1,0,1 , 计算,x1k和x2k的4点循环卷积y4k为:,y4k=2，3，2，2,x1k和x2k的5点循环卷积y5k为:,y5k=2，2，2，1，1,x1k和x2k的6点循环

3、卷积y6k为:,y6k=1，2，2，2，1，1,x1k和x2k的7点循环卷积y7k为:,y7k=1，2，2，2，1，1，0,解:,x1k和x2k 6点循环卷积,y6k=1,2,2,2,1,1,x1k和x2k 线性卷积,(1) x1k和x2k的线性卷积；,(2) x1k和x2k的4点循环卷积；,(3) x1k和x2k的5点、6点和7点循环卷积。,例1：x1k=1,1,1, x 2k=1,1,0,1 , 计算,线性卷积与循环卷积的关系：,如果x1k的长度为N1=3， x1k的长度为N2=4，那么：,当循环卷积的长度=N1+N2-1时，循环卷积=线性卷积。,线性卷积与循环卷积的关系：,长度为3与长度

4、为4的两个序列线性卷积的矩阵表示,4点循环卷积的矩阵表示,利用DFT计算序列线性卷积的步骤：,若xk的长度为N，hk的长度为M。,一、两个有限长序列的线性卷积,1、将xk和hk以补零的方式延长到L=N+M-1点； 2、分别做延长后两个序列的DFT，再相乘； 3、乘积的IDFT就是xk与hk的线性卷积。,二、有限长序列和无穷长序列的线性卷积,直接利用DFT计算线性卷积的缺点：,(1) 信号要全部输入后才能进行计算，延迟太多。,(2) 内存要求大。,(3) 算法效率不高。,解决问题方法：采用分段卷积,分段卷积可采用重叠相加法和重叠保留法。,1. 重叠相加法（overlap add）,基本思想：将长

5、序列 分为若干段长度为L的序列,每一段分别与短序列进行循环卷积，对重叠部分相加,其中,二、有限长序列和无穷长序列的线性卷积,1. 重叠相加法,y0k的非零范围：,y1k-L的非零范围：,序列 y0k, y1k的重叠部分：,重叠的点数：,(L+M-2)-L+1=M-1,依次将相邻两段的M-1个重叠点相加，即得到最终的线性卷积结果。,二、有限长序列和无穷长序列的线性卷积,yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14,解: 重叠相加法,x1k=2, 3, 4, 5, 6,x2k=7, 8, 9, 10, 11,x3k=12,1

6、3, 14,y1k=2, 7, 12, 16, 20, 17, 6,y2k= 7, 22, 32, 36, 40, 32, 11,y3k=12, 37, 52, 41, 14,例2: 已知序列xk=k+2,0k12, hk=1,2,1，试分别利用重叠相加法计算线性卷积, 取L=5 。,M=3,M-1=2个重叠点相加！,hk=1,2, 1,2. 重叠保留法（overlap save）,二、有限长序列和无穷长序列的线性卷积,基本思想： (1)将长序列 分为若干段长度为L的序列,每一段与前一段有M-1个点重叠,第一段前面添加M-1个0，最后一段不够L点时，补零； (2)然后每一段分别与短序列进行循环

7、卷积； (3)去掉每次卷积结果的前M-1个点后再依次相连。,2. 重叠保留法（overlap save）,二、有限长序列和无穷长序列的线性卷积,2. 重叠保留法（overlap save）,二、有限长序列和无穷长序列的线性卷积,2. 重叠保留法（overlap save）,y0k中的M-1, L-1点对应于线性卷积xk*hk中的0 , L-M点。,y1k中的M-1, L-1点对应于线性卷积xk*hk中的, L-(M-1), 2L-M-(M-1)点。,二、有限长序列和无穷长序列的线性卷积,解: 重叠保留法,yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44,

8、48, 52, 41, 14,x1k=0, 0, 2, 3, 4,x2k=3, 4, 5, 6 ,7,x3k=6 ,7 , 8, 9, 10,y1k= x1khk= 11, 4, 2, 7, 12,x4k=9, 10 , 11, 12,13,y2k= x2khk= 23, 17, 16, 20, 24,y3k= x3khk= 35, 29, 28, 32, 36,y4k= x4khk= 47, 41, 40, 44, 48,x5k=12,13, 14, 0, 0,y5k= x5khk= 12, 37, 52, 41, 14,例3: 已知序列xk=k+2,0k12, hk=1,2,1，试分别利用重叠保留法计算线性卷积, 取L=5 。,M=3,M-1=2个重叠点保留！,1、两个有限长序列的线性卷积,三、小结,2、有限长序列和无穷长序列的线性卷积,利用DFT计算序列线性卷积的步骤：,(1) 重叠相加法,基本思想：将