利用DFT计算线性卷积

1、广州大学物理与电子工程学院广州大学物理与电子工程学院2.42.4 利用利用DFTDFT计算线性卷积计算线性卷积第二章第二章 离散离散FourierFourier变换变换主要内容主要内容重点与难点重点与难点重点重点1、有限长序列的线性卷积、有限长序列的线性卷积难点难点1、无限长序列的线性卷积、无限长序列的线性卷积问题提出：问题提出：LTI系统响应：系统响应： yk=x k hk为什么要利用为什么要利用DFTDFT计算线性卷积？计算线性卷积？因为因为DFTDFT有快速算法！有快速算法！x1k=1,1,1, x 2k=1,1,0,1 , 计算计算(1) x1k和和x2k的的线性线性卷积卷积y1k ；

2、(2) x1k和和x2k的的4点点循环循环卷积卷积y4k；(3) x1k和和x2k的的5点、点、6点和点和7点点循环循环卷积。卷积。线性卷积与循环卷积的关系：线性卷积与循环卷积的关系：1 , 1 ,2 ,2 ,2 , 11ky4 2, 3, 2, 2yk4点点循环循环卷积卷积1 , 1 ,2 ,2 ,2 , 11ky5 2, 2, 2, 2,1yk5点点循环循环卷积卷积1 , 1 ,2 ,2 ,2 , 11ky6 1,2,2,2,1,1yk6点点循环循环卷积卷积(1) x1k和和x2k的线性卷积；的线性卷积；(2) x1k和和x2k的的4点循环卷积；点循环卷积；(3) x1k和和x2k的的5点

3、、点、6点和点和7点循环卷积。点循环卷积。x1k和和x2k的的线性卷积线性卷积y1k为为:y1k=1，2，2，2，1，1x1k=1,1,1, x 2k=1,1,0,1 , 计算计算x1k和和x2k的的4点循环卷积点循环卷积y4k为为:y4k=2，3，2，2x1k和和x2k的的5点循环卷积点循环卷积y5k为为:y5k=2，2，2，1，1x1k和和x2k的的6点循环卷积点循环卷积y6k为为:y6k=1，2，2，2，1，1x1k和和x2k的的7点循环卷积点循环卷积y7k为为:y7k=1，2，2，2，1，1，0 x1k和和x2ky6k=1,2,2,2,1,1x1k和和x2k12 1,2,2,2,1,1

4、x kx k(1) x1k和和x2k的线性卷积；的线性卷积；(2) x1k和和x2k的的4点循环卷积；点循环卷积；(3) x1k和和x2k的的5点、点、6点和点和7点循环卷积。点循环卷积。x1k=1,1,1, x 2k=1,1,0,1 , 计算计算如果如果x1k的长度为的长度为N1=3， x1k的长度为的长度为N2=4，那么：，那么：当循环卷积的长度当循环卷积的长度=N1+N2-1时，循环卷积时，循环卷积=线性卷积。线性卷积。线性卷积与循环卷积的关系：线性卷积与循环卷积的关系： 0010115432 1 0yyyyyy01 200001 20001 2001 201 0111111111111

5、111xxxxxxxxxxxxxxx0032 1 02222xxxx111000111001110111111 12222132 1 0yyyy0 1 2 3 30 1 22 30 1 1 2 301111111111111111xxxxxxxxxxxxxxxx32 1 02222xxxx111001111011110110112232利用利用DFT计算序列线性卷积的步骤：计算序列线性卷积的步骤： 若若xk的长度为的长度为N，hk的长度为的长度为M。1、将、将xk和和hk以补零的方式延长到以补零的方式延长到L=N+M- -1点；点；2、分别做延长后两个序列的、分别做延长后两个序列的DFT，再相

6、乘；，再相乘；3、乘积的、乘积的IDFT就是就是xk与与hk的的线性卷积线性卷积。(1) 信号要全部输入后才能进行计算，延迟太多。信号要全部输入后才能进行计算，延迟太多。(2) 内存要求大。内存要求大。(3) 算法效率不高。算法效率不高。分段卷积可采用分段卷积可采用和和基本思想基本思想：将长序列：将长序列 分为若干段长度为分为若干段长度为L的序列的序列,每每一段分别与短序列进行循环卷积，对重叠部分相加一段分别与短序列进行循环卷积，对重叠部分相加0nLkxkxnn- - - 010 其他LknLkxkxn其中其中0khnLkxkhkxnn-0nLkynn-y0k的非零范围：的非零范围：20-ML

7、ky1k- -L的非零范围：的非零范围： 22-MLkL序列序列 y0k, y1k的重叠部分：的重叠部分：2-MLkL重叠的点数：重叠的点数：(L+M- -2)- -L+1=M- -1: nny knLx knLh k-记yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14 x1k=2, 3, 4, 5, 6x2k=7, 8, 9, 10, 11x3k=12,13, 14y1k=2, 7, 12, 16, 20, 17, 6y2k= 7, 22, 32, 36, 40, 32, 11y3k=12, 37, 52, 41, 14

8、已知序列已知序列xk=k+2,0 k 12, hk=1,2,1，试分别试分别利用利用重叠相加重叠相加法法计计算线性卷积算线性卷积, , 取取L=5 。M=3M-1=2个重叠点相加！个重叠点相加！hk=1,2, 1 基本思想基本思想：(1)将长序列将长序列 分为若干段长度为分为若干段长度为L的序列的序列,每一段与每一段与前一段有前一段有M- -1个点重叠个点重叠,第一段前面添加第一段前面添加M- -1个个0 0，最后一段不够最后一段不够L L点时，补零点时，补零；(2)然后每一段分别与短序列进行循环卷积；然后每一段分别与短序列进行循环卷积；(3)去掉每次卷积结果的前去掉每次卷积结果的前M- -1

9、个点后再依次相连个点后再依次相连。-x k (M1)M-1-L (M 1)L-1x 0kx 1k2L-Mk)1(-MLnkxkxn第一段前需补第一段前需补M-1-1个零个零第一段与第二段有第一段与第二段有M-1-1个点重合个点重合记：ynk =xn k L hk0 nnx kh kx knL Lh k-0nny knL- y0k中的中的M- -1, L- -1点对应于线性卷积点对应于线性卷积xk hk中中的的0 , L- -M点。点。 y1k中的中的M- -1, L- -1点对应于线性卷积点对应于线性卷积xk hk中的中的 L- -(M- -1), 2L- -M- -(M- -1)点。点。-0

10、)1(nnMLnkykhkxky yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14x1k=0, 0, 2, 3, 4x2k=3, 4, 5, 6 ,7x3k=6 ,7 , 8, 9, 10y1k= x1k hk= 11, 4, 2, 7, 12x4k=9, 10 , 11, 12,13y2k= x2k hk= 23, 17, 16, 20, 24y3k= x3k hk= 35, 29, 28, 32, 36y4k= x4k hk= 47, 41, 40, 44, 48x5k=12,13, 14, 0, 0y5k= x5k hk= 12, 37, 52, 41, 14 已知序列已知序列xk=k+2,0 k 12, hk=1,2,1，试分别试分别利利用用重重叠保留法叠保留法计算线性卷积计算线性卷积, , 取取L=5 。M=3M-1=2个重叠点保留！个重叠点保留！1、2、利用利用DFT计算序列线性卷积的步骤：计算序列线性卷积的步骤： 基本思想基本思想：将长序列：将长序列 分为若干段长度为分为若干段长度为L的序列的序列,每一每一段分别与短序列进行循环卷积，对重叠部分相加。段分别与短序