1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 8, 2015 at 23:50

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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