# Understanding circular convolution

Let $a$ and $b$ $\in \mathbb C^N$ and $a[k] = a[k \mod N]$ (same with b). Then the circular convolution of $a$ and $b$ is defined by

$$(a * b)[n] = \sum_{p=0}^{N-1} a[p] b[n-p].$$

I have a problem understanding the flip operation on the convolution. Let $(Ja)[n] = a[-n]$, then

$$J(a*b)[n] = \sum_{p=0}^{N-1} a[p]b[-n-p].$$

so we first apply the convolution and then we flip the n - is this correct? Or do we flip the whole index of $b$, meaning that

$$J(a*b)[n] = \sum_{p=0}^{N-1} a[p]b[-n+p].$$ On the other hand we have

$$((Ja)*(Jb))[n] = \sum_{p=0}^{N-1}a[-p]b[n+p].$$ so we first flip $a$ and $b$ and then apply the convolution. However, my book says $J(a*b)[n] = ((Ja)*(Jb))[n]$, which is not the case with my calculation, so I'm sure did something wrong. Can you help me finding the logical mistake here?

• being a Johnny-come-lately here, i would just periodically extend both $a[n]$ and $b[n]$ so that $$a[n+N] = a[n] \quad \forall n$$ and $$b[n+N] = b[n] \quad \forall n$$. this is truly what the DFT assumes (and it's within the DFT where circular convolution appears). it means you can add (or subtract) any integer multiple of $N$ you like to your indices. (sorta like adding or subtracting $2\pi$ to any $\sin()$ or $\cos()$ function. nothing gets changed, but your expression might be easier to deal with.) then your subsequent math is easy. Jan 8 '15 at 23:50

## 2 Answers

Your first version of $J(a*b)[n]$ is correct:

$$J(a*b)[n] = \sum_{p=0}^{N-1} a[p]b[-n-p]$$

because you simply have to flip $n$, and not the summation index.

The problem is in your formulation of the circular convolution of $(Ja)[n]$ and $(Jb)[n]$. It should be

$$((Ja)*(Jb))[n]=\sum_{p=0}^{N-1} a[-p]b[-n+p]$$

because you have to negate the arguments of both sequences, so $p$ becomes $-p$, and $n-p$ becomes $-n+p$. Now you can simply change the sign of $p$ because it doesn't matter in which order you compute the sum. This gives

$$((Ja)*(Jb))[n]=\sum_{p=0}^{N-1} a[p]b[-n-p]$$

which is identical to $J(a*b)[n]$ as given above, as it should be.

No, since this is a circular convolution and thus $a[-n] = a[N-n]$ etc, we have that \begin{align} ((Ja)\star(Jb))[n] &= \sum_{p=0}^{N-1} Ja[p]Jb[n-p]\\ &= \sum_{p=0}^{N-1} a[-p]b[p-n]\\ &= a[0]b[-n] + \sum_{p=1}^{N-1}a[-p]b[p-n]\\ &= a[0]b[N-n] + \sum_{p=1}^{N-1}a[N-p]b[p-n] \end{align} Now, as $p$ runs from $1$ to $N-p$, $q = N-p$ runs from $N-1$ to $1$. So we substitute $N-q$ for $p$ and write \begin{align} ((Ja)\star(Jb))[n] &= a[0]b[N-n] + \sum_{p=1}^{N-1}a[N-p]b[p-n]\\ &= a[0]b[N-n] + \sum_{q=1}^{N-1}a[q]b[N-q-n]\\ &= \sum_{q=0}^{N-1}a[q]b[(N-n)-q]\\ &= (a\star b)[N-n]\\ &= (a\star b)[-n]\\ &= J(a\star b)[n] \end{align}