# How to derive the answer to this convolution problem?

I came across this below question, (which was a homework assignment question for Signal Processing class, which my friend mailed me for help solving), mulled over it for an hour and had no idea how to proceed with solving it.

Let $C(x) = A(x)B(x)$ where:

$$A(x)=\sum_{n=0}^{N_1}a(n)x^n$$ $$B(x)=\sum_{n=0}^{N_2}b(n)x^{2n}$$ $$C(x)=\sum_{n=0}^{N_3}c(n)x^n$$

Find expressions for $N_3$ and $c(n)$ as functions of $N_1$,$N_2$, the $a(n)$ and $b(n)$.

Apparently, it has something to do with convolution, as in $c(n)$ is the convolution result of $a(n)$ & $b(n)$ or something like that.
But I still can't figure out how that is. Can anybody please explain me the answer of $N_3$ and $c(n)$

HINT: what is the highest power of $x$ after multiplying $A(x)$ and $B(x)$? This gives you directly the value of $N_3$. Then rewrite $B(x)$ as

$$B(x)=\sum_{n=0}^{2N_2}\hat{b}_nx^n$$

and you can use normal convolution of $a(n)$ and $\hat{b}(n)$ to derive $c(n)$. Now you just need to express $\hat{b}(n)$ in terms of $b(n)$.

EDIT: OK, so here's the solution:

We have

$$C(x)=\sum_{n=0}^{N_3}c_nx^n$$

Since $C(x)=A(x)B(x)$, the highest power of $C(x)$ must be $N_3=N_1+2N_2$. You can rewrite $B(x)$ as

$$B(x)=\sum_{n=0}^{2N_2}\hat{b}_nx^n$$

with

$$\hat{b}_n=\begin{cases}b_{n/2},&n \text{ even}\\ 0,&n \text{ odd}\end{cases}$$

Now the coefficients $c_n$ can be written as the convolution of $a_n$ and $\hat{b}_n$:

$$c_n=\sum_k\hat{b}_ka_{n-k}$$

For the index $k$ in the above sum we have the following constraints:

$$0\le k\le 2N_2\quad\text{and}\quad 0\le n-k\le N_1$$

which results in the summation limits

$$c_n=\sum_{k=\max\{0,n-N_1\}}^{\min\{n,2N_2\}}\hat{b}_ka_{n-k},\quad 0\le n\le N_3$$

If you sum only over even $k$, you can replace $\hat{b}_k$ by the coefficients $b_{k/2}$:

$$c_n=\sum_{k=\max\{0,n-N_1\},k\text{ even}}^{\min\{n,2N_2\}}b_{k/2}a_{n-k},\quad 0\le n\le N_3$$

which can be rewritten once more as

$$c_n=\sum_{k=\lceil{\max\{0,n-N_1\}/2}\rceil}^{\lfloor{\min\{n,2N_2\}/2}\rfloor}b_{k}a_{n-2k},\quad 0\le n\le N_3$$

• Thanks for that hint. So, N3 = N1 + 2*N2 & c(n) = a(n - (2*N2)) * b((n/2) - (N1/2)). Is that correct? – KharoBangdo Sep 8 '14 at 8:38
• @KharoBangdo: $N_3$ is correct. I can't really parse your second equation. In any case, $c(n)=(a*\hat{b})(n)$, where $*$ is convolution, and $\hat{b}(n)=b(n/2)$ for even $n$ and zero otherwise. – Matt L. Sep 8 '14 at 11:21
• Can u please post the full answer please. ie. the expanded form of the convolution along with the summation limits. I didn't get the the convolution part – KharoBangdo Sep 10 '14 at 4:23
• @KharoBangdo: I've added the solution to my answer. – Matt L. Sep 10 '14 at 7:56