# Express Circular Convolution in Terms of Linear Convolution

g[n], h[n] : finite length sequences of length 7 yC[n]: circular convolution yL[n]: linear convolution

Express yC[n] in terms of yL[n].

If same two sequences of equal length are convolved using both linear(by tabular method) and by circular(matrix method) the output is of differing length and values.

How can I possibly relate circular convolution to linear convolution?

• For homework type questions like this one you need to show your efforts and explain where exactly you're stuck. Putting the two expressions for linear and for circular convolution next to each other might help. – Matt L. Dec 3 '16 at 13:00
• That is exactly where I am stuck, I just don't know how to start. – Mann Dec 4 '16 at 5:27
• If you would just follow MattL's sage advice and write out each of the 13 terms in the linear convolution explicitly meaning no gobbledygook such as $\sum$ or $[n-k]_N$ or symbols -- each argument surrounded by $[$ and $]$ is an integer in the range $[0,6]$ -- preferably neatly tabulated, and similarly for the circular convolution, and then just stare at the results for a while, something might occur to you..... – Dilip Sarwate Jul 2 '17 at 13:49

$h[n]_N$ is the periodic extension of $h[n]$.

$$h[n]_N = h[n + mN] \quad \text{for } 0 \le n+mN < N \text{ and } m \in \mathbb{Z}$$

so, given an $n$ and knowing $N$, you have to choose the correct integer $m$ so that

$$0 \le n+mN < N$$ or $$-n \le mN < N-n$$ or $$-\frac{n}{N} \le m < \frac{N-n}{N} = 1 - \frac{n}{N}$$.

Or, for the term $h[n-k]_N$,

$$h[n-k]_N = h[n -k + mN] \quad \text{for } 0 \le n-k+mN < N \text{ and } m \in \mathbb{Z}$$

and

$$-\frac{n-k}{N} \le m < 1 - \frac{n-k}{N}$$

so, you have to split your summation into two summations.

Consider the $N^2$ terms of the form $g[m]h[n], 0\leq m < N, 0 \leq n < N$.

Each term occurs once and only once in the $2N-1$ sums that define the values of $yL[k]$, $0 \leq k < 2N$.

Each term occurs once and only once in the $N$ sums that define the values of $yC[\ell], 0 \leq \ell < N$.

So, make a $N\times N$ table of values $(m,n)$ and figure out which $k$ and which $\ell$ each $(m,n)$ maps to. Write the answers in matrix form where the $(m,n)^{\text{th}}$ entry is of the form $k~ ||~ \ell$. Then ponder the questions:

• For a fixed value of $\ell$, what are the various values of $k$ that you have listed in all matrix entries of the form $k~ ||~ \ell$?
• Are these values of $k$ associated with any other values of $\ell$?

It is sincerely to be hoped that you will find the answer to the second question to be No. If so, and if the answers to the first question are "$k$ can equal $k_1 k_2, \cdots, k_i$", then you have just discovered that $yC[\ell] = yL[k_1]+yL[k_2]+ \cdots + yL[k_i]$.