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

enter image description here

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?

  • $\begingroup$ 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. $\endgroup$
    – Matt L.
    Commented Dec 3, 2016 at 13:00
  • 1
    $\begingroup$ That is exactly where I am stuck, I just don't know how to start. $\endgroup$
    – Mann
    Commented Dec 4, 2016 at 5:27
  • 2
    $\begingroup$ 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..... $\endgroup$ Commented Jul 2, 2017 at 13:49

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


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


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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.