Operations on Finite-Length Sequences

Circular Time-reversal of a Sequence (Section 2.3.1 ) Circular Shift of a Sequence(Section 2.3.2 and 5.7 ) Circular Convolution(Section 5.4 and 5.7 )

3. Circular Convolution

3、Circular Convolution

Example Determine the 4-point circular convolution of the two length-4 sequences: g[n]={1 2 0 1}, h[n]={2 2 1 1} as skecthed below

3、Circular Convolution

The result is a length-4 sequence yC[n]N 1 m 0 N

N h(n) yC (n) g (n) g (m)h n m

, 0 n N 1;

From the above we observe

yC (0) g (m)h mm 0

3

4

g[0]h[0] g[1]h[3] g[2]h[2] g[3]h[1] 1 2 2 1 0 1 1 2 6

3、Circular Convolution

Likewise, yC (1) g (m)h 1 mm 0

3

4

g[0]h[1] g[1]h[0] g[2]h[3] g[3]h[2] 1 2 2 2 0 1 1 1 7 yC (2) g (m)h 2 mm 0 3 4

g[0]h[2] g[1]h[1] g[2]h[0] g[3]h[3] 1 1 2 2 0 2 1 1 6

3、Circular ConvolutionyC (3) g (m)h 3 mm 0 3 4

g[0]h[3] g[1]h[2] g[2]h[1] g[3]h[0] 1 1 2 1 0 2 1 2 5

yC[n]

3、Circular Convolution

循环卷积过程图解h(0)g (0)

h(1)g (0)

h(1)

g (3)

g (1) h(3)

h(2)

g (3)

g (1) h(0)

g (2)h(2)

g (2)h(3)

(a) yc[0]

(b) yc[1]

3、Circular Convolution

The circular convolution can also be computed using a DFT-based approach The N-point circular convolution can be written in matrix form as

3、Circular Convolution

Note: 1、The element in each row of the matrix are obtained by circularly rotating the elements of the previous row to the right by one position. Such a matrix is called a circulant matrix(轮换矩阵、 循环行列式矩阵) 2、使用矩阵形式计算循环卷积前，需要通过补零把参与循 环卷积的两个输入序列扩充成相同长度，且此长度等于 DFT的点数

3、Circular Convolution

Example Now let us extend the two length-4 sequences to length 7 by appending each with three zero-valued samples, i.e.,

3、Circular Convolution

ge (n) {1, 2,0,1,0,0,0}he (n) {2, 2,1,1,0,0,0}

0 n 60 n 6

We next determine the 7-point circular convolution of ge[n] and he[n]:

yC (n) ge (m)he n mm 0

6

7

,0 n 6

Matrix method: Y y (1) y (2) H eGe y ( N 1) y (0) 1 g e (0) 2 g e (1) 0 Ge g e (2) 1 0 g e ( N 1) 0 0

he (0) he (1) H e he (2) he ( N

1)

2 he ( N 1) he ( N 2) he (1) 2 he (0) he ( N 1) he (2) 1 he (1) he (0) he (3) 1 0 0 he ( N 2) he ( N 3) he (0) 0

0 0 0 1 1 2 2 0 0 0 1 1 2 2 0 0 0 1 1 2 2 0 0 0 1 1 2 2 0 0 0 1 1 2 2 0 0 0 1 1 2 2

y (0) 2 y (1) 2 y (2) 1 y (3) 1 y (4) 0 y (5) 0 y (6) 0

0 0 0 1 1 2 1 2 2 0 0 0 1 1 2 6 2 2 0 0 0 1 0 5 1 2 2 0 0 0 1 5 1 1 2 2 0 0 0 4 0 1 1 2 2 0 0 1 0 1 0 0 1 1 2 2

3、Circular Convolution

As can be seen from the above that y[n] is precisely the sequence yL[n] obtained by a linear convolution of g[n] and h[n]yC[n]

Try to think: What is the relation between the circular convolution and the linear convolution?

3、Circular Convolution