循环卷积_DFT求线性卷积 (1)

1、专题：专题：循环卷积、用循环卷积、用DFT求线性卷积求线性卷积首先，我们要理解周期卷积仅仅针对离散傅里叶级数，循环首先，我们要理解周期卷积仅仅针对离散傅里叶级数，循环卷积（又称圆周卷积）仅仅针对离散傅里叶变换。这里的卷积（又称圆周卷积）仅仅针对离散傅里叶变换。这里的“循环循环”是针对周期序列而言，我们要始终记住，离散傅里是针对周期序列而言，我们要始终记住，离散傅里叶变换的序列叶变换的序列x(n)是周期序列是周期序列 的主值序列。的主值序列。而线性卷积是针对有限长序列，要用而线性卷积是针对有限长序列，要用DFT求线性卷积，必然求线性卷积，必然要求周期序列在一个周期内求卷积能和有限长序列求线性卷要

2、求周期序列在一个周期内求卷积能和有限长序列求线性卷积等值。因此我们求积等值。因此我们求N点长度的循环卷积必然要和线性卷积点长度的循环卷积必然要和线性卷积长度一致。起码长度一致。起码N要不少于线性卷积的长度。要不少于线性卷积的长度。)(nx 有限长序列的循环卷积（又称圆周卷积）有限长序列的循环卷积（又称圆周卷积） (1) 定义定义n设x1(n) 和x2(n) 是两个长度为 L、M的有限长序列，它们的N点循环卷积x3(n) 定义为： 注意：其中N=MaxL,M)()()()()()(1021213nRmnxmxnxnxnxNNmn注意：如果其中一个序列如果其中一个序列(或者两个序列）的长度没有所或

3、者两个序列）的长度没有所求求N点循环卷积的长度长，那在该序列后面补零，直到长点循环卷积的长度长，那在该序列后面补零，直到长度达到度达到Nn(c) 用解析式计算 n此式可用矩阵表示为：)()()()()()(10nRmnhmxnhnxnyNNmNN ) 1() 2() 2() 1 () 0 ( ) 0 () 3() 2() 1() 1() 4() 3() 2() 3 () 0 () 1 () 2() 2() 1() 0 () 1 () 1 () 2() 1() 0 () 1() 2() 2() 1 () 0 (NxNxxxxhNhNhNhNhNhNhNhhhhhhNhhhhNhNhhNyNyyy

4、yNNNNN注意矩阵的对角线为 然后每列往下依次是1、2、3.循环移位)0(hn h矩阵这个N阶方阵中的元素都是n由0到N-1区间的h(n)，这是通过求模(n-m)N 而得到的。在实际运用时只需要按照h矩阵中元素排列的规律直接写出这个矩阵。n 例例 设 x1(n) = 1,2,3,4,5，x2(n)=6,7,8,9，计算 5 点循环卷积 。n 解： x2(n) 为 4 点序列，在其尾部填零使其成为 5 点序列，再进行循环卷积运算。)()()(213nxnxnx10070859510054321 6 7 8 9 00 6 7 8 99 0 6 7 88 9 0 6 77 8 9 0 6)4()3

5、()2() 1 ()0(33333xxxxx 循环卷积与线性卷积的关系循环卷积与线性卷积的关系n我 们 已 经 知 道 ， 可 以 用 DFT 来 求 循环卷积，即 ，因此只要找到循环卷积与线性卷积之间的关系，就可以解决用DFT求线性卷积的问题。 )()()()(kHkXIDFTnhnx用用DFTDFT求线性卷积求线性卷积nDFT不仅可以用来对信号进行频谱分析，而且还可以用来计算序列的线性卷积。 n设x(n) 长度为N1，h(n) 长度为N2，则线性卷积n之长为N = N1+N2-1。为了便于用矩阵表示，我们在序列x(n) 的后面添N2-1个0，使x(n) 的长度变为N，这样，线性卷积为： n

6、用矩阵表示为：10),()()()()(Nm1Nn0 mnhmxnhnxny)()()(nhnxny0000) 1() 1 () 0 () 0 () 1 () 2() 1(000) 0 () 2() 1(00) 0 () 1 () 2 (00) 0 () 1 () 1(0) 0 () 2() 1() 0 () 1 () 0 () 1() 2() 1()() 1() 1 () 0 (12222222222NxxxhhNhNhhNhNhhhhhhNhhNhNhhhhNyNyNyNyNyyyn 与循环卷积的矩阵表示相比较，可以看出，即使进行线性卷积的两个序列长度也都是N，其结果也与循环卷积不同：两个

7、表示式中h矩阵不但元素的排列不同，而且矩阵的大小也不同。事实上，如果x(n)和h(n)的长度都为N，则它们的循环卷积yN(n)之长度为N，而它们的线性卷积y(n)之长度为2N-1。n 但是，在一定的条件下，可以使循环卷积与线性卷积的结果相同。考虑两个有限长序列的线性卷积：设x(n)的非零区间为0nN1-1, h(n)的非零区间为0nN2-1，则线性卷积y(n)=x(n)*h(n)的长度为N=N1+N2-1，非零区间是0nN-1。n 现在来设法构造这两个序列x(n) 与h(n) 的循环卷积，使其结果与线性卷积相同。n在x(n) 后面补充N2-1个0，使x(n)长度变为 N，x(n)：x(0)、x

8、(1)、x(N1-1)、0、0、0。n在h(n) 后面补充N1-1个0，使h(n)长度变为 N，h(n)：h(0)、h(1)、h(N2-1)、0、0、0。n再将h(n) 进行周期延拓，周期为N： rrNnhnh)()(n为了计算x(n)与h(n)的循环卷积yN(n)，我们先计 算 与 的周期卷积 ： )(nx)(nh)(nyN rrNmrNmNmNmNrNnymrNnhmxrNmnhmxmnhmxmnhmxny)()()()()()()()()()(10101010n 此式说明，周期卷积 是x(n)与h(n)的线性卷积y(n) 的周期延拓。由于 与 的周期都为N，因此它们的周期卷积 的周期也为

9、N，正好等于y(n)的长度，即上式中以N为周期的周期延拓没有发生混叠，线性卷积y(n)正好是周期卷积 的一个周期。 )(nyN)(nyN)(nyN)(nx)(nhn而循环卷积又是周期卷积的主值序列，因此，此时循环卷积yN(n)与线性卷积y(n)完全相同，即： 1010)()()()()()()()(NmNNNNnmnhmxnynRnynhnxnyn 例例 设两个有限长度序列：x(n), 0n7；y(n), 0n19。令X ( k ) 和 Y ( k ) 分 别 表 示 它 们 的 2 0 点 D F T ， 而 序 列r(n)=IDFTX(k)Y(k)。试指出r(n)中的哪些点相当于线性卷积g

10、(n)=x(n)*y(n)中的点。n 解：设R(k)=X(k)Y(k)，于是 ，并且r(n)之长度为20。又设g(n)=x(n)*y(n)，则线性卷积g(n)之长度为8+20-1=27。循环卷积r(n)是周期卷积 的主值序列，而 又是线性卷积g(n)的周期延拓，延拓的周期就是周期卷积的周期20。 )()()(nynxnr)(nr)(nrn由于2027，即延拓的周期小于线性卷积的长度，故延拓时必然发生线性卷积的混叠，即 的每一个周期的前27-20=7个值都是g(n)的前一个周期的后7个值与后一个周期的前7个值的混叠，也就是说，循环卷积r(n) 的20个值中，后13个值才与g(n)中间部分的13个值相同。因此，对于循环卷积r(n)，（0n19），只有7n19这13个点相