Express Circular Convolution in Terms of Linear Convolution

Question

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?

Answer 1

$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.

Answer 2

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]$.